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 ich in den beiden kommenden Semestern durchführen werde. Sie sind für das Informatik-Master (bzw. Hauptstudium Diplom) vorgesehen, können aber auch als Vertiefung im Informatik-Bachelor gewählt werden.

1. Wavelettransformationen in der Bildverarbeitung (WS 2012/13)

   Aufbauend auf 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 wie in “Mustererkennung”.

   Nähere Informationen dazu im UnivIS früherer Semester (z.B. WS 2010/11) und unter diesem Link

2. Quantencomputing und Quanteninformation (SS 2012)

   Diese Veranstaltung hat zum Ziel, die Teilnehmer mit den grundlegenden Konzepten, Techniken und Resultaten des Quantencomputing und der Quanteninformation vertraut zu machen. Nach einer Diskussion grundlegender Phänomene wie Superposition und Verschränkung und einer Behandlung des mathematischen Formalismus werden insbesondere solche Themen behandelt, die aus der Sicht der Informatik interessant sind: Deutsch-Josza-Problem und Verwandtes; Phasenschätzung, Fouriertransformation und Shors Faktorisierungsalgorithmus; Grovers Suchalgorithmus; kryptografische Protokolle wie BB84; Verwendung fehlerkorrigierender Codes. Diese ist eine Vertiefungs-Veranstaltung für “Theoretische Informatik"

   Nähere Informationen dazu im UnivIS früherer Semester (z.B. SS2010) und unter diesem Link.

4. Mai

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

6. Mai

Rekursive Algorithmen (Divide-and-Conquer) für die Multiplikation von ganzen Zahlen
Komplexität der Multiplikation: Traditionell und Karatsuba
Ansatz zur Lösung des Frisbee-Problems: Wege in Graphen, Trellis-Diagramm

11. Mai

Lösung des Frisbee-Problems
Erläuterungen zur Komplexität von Algorithmen und Problemen

13. Mai

Lösung des Frisbee-Problems
Weitere Erläuterungen zur Komplexität von Algorithmen und Problemen
Asymptotisches Vehalten in einigen wichtigen Fällen

18. Mai

Goldener Schnitt, geometrische Folgen,
Potenzen von Matrizen und Eigenwerte,
C-rekursive Folgen, Rekursionspolynom, charakteristisches Polynom,
VR-Basis mittels Nullstellen des charakteristischen Polynoms
kanonische Basis und Vandermonde-Determinante

20. Mai

C-rekursive Folgen: asymptotisches Verhalten aus den geometrischen Basislösungen,
der Fall mehrfacher Nullstellen des charakteristischen Polynoms,
Maple-Beispiele (siehe Materialien),
Potenzen von Matrizen, das Theorem von CAYLEY-HAMILTON,
Eine Variante des Frisbee-Problems

HINWEIS

8. Juni

Multiplikation von Polynomen mittels Auswertung und Interpolation
Schnelle Multiplikation von Polynomen mittels FFT
Maple-Illustrationen zu diesen Verfahren
Potenzen von Matrizen und die Bedeutung des Cayley-Hamilton-Theorems
Wege in Graphen

15. Juni

Stationäre Verteilungen für stochastische Matrizen
Googles PageRank-Algorithmus
C-Rekursion und rationale Funktionen
forcierte (=inhomogene) C-Rekursionen
Beispiel zur Analyse asymptotischen Verghaltens einer forcierten Rekursion
Anwendung: one-time pad mittels einer binären Pseudozufallsfolge

17. Juni

Zur Analyse von divide-and-conquer-Algorithmen, asymptotisches Verhalten, Master Theorem
Illustrationen zum Unschärfeprinzip für die Fouriertransformation

22. Juni

Asymptotisches Verhalten dreier nicht-C-rekursiver Folgen: harmonische Zahlen, Fakultäten, Catalan-Zahlen
Binärbäume und ihre Codierung: Lukasiewicz-Sprache und Dyck-Sprache
Rekursionen mit polynomiellen Koeffizienten für die drei Beispiele

