AG Algorithmen und Komplexität
>

Kombinatorische Algorithmen (SS 13)

Aktuelles

  • Es gibt zwei neu konvertierte PDFs im Literaturverzeichnis, diese sollten jetzt mit jedem Viewer benutzbar sein.
  • Aufgabe 10 (Blatt 6) wurde modifiziert; in der ursprünglichen Fassung gab es Probleme.
  • Die Termine der Woche vom 27.05 bis 02.06. fallen aus, d.h. es findet am 28.05. keine Fragestunde und am 29.05. keine Übung statt. Die Termine werden in der darauffolgenden Woche nachgeholt.
  • Die Referenzliteratur zum zweiten Teil des String Matchings umfasst die drei Abschnitte 6.1.3, 6.1.4 und 6.1.5 aus [Neb12]; die alte Angabe (6.1.3,6.1.5) war diesbezüglich missverständlich.
  • Der erste Übungstermin findet trotz Feiertag zum üblichen Termin, also 1. Mai, 11:45 Uhr statt. Wir treffen uns kurz vorher am Eingang zu Gebäude 48 in der Unterführung (da die Türen abgeschlossen sein werden.)
  • Der erste Übungstermin fällt auf den 1. Mai; wir werden einen Ausweichtermin in der nächsten Vorlesungsstunde suchen.

Inhalte

Diskrete Strukturen (wie z.B. Wörter, Bäume und Graphen) werden oft verwendet, um Probleme aus der Praxis zu modellieren. Für viele Probleme kann man dann eine Lösung auf Basis einiger weniger Standardalgorithmen auf diesen Strukturen gewinnen. In der Vorlesung Kombinatorische Algorithmen stellen wir einen Baukasten solcher Verfahren zusammen:

  • effizientes String Matching (Finden von Wörtern in Texten)
  • Komprimierungsverfahren
  • Algorithmen auf Graphen im Kontext von
    • Matchings und
    • Flussproblemen
  • Zufällige Erzeugung von kombinatorischen Strukturen

Die zufällige Erzeugung von Strukturen hat dabei nicht nur direkte Anwendungen in der Bioinformatik, sondern dient auch der Datenbeschaffung für experimentelle Studien, z.B. um die Effizienz von Algorithmen zu ermitteln oder Eigenschaften gewisser Klassen kombinatorischer Strukturen zu untersuchen.

Kombinatorische Algorithmen ist eine 4 ECTS-Veranstaltung; weitere Informationen finden Sie im Modulhandbuch des Fachbereichs.

Alice explaining the use of random phrase generators in project reports.

Random string generation as seen in practice.

Organisatorisches

Die Vorlesung wir im Stile des flip teaching organisiert, d. h. es wird zu jedem Thema (Original-) Literatur und/oder Lehrbücher geben, die eigenständig erarbeitet werden. Die “Vorlesungs”-Termine dienen dann zur Klärung von Fragen und der Diskussion über den Stoff und finden jeweils Dienstags, 10:00 - 11:30 Uhr im Seminarraum der AG (48-654) statt.

Für jedes Thema ist eine Quelle als Hauptreferenz angegeben; diese definiert den prüfungsrelevanten Umfang. Weitere Referenzen dienen der Beleuchtung zusätzlicher Aspekte oder präsentieren die Thematik aus einem anderen Blickwinkel um das Verständnis zu erleichtern.

Semesterplan

Hier ist für jeden Termin aufgeführt, welches Thema besprochen wird. Die jeweilige Hauptreferenz ist fett gedruckt.

Termin

Thema

Referenzen
16.04.

Einführung

—
23.04.

String Matching – Naiv & Knuth-Morris-Pratt

[Neb12b, 6.1.1,6.1.2], [SW11, Sec5.3 until p769], [SW13, week4.2 lec1–3]
30.04.

String Matching – Boyer-Moore & Rabin-Karp

[Neb12b, 6.1.3-6.1.5], [SW11, Sec5.3 p770–], [SW13, week4.2 lec4–5]
07.05.

String Komprimierung

[LZ76], [ZL78, Thm1+2 incl proofs], [SM09, Ch6]
14.05.

String Komprimierung

[SW11, Sec5.5,page 839–], [SW13, week5.2 lec4], [SM09, Ch6]
21.05.

Network Flows – Augmenting Paths

[KN12a, Sec9.1–9.5], [SW11, p886–902], [SW13, week3.1], [CLRS09, Sec26.1,26.2]
(28.05.)

Network Flows – Push Relabel

[KN12a, Sec9.7], [CLRS09, Sec26.4]
04.06.

Network Flows – Push Relabel

[KN12a, Sec9.7], [CLRS09, Sec26.4]
11.06.

Assignments & Matchings

 [KN12a, Sec9.10.1,9.10.2], [KN12b, Sec10.1–10.3,10.6], [CLRS09, Sec26.3], [wiki]
18.06.

Einführung Symbolic Method

[SF13, Sec5.1–5.3,5.4], [Sed13, week 5 lec1,2]
25.06.

Random Generation top down

[FZV94, Sec1–4]
02.07.

Singularity Analysis, Boltzmann Sampling

[SF13, Sec5.5], [Neb12a, Sec1.3.1], [DFLS04, Sec1–4], [GKP94, p394–395]
09.07.

Boltzmann Sampling

[DFLS04, Sec6]
16.07.

Random Number Generation

[Knu01, Sec3.1–3.2.1.3]

Übungen

Zur zusätzlichen Vertiefung werden regelmäßig Übungsaufgaben in Kleingruppen abgegeben. Die Lösungen besprechen wir in der Übung jeweils Mittwochs, 11:45 Uhr im Seminarraum der AG (48-654). Auch die Inhalte aus den Übungen sind Teil des Prüfungsstoffes.

