Das Ziel eines Seminars ist einerseits die vertiefte inhaltliche Auseinandersetzung mit einem Thema, andererseits dient ein Seminar aber auch dazu, die Fähigkeiten im Ausarbeiten und Halten von Vorträgen zu verbessern. Dazu gehören aus aktuellem Anlass auch die Grundlagen wissenschaftlichen Arbeitens, beispielsweise das korrekte Zitieren.
Seminar: Spektrale Graphentheorie und ihre Anwendungen
- Leitung:
PD Dr. Hanjo Täubig - Modul: IN0014, IN2107
- Bereich:
2 SWS Seminar im Bereich Informatik III (Theoretische Informatik)
- Anmeldung:
Die Anmeldung erfolgt über das Matching Tool. - Zeit:
Das Seminar wird als Blockveranstaltung abgehalten:- Samstag 12.01.2019 10-16 Uhr (MI 03.11.018)
- Samstag 26.01.2019 10-16 Uhr (MI 03.11.018)
- Schein:
Einen Seminarschein erhält, wer einen Vortrag gehalten, eine Ausarbeitung geschrieben und regelmäßig aktiv am Seminar teilgenommen hat. - Hörerkreis:
Studierende im Bachelorstudiengang Informatik
Studierende im Masterstudiengang Informatik
- Voraussetzungen:
Voraussetzung für die Teilnahme am Seminar sind neben Interesse an Algorithmen, auch Englischkenntnisse, die ausreichend für die Bearbeitung der überwiegend englischsprachigen Literatur sein müssen.
Zusammenfassung
Mögliche Themen
- Graph Isomorphism Testing
- Random Walks, Cheeger Inequalities
- Google's PageRank Algorithm
- Kleinberg's HITS (Hubs and Authorities) Algorithm
- Paths, Flows, and Routing
- Graph Partitioning and Clustering, Spectral Image Segmentation
- Distributions of Eigenvalues and Compression
- Eigenvalue Computation
- Eigenvalues and Quasi-Randomness
Themenverteilung
- Graph Isomorphism Testing
Ajvi Meçe - Random Walks, Cheeger Inequalities
Xaver Höllinger - Google's PageRank Algorithm
Subhan-Jamal Sohail - Kleinberg's HITS (Hubs and Authorities) Algorithm
Klaus Weidinger - Paths, Flows, and Routing
Stefan Wege - Graph Partitioning and Clustering, Spectral Image Segmentation
Florian Gyrock - Distributions of Eigenvalues and Compression
Sanel Dilji - Eigenvalue Computation
Konstantin Pervunin - Eigenvalues and Quasi-Randomness
Maximilian Vollath
Literatur
Es wird erwartet, dass alle Teilnehmer/-innen eigenständig geeignete Literatur (Bücher, Journal-Artikel, Konferenzbeiträge, Manuskripte / Technische Berichte, Vorlesungsunterlagen, etc.) recherchieren. Folgende Bücher könnten dabei z.B. als Grundlage dienen:- Z. Stanić: Inequalities for Graph Eigenvalues,
- D. Stevanović: Spectral Radius of Graphs,
- U. Brandes, Th. Erlebach (Eds.): Network Analysis - Methodological Foundations,
- R. A. Brualdi, S. Friedland, V. Klee (Eds.): Combinatorial and Graph-Theoretical Problems in Linear Algebra,
- R. A. Brualdi, D. Cvetković: A Combinatorial Approach to Matrix Theory and Its Applications,
- Fan R. K. Chung: Spectral Graph Theory (revised chapters),
- H. Täubig: Matrix Inequalities for Iterative Systems,
- Spectral Graph Theory and its Applications (Daniel A. Spielman, Yale University)
- Lectures on Spectral Graph Theory (Fan R. K. Chung, University of Pennsylvania, Philadelphia)
- A brief introduction to Spectral Graph Theory (Bogdan Nica, McGill University, Montreal, Canada)
- Introduction to Spectral Graph Theory and Graph Clustering (Chengming Jiang, University of California, Davis)
Hinweise
- Vorbereitung
- Jeder Studierende wählt ein Thema, sucht sich relevante Literatur und verschafft sich einen Überblick über das Thema. Anschließend wird der Entwurf der Präsentation erstellt, dies beinhaltet beispielsweise das Erstellen der Folien und die Planung des Tafelbilds.
- Vorbesprechung
- Spätestens zwei Wochen vor dem Vortragstermin wird der Entwurf des Vortrags mit dem Betreuer besprochen. Dazu vereinbart jeder Studierende rechtzeitig einen Termin. Zu diesem Zeitpunkt muss auch mindestens die Gliederung der Ausarbeitung vorliegen.
- Seminarvortrag
- Der Seminarvortrag soll ca. 60(±5) Minuten dauern. Vortrag und Folien können auf deutsch oder englisch gehalten bzw. verfasst werden. Nach dem Vortrag hat das Publikum die Möglichkeit, Fragen zu stellen. Eine LaTeX-Vorlage für die Präsentation findet sich in diesem Ordner. Eine Powerpoint-Vorlage kann man auf der Seite vom TUM Corporate Design herunterladen (Login mit MyTUM-Kennung). Diese Vorlagen müssen nicht verwendet werden oder können bei Bedarf auch angepasst werden.
- Seminararbeit
- Die Seminararbeit ist mit Hilfe von LaTeX zu erstellen. Die Endfassung der Seminarbeit ist als PDF-Datei abzugeben. (Das PDF File kann z.B. mit pdflatex erstellt werden.) Der Umfang der Seminararbeit beträgt 10 ± 2 Seiten (ohne Abbildungen, Inhalts- und Literaturverzeichnis).
- Anwesenheit
- Jeder Studierende muss bei allen Vorträgen anwesend sein und sich aktiv an der Diskussion beteiligen.
Gute Vorträge
Hinweise zum Vorbereiten und Halten guter Präsentationen:
- Hilfreiche Hinweise zur Vorbereitung, zum Erstellen der Folien und zum eigentlichen Vortrag geben Garr Reynolds' presentation tips.
- Einige sehr wichtige Aspekte guter Vorträge sind auch im Beamer User Guide in Kapitel I.5
Guidelines for Creating Presentations
beschrieben. - Die Fokussierung auf eine wichtige Nachricht wird in der kurzen Präsentation Rethinking Presentation Design betont.
- Bei einigen Themen bietet es sich möglicherweise an, den Algorithmus in einer kurzen Live-Demonstration vorzuführen (z.B. per Java-Applet).