| Wer einen Vorgeschmack auf die Vorlesung haben möchte, findet hier drei appetizer. |
| Wichtig:
bitte
informieren Sie mich per email, wenn der Zugriff
auf files über die unten angegebenen links nicht funktioniert.
Bitte nur von uni-erlangen.de aus versuchen! Ich bitte auch um Benachrichtigung und Rückfragen, falls in den Texten und Folien Unklarheiten, Fehler usw. auftauchen.Ringen |
|
Themen
|
Folien
|
Lesen! Links!
|
|
|
20. Oktober
|
Informationen
zur Vorlesung und zur
Organisation der Übungen Themen der Vorlesung Grundbegriffe: Probleme, Algorithmen, Komplexität Beispiel: Anzahl der Wörter gegebener Länge in einer regulären und in einer kontextfreien Sprache |
Einführung |
Heun (GA) Random-Access-Maschine Komplexitätsbegriffe |
| 24. Oktober |
Saturn
und
Cassini Erläuterung zu Problemkomplexität, obere und untere Schranken Beispiel: Multiplikation von Zahlen und von Polynomen (klassisch, russische Bauernmultiplikation, Karatsuba) Veranschaulichung der Komplexität von Karatsuba-Methode und FFT-Methode im Vergleich zur klassischen Multiplikation |
Cassini Multiplikation 1 Multiplikation 2 Multiplikation 3 |
Biographie:
Cassini Cassini's Ovals Cassini's Identity |
| Die
Landau-Notation für asymptotisches Verhalten (Wachstumsordnung)
von Folgen und Funktionen mit den Symbolen O, Omega, Theta, ~
usw. wird nicht mehr ausführlich behandelt, da sie
bereits
Gegenstand in anderen Lehrveranstaltungen war. |
Landau-Notation Regeln für die Landau-Symbole Tabellen (pdf) |
Cormen, Leiserson, Rivest (Kapitel 2) u.v.a.m. |
|
| 27. Oktober |
Anmerkungen
zur
Geschichte der Arithmetik Einige mathematische Grundlagen: geometrische Reihe, Anwendung auf die Analyse einfacher divide-and-conquer-Rekursionen (Master Theorem) |
Arithmetik (pdf) | Karatsuba/Strassen (pdf) divide-and-conquer: Ausführlicher Text (pdf) Heun GA Kap. 2.5 CLR Kap 4 Sedgewick/Flajolet Heun GA Kap. 7.6 und 7.8 CLR Kap 31 Schöning, Algorithmik, Kap. 1.9 |
| 31. Oktober |
Binomialformel,
Binomialkoeffizienten,
Binomialreihe, Abschätzung von Potenzsummen durch Integrale, Fakultäten (Stirlings Formel), |
Mathematische Hilfsmittel
(pdf) |
Maple
worksheets (auch pdf) harmonic stirling bintree |
| 3. November |
Binomialkoeffizienten
(Shannons Formel) Binärbäume, geordnete Bäume, Dyck-Sprache Exakte und asymptotische Anzahlen von Binärbäumen (Catalans Formel) |
catalan (pdf) |
binomial (Maple) Catalan-Zahlen |
| 7. November |
Beweis
von
Catalans
Formel per Induktion Bitvektoren, boolescher Ring, Hamming-Abstand, Hammingkugeln und deren Volumen Szenario der Codierungstheorie |
codes (pdf) (ergänzt und korrigiert am 13.11.) |
|
| 10. November |
Codes,
Rate,
Minimaldistanz lineare Codes, Generator- und Kontrollmatrizen Fano-Geometrie, Hamming-Codes |
||
| 14. November |
Reed-Muller-Codes asymptotische Schranken für Codes (Plotkin, Gilbert-Varshamov) |
||
| 17. November | worst-case
versus
average-case für zwei
einfache Algorithmen: Grössenvergleich in lexicografischer Ordnung
und Maxixmumsuche Permutationen: Links-Rechts-Maxima und Inversionen |
Lexorder maxfind Inversionen Inversionen (Maple ) |
Einige Grundbegriffe der diskreten
Wahrscheinlichkeitsrechnung |
| 21. November | Sortieren:
allgemeine Bemerkungen, Rolle der Inversionen, einfache Sortieralgorithmen (InsertionSort, SelectionSort) Mergesort rekursiv und iterativ Heapsort |
Sortieren (pdf) Mergesort (pdf) mergerec2.pdf Heapsort (pdf) |
Knuth
TAOCP, vol.3 (5.5.1) Graham/Knuth/Patashnik Heun GA Kap. 2.1 Cormen/Leiserson/Rivest Kap. 1 Heun GA Kap. 2.3 |
| 24. November |
Analyse
von
Heapsort, Quicksort, Splittereigenschaft, Analyse von Quicksort |
Quicksort (pdf) quick(pdf) splitter (pdf) Splitter (pdf) |
Heun
GA Kap.
2.3, 2.4 Knuth TAOCP, vol.3 (5.2.2, 5.2.3) CLR Kap. 7, 8 weitere Texte zu Quicksort siehe unten |
| 28. November |
divide-and-conquer-Algorithmen Beispiele, Analyse Master-Theorem für asymptotisches Verhalten der Lösungen von divide-and-conquer Rekursionen |
Karatsuba/Strassen (pdf) Closest Pair (pdf) Folien SS03/04 (pdf) Ausführlicher Text (pdf) |
Heun
GA
Kap. 2.5 CLR Kap 4 Sedgewick/Flajolet Heun GA Kap. 7.6 und 7.8 CLR Kap 31 Ottmann Schöning, Algorithmik, Kap. 1.9 |
| 1. Dezember |
Beweis des
Master-Theorems Binäre Bäume, Parameter von binären Bäume binäre Suchbäume, innere Weglänge Quicksort-Rekursion für die innere Weglänge Vergleich von Komplexitätsfunktionen für das Sortieren |
bintrees1 bintrees2 priorität (pdf) Vergleich (pdf) |
Schöning,
Algorithmik, Kap. 1.9 Knuth TAOCP, vol. 1, Kap. 2.3 Knuth, TAOCP, vol 3, Kap. 6.2.2 Knuth TAOCP, vol.3, Kap. 5.3.1 |
| 5. Dezember |
Höhe von
Binärbäumen, binäre Entscheidungsbäume, untere Schranke für das Sortierproblem, Zusammenhang mit dem Entropiebegriff |
sortingbound (pdf) Entscheidungsbaum für mergesort (pdf) 3elemsort.jpg insertionsort.jpg heapsort.jpg |
Heun GA
Kap. 2.6 |
| 8. Dezember |
Entropie und
Codierung Präfixcodes und Binärbäume, Ungleichung von Kraft, Shannons Quellcodierungstheorem |
Entropie (pdf) | CLR
Kap. 17.3 siehe auch Folien zur Vorlesung |
| 11. Dezember |
optimale
Präfixcodierung, Produkte von Quellen |
produkte (pdf) |
|
| 15. Dezember |
Kapazität des
BSC |
capacity (pdf) |
|
| 19. Dezember | Beispiele zur
probabilistischen Methode |
probabilistic (pdf) |
|
| 22. Dezember | Shannons Kanalcodierungstheorem | channelcoding (pdf) | |
| Leseempfehlungen
zu den Feiertagen und darüber hinaus..... hyperfano (pdf): Fano-Geometrie mit hyperbolischen Christbaumkugeln |
Edmonds,Eidinow:
Wie Ludwig Wittgenstein Karl Popper mit dem Feuerhaken drohte Yourgrau: Göldel, Einstein und die Folgen Pesic: Abels Beweis Kehlmann: Die Vermessung der Welt |
||
| 9.
Januar |
Arithmetik der ganzen
Zahlen, grundlegende
Eigenschaften, Algorithmus von Euklid, Analyse (Satz von Lame), binärer euklidischer Algorithmus |
Arithmetik
(pdf) |
Heun GA Kap
7.1 CLR Kap. 33 Knuth TAOCP, vol. 2, Kap. 4.5 |
| 12./16.
Januar |
Restklassenringe mod n, Einheitengruppe, Eulers phi-Funktion, Möbius-Funktion und Möbius-Inversion, Ordnung von Elementen in einer Gruppe, Sätze von Fermat, Euler, Lagrange, Ordnung und Faktorisierung |
Restklassenringe (pdf) | Heun GA Kap.
7.2 CLR Kap. 33 GKP, Kap 4, insbes. 4.6 und 4.9 Aigner, Kap. 12 Für weitere Informationen zur Arithmetik der Restklassenringe (worksheets!) siehe " Weitere Materialien und Informationen " (unten) |
| 16. Januar |
Schnelle Exponentiation |
Exponentiation
(pdf) Fibonacci-Berechnung (pdf) |
Knuth, TAOCP
vol 2, Kap. 4.6.3 Heun, GA 1.2 |
| 19. Januar |
Homomorphismen,
chinesischer Restesatz, modulare Arithmetik |
Modulare Arithmetik
(erweitert 19.1.06) |
Heun, GA
Kap. 7.2 CLR Kap. 33 Knuth, TAOCP vol 2, Kap. 4.3.2 Für weitere Informationen zur modularen Arithmetik siehe " Weitere Materialien und Informationen " (unten) |
| 23./26. Januar |
Primzahlen, Primzahltests, insbesondere Miller-Rabin |
Primes in NP Primzahltests (pdf) Primzahltest (Maple) Primzahltest (pdf) |
Heun, Kap.
7.3 Für weitere Informationen zu Primzahlen und Primzahltests siehe "Weitere Materialien und Informationen " (unten) CLR Kap. 33.8 |
| 26./30. Januar |
Verschlüsselung
durch Exponentiation, public-key Kryptografie, RSA-Kryptosystem |
RSA-Kryptosystem
(pdf) RSA-576 (pdf) RSA-640 (RSA) RSA-640 (Mathworld) |
CLR, Kap.
33.7 (u.v.a.m) Heun, GA Kap. 7.4 |
| 30. Januar |
Anwendungen der
Exponentiation in kryptografischen Protokollen (Diffie-Hellman, Shamir, El Gamal) Ergänzung zur modularen Arithmetik: der chinesische Restesatz für nicht notwendig teilerfremde Moduln |
Exponentiation (ps) |
|
| 2. Februar |
Ergänzung zur
modularen Arithmetik: das Konsistenz- und das
Überdeckungsproblem NP-Vollständigkeit des Überdeckungsproblems NP-Vollständigkeit des Decodierungsproblems für lineare Codes Das Kryptosystem von McEliece |
covering (pdf) linear decoding (pdf) mceliece (pdf) |
|
| 6./9.
Februar 2006 |
Fouriertransformation klassisch, Diskrete Fourier-Transformation, Schnelle Fourier-Transformation, Anwendung auf die Polynommultiplikation |
FFT (pdf) Polynommultiplikation mittels DFT (pdf ) Maple-worksheet FFT mit Maple (pdf) Maple worksheet |
CLR Kap. 32 Heun, GA Kap. 7.5 Lipson, Elements of Algebra and Algebraic Computing weitere Texte und Materialien siehe unten: "Weitere Materialien und Informationen " |
| 5. April |
Klausur Theoretische Informatik Ort: Mensa-Süd Zeit: 8:30-11:30 |
|
Erstes Übungsblatt
|
20. Oktober
|
übungen-1 (pdf) |
||
| Zweites
Übungsblatt |
27. Oktober
|
übungen-2 (pdf) | ||
|
Drittes Übungsblatt (korr.)
|
3. November
|
übungen-3 (pdf) | Aufgabe 9 korr. 8.11. |
|
|
Viertes Übungsblatt
|
10. November
|
|||
|
Fünftes Übungsblatt
|
17. November
|
|||
|
Sechstes Übungsblatt
|
24. November
|
|||
|
Siebtes Übungsblatt
|
1. Dezember
|
|||
|
Achtes Übungsblatt
|
8. Dezember
|
|||
|
Neuntes Übungsblatt
|
15. Dezember
|
|||
|
Zehntes Übungsblatt
|
12. Januar
|
|||
|
Elftes Übungsblatt
|
19. Januar
|
|||
|
Zwölftes Übungsblatt
|
26. Januar
|
|||
|
Dreizehntes Übungsblatt
|
2.
Februar |
|||
|
Sammlung weiterer Aufgaben
|
||||
|
Klausur Theoretische Informatik
|
Herbst 2002
|
|||
|
Klausur Theoretische Informatik
|
Frühjahr 2003
|
|||
|
Klausur Theoretische Informatik
|
Herbst 2003
|
|||
|
Klausur Theoretische Informatik
|
Frühjahr 2004
|
|||
|
Klausur Theoretische Informatik
|
Herbst 2004
|
|||
|
Klausur Theoretische Informatik
|
Frühjahr 2005
|
|||
|
Klausur Theoretische Informatik
|
Herbst 2005
|
|||
| Klausur Theoretische Informatik | Frühjahr 2006 | F06 (pdf) | ||
| Klausur Theoretische Informatik | Herbst 2006 |
|
| Buch Grundlegende Algorithmen von V.
Heun (2. Auflage) |
heunvieweg
|
|||||||||||||||
| Beweis der Formel von de Moivre für die
Fibonacci-Zahlen |
demoivre.pdf |
|||||||||||||||
| Folien zu Don Knuth |
knuth.pdf |
|||||||||||||||
| Lösung der Rekursionsgleichung für
Mergesort |
mergerec2.pdf
|
|||||||||||||||
| Ausführlicher Text zu Quicksort : Ideen, Programme, Daten, average-case Analyse mittels Lösen einer Differentialgleichung |
quick.pdf |
|||||||||||||||
| Analytische Untersuchung zum Begriff des
Splitters |
splitter.pdf
|
|||||||||||||||
| Quicksort und Prioritätsbäume |
prioritaet.pdf
|
|||||||||||||||
| Folien Claude Shannon |
shannon.pdf
|
|||||||||||||||
| Entscheidungsbäume für drei
Sortierverfahren |
3elemsort.jpg
insertionsort.jpg heapsort.jpg |
|||||||||||||||
| Ein homepage für die Entropie |
Entropie |
|||||||||||||||
| Ein homepage für Divide-and-Conquer |
Divide-and-Conquer
|
|||||||||||||||
| Informationen zum Thema (Integer-)Arithmetik
a) Grundlegende Eigenschaften der ganzen Zahlen |
|
|||||||||||||||
| Weitere Informationen und Maple-worksheets zum
Thema (Integer-)Arithmetik
a) Eigenschaften der Restklassenringe |
|
|||||||||||||||
| Im Zusammenhang mit Primzahltests und der
Verifikation der
Primheit ist das Verfahren von V. Pratt von Interesse |
pratt (ps) |
|||||||||||||||
| Ausfuehrlicher Text zur Diskreten
Fouriertransformation |
fourier
(ps) fourier (pdf) |
|||||||||||||||
| Kurzfassung des Textes (i.w. nur die Formeln) |
FFT (ps) FFT (pdf) |
|||||||||||||||
| Maple worksheet zur Diskreten
Fouriertransformation |
Maple
worksheet (mws) Maple worksheet (pdf) |
|||||||||||||||
| Skandal! |
skandal |
|||||||||||||||
| Weitere Texte zu P-versus-NP |
|
| 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. |
Pressemitteilung
der ACM |
| Primzahlen (Juni 2003) |
Informationen (fuer "Einsteiger") zum
Thema Primzahlen in der Feature Column der American
Mathematical Society (Juni 2003) |
primes |
| 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,...). Kuerzlich haben D. Goldston und C. Yildrim ein Resultat ueber die Abstaende zwischen aufeinanderfolgenden Primzahlen erzielt, das weit ueber das bisher bekannte hinausgeht und das "Durchbruch" bezeichnet wird. |
Pressemitteilung
des American Institute of Mathematics Technische Informationen zu dem Resultat von Goldston und Yildrim |
| Nachtrag zu vorigem Thema |
Luecke im Beweis??? |
luecke
|
| 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". |
Kurzer
Text in den Prime Pages AKS-Artikel (pdf) |
| 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. Nebenbei: das Original des Artikels ist in Deutsch geschrieben, aber die amerikanische Uebersetzung ist bei der AMS frei zugänglich. |
breakthrough
|
| Entropie |
Webseite zum Begriff Entropie
|
|
| nochmal Primzahlen |
neue Mersenne-Primzahl? |
mersenne-40a
|
| oder doch nicht? |
mersenne-40b
|
|
| P-versus-NP |
Link zu den Millenium
Prize Problems des Clay Mathematics
Institute Link zu einer Seite des Mathematischen Instituts Erlangen (-> Seminare) |
P-vs.-NP
Millenium Prize Math. Institut |