Um die mündliche Prüfung antreten zu könenn, müssen mindestens 40% der Übungspunkte erreicht werden.

Übungsblätter











Literatur

Die wichigsten Quellen bekommen Sie in unserer Literatursammlung zur Vorlesung.
Aus rechtlichen Gründen müssen sich vorher hier mit dem Vorlesungspasswort anmelden, das Sie bei Sebastian Wild erfragen können.

[CLRS09]Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.

[DFLS04]Philippe Duchon, Philippe Flajolet, Guy Louchard, and Gilles Schaeffer. Boltzmann Samplers for the Random Generation of Combinatorial Structures. Combinatorics, Probability and Computing, 13(4-5):577–625, July 2004. doi: 10.1017/S0963548304006315.

[Eve65] Shimon Even. On Information Lossless Automata of Finite Order. Electronic Computers, IEEE Transactions on, EC-14(4):561–569, 1965. doi: 10.1109/PGEC.1965.263996.

[FPS11] Philippe Flajolet, Maryse Pelletier, and Michèle Soria. On Buffon machines and numbers. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’11, pages 172–183. SIAM, January 2011.

[FZV94] Philippe Flajolet, Paul Zimmerman, and Bernard Van Cutsem. A calculus for the random generation of labelled combinatorial structures. Theoretical Computer Science, 132(1-2):1–35, September 1994. doi:10.1016/ 0304-3975(94)90226-7.

[GKP94] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Discrete Probability. In Concrete mathematics: a foundation for computer science, chapter 8. Addison-Wesley, 2nd edition, 1994.

[KN12a] Sven Oliver Krumke and Hartmut Noltemeier. Flüsse und Strömungen. In Graphentheoretische Konzepte und Algorithmen, chapter 9, pages 195–272. Vieweg & Teubner Verlag, Wiesbaden, 2012. URL: http://link.springer.com/chapter/10.1007/978-3-8348-2264-2\_9.

[KN12b] Sven Oliver Krumke and Hartmut Noltemeier. Matchings. In Graphentheoretische Konzepte und Algorithmen, chapter 10, pages 273–300. Vieweg & Teubner Verlag, Wiesbaden, 2012. URL: http://link.springer.com/chapter/10.1007/978-3-8348-2264-2\_10.

[Knu01] Donald Ervin Knuth. The Art Of Computer Programming: Seminumerical Algorithms, volume 2. Addison-Wesley, 3rd edition, 2001.

[Knu11] Donald Ervin Knuth. The Art Of Computer Programming: Combinatorial Algorithms, Part1. Addison-Wesley, 1st edition, 2011.

[Lie98] Jens Liebehenschel. Ranking and unranking of lexicographically ordered words: an average-case analysis. Journal of Automata, Languages and Combinatorics, 2(4):227–268, July 1998.

[LZ76] Abraham Lempel and Jacob Ziv. On the Complexity of Finite Sequences. Information Theory, IEEE Transactions on, 22(1):75–81, 1976. doi:10. 1109/TIT.1976.1055501.

[MM01] Conrado Martínez and Xavier Molinero. A generic approach for the unranking of labeled combinatorial classes. Random Structures and Algorithms, 19(3-4):472–497, October 2001. doi:10.1002/rsa.10025.

[MM05] Conrado Martínez and Xavier Molinero. Efficient iteration in admissible combinatorial classes. Theoretical Computer Science, 346(2-3):388–417, November 2005. doi:10.1016/j.tcs.2005.08.028.

[Neb12a] Markus E. Nebel. Einleitung. In Entwurf und Analyse von Algorithmen, chapter 1, pages 1–39. Vieweg & Teubner Verlag, Wiesbaden, 2012. URL: http://link.springer.com/chapter/10.1007/978-3-8348-2339-7\_1.

[Neb12b] Markus E. Nebel. String-Algorithmen. In Entwurf und Analyse von Algorithmen, chapter 6, pages 245–286. Vieweg & Teubner Verlag, Wiesbaden, 2012. URL: http://link.springer.com/chapter/10.1007/978-3-8348-2339-7\_6.

[Pon08] Yann Ponty. Efficient sampling of RNA secondary structures from the Boltzmann ensemble of low-energy: the boustrophedon method. Journal of mathematical biology, 56(1-2):107–27, January 2008. doi:10.1007/ s00285-007-0137-z.

[Sed13] Robert Sedgewick. Analytic Combinatorics, Part I, 2013. URL: http://class.coursera.org/introACpartI-001.

[SF13] Robert Sedgewick and Philippe Flajolet. An Introduction to the Analysis of Algorithms. Addison-Wesley Professional, 2nd edition, 2013.

[SM09] David Salomon and Giovanni Motta. Handbook of Data Compression. Springer, 5th edition, 2009.

[SW11] Robert Sedgewick and Kevin Wayne. Algorithms. Addison-Wesley, March 2011.

[SW13] Robert Sedgewick and Kevin Wayne. Algorithms, Part II, 2013. URL: http://class.coursera.org/algs4partII-001.

[Wel84] T.A. Welch. A technique for high-performance data compression. Computer, 17(6):8–19, 1984. doi:10.1109/MC.1984.1659158.

[ZL77] Jacob Ziv and Abraham Lempel. A universal algorithm for sequential data compression. Information Theory, IEEE Transactions on, 23(3):337–343, 1977. doi:10.1109/TIT.1977.1055714.

[ZL78] Jacob Ziv and Abraham Lempel. Compression of individual sequences via variable-rate coding. Information Theory, IEEE Transactions on, 24(5):530–536, 1978. doi:10.1109/TIT.1978.1055934.

Die Übung zur Vorlesung wird im SS13 von Sebastian Wild betreut.