Proseminar, Wintersemester 2020/21
News
- 10.06.2020: Wir sind online!
Einführung und Themenvergabe
Termine
| 30.10.2020 | Frist für Themenauswahl |
| 23.11.2020 | Letzte Rücktrittsmöglichkeit |
| 30.11.2020 | Vorlage der detaillierten Inhaltsübersicht |
| 11.01.2021 | Vollständige Fassung der Ausarbeitung |
| 01.02.2021 | Vollständige Fassung der Folien |
| 10./11.02.2021 | Blockseminar |
Beachten Sie bitte, dass die vollständigen Fassungen von Ausarbeitung und Vortragsfolien Ihre finale Einreichung darstellen und sich von der endgültigen Version nur durch kleinere Anpassungen unterscheiden sollen, die nach Rücksprache mit Betreuerin bzw. Betreuer erfolgen. Es ist aber möglich (und dringend empfohlen!), vor den jeweiligen Fristen Entwurfsversionen Ihrer Dokumente 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.
Zeitplan
| Zeit | Mittwoch, 10. Februar | Donnerstag, 11. Februar |
| 09:00-10:00 | Selin Ata, Felix Middeldorf, Youssef Kharita | Henrik Sören Hützen, Martin Schymiczek, Maximilian Hense |
| 10:30-11:10/11:30 | Alexander Wiegel, Ping Wan, Stanislav Mironenko | Mohamed Alyousef, Anastasiia Petrova |
Themen
| Nr. | Thema | Referent/in | Betreuer/in |
|---|---|---|---|
| Algorithmen | |||
| 1 | PageRank-Algorithmus | Selin Ata, Henrik Sören Hützen | Jip Spel |
| 2 | Huffman-Kodierung | Felix Middeldorf | Jana Berger |
| 3 | LZW-Datenkompression | – | – |
| 4 | RSA-Kryptosystem | Mohamed Alyousef, Alexander Wiegel | Thomas Noll |
| 5 | Längste gemeinsame Teilsequenz | Youssef Kharita, Martin Schymiczek | Jana Berger |
| 6 | Deutsch-Schorr-Waite Baumtraversierung | – | – |
| 7 | Problem der K kürzesten Pfade | – | – |
| 8 | Amortisierte Laufzeitanalyse | – | – |
| 9 | String Matching | – | – |
| 10 | Lineare Programmierung | Maximilian Hense | Thomas Noll |
| 11 | A*-Suchalgorithmus | Ping Wan | Tim Quatmann |
| 12 | Randomisierte Algorithmen | Stanislav Mironenko, Anastasiia Petrova | Ira Fesefeldt |
| Datenstrukturen | |||
| 13 | Splay-Bäume | – | – |
| 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, Third Edition. MIT Press and McGraw-Hill, 2009]- Gopal Pandurangan, Prabhakar Raghavan, and Eli Upfal: Using PageRank to characterize web structure. Internet Math. Volume 3, Number 1 (2006), 1-20.
- 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.
- 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.
- D.D. Sleator and R.E. Tarjan: Self-Adjusting Binary Search Trees. Journal of the ACM 32:3, 652-686, 1985.
- 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>