24. Juni

Drei Methoden zur Berechnung der Glieder C-rekursiver Folge:
rekursiv, iterativ, schnelle Exponentiation der Begleitmatrix
Schnelle Exponentiation mittels square-and-multiply
Quicksort mit Analyse des average-case-Aufwandes

29. Juni

Optimale Auswertung von Matrixprodukten und binäre Bäume
Dynamische Programmierung für das Problem der optimalen Auswertung
Parameter von Binärbäumen (insbes. Höhe, Weglänge)
Sortierkomplexität und Entscheidungsbäume

1. Juli

Höhe und mittlere Höhe von Binärbäumen
Fundamentale Beziehungen zwischen Höhe und Anzahl der Blätter
Auftreten der Entropiefunktion im Beweis der
fundamentalen Ungleichung für die mittlere Höhe von Binärbäumen
Sortierkomplexität und Entscheidungsbäme:
untere Schranke für die Anzahl von Vergleichen im worst-case und im average-case
Komplexität von Sortierverfahren (Beispiele)
Informationen zur ''wahren'' Komplexität des Sortierens
Shannons Entropiefunktion: Motivation, Definition, Eigenschaften, Beispiele
Ungleichung von GIBBS (key lemma)

6. Juli

Zusammenfassung: Sotierkomplexität und Binärbäume
Beispiele zur Entropie von Verteilungen und Texten
Gewichtete mittlere Höhe von Binärbäumen
SHANNONs Quellcodierungstheorem
Beweis der unteren Schranke
Quellen, Codierungen, Codes, Präfixcodes, mittlere Codewortlänge

8. Juli

Ungleichung von KRAFT
Beweis der oberen Schranke von SHANNONs Theorem
HUFFMANs Konstruktion optimaler Präfixcodes
Zur Optimalität von HUFFMANs Konstruktion
Komplexität von HUFFMANs Konstruktion
Bemerkungen zu GREEDY-Algorithmen

13. Juli

Beispiel zur Huffman-Codierung
Bit-Komplexität arithmetischer Operationen (Übersicht)
Arithmetische Eigenschaften des Ringes der ganzen Zahlen
Schwierigkeit des Faktorisierens (Primfaktorzerlegung)
Der GGT und seine Berechnung
Der Algorithmus von EUKLID (EA)
Korrektheit und Termination des EA
Aufwand des EA: Satz von LAME

15. Juli

Untergruppen von (Z,+)
Algebraische Charakterisierung des ggT
Lösungen ganzzahliger Geradengleichungen
Überblick: Lösungen von Gleichungssystemen und Komplexität
Erweiterte Form des euklidischen Algorithmus
Beispiel zum erweiterten EA

20. Juli

Nochmal Komplexitätdes euklidischen Algorithmus (auch im logarithmischen Kostenmodell)
Restklassenringe “modulo n”
Einheitengruppe U_n
EULERs phi-Funktion, Sätze von EULER und FERMAT
Exponentiation modulo p als Verschlüsselung (Pohlig-Hellman)

22. Juli

Ein ineffizienter Algorithmus für EULERs φ-Funktion
Restklassenringe “modulo n” und Einheitengruppe U_n
Multiplikativität der φ-Funktion
Simultane Kongruenzen (chinesischer Restesatz)
Ordnung modulo n von Elementen aus U_n
Sätze von LAGRANGE und EULER-FERMAT
Idee der public-key-Kryptographie
Das RSA-Kryptosystem

27. Juli

Effizienz und Sicherheit des RSA-Kryptosystems
Berechnung von Ordnungen und Faktorisierung
Effiziente Verifikation von Primzahlen: "Primes in NP" (PRATT)

29. Juli

