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.

Themen

Folien

Lesen! Links!

19. 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
einer regulären bzw. kontextfreien Sprache

Kurt Gödel (1906-1978)

Einführung











Extra: Kurt Gödel

Heun (GA)

Random-Access-Maschine

Komplexitätsbegriffe




Es gab Gödel. Und es gibt Blödel.
(letzter Beitrag im neuesten Aviso-Heft)

24. Oktober

Anmerkungen zum Gödelschen Unvollständigkeitssatz

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

Saturn und Cassini

Multiplikation 1


Multiplikation 2

Multiplikation 3




Cassini

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.

26. Oktober

Anmerkungen zur Geschichte der Arithmetik

Einige mathematische Grundlagen:
geometrische Reihe, Anwendung auf die
Analyse einfacher divide-and-conquer-Rekursionen
(Master Theorem)

Arithmetik (pdf)

Mathematische Hilfsmittel (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

26. Oktober
30. Oktober

Binomialformel, Binomialkoeffizienten, Binomialreihe,
Abschätzung von Potenzsummen durch Integrale, Fakultäten (Stirlings Formel),
Binomialkoeffizienten (Shannons Formel)

Mathematische Hilfsmittel (pdf)

Maple worksheets
(auch pdf)
harmonic
stirling
bintree
binomial-1
binomial-2

2. November

Binärbäume, geordnete Bäume, Dyck-Sprache
Exakte und asymptotische Anzahlen von Binärbäumen (Catalans Formel)
Beweis von Catalans Formel per Induktion
Bitvektoren, boolescher Ring, Hamming-Abstand,

catalan (pdf)

Catalan-Zahlen

6. November

Hammingkugeln und deren Volumen
Szenario der Codierungstheorie
Codes, Rate, Minimaldistanz
lineare Codes, Generator- und Kontrollmatrizen

codes (pdf)

9. November

Fano-Geometrie, Hamming-Codes

13. November

Reed-Muller-Codes
asymptotische Schranken für Codes
(Plotkin, Gilbert-Varshamov)

16. 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

20. November

Sortieren: allgemeine Bemerkungen,
Rolle der Inversionen,
Inversionsvektoren und
faktorielle Zahldarstellung
einfache Sortieralgorithmen (InsertionSort, SelectionSort),
mittlere Anzahl von Inversionen

Sortieren (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

23. November

Mergesort rekursiv und iterativ,
Sortieren mit Netzwerken,
Heapsort,
Analyse von Heapsort

Mergesort (pdf)
mergerec2.pdf
Heapsort (pdf)

Heun GA Kap. 2.3, 2.4
Knuth TAOCP, vol.3
(5.2.2, 5.2.3)
CLR Kap. 7, 8

27. November

Quicksort,
Splittereigenschaft,
Analyse von Quicksort

closest-pair Problem

Quicksort (pdf)
quick (pdf)
splitter (pdf)
Splitter (pdf)
Closest Pair (pdf)

weitere Texte zu Quicksort siehe unten

30. November

divide-and-conquer-Algorithmen
Beispiele, Analyse
Master-Theorem für asymptotisches Verhalten der Lösungen von divide-and-conquer Rekursionen
Beweis des Master-Theorems

Karatsuba/Strassen (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

Ab 4. Dezember findet die Vorlesung im H4 statt, falls nicht etwas anderes ausdrücklich bekanntgegeben wird

4. Dezember

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

4. 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

7. Dezember

Entropie und Codierung
Präfixcodes und Binärbäume,
Shannons Quellcodierungstheorem

Entropie (pdf)

CLR Kap. 17.3

siehe auch Folien zur Vorlesung

Die Maschine von Antikythera (pdf)

11. Dezember

Ungleichung von Kraft,
optimale Präfixcodierung,
Verfahren von Huffman

14. Dezember

Produkte von Quellen,

produkte (pdf)
capacity (pdf)

18. Dezember

Kapazität des BSC
Beispiele zur probabilistischen Methode

probabilistic (pdf)

22. Dezember

Zur probabilistischen Methode: das Ramsey-Problem

Überraschungsvideo(s)

channelcoding (pdf)
(kommt später dran)

Zu den am 22. Dezember gezeigten Videos:

1. MESH - A Journey Through Discrete Geometry
   von Beau Janzen und Konrad Polthier

2. FAUST
   von Johann Wolfgang von Goethe
   in der Inszenierung von Gustaf Gründgens am Hamburger Schauspielhaus 1960

1. ist gerade eben (Dez. 2006) im Springer-Verlag erschienen und hat die ISBN 978-3-540-28478-9. Das kann man über den Buchhandel oder Internet-Versender wie den Online-Shop vom Spektrum-Verlag beziehen.

2. ist beim DVD-Vertrieb ARTHAUS unter Katalognummer D 1874 erschienen. Bezugsquellen findet man reichlich im Internet.

Leseempfehlungen zu den Feiertagen und darüber hinaus..... (von 2005, aber immer noch gut)



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

8. Januar

ausnahmsweise im H9 !

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

Zu ggT und euklidischem Algorithmus

Euclid's game

11./15. Januar

Restklassenringe mod n,
Einheitengruppe, Eulers phi-Funktion,
Ordnung von Elementen in einer Gruppe,
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)

18. Januar

Vorlesung wegen Unwetterwarnung ausgefallen

22. Januar

Multiplikativität der phi-Funktion
Sätze von Lagrange, Fermat, Euler
Schnelle Exponentiation
Drei Methoden, die Fibonacci-Zahlen zu berechnen

Exponentiation (pdf)    

Fibonacci-Berechnung (pdf)

Knuth, TAOCP vol 2, Kap. 4.6.3
Heun, GA 1.2

25. 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)

29. Januar/
1. Februar

Primzahlen,
Verifikation der Primzahleigenschaft,
Primes in NP: Pratt),
zur Komplexität von "Primes",
Primzahltests, insbes. 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

