Argl... Ich habe Kopfschmerzen. Aspirin hilft nicht.
Wie kommt's?, fragt sich der motivierte Leser. Die Antwort: heute in CPSC 500, "Funtamentals of Algorithm Design and Analysis", hat sich der Prof 90 Minuten zeitgenommen, um NP zu erklären. Von vorne. Sehr methodisch.
Für nicht-Informatiker: NP ist die Klasse der Sprachen, die von einer nicht-deterministischen Turingmaschine in polynomieller Zeit entschieden werden können. Wenn das jetzt merkwürdig klingt, dann wollt Ihr gar nicht mehr wissen; ansonsten sei an dieser stelle einfach mal auf Wikipedia verwiesen ;)
Darmstädter Informatiker werden die Situation nachvollziehen können: das macht man doch im Grundstudium! Abgesehen davon: ich habe dieses Semester "Complexity of Computation" gehört, und da ging es um sehr viele und meistens kompliziertere Komplexitätsklassen... Den Kram heute hätte ich auch runterbeten können; allerdings hätte ich mir dabei nicht so viel Zeit gelassen ;)
Wenn er wenigstens zum interessanten Part gekommen wäre, also NP-Vollständigkeit und ernsthaftere Annäherungen an die Frage, ob P=NP... aber nein, er hat nur NP eingeführt. Klasse. Ich freu' mich schon auf nächste Woche ;)
Geschrieben von Conrad um 25.03.04 06:58 | TrackBackDa zeigt er dann, daß P=NP, das Universum doch unendlich und die Lichtgeschwindigkeit unter bestimmten umständen erreicht werden kann...
Verspricht spannend zu werden. :)
;) klingt gut! *hoff*
Posted by: Conrad at 26.03.04 19:38