Effizienz der Primzahl-Verifikation von Pratt
Das Prinzip hinter dem Miller-Rabin-Test
Zeugen für Zusammengesetztheit (Teilbarkeit, Euklid, Fermat-Euler, Miller-Rabin)
Struktur probabilistischer Primzahltests
Der Primzahltest von MILLER-RABIN
"Konstruktion" grosser Primzahlen

4. Mai

Skriptum aus dem SS 2009 (korr. Version vom 19. Juni 2010)

11. Mai

Asymptotische Notation, Landau-Symbole
worm-up! Eine sehr ausführliche Lösung des Wurm-Problems

13. Mai

Zur Multiplikation (Folien)
Ein Fibonacci-Puzzle

18. Mai

Stichwort: Vandermonde-Matrix
Stichwort: Cayley-Hamilton-Theorem

18. Mai

Ein kurzer, knackiger Beweis der Determinantenformel von Vandermonde
Ein historischer Text (von vielen) zu den Fibonacci-Zahlen

20. Mai

Maple-worksheet Frisbee-Variante -- als pdf -- als mw
Maple-worksheet Anwendung von LFSR-Folgen -- als pdf -- als mw
Maple-worksheet Beispiele zur Lösung von linearen Rekursionen -- als pdf -- als mw
Maple-worksheet stochatische Matrix als pdf -- als mw

7. Juni

Folien und Materialien zu den Vorlesungen der vorletzten Woche
Die Divide-and-Conquer-Algorithmen von Karatsuba und Strassen
Daten zur gemessenen Effizienz von Multiplikationsalgorithmen
Folien zum closest-pair-Algorithmus
Folien zum Satisfiability-Algorithmus von Monien-Speckenmayer
Beispiel zum Satisfiability-Algorithmus von Monien-Speckenmayer

7. Juni

Folien und Materialien zu den Vorlesungen der vorigen Woche
Diskrete und schnelle Fouriertranmsfrormation FFT
Anwendungen der Fouriertransformation in der Bildverarbeitung (Gonzales/Woods)
Anwendungen der Fouriertransformation in der Kernspinresonanzanalyse (R. Ernst)
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)
Maple-Beispiel zur “Verwendung der FFT (mw)”

10. Juni

15. Juni

Maple-worksheet zu Googles PageRank-Algorithmus – als pdf – als mw

17. Juni

Asymptotik der linearen Rekursionen (ausführliche Folien mit vielen Beispielen)
Zur Analyse von divide-and-conquer-Algorithmen
Beispiele für die Lösung von divide-and-conquer-Rekursionen
Maple-worksheet mit Illustrationen zum Unschärfeprinzip für die Fouriertransformation – als pdf – als mw

24. Juni

Asymptotik der Fakultäten Maple-ws und pdf
Asymptotik der Catalan-Zahlen Maple-ws und pdf
Drei Methoden zur Berechnung der Glieder einer C-rekursiven Folge auch als Maple-worksheet
Folien zu “Schnelle Exponentiation”
Berechnung der Fibonacci-Zahlen
Typische Anwendungen der Schnellen Exponentiation in der Kryptografie

Folien zur Analyse von Quicksort (heutige Vorlesung)
Folien zum Sortierproblem allgemein (pdf)
Ausührlicher Text zu Quicksort (pdf)
Ältere Quicksort-Folien (pdf)
Text zur Splitter-Wahrscheinlichkeit (pdf)
Folien zu Splittern (pdf)

Folien zur Dynamische Programmierung
Folien zu Binärbäumen (1) (pdf)
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

6. Juli

Folien zur Sortierkomplexität
Folien zur Entropiefunktion
Information und Entropie für geometrische und Binomialverteilungen (als Maple-worksheet und als pdf)
Beispiele zur Entropie von Verteilungen (1) (als Maple-worksheet)
Beispiele zur Entropie von Verteilungen (2) (als Maple-worksheet)
Beispiele zur Entropie von Texten (als Maple-worksheet)

