Komplexität von Algorithmen

Studierende der Informatik, aber auch für Studierende aus anderen Fächern (Mathematik, Physik, E-Technik...), die Interesse und Gefallen an den Themen dieser Komplexitäts-Vorlesung gefunden haben, möchte ich an dieser Stelle auf zwei Veranstaltungen hinweisen, die im im kommenden Wintersemester durchführen werde. Beide Veranstaltungen sind für das Diplom-Hauptstudium bzw. Informatik-Bachelor ab 5. Semester vorgesehen.

Information und Codierung

Hier geht es um die Grundzüge der Informationstheorie mit dem Schwerpunkt “Kanalcodierung” und “Fehlerkorrigierende Codes”. Dies schliesst unmittelbar an das in der in diesem Semester behandelte Thema “Quellcodierung” an und führt von den klassischen Resultaten von Shannon bis zu den neuen Entwicklungen, mit denen Shannons Aussagen nun endlich konkret realisiert werden können.
Diese Veranstaltung wird im Sommersemester ergänzt durch eine Vorlesung über Quantencomputing und Quanteninformation. Die ergibt zusammen den Modul Information, Codierung, Komplexität als Vertiefung im Bachelorstudium.

Wavelettransformationen in der Bildverarbeitung

Nach einer Einführung in das Reich der Fouriertransformation wird der Formalismus der Wavelettransformationen in Theorie und Praxis behandelt. Die Anwendungsbeispiele stammen aus dem Bereich der Bildverarbeitung, deshalb wird diese Vorlesung durch Übungen ergänzt, die vom Lehrstuhl für Mustererkennung betreut werden. Diese Veranstaltung eignet sich daher für eine Vertiefung in “Theoretischer Informatik” und ebenso in “Mustererkennung”.

Nähere Informationen zu beiden Veranstaltungen im UnivIS.

20. April

Organisatorisches, Themen der Veranstaltung
Einführende Bemerkungen
Probleme zum Einstieg (2. Kapitel des Skripts)

24. April

Lösung der Wurm-Problems (harmonische Zahlen)
Einführende Erläuterungen zur Komplexität von Multiplikation und Sortieren
Ansatz zur Lösung des Frisbee-Problems: Wege in Graphen, Trellis-Diagramm,
Matrixdarstellung, C-rekursive Folgen, Eigenwerte, ...

27. April

C-rekursive Folgen: der Fall k=1
Potenzen von Matrizen und Eigenwerte
C-rekursive Folgen allgemein, Rekursionspolynom, charakteristisches Polynom,
VR-Basis mittels Nullstellen,
Matrizen und C-Rekursion: das Theorem von CAYLEY-HAMILTON
Lösung des Frisbee-Probelms

4. Mai

Vor Graphen zu Matrizen
Pfade in Graphen,
Theorem von KLEENE (reguläre Sprachen = rationale Sprachen),
C-Rekursion und reguläre Sprachen
Von Matrizen zu Graphen
Stochastische Matrizen, Konvergenz im Beispiel

8. Mai

Pseudozufallsfolgen und Schieberegister
Unzerlegbare und primitive Matrizen
Das Theorem von PERRON-FROBENIUS
Folgerung für stochastische Matrizen

11. Mai

Stationäre Verteilungen für stochastische Matrizen
Googles PageRank-Algorithmus

15. Mai

Schnelle Exponentiation (square-and-multiply)
Drei Algorithmen zur Berechnung der Fibonacci-Zahlen
Divide-and-Conquer-Rekursionen

18. Mai

Zwei “klassische” Divide-and-Conquer-Algorithmen:
Multiplikation von Polynomen (und Zahlen) von KARATSUBA
Multiplikation von Matrizen von STRASSEN
Von Divide-and-Conquer-Algorithmen zu linearen Rekursionen
Der Fall mehrfacher Nullstellen

22. Mai

Standard-Divide-and-Conquer-Rekursionen (2 Typen)
C-Rekursionen und Rationale Funktionen
(incl. geometrische Reihe, Binomialreihe von Newton)
Mehrfache Nullstellen in C-Rekursionen
Beispiel: ein effizienter Algorithmus für das Closest-Pair-Problem

25. Mai

