Proseminar, Wintersemester 2018/19
News
- 09.07.2018: Wir sind online!
Termine
| 10.10.2018, 14:00 | Einführungsveranstaltung Seminarraum 5053.a (Informatikzentrum, Foyer E2, Erdgeschoss gegenüber AH 5) | ||||||||
|
Einführung in die Literaturrecherche (Bibliothek) | ||||||||
| 02.11.2018 | Letzte Rücktrittsmöglichkeit | ||||||||
| 12.11.2018 | Vorlage der detaillierten Inhaltsübersicht | ||||||||
| 10.12.2018 | Vollständige Fassung der Ausarbeitung | ||||||||
| 14.01.2018 | Vollständige Fassung der Folien | ||||||||
| 31.01./01.02.2019 | Blockseminar Seminarraum Inf. 2 (Raum 4201b) |
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 | Donnerstag | Freitag |
|---|---|---|
| 09:00-10:20 | 18 (Bursch), 20 (Spies), 1 (Appenzeller), 2 (Gashi) | 18 (Mensendiek), 20 (Jansen), 1 (Kocher), 2 (He) |
| 10:45-11:45 | 3 (Alt), 5 (Piel), 10 (Criste) | 3 (Meyer), 5 (Manthey), 14 (Kräll) |
| 14:00-15:00 | 4 (Schoolmann), 9 (Dolif), 11 (Hugenroth) | 4 (Schulte), 9 (Gose), 11 (Gehnen) |
Themen
| Nr. | Thema | Referent/in | Betreuer/in |
|---|---|---|---|
| Algorithmen | |||
| 1 | PageRank-Algorithmus | Matthias Appenzeller, Nick Kocher | Christian Hensel/Thomas Noll |
| 2 | Huffman-Kodierung | Labrik Gashi, Qingyun He | Jip Spel |
| 3 | LZW-Datenkompression | Lukas Alt, Felix Meyer | Benjamin Kaminski |
| 4 | RSA-Kryptosystem | Bernd Schoolmann, Niklas Schulte | Philipp Berger |
| 5 | Längste gemeinsame Teilsequenz | Georg Manthey, Patrick Konrad Piel | Benjamin Kaminski |
| 6 | Deutsch-Schorr-Waite Baumtraversierung | – | – |
| 7 | Problem der K kürzesten Pfade | – | – |
| 8 | Amortisierte Laufzeitanalyse | – | – |
| 9 | String Matching | Philipp Dolif, Moritz Gose | Thomas Noll |
| 10 | Lineare Optimierung | Silviu-Eric Criste | Christian Hensel/Thomas Noll |
| 11 | A*-Suchalgorithmus | Christina Gehnen, Philipp Hugenroth | Philipp Berger |
| Datenstrukturen | |||
| 12 | Splay-Bäume | – | – |
| 13 | Fibonacci-Heaps | – | – |
| 14 | AVL-Bäume | Sebastian Kräll | Thomas Noll |
| 15 | B-Bäume | – | – |
| 16 | Bitstate Hashing | – | – |
| 17 | Binäre Entscheidungsdiagramme | – | – |
| 18 | Spielbäume | Tom Torsten Bursch, Constantin Mensendiek | Sebastian Junges |
| 19 | Rot-Schwarz-Bäume | – | – |
| 20 | Bayessche Netze | Niklas Jansen, Achim Spies | Sebastian Junges |
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 31.7: RSA Crypto System.
- Terry Welch: A Technique for High-Performance Data Compression. IEEE Computer, 1984, 8-19.
- CLRS, Section 16.3: Huffman Codes.
- 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.
- 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.
- CLRS, Chapter 13: Red-Black Trees.
- 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
Kontakt
Thomas Noll <noll at cs.rwth-aachen.de>