8. und 13. Juli

Illustration zum Optimalitätsbeweis für die Huffman-Konstruktion
Folien zur Konstruktion optimaler Codes
Maple-Beispiel zur Konstruktion optimaler Codes (pdf) (auch als Maple-worksheet)

Literaturempfehlungen:

1. Claude Shannon, A Mathematical Theory of Information, Bell System Technical Journal 27:379-423 und 623-656, 1948
   (die "Geburtsurkunde" der Informationstheorie überhaupt, auch nach über 60 Jahren noch eine lohnende Lektüre!)
   
2. David Salomon, Data Compression, The Complete Reference, Springer 2007 (über 1000 Seiten! Für diejenigen, die den kompletten Überblick haben wollen)
   
3. David Salomon, Variable-length Codes for Data Compression, Springer 2007 (knapp 200 Seiten. Der Teil aus dem vorigen Titel, der sich mit Huffman-Codierung etc. befasst)
   
4. James Gleick, The Information. A History, a Theory, a Flood, Harper-Collins 2011 (um die 500 Seiten. Die Geschichte der Informationstheorie als anregende Sommerlektüre)

13. Juli

Folien zur Arithmetik
Komplexität arithmetischer Operationen Tabelle
Existenz von Lösungen von Gleichungssystemen und Komplexität

15. Juli

Maple-Beispiele zum Algorithmus von Euklid (pdf) auch als Maple-worksheet
Existenz von Lösungen von Gleichungssystemen und Komplexität

20. Juli

Folien zu Restklassenringen
Folien zum RSA-System

22. Juli

Folien zum Chinesischen Restesatz und Modularer Arithmetik
Alternative Folien (mit MILLER-RABIN-Beispiel)

1. Jim Al-Khalili, Im Haus der Weisheit, S. Fischer Verlag 2011.
   Die (von einem theoretischen Physiker) interessant erzählte Geschichte der Rolle der arabischen Wissenschaften im Mittelalter. Der Mathematiker und Astronom Abu Abudullah Muhammad ibn Musa al Khwarizmi (ca. 780-850), einer der bedeutendsten Wissenschaftler des Mittelaltes, wird eingehend gewürdigt. Er schrieb mit Kitab al-Jebr das erste Buch über "Algebra" (diese Bezeichnung leitet sich aus dem Titel ab) und er war (mit-)verantwortlich für die Bekanntmachung der hinduistischen Mathematik (im Buch mit dem lateinischen Titel De numeris indorum: Positionsdarstellung von Zahlen Dezimalsystem und die damit verbindenen Rechenverfahren!) im arabischen Raum und damit (auf dem Weg über das maurische Spanien und mittels lateinischer Übersetzungen seiner Werke) auch in Europa. Interessant für Informatiker: das Wort "Algorithmus" leitet sich aus dem Namen "al-Khwarzimi" (eigentliche eine Herkunftsbezeichnung, latinisiert "algorismi") ab.
   Englicher Originaltitel: Pathfinders: The Golden Age of Arabic Science, Penguin Books 2010.
   
2. Simon Singh Geheime Botschaften. Die Kunst der Verschlüsselung von der Antike bis in die Zeiten des Internet, dtv 2000.
   Eine spannend (ohne mathematisch-technische Vertiefung) geschriebene Geschichte der Kryptographie von einem renommierten populärwissenschaftlichen Autor.
   Englischer Originaltitel: The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography, Anchor Books 2000.
3. Emil A. Fellmann, Leonhard Euler, Birkhäuser 2007.
   Die Lebensgeschichte (1707-1783) des ... by far the most productive mathematician in the history of mankind (so der Klappentext), vom Herausgeber von Eulers Briefwechsel "frei von Formeln" (aber bebildert), also sehr kompetent und gut lesbar. Übrigens: die Herausgabe von Eulers opera omnia ist noch immer nicht abgeschlossen...

