Kombinatorische Algorithmen (WS 14/15)
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.
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. Zur Vorbereitung des Gesprächs erarbeiten die Teilnehmer Fragen über das jeweilige Material.
Wir treffen uns jeden Mittwoch um 10:00 Uhr in 48-654, um die für die jeweilige Kalenderwoche anstehenden Themen zu besprechen.
Für die Verwaltung der Übungspunkte und Kontaktaufnahme werden wir OLAT einsetzen. Bitte melden Sie sich dort an. Vergessen Sie bitte nicht, Ihre Matrikelnummer im Profil (via "Einstellungen") im Feld "Institutionsnummer" einzutragen; nur so können wir Ihre Übungsleistung zweifelsfrei der Prüfungsannmeldung zuordnen.
Semesterplan
Für jedes Thema ist eine Quelle als Hauptreferenz (fett gedruckt) 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.
Hier ist für jeden Termin aufgeführt, welches Thema besprochen wird. Bitte bereiten Sie das Material rechtzeitig vor und formulieren spezifische Fragen zu den Punkten, die Ihnen Probleme bereiten.
Weiterhin senden Sie bitte bis spätestens Dienstag um 15:00 Uhr vor jedem Treffen wenigstens drei "Prüfungsfragen" an Raphael – eine für jedes der drei Kompetenzniveaus Reproduktion, Anwendung und Transfer. Diese werden unser Gespräch anregen und eine Basis für die Prüfungsvorbereitung bieten.
| Termin |
Thema |
Referenzen |
| 27.10. |
Einführung |
— |
| 05.11. |
String Matching – Naiv & Knuth-Morris-Pratt |
[Neb12b, 6.1.1,6.1.2], [SW11, Sec5.3 until p769], [SW13, week4.2 lec1–3] |
| 12.11. |
String Matching – Boyer-Moore & Rabin-Karp |
[Neb12b, 6.1.3-6.1.5], [SW11, Sec5.3 p770–], [SW13, week4.2 lec4–5] |
| 19.11. |
String Komprimierung |
|
| 26.11. |
String Komprimierung |
|
| 03.12. |
Network Flows – Augmenting Paths |
[KN12a, Sec9.1–9.5], [SW11, p886–902], [SW13, week3.1], [CLRS09, Sec26.1,26.2] |
| 10.12. |
Network Flows – Push Relabel |
|
| 17.12. |
Assignments & Matchings |
[KN12a, Sec9.10.1,9.10.2], [KN12b, Sec10.1–10.3,10.6], [CLRS09, Sec26.3], [wiki] |
| 07.01. |
Einführung Symbolic Method |
|
| 14.01. |
Random Generation top down |
[FZV94, Sec1–4] |
| 21.01. |
Singularity Analysis, Boltzmann Sampling |
[SF13, Sec5.5], [Neb12a, Sec1.3.1], [DFLS04, Sec1–4], [GKP94, p394–395] |
| 28.01. |
Boltzmann Sampling |
[DFLS04, Sec6] |
| 04.02. |
Random Number Generation |
[Knu01, Sec3.1–3.2.1.3] |
Notizen & Fragen
Übungen
Zur zusätzlichen Vertiefung werden regelmäßig Übungsaufgaben in Kleingruppen abgegeben. Auch die Inhalte aus den Übungen sind Teil des Prüfungsstoffes.
Um die mündliche Prüfung antreten zu können, müssen mindestens 40% der Übungspunkte erreicht werden. Die Aufgaben werden in einer wöchentlichen Veranstaltung besprochen; diese findet montags um 17:15 in 48-654 statt.
Ü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 Raphael Reitzig 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 WS 14/15 von Raphael Reitzig betreut.