Ergänzung: Inhomogene C-Rekursionen
Das satisfiability-Problem
Der Divide-and-Conquer-Algorithmus von MONIEN-SPECKENMEYER für k-SAT
Polynome: Auswertung, Hornerschema

Am Freitag, den 29. Mai, finden keine Übungen statt.
Nächster Termin für die Freitagsgruppen ist der 5. Juni.

29.05.09

Dualismen in Physik und Mathematik
Darstellung von Polynomen als Koeffizientenvektoren und Auswertungsvektoren
Inversionsformel von Lagrange
Polynommultiplikation mittels Auswertung und Interpolation
Komplexität dieses Verfahrens

06.06.09

Polynommultiplikation mittels Auswertung und Interpolation (Beispiel)
Komplexe Einheitswurzeln als Interpolationspunkte
Diskrete Fouriertransformation und Inverse Transformation
DFT-Matrizen als unitäre Matrizen
Divide-and-Conquer-Methode zur Realisierung der DFT
Der FFT-Algorithmus und seine Komplexität

08.06.09

Quicksort

12.06.09

Abschätzung der Grösse von Fakultäten, Formel von STIRLING
Die Folge (n!)_{n >=0} ist nicht C-rekursiv
Binäre Bäume, lineare Codierung
Lukasiewicz- und Dyck-Sprache
Quadratische Rekursion für die Catalan-Zahlen
Explizite Formel (Beweis folgt noch)
Die Folge der Catalan-Zahlen ist nicht C-rekursiv
Die Lukasiewicz- und Dyck-Spraches sind kontextfrei, aber nicht regulär

15.06.09

Drei Beweise für die Catalan-Formel:
1- Das Zykellemma für die Lukasiewicz-Sprache
2- Quadratische Gleichung für die Potenzreihe
3- Bijektion mit binären Bäumen
Optimale Auswertung von Matrixprodukten und binäre Bäume
Dynamische Programmierung für das Problem der optimalen Auswertung

19.06.09

Nochmal Dynamische Programmierung
Parameter von Binärbäumen (insbes. Höhe, Weglänge)
Binäre Suchbäume
Suchkomplexität und Weglänge
Konstruktion binärer Suchbäume
Eine Wahrscheinlichkeitsverteilung auf Binärbäiumen
Das Shuffle-Produkt von Wörtern und Sprachen

22.06.09

Permutationen und ihre binären Suchbäume – qantitativ
Die Quicksort-Rekursion für die mittlere Suchkomplexität
Komplexität von Sortierverfahren,
Entscheidungsbäume, Höhe und mittlere Höhe
Beispiele für (kleine) Entscheidungsbäume

26.06.09

Sortierkomplexität und binäre Bäume
Informationen zur ''wahren'' Komplexität des Sortierens
Fundamentale Ungleichung für die mittlere Höhe von Binärbäumen
Auftreten der Entropiefunktion im Beweis
Shannons Entropiefunktion: Motivation, Definition, Eigenschaften
Ungleichung von GIBBS
Gewichtete mittlere Höhe von Binärbäumen (Beispiele)

29.06.09

Gewichtete mittlere Höhe von Binärbäumen
SHANNONs Quellcodierungstheorem
Beweis der unteren Schranke
Quellen, Codierungen, Codes, Präfixcodes,
mittlere Codewortlänge
Ungleichung von KRAFT
Beweis der oberen Schranke von SHANNONs Theorem
HUFFMANs Konstruktion optimaler Präfixcodes

03.07.09

Zur Optimalität von HUFFMANs Konstruktion
Komplexität von HUFFMANs Konstruktion
Bemerkung zu GREEDY-Algorithmen

Arithmetische Eigenschaften des Ringes der ganzen Zahlen
Schwieigkeiten des Faktorisierens (Primfaktorzerlegung)
Der GGT und seine Berechnung
Der Algorithmus von EUKLID
Korrektheit und Termination
Aufwand des euklidischen Algorithmus: Satz von LAME
Alternative Herleitung der arithmetischen Komplexität
Komplexität im logarithmischen Kostenmodell
Bezout-Gleichung und ganzzahlige Geradengleichung

06.07.09

Untergruppen von (Z,+)
Algebraische Charakterisierung des ggT
Lösungen ganzzahliger Geradengleichungen

