Wintersemester 2026/27
News
- 03.06.2026: Wir sind online!
Einführung und Themenvergabe
- Folien zur Einführung
Termine
| TBA | Einführungsveranstaltung (Raum 9U10) |
| TBA | Frist für Themenauswahl |
| TBA | Letzte Rücktrittsmöglichkeit |
| TBA | Vorlage der detaillierten Vortragsstruktur |
| TBA | Vollständige Fassung der Folien |
| TBA | Blockseminar (Raum 9U10) |
| TBA | Einreichung der Ausarbeitung |
Beachten Sie, dass die vollständige Fassung der Vortragsfolien Ihre zu bewertende Einreichung darstellt und sich von der endgültigen Version nur durch kleinere Anpassungen unterscheiden sollte, die nach Rücksprache mit der betreuenden Person erfolgen. Es ist aber möglich (und dringend empfohlen!), vor den jeweiligen Fristen Entwurfsversionen Ihrer Ergebnisse einzureichen.
Themen
Dieses Proseminar bietet eine Weiterführung und Vertiefung diverser Themen, die im Rahmen der Vorlesung Datenstrukturen und Algorithmen behandelt werden. Die folgende Tabelle gibt einen vollständigen Überblick. Alle Themen sollen jeweils in Zweiergruppen bearbeitet werden.
Nr. | Thema | Referent/in | Betreuer/in |
|---|---|---|---|
| Algorithmen | |||
| 1 | PageRank-Algorithmus | – | – |
| 2 | Huffman-Kodierung | – | – |
| 3 | LZW-Datenkompression | – | – |
| 4 | RSA-Kryptosystem | – | – |
| 5 | Längste gemeinsame Teilsequenz | – | – |
| 6 | Kürzeste gemeinsame Obersequenz | – | – |
| 7 | Deutsch-Schorr-Waite Baumtraversierung | – | – |
| 8 | Problem der K kürzesten Pfade | – | – |
| 9 | Amortisierte Laufzeitanalyse | – | – |
| 10 | String Matching | – | – |
| 11 | Lineare Programmierung | – | – |
| 12 | A*-Suchalgorithmus | – | – |
| 13 | Randomisierte Algorithmen | – | – |
| Datenstrukturen | |||
| 14 | Fibonacci-Heaps | – | – |
| 15 | AVL-Bäume | – | – |
| 16 | B-Bäume | – | – |
| 17 | Bitstate Hashing | – | – |
| 18 | Binäre Entscheidungsdiagramme | – | – |
| 19 | Spielbäume | – | – |
| 20 | Bayessche Netze | – | – |
Literatur
[CLRS = Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms, 4th edition. MIT Press and McGraw-Hill, 2013]
- Fan Chung: A Brief Survey of PageRank Algorithms. IEEE Transactions on Network Science and Engineering 1(1), 2014.
- CLRS, Section 16.3: Huffman Codes.
- Terry Welch: A Technique for High-Performance Data Compression. IEEE Computer, 1984, 8-19.
- CLRS, Section 31.7: RSA Crypto System.
- CLRS, Section 15.4: Longest Common Subsequence.
- Jonathan S. Turner: Approximation algorithms for the shortest common superstring problem. Information and Computation 83 (1), 1989, 1-20.
- H. Schorr and W. M. Waite: An efficient machine-independent procedure for garbage collection in various list structures. Commun. ACM 10(8), 1967, 501-506.
- Victor M. Jimenez and Andres Marzal: Computing the K Shortest Paths: A New Algorithm and an Experimental Comparison. WAE, LNCS 1668, 1999, 15-29.
- CLRS, Chapter 17: Amortized Analysis.
- CLRS, Chapter 32: String Matching.
- CLRS, Chapter 29: Linear Programming.
- Stuart Russell and Peter Norvig: Artificial Intelligence: A Modern Approach. 3rd Edition, Prentice Hall, 2009. Section 3.5.2.: A* Search.
- Howard Barringer: Randomized algorithms – a brief introduction. Lecture notes.
- CLRS, Chapter 19: Fibonacci Heaps.
- Donald Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching. Second Edition. Addison-Wesley, 1998, Section 6.2.3: Balanced Trees.
- CLRS, Chapter 18: B-Trees.
- Matthias Kuntz and Kai Lampka: Probabilistic Methods in State Space Analysis. Validation of Stochastic Systems, LNCS 2925, 2004, 251-266.
- Randal E. Bryant: Graph-Based Algorithms for Boolean Function Manipulation. IEEE Trans. Computers, Vol. C-35, No. 8, 1986, 677-691.
- George T. Heineman, Gary Pollice, and Stanley Selkow: Algorithms in a Nutshell. Oreilly Media, 2008, Chapter 7: Path Finding in AI, 217-223.
- Eugene Charniak: Bayesian Networks without Tears, AI Magazine 12(4), 1991, 50-63.
Anmeldung
Die Anmeldung erfolgt über eine zentrale Fachgruppenseite. Nachträgliche Anmeldungen sind nicht möglich.
Weitere Informationen
- Muster zur Ausarbeitung
- Muster zu den Vortragsfolien
- How to Write a Seminar Paper
- How to give presentations
- Ethische Richtlinien für das Verfassen wissenschaftlicher Arbeiten
- Introduction to LaTeX
Kontakt
Thomas Noll <noll at cs.rwth-aachen.de>