| 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! |
|
| 8. April 2005 |
Fehler in den Folien mergerec2.pdf
und bin4.pdf korrigiert |
| Die Klausur im Rahmen des
Informatik-Vordiploms zu Theoretische Informatik
hat am 8. März 2005
statt gefunden.Die Korrektur ist durchgeführt. Die Resultate hängen am Schwarzen Brett von Lehrstuhl 8 im Informatik-Gebäude aus. Eine Einsichtnahme findet statt:
|
| Extra: eine Lösung
der MIU-Aufgabe (9. Übungsblatt) (pdf) |
|
Themen
|
Folien
|
Lesen!
|
|
|
18. Oktober
|
Informationen zur Vorlesung und zur
Organisation der Übungen, Themen der Vorlesung, Grundbegriffe: Probleme, Algorithmen Beispiel: Anzahl der Wörter gegebener Länge in einer regulären und in einer kontextfreien Sprache Beispiel: Multiplikation von Polynomen (wird forrtgesetzt) |
Einführung
1 (pdf, vorläufiger Text, noch nicht vollständig) Multiplikation 1 (pdf) Multiplikation 2 (pdf) |
Heun (GA) Random-Access-Maschine (pdf) Komplexitätsbegriffe (pdf) |
|
21. Oktober
|
Notation und Begriffe zu
boolescher Algebra und Aussagenlogik Bewertungen und partielle Bewertungen Satisfiability (SAT) Beispiel: Ein divide-and-conquer-Algorithmus für SAT Aufwandsabschätzung |
Einführung 2 (pdf) Ein divide-and-conquer-Algorithmus für SAT |
Schöning,
Algorithmik, Kap. 11 |
|
25. Oktober
|
SAT (Fortsetzung) Aufwandsabschätzung des divide-and-conquer-Verfahrens mittels linearer Rekursion Multiplikation: klassisch und Karatsuba Zur Geschichte der Arithmetik Sortieren (Uebersicht) |
(siehe oben) Arithmetik (pdf) |
Literatur zu Fibonacci und den
Fibonacci-Zahlen: Mathworld Tognetti Peters (von sehr vielen.....) |
|
28. Oktober
|
Achtung: die
Vorlesung findet heute ausnahmsweise
im H4 statt Wachstumsverhalten von Funktionen, Landau-Notation Summationen und deren Abschätzung Beispiele: harmonische Zahlen, Stirling-Formel, Catalan-Zahlen |
Landau-Notation
Einige Regeln für die Landau-Symbole Tabellen (pdf) Maple worksheets: harmonic stirling bintree |
Cormen/Leiserson/Rivest Kapitel 2 Catalan-Zahlen |
|
4. 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 |
|
|
8. November
|
Sortieren: allgemeine Bemerkungen, Rolle der
Inversionen, einfache Sortieralgorithmen (InsertionSort, SelectionSort) Mergesort rekursiv und iterativ Heapsort |
Sortieren (pdf) Inversionen ( Maple ) Mergesort (pdf) mergerec2.pdf |
Knuth TAOCP, vol.3 (5.5.1) Graham/Knuth/Patashnik Heun GA Kap. 2.1 Cormen/Leiserson/Rivest Kap. 1 |
|
11. November
|
Analyse von Heapsort Quicksort, Splittereigenschaft und Analyse |
Heapsort (pdf)
Quicksort (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 |
|
15. November
|
Splitter in Permutationen Binäre Bäume, binäre Suchbäume, innere und äussere Weglänge Quicksort-Rekursion für die mittlere innere Weglänge Vergleich von Komplexitätsfunktionen für das Sortieren |
splitter (pdf)
, Splitter (pdf) Binärbäume (pdf) ( neu, ergänzt am 25.11.) quick (pdf) , prioritaet (pdf) Vergleich (pdf) |
Knuth, TAOCP, vol 3, insbes. Kap. 6.2 Entscheidungsbäume für drei Sortierverfahren siehe unten Knuth TAOCP, vol.3, Kap. 5.3.1 |
| 18. November |
Binärbäume, geordnete Bäume
und die Dyck-Sprache Beweis von Catalans Formel Höhe von Binärbäumen untere Schranke für das Sortierproblem Zusammenhang mit dem Entropiebegriff |
catalan (pdf)
(neu! ) sortingbound (pdf) Entscheidungsbaum für mergesort (pdf) |
Knuth TAOCP, vol. 1, Kap. 2.3 Heun GA Kap. 2.6 |
|
22. November
25. November |
Entropie und Codierung Präfixcodes und Binärbäume, Ungleichung von Kraft Shannons Quellcodierungstheorem optimale Präfixcodierung |
Entropie (pdf)
|
CLR Kap. 17.3 |
| Vorbereitende und
ergänzende Lektüre zur Analyse von Divide-and-Conquer-Algorithmen |
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 |
|
|
29. November
|
Folgen, Reihen, rationale Sprachen und Funktionen |
FolgenReihenFunktionen
(pdf) (neu! korrigiert! ergänzt!) |
Aigner, Diskrete Mathematik,
Kap. 3 Sedgewick/Flajolet Graham/Knuth/Patashnik, Kap. 7 |
|
2. Dezember
6. Dezember |
C-rekursive Folgen, Charakterisierungen, Transfermatrix-Methode für reguläre Sprachen, Anwendungen, asymptotisches Verhalten, Analyse von divide-and-conquer-Rekursionen |
C-rekursive
Folgen (pdf) (neu! ergänzt am 2.12.!) Maple worksheets: Matrixbeispiel 1 (mw) (pdf) Matrixbeispiel 2 (mw) (pdf) Gamblers ruin: Mathematica-Notebook (nb) Printout (kurz) (pdf) Printour (lang) (pdf) |
Aigner, Diskrete Mathematik,
Kap. 3 Sedgewick/Flajolet Graham, Knuth, Patashnik, Kap. 7 |
| Vorschau: ---> Am Montag, den 6. Dezember , findet die Vorlesung ausnahmsweise zu den Zeiten und am Ort der Softwaresysteme 2 statt, also von 10:15--11:45 Uhr im H8 . ---> Am Montag, den 13. Dezember , findet keine Vorlesung statt. An Stelle der Vorlesung werden zur gleichen Zeit Übungen im Hörsaal H9 abgehalten. In dieser speziellen Hörsaalübung wird das siebte Übungsblatt (s.u.) behandelt. Die wöchentlichen Übungsgruppen behandeln anschliessend an das sechste das achte Übungsblatt. |
|||
|
9. Dezember
|
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 |
|
13. Dezember
|
Hörsaalübung zum 7.
Übungsblatt (Entropie, Codes) |
||
|
16. Dezember
|
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) (neue Version, erweitert!) |
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) |
| Historisches |
Kurzbiografie
von A. F. Möbius Zu einem berühmt-berüchtigten Werk von P. J. Möbius (Enkel von A.F.M.) |
||
|
20. Dezember
|
Geändertes Programm: zum Abschluss in
diesem Jahr
eine besonderes highlight aus der Theoretischen Informatik |
Verifikation von Primzahlen Primes in NP |
pratt
(ps) |
|
21. Dezember
|
Besprechung zu den vergangenen TI-Klausuren
|
ab 16 Uhr im K1
|
|
|
22. Dezember
|
zusätzliche Übung, auch
Fragestunde,
für Interessierte aus allen Übungsgruppen, sofern ihre Übungsgruppe nicht gleichzeitig stattfindet |
12-14 im K1
|
|
| 10. Januar 2005 13. Januar 2005 |
Schnelle Exponentiation Modulare Arithmetik |
Exponentiation
(pdf) Fibonacci-Berechnung (pdf) Modulare Arithmetik (pdf) Modulare Arithmetik (erweitert 12.1.05) |
Knuth, TAOCP vol 2, Kap. 4.6.3 Heun, GA 1.2 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) |
| 17. Januar 2005 |
Primzahltests, insbesondere der probabilistische
Test von Miller-Rabin |
Primzahltests
(pdf) |
Heun, Kap. 7.3 Für weitere Informationen zu Primzahlen und Primzahltests siehe "Weitere Materialien und Informationen " (unten) CLR Kap. 33.8 |
| 17. und 20. Januar 2005 |
Verschlüsselung durch Exponentiation public-key Kryptographie, RSA-Kryptosystem |
RSA-Kryptosystem
(pdf) RSA-576 (pdf) |
CLR, Kap. 33.7 (u.v.a.m) Heun, GA Kap. 7.4 |
|
Tip für Krypto-Interessierte
-->
|
Heise newsticker
18.1.05 |
Link dazu nach Bochum |
|
| 24. und 27. Januar 2005 |
Fouriertransformation klassisch, Diskrete Fourier-Transformation, Schnelle Fourier-Transformation, Anwendung auf die Polynommultiplikation |
FFT (
neu! ) (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 " |
| 31. Januar und 3. Februar 2005 | Die Komplexitätsklassen P und NP Reduktion zwischen Problemen NP-vollständige Probleme (Theorem von Cook-Levin) |
PNP-Folien (pdf)
PNP-Vortrag (pdf) |
CLR Kap. 36 Heun GA Kap. 6.2 Garey/Johnson: Computers and Intractability siehe unten "Weitere Materialien und Informationen " und die Literaturangaben in den Folien |
| 8. Februar 2005 |
Extra-Übung, 16h im K1 |
besprochen wird der letzte
Teil der MIU-Aufgabe, dazu Aufgaben aus früheren Klausuren |
|
| 7. und 10. Februar 2005 im H10 !! |
Quantencomputing und Faktorisierung Algorithmus von Shor |
Quantencomputing
(pdf) [Scans-5MB!!] Quantencomputing (Folien-pdf) Faktorisierung (Folien-pdf) Maple-worksheet (mw und pdf) |
Siehe Literaturangaben auf den Folien |
Link zu einem aktuellen Übersichtsartikel von A. Granville über den state-of-the-art bei der Erkennung von Primzahlen (Bulletin of the American Mathematical Society) |
|||
| Die
nächste Klausur im Rahmen des Informatik-Vordiploms zu Theoretische Informatik
findet am 8. März 2005
statt.Ort: Mensa-Süd und H8, Beginn 8:00 Uhr |
|||
|
Erstes Übungsblatt
|
19. Oktober 2004
|
uebungen-1 (pdf) |
| Zweites Übungsblatt |
28. Oktober 2004
|
uebungen-2 (pdf) |
|
Drittes Übungsblatt
|
4. November 2004
|
|
|
Viertes Übungsblatt
|
11. November 2004
|
|
|
Fünftes Übungsblatt
|
18. November 2004
|
|
|
Sechstes Übungsblatt
|
25. November 2004
|
|
|
Siebtes Übungsblatt
|
2. Dezember 2004
|
|
|
Achtes Übungsblatt
|
2. Dezember 2004
|
|
|
Neuntes Übungsblatt
|
7. Dezember 2004
|
|
|
Zehntes Übungsblatt
|
20. Dezember 2004
|
|
|
Elftes Übungsblatt
|
13. Januar 2005
|
|
|
Zwölftes Übungsblatt
|
13. Januar 2005
|
|
|
Dreizehntes Übungsblatt
|
20. Januar 2005
|
|
|
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
|
| 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 |