Überblick: Lösungen von Gleichungssystemen und Komplexität

Erweiterte Form des euklidischen Algorithmus

10.07.09

Beispiel zum erweiterten EA
Motivation: das RSA-Kryptosystem
Restklassenringe “modulo n” U_n
Einheitengruppe,
EULERs phi-Funktion,
Ordnung modulo n von Elementen aus U_n,
Satz von LAGRANGE,
Satz von EULER-FERMAT

13.07.09

Ordnungsberechnung und Faktorisierung
Das Beispiel RSA
Chinesischer Restesatz
Schema der modularen Arithmetik
Beispiele

17.07.09

Ergänzungen zum Thema “Modulare Arithmetik”
Der Fall von nicht-teilerfremden Moduln
Der Primzahltest von MILLER-RABIN (siehe 24.07.) im Licht der modularen Arithmetik

20.07.09

Effiziente Verifikation von Primzahlen (PRATT)

24.07.09

Der Primzahltest von MILLER-RABIN

20. April

Mathematische Hilfsmittel (1. Kapitel des Skripts)

25. April

Asymptotische Notation, Landau-Symbole

8. Mai

NOTABENE: dies sind vorläufige Versionen von Teilen des Skripts!
Nur für den internen Gebrauch zur Vorlesung und den Übungen!

Skript Kapitel 3 -- Version vom 7.5.09
Skript Kapitel 4 -- Version vom 7.5.09

Maple-worksheet Frisbee-Variante -- als pdf -- als mw
Maple-worksheet Stochastische Matrix -- als pdf -- als mw

11. Mai

Maple-worksheet PageRank-Algorithmus – als pdf – als mw
vorläufige Notizen zu Googles PageRank-Algorithmus

15. Mai

Folien zu “Schnelle Exponentiation”
Berechnung der Fibonacci-Zahlen

17. Mai

NOTABENE: dies sind vorläufige Versionen von Teilen des Skripts!
Nur für den internen Gebrauch zur Vorlesung und den Übungen!

Skript Kapitel 3 -- Version vom 17.5.09 (mit Literatur)
Skript Kapitel 4 -- Version vom 17.5.09 (mit Literatur)
Skript Kapitel 5 -- Version vom 17.5.09 (noch fragmentarisch)

18. Mai

Die Divide-and-Conquer-Algorithmen von Karatsuba und Strassen
Daten zur gemessenen Effizienz von Multiplikationsalgorithmen
Asymptotik der linearen Rekursionen
Typische Anwendungen der Schnellen Exponentiation in der Kryptografie

22. Mai

NOTABENE: dies sind vorläufige Versionen von Teilen des Skripts!
Nur für den internen Gebrauch zur Vorlesung und den Übungen!

Skript Kapitel 3 -- Version vom 21.5.09 (mit Literatur)
Skript Kapitel 4 -- Version vom 21.5.09 (mit Literatur)
Skript Kapitel 5 -- Version vom 21.5.09 (noch nicht komplett)

28. Mai

Ein ausführlicher Text zum Thema Fouriertransformation
Kopien von Folien zum Thema Fouriertransformation
Maple-worksheet zur Polynommultiplikation mittels DFT (pdf und mw)
Maple-worksheet zur Anwendung der DFT (pdf und mw)

08.06.09

Folien zum Sortierproblem allgemein (pdf)
Ausührlicher Text zu Quicksort (pdf)
Quicksort-Folien (pdf)
Text zur Splitter-Wahrscheinlichkeit (pdf)
Folien zu Splittern (pdf)

Skript Kapitel 5 – Version vom 7.6.09

12.06.09

Folien zu Binärbäumen (pdf)

NOTABENE:
Dies sind korrigierte und ergänzte vorläufige Versionen von Teilen des Skripts!
Nur für den internen Gebrauch zur Vorlesung und den Übungen!

Skript Kapitel 1 -- Version vom 12.6.09 (mit Literatur)
Skript Kapitel 3 -- Version vom 12.6.09 (mit Literatur)
Skript Kapitel 4 -- Version vom 12.6.09 (mit Literatur)
Skript Kapitel 5 -- Version vom 13.6.09 (mit Literatur)

Wie immer bitte ich um Rückmeldung bei Unklarheiten, Fehlern, Fragen, Anregungen usw.