27. Juli

Folien zur Primzahlverifikation (PRATT)
Folien zum Primzahltest von MILLER-RABIN
Maple-Beispiele zum Miller-Rabin-Test (mw)
Maple-Beispiele zum Miller-Rabin-Test (pdf)

• Die schriftlich zu bearbeitenden Aufgaben und die Bonusaufgaben 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äudes ("Blaues Hochhaus") einzuwerfen.

• Die Aufgaben können in Teams mit bis zu vier Teilnehmern aus derselben Übungsgruppe bearbeitet werden.

• Diese Teams und ihre Zuordnung zu den Übungsgruppen sollen über das Semester hinweg stabil bleiben.
  Auf dem abgegebenen Blättern ist die Übungsgruppe deutlich zu vermerken.

• Jede Lösung einer schriftliche Aufgabe wird mit bis zu 5 Punkten bewertet. Dabei bedeutet:
  0 = nicht bearbeitet oder völlig daneben
  1 = nur ansatzweise richtig bearbeitet, mehr falsch als richtig
  2 = weitgehend bearbeitet, aber nur teilweise richtig
  3 = weitgehend bearbeitet und überwiegend korrekt
  4 = einwandfreie und komplette Lösung
  5 = besonders originelle (und korrekte) Lösung

0. Aufgabe:
(4. Mai)

Zum Aufwärmen: worm up!

wird in der ersten Übungsstunde behandelt
keine schriftliche Bearbeitung

1. Aufgabe:
(4. Mai)

Fingerübungen zum Rechnen mit Logarithmen

wird in der ersten Übungsstunde behandelt
keine schriftliche Bearbeitung

2. Aufgabe:
(4. Mai)

Laufzeitenvergleiche

wird in der ersten Übungsstunde behandelt
keine schriftliche Bearbeitung

3. Aufgabe:
(11. Mai)

Umgang mit asymptotischer Notation

wird am 16,/17./18. Mai behandelt
keine schriftliche Bearbeitung

4. Aufgabe:
(11. Mai)

Fibonacci-Zahlen, Rekursion und Induktion

schriftlich zu bearbeiten

Abgabe bis 20. Mai, 12 Uhr
im Kasten am Blauen Hochhaus

5. Aufgabe:
(11. Mai)

Eine Variante des Frisbee-Spiels

schriftlich zu bearbeiten

6. Aufgabe:
(18. Mai)

Quickies zum Selbsttest (1)

7. Aufgabe:
(18. Mai)

Eine zweite Folge zur Fibonacci-Rekursion

schriftlich zu bearbeiten

8. Aufgabe:
(18. Mai)

Die Begleitmatrix einer linearen Rekursion

Bonusaufgabe für mathematisch Interessierte (nicht obligatorisch)
schriftliche Lösungen
bis 27. Mai, 10 Uhr
im Kasten am Blauen Hochhaus

9. Aufgabe:
(24. Mai)

Asymptotisches Verhalten von C-rekursiven Folgen

schriftlich zu bearbeiten

10. Aufgabe:
(24. Mai)

Eingeschränkte Kanäle

schriftlich zu bearbeiten

11. Aufgabe:
(24. Mai)

Douglas Hofstadters MIU-System

Bonusaufgabe (nicht obligatorisch)
schriftliche Lösungen
bis 10. Juni, 10 Uhr
im Kasten am Blauen Hochhaus

12. Aufgabe
(8. Juni)

Eine weitere schnelle Transformation

schriftlich zu bearbeiten

13. Aufgabe
(8. Juni)

Eigenschaften der DFT

schriftlich zu bearbeiten

14. Aufgabe
(8. Juni)

Quickies zum Selbsttest (2)

keine schriftliche Bearbeitung, diese Aufgaben werden in den Übungsgruppen behandelt, falls das nachgefragt wird

15. Aufgabe
(16. Juni)

