LTI
LTI

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 11.01.2020 10-16 Uhr (MI 03.11.018)
    • Samstag 18.01.2020 10-16 Uhr (MI 03.11.018)
    Die erste Veranstaltung findet am Donnerstag, dem 17.10.2019 um 14:15 Uhr im Seminarraum 03.11.018 statt. Dann wird der organisatorische Rahmen besprochen, die Themen verteilt und die Termine der Blockveranstaltung(en) festgelegt.
  • 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

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.

Mögliche Themen

  • Graph Isomorphism Testing
  • Random Walks, Cheeger Inequalities
  • Diameters and eigenvalues
  • Paths, Flows, and Routing
  • Google's PageRank Algorithm
  • Kleinberg's HITS (Hubs and Authorities) Algorithm
  • Graph Partitioning and Clustering, Spectral Image Segmentation
  • Distributions of Eigenvalues and Compression
  • Eigenvalue Computation
  • Eigenvalues and Quasi-Randomness
  • Expanders and explicit constructions
  • Eigenvalues of symmetrical graphs
  • Eigenvalues of subgraphs with boundary conditions
  • Heat kernels
sowie andere ausgewählte Kapitel aus den unten angegebenen Büchern.

Themenverteilung

  • Graph Isomorphism Testing
    Maximilian Prokop
  • Random Walks, Cheeger Inequalities
    Simon Dominick
  • Diameters and eigenvalues
    -
  • Paths, Flows, and Routing
    Adem Rimpapa
  • Google's PageRank Algorithm
    Andreas Kruck
  • Kleinberg's HITS (Hubs and Authorities) Algorithm
    Teodora Dobos
  • Graph Partitioning and Clustering, Spectral Image Segmentation
    Tim Türk
  • Distributions of Eigenvalues and Compression
    Valentin Starlinger
  • Eigenvalue Computation
    Alexander Eichler
  • Eigenvalues and Quasi-Randomness
    Gabriel Guevara Quesada
  • Expanders and explicit constructions
    -
  • Eigenvalues of symmetrical graphs
    Daniel Seidl
  • Eigenvalues of subgraphs with boundary conditions
    -
  • Heat kernels
    -

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: Weitere Quellen:

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).
Lehrstuhl für Algorithmen und Komplexität
Prof. Dr. Susanne Albers

Boltzmannstr. 3
85748 Garching bei München

Tel +89.289.17706
Fax +89.289.17707

E-Mail