15.06.09

Skript Kapitel 5/6 -- Version vom 15.6.09 (mit Literatur)

19.06.09

Folien zu Binärbäumen (pdf)

22.06.09

Folien zur Sortierkomplexität
Wege im Entscheidungsbaum für 4-Element-Mergesort
Entscheidungsbaum für ein 3-Element-Sortierverfahren
Entscheidungsbaum für 3-Element-Insertionsort
Entscheidungsbaum für 3-Element-Heapsort

Skript Kapitel 6 – Version vom 21.6.09

26.06.09

Folien Daten zur Sortierkomplexität
Folien zur Entropiefunktion

27.06.09

Skript Kapitel 6 – Version vom 27.6.09

03.07.09

Illustration zum Optimalitätsbeweis für die Huffman-Konstruktion

Folien zur Arithmetik

06.07.09

Existenz von Lösungen von Gleichungssystemen und Komplexität

10.07.09

Folien zu Restklassenringen
Folien zum RSA-System

10.07.09

Skriptum: Version vom 12. Juli 2009 (verbessert am 19.10.07)

13.07.09

Folien zum Chinesischen Restesatz und Modularer Arithmetik

17.07.09

Alternative Folien (mit MILLER-RABIN-Beispiel)

17.07.09

Folien zur Primzahlverifikation (PRATT)

Folien zum Primzahltest von MILLER-RABIN

• Die schriftlich zu bearbeitenden Aufgaben werden in der nachfolgenden Liste als solche gekennzeichnet

• Der Abgabetermin wird jeweils mit angegeben. Die schriftlichen Lösungen sind ein den dafür vorgesehenen Briefkasten am Eingang des Informatik-Gebädes einzuwerfen.

• Die Aufgaben können in Teams mit bis zu drei Teilnehmern aus derselben Übungsgruppe bearbeitet werden.
  Diese Teams sollten über das Semester hinweg stabil bleiben.
  Auf dem abgegebenen Blättern ist die Übungsgruppe zu vermerken.

• Jede Lösung einer schriftliche Aufgabe wird mit bis zu 10 Punkten bewertet.

1.Aufgabe:
(20. April)

Fingerübungen zum Rechnen mit Logarithmen

wird am 27. April behandelt
keine schriftliche Bearbeitung

2. Aufgabe:
(20. April)

Laufzeitenvergleiche

wird am 27. April behandelt
keine schriftliche Bearbeitung

3. Aufgabe:
(24. April)

Fibonacci-Zahlen, Rekursion und Induktion

schriftlich zu bearbeiten
Abgabe bis 4. Mai, 10 Uhr im Kasten

4. Aufgabe:
(24. April)

Eingeschränkte Kanäle/Sprachen

schriftlich zu bearbeiten
Abgabe bis 4. Mai, 10 Uhr im Kasten

Ergänzung und Anregung zur Aufgabe 4.1

OpenDocument-Format

5. Aufgabe:
(25. April)

Umgang mit asymptotischer Notation

wird am 4. Mai behandelt
keine schriftliche Bearbeitung

Lösungen zur Aufgabe 5 (von Ph. Schneider)
Maple-worksheet zur Aufgabe 5 (auch von Ph. Schneider)

.pdf-Format
.mw-Format

6. Aufgabe:
(3. Mai)

Douglas Hofstadters MIU-System

schriftlich zu bearbeiten
Abgabe bis 11. Mai, 10 Uhr im Kasten

7. Aufgabe:
(11. Mai)

Devil's Staircase

schriftlich zu bearbeiten
Abgabe bis 18. Mai, 10 Uhr im Kasten

8. Aufgabe
(11. Mai)

Quickies zum Selbsttest

werden in den Übungsgruppen behandelt, falls das nachgefragt wird

9. Aufgabe
(18. Mai)

Banale und Schnelle Exponentiation

schriftlich zu bearbeiten
Abgabe bis 25. Mai, 10 Uhr im Kasten

10. Aufgabe
(18. Mai)

Quickies zum Selbsttest

werden in den Übungsgruppen behandelt, falls das nachgefragt wird

11. Aufgabe
(18. Mai)

Lösungen einer inhomogenen Rekursion

