Einführung in die Theoretische
Informatik III
V. Strehl, Informatik 8
Sommersemester 2000
Mehr Informationen zu diesem Bild bei Hubble Heritage
Was ist Amorphous Computing? Computing with Molecules?
When
easy maths turns hard : ein Aufsatz zu Aspekten der Berechnungskomplexität
aus IBM Research (über Richard Karp, einen der Gründerväter
der Theorie der NP-Vollständigkeit,
Scott Kirkpatrick und das Phänomen der Phasenübergänge
beim SAT-Problem, Mike Shub und Komplexität beim ``kontinuierlichen''
(statt diskreten) Rechnen.
à propos: Travelling Salesperson Problem -- Internet-Seite zum TSP
à propos: Primzahlen und Faktorisierung -- Internet-Seite von RSA-Security und Cryptographic Challenges
à propos: Quantum Computing. Ich habe in der Vorlesung am 5.7. erwähnt, dass die Fourier-Transformation im Kontext des Quantum-Computing (konkret: für den Faktorisierungs-Algorithmus von P. Shor) eine ganz zentrale Rolle spielt. Da ich nach Literatur zu diesem aktuellen Thema gefragt worden bin, hier zwei Hinweise auf gut lesbare Bücher zum Thema:
A.O. Pittenger, An Introduction to Quantum Computing Algorithms, Birkhäuser-Verlag, 1999 (138 Seiten, kostet DM 98,-) [knapp, konzise und klar geschrieben - wenig über die physikalischen Grundlagen]
J. Gruska, Quantum Computing, McGraw-Hill, 1999 (439 Seiten, kostet ca. DM 73.-) [breit geschrieben, vielseitig, behandelt auch die physikalische Aspekte und gibt eine Einführung in den mathematischen Formalismus der Quantenmechanik (Hilberträume, Operatoren usw.) ]
Der bahnbrechende Artikel zur Faktorisierung ist übrigens:
P. Shor, Algorithms for Quantum Computing: Discrete Logarithm
and Factoring,
IEEE Annual Symposium on Foundations of Computer Science 1994; eine
revidierte Fassung ist erschienen unter dem Titel: Polynomial-time algorithms
for prime factorization and discrete logarithms on a quantum computer,
SIAM Journal of Computing, vol26/5 (1997), pp. 1484-1509.
P. Shor hat dafür 1998 in Berlin auf dem Kongress der Internationalen
Mathematiker Union den Nevalinna-Preis erhalten, was man getrost als eine
Art Nobel-Preis für algorithmische Mathematik ansehen kann.
Im übrigen ist die Literatur zu diesem Thema immens. Wer mal über
das Internet reinriechen möchte, dem empfehle ich die web-Seite des
Centre
for Quantum Computation an der Universität Oxford.
Dort findet man auch gute tutorials für Einsteiger.
a propos: das P-vs-NP-Problem
Am 24. Mai 2000 hat am Collège de France in Paris ein "Millenium
Meeting" stattgefunden, bei dem - fast 100 Jahre nach Hilbert's Vorstellung
einer Liste von 23 Problemen, die im 20. Jahrhundert gelöst werden
sollte - eine Liste von sieben wichtigen (die wichtigsten?) , bislang ungelösten
mathematischen Problemen präsentiert wurde. Um deren Bedeutung zu
unterstreichen, hat das Clay Mathematics Institute sieben Preise
von je einer Million Dollar ausgesetzt. Die Liste, Informationen zu den
einzelnen Problemen und die genaueren Bedingungen der Ausschreibung findet
man auf einer speziellen Internet-Seite Millenium
Prize Problems der Clay Mathematics Institutes.
Das erste Problem auf dieser prestige-trächtigen Liste ist das
notorische
P-vs-NP-Problem der Theoretischen Informatik
Dieses Problem wird uns im zweiten Teil der Vorlesung noch ausgiebig
beschäftigen, wobei es darum geht, überhaupt zu verstehen, was
diese Problemstellung beinhaltet. Aus Anlass des Preisausschreibens hat
Stephen
A. Cook (University of Toronto), einer der Begründer der Theorie
der NP-Vollständigkeit, einen knappen Übersichtsartikel The
P-vs-NP-Problem geschrieben, den Sie als pdf-file hier direkt abrufen
können. Dessen Lektüre ist eine gute Einstimmung auf den zweiten
Teil der Vorlesung.
Aktuell!! Wichtig!!
bei der Vorlesung und den Übungen treten in der Zeit vom 5.Juli bis 12. Juli folgende Vertauschungen ein:
Mittwoch, 5. Juli - Vorlesung im
H4 von 10-12 Uhr
Donnerstag, 6. Juli - Übung
im H7 von 14-16 Uhr
Montag, 10. Juli - Übung im
H7 von 10-12 Uhr
Mittwoch, 12. Juli - Vorlesung
im H8 von 10-12 Uhr
Die Vorlesung findet statt:
Montags, 10-12 und Donnerstags, 14-16 im H7
Beginn: 4. Mai 2000
Die Übungen finden zu den folgenden Terminen
statt:
MO, 12-14, im Raum 2.038 (Rechenzentrum RRZE)Die Übungen haben am Donnerstag, den 11. Mai 2000 begonnen
DI, 10-12, im Raum 2.037 (RRZE)
DI, 12-14, im Raum E. 1.11 (E-Technik, Cauerstrasse 7)
MI, 10-12, im Raum 2.037 und im Raum 2.038 (RRZE)
Eine grobe Inhaltsübersicht in LaTeX, PostScript und in PDF
Nähere Angaben zum Inhalt finden Sie (vorläufig) hier auf der homepage der entsprechenden Vorlesung im Sommersemester 1999.
Übungsaufgaben, Texte zur Vorlesung, Kopien von Folien (soweit neu).
Weitere interessante Informationen im Zusammenhang mit der Vorlesung.
Einige Links zum Buch Models of Computation von John E. Savage
Ausserdem ein Vorschlag für einen Museumsbesuch
...
Kontakt:
Ich bin per email erreichbar unter: strehl@cs.fau.de
oder telefonisch unter +49-9131-8529914.
Mein Büro befindet sich in
Tennenlohe, Am Weichselgarten 9,
2. Stock, Zimmer 215b.
Sprechstunden nach Vereinbarung.
see you in my office ...