Quickies zum Selbsttest (3)

keine schriftliche Bearbeitung, diese Aufgaben werden in den Übungsgruppen behandelt, falls das nachgefragt wird

16. Aufgabe
(16. Juni)

Devil's staircase

Bonusaufgabe (nicht obligatorisch)
schriftliche Lösungen
bis 24. Juni, 10 Uhr
im Kasten am Blauen Hochhaus

17. Aufgabe
(16. Juni)

Lösung einer inhomogenen (forcierten) Rekursion

schriftlich zu bearbeiten

18. Aufgabe
(17. Juni)

divide-and-conquer-Rekursionen

schriftlich zu bearbeiten

19. Aufgabe
(24. Juni)

divide-and-conquer für ein NP-vollständiges Problem

Bonusaufgabe (nicht obligatorisch)
schriftliche Lösungen
bis 8. Juli, 10 Uhr
im Kasten am Blauen Hochhaus

20. Aufgabe
(24. Juni)

Banale und schnelle Exponentiation im Vergleich

schriftlich zu bearbeiten

21. Aufgabe
(24. Juni)

Charakterisierung der Dyck- und Lukasiewicz-Sprachen

schriftlich zu bearbeiten

22. Aufgabe
(1. Juli)

Quickselect

schriftlich zu bearbeiten

23. Aufgabe
(1. Juli)

Entscheidungsbaum für Merge

schriftlich zu bearbeiten

24. Aufgabe
(1. Juli)

Optimales Matrizenprodukt -- ein Spezialfall

Bonusaufgabe (nicht obligatorisch)
schriftliche Lösungen
bis 15. Juli, 10 Uhr
im Kasten am Blauen Hochhaus

25. Aufgabe
(1. Juli)

Quickies zum Selbsttest (4)

keine schriftliche Bearbeitung, diese Aufgaben werden in den Übungsgruppen behandelt, falls das nachgefragt wird

26. Aufgabe
(8. Juli)

Quickies zum Selbsttest (5)

keine schriftliche Bearbeitung, diese Aufgaben werden in den Übungsgruppen behandelt, falls das nachgefragt wird

27. Aufgabe
(8. Juli)

Entropie der geometrischen Verteilungen

schriftlich zu bearbeiten

Abgabe bis 15. Ju1i, 10 Uhr
im Kasten am Blauen Hochhaus

28. Aufgabe
(8. Juli)

Prinzip der maximalen Entropie

Bonusaufgabe schriftliche Lösungen zu bearbeiten
Abgabe bis 15. Juli, 10 Uhr im Kasten am Blauen Hochhaus

29. Aufgabe
(8. Juli)

Huffman-Codierung

schriftlich zu bearbeiten

Abgabe bis 15. Juli, 10 Uhr im Kasten am Blauen Hochhaus

30. Aufgabe
(13. Juli)

Nochmal Sortieren

Bonusaufgabe schriftliche Lösungen zu bearbeiten
Abgabe bis 22. Juli, 10 Uhr im Kasten am Blauen Hochhaus

31. Aufgabe
(13. Juli)

Quickies zum Selbsttest (6)

werden in den Übungsgruppen behandelt, falls das nachgefragt wird

32. Aufgabe
(13. Juli)

Ausgewählte Quickies (7)

Ergänzungsaufgabe
(siehe einleitenden Text zum Aufgabenblatt)

33. Aufgabe
(13. Juli)

Das Spiel von Euklid

Extra-Aufgabe für Liebhaber
(nicht obligatorisch, keine schriftliche Bearbeitung)

Lösungen
(18. Juli)

Schriftliche Ausarbeitung der Lösungen etlichen Aufgaben
von Ulrich Dorsch und Christoph Rauch kompiliert

HINWEIS:

Auf der enstprechenden Seite vom Sommersemester 2009 finden Sie Links zu ausführlichen schriftlichen Lösungen einiger Aufgaben