schriftlich zu bearbeiten
Abgabe bis 25. Mai, 10 Uhr im Kasten

12. Aufgabe
(25. Mai)

Boolesche Matrixmultiplikation und Transitive Hülle (I)

schriftlich zu bearbeiten
Abgabe bis 8. Juni, 10 Uhr im Kasten

13. Aufgabe
(25. Mai)

Boolesche Matrixmultiplikation und Transitive Hülle (II)

Bonusaufgabe, Bearbeitung nicht obligatorisch; schriftliche Lösungen bis
8. Juni, 10 Uhr im Kasten

14. Aufgabe
(5. Juni)

Zur Komplexität der Matrixmultiplikation

schriftlich zu bearbeiten
Abgabe bis 15. Juni, 10 Uhr im Kasten

15. Aufgabe
(5. Juni)

Simultane Suche nach Maximum und Minimum

schriftlich zu bearbeiten
Abgabe bis 15. Juni, 10 Uhr im Kasten

16. Aufgabe
(5. Juni)

Quickies zum Selbsttest

werden in den Übungsgruppen behandelt, falls das nachgefragt wird

17. Aufgabe
(13. Juni)

Quickselect

schriftlich zu bearbeiten
Abgabe bis 22. Juni, 10 Uhr im Kasten

18. Aufgabe
(13. Juni)

Charakterisierungen der Lukasiewicz- und der Dyck-Sprache

schriftlich zu bearbeiten
Abgabe bis 22. Juni, 10 Uhr im Kasten

19. Aufgabe
(17. Juni)

Quickies zum Selbsttest

werden in den Übungsgruppen behandelt, falls das nachgefragt wird

Lösungen
(17. Juni)

Schriftliche Ausarbeitung der Lösungen
zu den Aufgaben 7, 8 und 11
Aufgabe 7 --- Aufgabe 8 --- Aufgabe 11

dankenswerterweise von Florian Forster zur Verfügung gestellt

20. Aufgabe
(22. Juni)

Balancierte Binärbäume

schriftlich zu bearbeiten
Abgabe bis 29. Juni, 10 Uhr im Kasten

21. Aufgabe
(22. Juni)

Optimales Matrixprodukt -- ein Spezialfall

schriftlich zu bearbeiten
Abgabe bis 29. Juni, 10 Uhr im Kasten

22. Aufgabe
(27. Juni)

Quickies zum Selbsttest

werden in den Übungsgruppen behandelt, falls das nachgefragt wird

23. Aufgabe
(27. Juni)

Entropie der Binomialverteilungen

schriftlich zu bearbeiten
Abgabe bis 6. Juli, 10 Uhr im Kasten

24. Aufgabe
(27. Juni)

Huffman-Codierung

schriftlich zu bearbeiten
Abgabe bis 6. Juli, 10 Uhr im Kasten

25. Aufgabe
(27. Juni)

Entropie und Volumen von Hammingkugeln

Bonusaufgabe, Bearbeitung nicht obligatorisch; schriftliche Lösungen bis
6. Juli, 10 Uhr im Kasten

Lösungen
(2. Juli)

Schriftliche Ausarbeitung der Lösung
zur Aufgabe 21

dankenswerterweise von Florian Forster zur Verfügung gestellt

Lösungen
(3. Juli)

Schriftliche Ausarbeitung der Lösung
zur Aufgabe 18

dankenswerterweise von Philipp Schneider zur Verfügung gestellt

26. Aufgabe

Bezout im Originalton

schriftlich zu bearbeiten
Abgabe bis 15.Juli, 10 Uhr im Kasten

27. Aufgabe

Rechnen in Z_N

schriftlich zu bearbeiten
Abgabe bis 15.Juli, 10 Uhr im Kasten

28. Aufgabe

Quickies zum Selbsttest

werden in den Übungsgruppen behandelt, falls das nachgefragt wird

29. Aufgabe

Das Spiel von Euklid

Bonusaufgabe, Bearbeitung nicht obligatorisch; schriftliche Lösungen bis
15. Juli, 10 Uhr im Kasten

Lösungen
(12. Juli)

Schriftliche Ausarbeitung der Lösung
zur Aufgabe 23

Lösungen
(12. Juli)

Schriftliche Ausarbeitung der Lösung
zur Aufgabe 25