Erstes Übungsblatt

20. Oktober

übungen-1 (pdf)

Zweites Übungsblatt

26. Oktober

übungen-2 (pdf)

Drittes Übungsblatt

1. November

übungen-3 (pdf)

Viertes Übungsblatt

8. November

übungen-4 (pdf)

Fünftes Übungsblatt

16. November

übungen-5 (pdf)

Sechstes Übungsblatt

23. November

übungen-6 (pdf)

Aufgaben zur Landau-Notation

21. November

aufgaben (pdf)

Siebtes Übungsblatt

29. November

übungen-7 (pdf)

Achtes Übungsblatt

6.Dezember

übungen-8 (pdf)

Neuntes Übungsblatt

13.Dezember

übungen-9 (pdf)

Zehntes Übungsblatt

10. Januar 2007

übungen-10 (pdf)

Elftes Übungsblatt

17. Januar 2007

übungen-11 (pdf)

Zwöftes Übungsblatt

24. Januar 2007

übungen-12 (pdf)

Dreizehntes Übungsblatt

31. Januar 2007

übungen-13 (pdf)

Klausuren Theoretische Informatik

Herbst 2002

H02 (pdf)

Frühjahr 2003

F03 (pdf)

Herbst 2003

H03 (pdf)

Frühjahr 2004

F04 (pdf)

Herbst 2004

H04 (pdf)

Frühjahr 2005

F05 (pdf)

Herbst 2005

H05 (pdf)

Frühjahr 2006

F06 (pdf)

Herbst 2006

H06 (pdf)

Frühjahr 2007

F07 (pdf)

Sammlung weiterer Aufgaben

sammlung (pdf)

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 
b) Basisalgorithmen der Integer-Arithmetik
c) Euklidischer Algorithmus, Kettenbruchentwicklung
d) Chinesischer Restesatz und Modulare Arithmetik

a

pdf

b

pdf

c

pdf

d

pdf

Weitere Informationen und Maple-worksheets zum Thema (Integer-)Arithmetik

a) Eigenschaften der Restklassenringe 
b) Determinanten mittels modularer Arithmetik
c) Euklidischer Algorithmus (M. Monagan)
d) Fermat's Theorem (J. Cosgrave)
e) Primzahltests (M. May)

a

mws

pdf

b

mws

pdf

c

mws

pdf

d

mws

pdf

e

mws

pdf

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

weitere Probleme und Reduktionen

cover.ps

Vierfarbenproblem
(Geschichte)

colors4.ps

Polynome und Färbungen

polychrom4.pdf

Resolution und 2-SAT

resolution4.pdf

kommentierte Folien (unvollstaendig) zu einem Vortrag

pnp (pdf)

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