Sommersemester 2024
News
- 04.12.2023: Wir sind online!
Einführung und Themenvergabe
Termine
| Mo, 15.04.2024, 14:30 | Einführungsveranstaltung (Raum 9U10) |
| Fr, 19.04.2024 | Frist für Themenauswahl |
| Fr, 10.05.2024 | Letzte Rücktrittsmöglichkeit |
| Mo, 13.05.2024 | Vorlage der detaillierten Vortragsstruktur |
| Mo 10.06.2024 | Vollständige Fassung der Folien |
| Mo/Di/Mi 08./09./10.07.2024 (?) | Blockseminar |
| Mo 22.07.2024 | 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.
Inhalt
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.
Themen
Alle Themen sollen jeweils in Zweiergruppen bearbeitet werden.
| Nr. | Thema | Referent/in | Betreuer/in |
|---|---|---|---|
| Algorithmen | |||
| 1 | PageRank-Algorithmus | – | – |
| 2 | Huffman-Kodierung | Carlotta Lucia Schwanenberg, Schalli Shally | Alexander Bork |
| 3 | LZW-Datenkompression | Julian Yassin Sehbaoui, Aleksandr Stadnitskii | Ira Fesefeldt |
| 4 | RSA-Kryptosystem | Paul Blumberg, Erik Nisamutdinoff | Lutz Klinkenberg |
| 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 | Yunus Gürbüz, Aleksandr Kachalov | Lena Verscht |
| 10 | String Matching | – | – |
| 11 | Lineare Programmierung | Dinh Hoang, Leon Paschke | Emma Ahrens |
| 12 | A*-Suchalgorithmus | Sercan Sahin, Jakob Senger | Alexander Bork |
| 13 | Randomisierte Algorithmen | Maxim Klöcker, Monika Krasteva | Emma Ahrens |
| Datenstrukturen | |||
| 14 | Fibonacci-Heaps | Paul Hermes, Jakob Kunz | Ira Fesefeldt |
| 15 | AVL-Bäume | Harun Düzel, Sami Zouhri | Lena Verscht |
| 16 | B-Bäume | Philipp Niklas Döbler, Shohrukhbek Yakhyoev | Ira Fesefeldt |
| 17 | Bitstate Hashing | – | – |
| 18 | Binäre Entscheidungsdiagramme | – | – |
| 19 | Spielbäume | Quentin Brandherm, Thorge Rieks | Ira Fesefeldt |
| 20 | Bayessche Netze | Heinrich Betzold, Deha Ortasarı | Lutz Klinkenberg |
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>