|
Themen
|
Folien
|
Lesen!
|
|
|
19. April
|
Informationen zur Vorlesung
und zur Organisation der Übungen, erste Beispiele: Multiplikation traditionell und nach Karatsuba, Komplexitaetsvergleiche fuer verschiedene Multiplikationsalgorithmen (theoretisch und experimentell) |
Informationen
(pdf)
Multiplikation 1 (pdf) Multiplikation 2 (pdf) |
|
|
23. April
|
Bemerkungen zum Szenarion der Komplexitätsanalyse
von Algorithmen und Problemen Primzahlen, Primzahltests, Faktorisierung: einige Bemerkungen Effizientes Entscheiden vs. effizientes Verifizieren |
Faktorisierung
(pdf)
|
Neues zur Faktorisierunghttp://www.rsasecurity.com |
|
26. April
|
Schnelle Exponentiation Berechnungsverfahren für Fibonacci-Zahlen |
Exponentiation
(pdf) Fibonacci (pdf) |
Heun, GA, 1.2 |
|
30. April
|
Komplexität der schnellen Exponentiation Anwendung auf Berechnung der Fibonacci-Zahlen Anmerkungen zur Geschichte der Arithmetik RAM-Maschinenmodell |
Random-Access-Maschine
(pdf) Arithmetik (pdf) |
Heun, GA, 1.3.1--1.3.4 |
|
3. Mai
|
asymptotisches Verhalten von Funktionen Landau-Notation |
Landau-Notation
(neu) Einige Regeln für die Landau-Symbole |
Heun (s.o.) Cormen/Leiserson/Rivest Kapitel 2 |
|
7. Mai
|
Asymptotisches Verhalten von harmonischen Zahlen,
Potenzsummen, Fakultäten Asymptotische Abzahl binärer Bäume Komplexitätsbegriffe |
Maple worksheets: harmonic stirling bintree Komplexitätsbegriffe (pdf) |
Catalan-Zahlen
Heun (s.o.) |
| Tabellarische Information zum Laufzeitverhalten |
Tabellen (pdf)
|
||
|
10. Mai
|
Lexicografischer Vergleich Maximumsuche in einer Liste worst-case, best-case, average-case |
Lexorder (pdf)
Maximumsuche (pdf) |
|
|
14. Mai
|
Permutationen und Inversionen Sortieren, einführende Bemerkungen, kombinatorische Aspekte, Sortieren durch Auswählen und durch Einfügen, |
Permutationen
und Inversionen
Inversionen (Maple) Sortieren (pdf) splitter.pdf |
Knuth TAOCP, vol.3 (5.5.1) Graham/Knuth/Patashnik Heun GA Kap. 2.1 Cormen/Leiserson/Rivest Kap. 1 |
|
17. Mai
|
Sortieren durch Mischen (mergesort) Heapsort |
Mergesort (pdf)
mergerec2.pdf |
Heun GA Kap. 2.2 Knuth TAOCP, vol.3 (5.2.4) CLR Kap. 1.3.1 |
|
21. Mai
|
Analyse von Heapsort Quicksort |
Heapsort (pdf)
|
Heun GA Kap. 2.3 Knuth TAOCP, vol.3 (5.2.3) CLR Kap. 7 |
|
24. Mai
|
Analyse von Quicksort Binäre Bäume, Entscheidungsbäume für das Sortierproblem, untere Schranke siehe unten: Entscheidungsbäume für drei Sortierverfahren |
Quicksort (pdf) quick.pdf sortingbound (pdf) |
Heun GA Kap. 2.4 Knuth TAOCP, vol.3 (5.2.2) CLR Kap. 8, 9.1 |
|
28. Mai
|
Entscheidungsbaum für Mergesort, untere Schranke für das Sortierproblem gewichtete Binärbäume, mittlere Höhe, Eigenschaften der Entropiefunktion |
Entscheidungsbaum
fuer Mergesort
Vergleich (pdf) |
Heun GA Kap. 2.6 Knuth TAOCP, vol.3, Kap. 5.3.1 |
|
4. Juni
|
Quellen und Codes Quellcodierungstheore (Shannon) optimale Präfixcodierung (Huffmann) |
Entropie (pdf)
|
CLR Kap. 17.3 |
|
7. Juni
11. Juni 14. Juni |
Divide-and-Conquer Beispiele: Polynommultiplikation (Karatsuba), Matrixmultiplikation (Strassen) Closest-Pair Problem |
Divide-and-Conquer
(pdf) Ausfuehrlicher Text (pdf) KaratsubaStrassen (pdf) ClosestPair (pdf) |
Heun GA Kap. 2.5 CLR Kap 4 Sedgewick,Flajolet Heun GA Kap. 7.6 und 7.8 CLR Kap 31 Ottmann |
| Vorschau: In der Woche vom 28.Juni -2. Juli findet keine Vorlesung statt. Die Vorlesungszeiten werden allerdings für Hörsaal-Übungen zu speziellen Aufgaben genutzt! Die Übungsgruppen finden aber trotzdem zu den gewohnten Zeiten statt. Die ausfallenden Vorlesungen werden am Semesterende nachgeholt. |
|||
|
11. Juni
|
Arithmetik der ganzen Zahlen, grundlegende Eigenschaften,
Algorithmus von Euklid |
Arithmetik (pdf)
(revidiert 13.5.04) |
Heun GA Kap 7.1 CLR Kap. 33 |
|
18. Juni
|
erweiterter euklidischer Algorithmus ganzzahlige lineare Gleichungen binärer euklidischer Algorithmus |
Heun GA Kap 7.1
CLR Kap. 33 Knuth TAOCP vol. 2, Kap. 4.5 |
|
| Extras: zum 50. Todestag von A. Turing, zum 60. Geburtstag von W. Diffie zu Aktivitäten des Lehrstuhls für Hardware-Software-Codesign |
Alan Turing, Wilfried Diffie (pdf) Poster Informatik 12 (pdf) |
Karatsuba! Euklid! |
|
|
21. Juni
|
Restklassenringe, Sätze von Lagrange, Fermat,
Euler |
Arithmetik (Forts.) (pdf)
Restklassenringe (pdf) (revidiert 22.6.) |
Heun GA Kap. 7.2 CLR Kap. 33 Für weitere Informationen zur Arithmetik der Restklassenringe (worksheets!) siehe "Weitere Materialien und Informationen" (unten) |
|
25. Juni
|
Modulare Arithmetik |
Modulare Arithmetik (detailliert) (pdf)
|
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) |
|
28. Juni
|
Hörsaalübung zum 8. Übungsblatt
|
||
|
2. Juli
|
Hörsaalübung zum 8. Übungsblatt
|
||
|
5. Juli
9. Juli |
Primzahlen und Primzahltests |
Primzahlen/Primzahltests
Zeugenmengen für Pseudoprimtests |
Heun Kap. 7.3 Für weitere Informationen zu Primzahlen und Primzahltests siehe "Weitere Materialien und Informationen " (unten) CLR Kap. 33.8 gerade eben erschienen |
| Die am 28. Juni und 2. Juli
ausgefallenen Vorlesungen werden am >> Mittwoch, den 21. Juli >> Donnerstag, den 22. Juli >> jeweils um 16:00 Uhr >> im H9 nachgeholt |
|||
|
12. Juli
|
Fourier-Transformation, Faltung, Anwendungen |
siehe Texte, worksheets weiter unten bei "Weitere Materialien und Informationen " |
|
|
16. Juli
|
Verschlüsselung durch Exponentiation public-key Kryptographie, RSA-Kryptosystem |
RSA-Kryptosystem
|
CLR Kap. 33.7 (u.v.a.m) Heun GA Kap. 7.4 |
|
19. Juli
|
Diskrete Fourier-Transformation, Polynommultiplikation (Faltung) mittels DFT |
Fouriertransformation
|
CLR Kap. 32 Heun GA Kap. 7.5 |
|
21. Juli
|
Ergänzende Vorlesung zum
P-NP-Problem (1) 16h, H9 |
P - NP (pdf)
|
Heun GA Kap. 6.2 CLR Kap. 36 weitere Informationen siehe unten "Weitere Materialien und Informationen " |
|
22. Juli
|
Ergänzende Vorlesung zum
P-NP-Problem (2) 16h, H9 |
pnp (pdf)
|
Heun GA Kap. 8.2 CLR Kap. 36 weitere Informationen siehe unten "Weitere Materialien und Informationen " |
|
23. Juli
|
Schnelle Fourier-Transformation, Polynommultiplikation (Faltung) mittels FFT |
Maple worksheet (pdf)
|
CLR Kap. 32 Heun GA Kap. 7.5 |
| Die Klausur im Rahmen des Informatik-Vordiploms
zu Einführung in die Theoretische Informatik findet am 14. September 2004 statt |
|
Erstes Übungsblatt
|
22. April 2004
|
uebungen1 (pdf)
|
| Zweites Übungsblatt |
29. April 2004
|
uebungen2 (pdf)
|
|
Drittes Übungsblatt
|
5. Mai 2004
|
|
|
Viertes Übungsblatt
|
12. Mai 2004
|
|
|
Fünftes Übungsblatt
|
20. Mai 2004
|
|
|
Sechstes Übungsblatt
|
1. Juni 2004
|
|
|
Siebtes Übungsblatt
|
9. Juni 2004
|
|
|
Achtes Übungsblatt
|
9. Juni 2004
|
|
| Die Aufgaben des achten Übungblattes
werden in den Hörsaalübungen in der Woche vom 28. Juni-
2. Juli (siehe oben) behandelt |
||
|
Neuntes Übungsblatt
|
13. Juni 2004
|
|
|
Zehntes Übungsblatt
|
13. Juni 2004
|
|
|
Elftes Übungsblatt
|
25. Juni 2004
|
|
|
Zwölftes Übungsblatt
|
8. Juli 2004
|
|
|
Dreizehntes Übungsblatt
|
8. Juli 2004
|
|
|
Sammlung weiterer Aufgaben
|
||
| 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 |
