Tagebuch und Materialien zur
Vorlesung
Theoretische
Informatik 3
Wintersemester
2007/08
Die
Ergebnisse der Klausur vom 24. September 2008
werden am Mittwoch,
den 15. Oktober 2008 ausgehängt!
Sie sind auch über
folgenden link zugänglich:
Termin für Einsichtnahme: wird noch bekanntgegeben
|
Wer einen Vorgeschmack auf die Vorlesung haben möchte, findet hier drei appetizer. |
|
Themen |
Folien |
Lesen! Links! |
|
15. Oktober: Organisatorisches zu der Vorlesung und den Übungen Anmerkungen zur Geschichte des Rechnens und der Arithmetik Multiplikation: Schulmethode, russische Bauernmultiplikation, Karatsuba-Methode Einige Bilder zu Fouriertransformation und Bildverarbeitung |
Was Sie schon immer über Zahlen, Zahldarstellungen, Zahlsysteme wissen wollten, finden Sie in dem Buch: Universalgeschichte
der Zahlen |
|
|
18. Oktober: Thema: How Fast Can We Multiply? Multiplikation im engeren und im weiteren Sinne Matrizenring Polynomring, Multiplikation mittels Interpolation Funktionenring, Faltung mittels Fouriertransformation |
||
|
22. Oktober: Multiplikation mittels Faktorisierung Boolescher Ring: Durchschnitt als Multiplikation Beispiel: Durchschnitt regulärer Sprachen Multiplikation im weiteren Sinne: Assoziative Operationen, Beispiele, Gegenbeispiele Transformationen und Permutationen |
|
|
|
25. Oktober: Bedeutung der Permutationen: Sortieren, Routen, Algebra,..., Determinante und Permanente, Komplexitätsklasse #P Komposition, Zykeldarstellung, Produkte von Transpositionen, Produkte von Transpositionen benachbarter Elemente, Coxeter Relationen Inversionen und Inversionsvektor |
|
|
|
29. Oktober:
Binäre Bäume
und assoziative Operationen, |
|
|
|
5. November:
Beweis der Anzahlformel
für Binärbäume, |
Platonische Körper (zum Einstieg) |
Zur Dynamischen
Programmierung: Cormen, Leiserson, Rivest, Stein, |
|
8. November:
Berechnung von
assoziativen Produkten: uniforme und logarithmische
Kostenmasse |
||
|
12. November:
Exponentiation:
Iteration von Funktionen, |
||
|
15. November: Primtest und Faktorisierung in Beziehung zu den Komplexitätsklassen P und NP, zur Geschichte des P-vs-NP-Problems Pollards rho-Methode zur Faktorisierung ganzer Zahlen |
|
|
|
19. November:
Bahnen unter bijektiven
Transformationen, |
Beispiele hierzu im Skriptum! |
|
|
22. November: divide-and-conquer-Algorithmen |
Karatsuba/Strassen
(pdf) |
Heun GA
Kap. 2.5 |
|
In der Woche vom 26.-30. November finden nicht alle Übungen wie geplant statt. Teilnehmer, deren Übung nicht stattfindet, sollten diesemal eine andere Gruppe aufsuchen – am besten eine zum gleichen Termin stattfindende Gruppe. |
folgende Gruppen finden in dieser Woche nicht statt: Mi 10-12 (König) |
folgende Gruppen finden statt: Mi 12-14
(Freundl) |
|
ab 3. Dezember wieder normaler Übungsbetrieb |
|
|
|
26. November
typische Fälle und Beispiele zum Master-Theorem für
Divide-and-conquer-Rekursionen, |
Heun
GA Kap 7.1 |
|
|
29. November
Komplexitätsanalyse des euklidischen
Algorithmus, |
|
|
|
3. Dezember
Ergänzungen
zu Kettenbrüchen, |
Heun GA Kap.
7.2 |
|
|
6. Dezember
Sätze
von Lagrange, Fermat, Euler, |
Heun, GA Kap.
7.2 |
|
|
10. Dezember
modulare
Arithmetik, |
|
siehe 6. Dezember |
|
13.
Dezember |
|
PNP-Folien
(pdf) CLR Kap. 36 |
|
17.
Dezember |
Heun GA, Kap. 7.3 |
|
|
20. Dezember
Video-Vorführung
im H4 |
20. Dezember
Video-Vorführung
im H4 |
20. Dezember
Video-Vorführung
im H4 |
|
7. Januar Testen von Matrizenprodukten
(Freivalds), |
siehe Notizen zur Vorlesung |
Binomialverteilung
grafisch (pdf) |
|
10. Januar Probabilistische Komplexitätsklassen
Verschlüsselung durch
Exponentiation, |
RSA-Kryptosystem
(pdf) |
CLR, Kap. 33.7
(u.v.a.m) |
|
14. Januar Historisches zu RSA, Weitere Anwendungen der
"Schnellen Exponentiation" in kryptografischen
Protokollen, |
Talbot/Welsh:
Complexity and Cryptography, Cambridge UP, 2006; |
|
|
17. Januar Einwegfunktionen und
Komplexität, |
siehe Skript |
|
|
21. Januar Fouriertransformation:
Funktionen im Orts- und Frequenzbereich |
|
|
|
24. Januar Die Determinante der
Vandermonde-Matrix (Beweis) |
|
|
|
28. Januar Schnelle Fouriertransformation
(FFT) |
|
|
|
31. Januar Schnelle Multiplikation von
ganzen Zahlen mittels FFT: der "three-primes"-Algorithmus |
|
Lipson, Elements of
Algebra and Algebraic Computing |
|
4. Februar keine Vorlesung |
|
|
|
7. Februar Fragestunde |
|
|
Übungsblätter,
weitere Aufgaben, Klausuren
|
Erstes Übungsblatt |
|
|
|
Zweites Übungsblatt |
|
|
|
Drittes Übungsblatt |
|
|
|
Viertes Übungsblatt |
|
|
|
Fünftes Übungsblatt |
korr. 19.11. |
|
|
Sechstes Übungsblatt |
|
|
|
Siebtes Übungsblatt |
|
|
|
Achtes Übungsblatt |
|
|
|
Neuntes Übungsblatt |
|
|
|
Zehntes Übungsblatt |
|
|
|
Elftes Übungsblatt |
|
|
|
Zwöftes Übungsblatt |
|
|
Klausuren Theoretische Informatik |
|
|
Herbst 2002 |
|
|
Frühjahr 2003 |
|
|
Herbst 2003 |
|
|
Frühjahr 2004 |
|
|
Herbst 2004 |
|
|
Frühjahr 2005 |
|
|
Herbst 2005 |
|
|
Frühjahr 2006 |
|
|
Herbst 2006 |
|
|
Frühjahr 2007 |
|
|
Herbst 2007 |
|
|
Frühjahr 2008 |
|
|
Herbst 2008 |
|
|
Sammlung weiterer Aufgaben |
|
Weitere Materialien und
Informationen
|
Buch Grundlegende Algorithmen von V. Heun (2. Auflage) |
|||||
|
Beweis der Formel von de Moivre für die Fibonacci-Zahlen |
|||||
|
Folien zu Don Knuth |
|||||
|
Lösung der Rekursionsgleichung für Mergesort |
|||||
|
Ausführlicher Text zu
Quicksort : |
|||||
|
Analytische Untersuchung zum Begriff des Splitters |
|||||
|
Quicksort und Prioritätsbäume |
|||||
|
Folien Claude Shannon |
|||||
|
Entscheidungsbäume für drei Sortierverfahren |
|||||
|
Ein homepage für die Entropie |
|||||
|
Ein homepage für Divide-and-Conquer |
|||||
|
Informationen zum Thema (Integer-)Arithmetik a) Grundlegende Eigenschaften der
ganzen Zahlen |
a |
||||
|
b |
|||||
|
c |
|||||
|
d |
|||||
|
|
|||||
|
Weitere Informationen und Maple-worksheets zum Thema (Integer-)Arithmetik a) Eigenschaften der
Restklassenringe |
a |
||||
|
b |
|||||
|
c |
|||||
|
d |
|||||
|
e |
|||||
|
|
|||||
|
Im Zusammenhang mit Primzahltests und der Verifikation der Primheit ist das Verfahren von V. Pratt von Interesse |
|||||
|
Ausfuehrlicher Text zur Diskreten Fouriertransformation |
|||||
|
Kurzfassung des Textes (i.w. nur die Formeln) |
|||||
|
Maple worksheet zur Diskreten Fouriertransformation |
|||||
|
Skandal! |
|||||
|
Weitere Texte zu P-versus-NP |
weitere Probleme und Reduktionen |
||||
|
Vierfarbenproblem |
|||||
|
Polynome und Färbungen |
|||||
|
Resolution und 2-SAT |
|||||
|
kommentierte Folien (unvollstaendig) zu einem Vortrag |
|||||
|
|
|||||
Neuigkeiten,
interessante Links
|
Turing Award 2003 |
Der A.M. Turing Award , benannt nach dem Engländer Alan Matheson Turing, einem der intellektuellen und praktischen Pioniere der Informatik (nicht nur wegen der Konzeption des nach ihm benannten Berechnungsmodells!), wird von der Association of Computing Machinery seit 1966 jährlich fuer herausragende Leistungen auf dem Gebiet der Informatik verliehen und ist (nicht nur wegen des damit einhergehenden Preisgeldes von $100,000) mit die hoechste Auszeichnung auf dem Gebiet der Informatik ueberhaupt. Die Auszeichnung fuer das Jahr 2002 geht an die drei Erfinder des RSA-Krypotosystems, Ronald L. Rivest, Adi Shamir und Leonard M. Adleman. Dieses System wird auch im Rahmen der Vorlesung dieses Sommersemesters noch behandelt werden. |
|
|
Primzahlen |
Informationen (fuer "Einsteiger") zum Thema Primzahlen in der Feature Column der American Mathematical Society (Juni 2003) |
|
|
Primzahlen (2003) |
Die Primzahlen
haben die Mathematiker schon seit der Antike fasziniert und die
Untersuchung ihrer Eigenschaften dauert bis heute an. Aus
algorithmischer Sicht interessiert man sich fuer diese Objekte
auch nicht erst ernsthaft, seitdem die Zahlentheorie --
beispielsweise für die Zwecke der Kryptographie, siehe
vorhergehender Eintrag zum RSA-System -- Ideen- und Faktenquelle
für ganz konkrete Anwendungen geworden ist. Eines der
aeltesten offenen Problem über Primzahlen ist die Frage, ob
es unendlich viele "Primzahlzwillinge", also
Primzahlpaare mit Abstand 2 gibt (wie 3 und 5, 17 und 19, 59 und
61,...). |
Pressemitteilung
des American Institute of Mathematics |
|
Nachtrag zu vorigem Thema |
Luecke im Beweis??? |
|
|
Primzahlen (2002 ) |
Die Frage nach den Primzahlzwillingen ist aus der Sicht der Zahlentheorie spannend, aber algorithmisch wohl nicht so sehr relevant. Ganz anders sieht es aus mit der Frage, ob man Primzahlen von zusammengesetzten Zahlen effizient unterscheiden könne (ohne notwendigerweise eine Faktorisierung in Primfaktoren vorzunehmen), ob also die Menge der Primzahlen in der Komplexitätsklasse P liegt? Mit diesem Problem haben sich viele Mathematiker und theoretische Informatiker lange und intensiv beschäftigt, die Indizien (zum Beispiel die sehr schnellen probabilistischen Verfahren von Solovay und Strassen bzw. Rabin und Miller, oder ein schnelles Verfahren von Miller unter einer unbewiesenen Zusatzhypothese, einer Verallgemeinerung der berühmten Riemann-Hypothese , oder auch immer schnellere deterministische Verfahren mit "fast-polynomialer" Laufzeit) sprachen schon eine ganze Weile für eine positive Antwort. Seit August 2002 ist die positive Antwort " Primes is in P" Faktum, beweisen von den drei indischen Mathematikern M. Agrawal, N. Kayal and N. Saxena . Verblüffend ist: wie elementar das ist! Der Code des Algorithmus (siehe Artikel) ist mal ganze 11 Zeilen lang. Der Beweis, dass der Algorithmus funktioniert und polynomiale Laufzeit hat, ist etwas länger, aber mit elementaren Kenntnissen durchaus "in Reichweite". |
|
|
Nochmal AKS-Algorithmus |
Eine schöner, ueberwiegend
weniger technischer Artikel zu dem AKS-Algorithmus von Folkmar
Bornemann, der klarmacht, dass "everyman" mit ein paar
Grundkenntnissen in Arithmetik verstehen kann, was da ablaeuft
--- mit vielen interessanten Informationen "drumherum",
wie z.B.: wie sind die Auswahlquoten an einer indischen
Universität, bei der Studenten (Kayal, Saxena) , die gerade
mal ihren Bachelor-Grad erworben haben, so sensationelle Sachen
machen? Ein andere Frage, wie ein solches Resultat in der
internationalen Presse "ankommt" und weitergereicht
wird, ist dann schon eher ein trauriges, wenn auch instruktives
Kapitel. |
|
|
Entropie |
Webseite zum Begriff Entropie |
|
|
nochmal Primzahlen |
neue Mersenne-Primzahl? |
|
|
|
oder doch nicht? |
|
|
P-versus-NP |
Link zu den Millenium Prize
Problems des Clay Mathematics Institute |
