LEA

  • Leitung:
    Tobias Lieber
    Falls Sie Interesse haben an dem Hauptseminar teilzunehmen, schreiben Sie eine Email, deren Betreff das Wort Hauptseminar beeinhaltet, an lieber@in.tum.de oder kommen Sie einfach bei mir im Büro vorbei.
  • Bereich:
    2 SWS Hauptseminar im Bereich Informatik III (Theoretische Informatik)
  • Zeit und Ort:
    TBA
  • Schein:
    Einen Seminarschein erhält, wer einen Vortrag gehalten und regelmäßig am Seminar teilgenommen hat.
  • Hörerkreis:
    Studierende im Hauptstudium der Informatik
    Studierende des Master Informatik
    Studierende des Bachelor der Informatik ab dem 4. Semester
    Studierende mit Nebenfach Informatik
  • Voraussetzungen:
    Voraussetzung für die Teilnahme am Hauptseminar sind neben Interesse an Algorithmen, Komplexität und mathematischen Fragestellungen auch Englischkenntnisse, die ausreichend für die Bearbeitung der ausschließlich englischsprachigen Literatur sein müssen.
  • Eine vorläufige Themenliste:
    1. Einführung: Definition, Existenz, Kriterien
    2. Verschiedene Konstruktionen: schwach explizite und sehr explizite
    3. Einführung Extraktoren, Kondensatoren und Konstruktion von Expandergraphen aus Extraktoren
    4. Pseudo Zufallszahlen Generatoren, Extraktoren und die Zusammenhänge
    5. Error Correcting Codes und Expander
    6. Anwendung: Das Zig-Zag-Produkt und USTCON auf Expandergraphen
    7. Anwendung: Logarithmische Sortiernetzwerke
    8. Eine Alternative zum Zig-Zag-Produkt: Derandomisiertes Quadrieren von Graphen
  • Literatur:
    Die Vortragsthemen basieren zu einem großen Teil auf dem Buch
    • Expander Graphs and their Applications
      von Shlomo Hoory, Nathan Linial und Avi Wigderson :
      Bull. Amer. Math Soc., 43, pp 439--561, 2006
      • PDF, Seite von Avi Wigderson.
    Die Literatur ist aber nicht nur auf das angegebene Buch beschränkt. Weitere Literaturhinweise erhalten sie von Ihrem Betreuer, wenn Ihr Thema feststeht.
  • Ablauf der Vorbereitung:

    Der Vortrag und die Ausarbeitung müssen mit dem Betreuer abgesprochen werden. Hierzu sind nachfolgende Terminvorgaben bindend (soweit nicht anders mit dem Betreuer abgestimmt). Werden die Termine nicht eingehalten, führt dies zur Streichung des Vortrags und zum Nichtbestehen des Seminars:
    bis 5 Wochen vor dem Vortrag erstes Treffen mit dem Betreuer (vor dem Treffen ist die Literatur bereits zu lesen); der genaue Termin ist bei den Vortragsterminen angegeben;
    bis 3 Wochen vor dem Vortrag Gliederung des Vortrags und der Ausarbeitung mit dem Betreuer besprechen;
    bis 1 Woche vor dem Vortrag Probevortrag vor den Betreuer; fertige Folien und vollständige erste Version der Ausarbeitung mit dem Betreuer abstimmen;
    bis 2 Wochen nach dem Vortrag fertige Ausarbeitung abgeben.
  • Hinweise zur Anfertigung einer Seminararbeit:
    • Alle Ausarbeitungen sollen vorzugsweise mit dem Textsatzsystem LaTeX erstellt werden. Hierzu sind folgende Richtlinien zu beachten:
    • Der folgende Rahmen ist zu verwenden (seminararbeit.tex). Dabei dürfen die Seitengröße und der Font nicht verändert werden.
    • Ein Beispiel kann in der Datei example.tex gefunden werden (das Bild example.eps wird eingebunden)
    • Die Ausarbeitung soll auf die verwendete Literatur verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib).
    • Bei Fragen zu LaTeX sei einerseits auf die folgenden Links hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden:
    • Eine TeX-Implementation unter Windows finden Sie hier.
  • Hinweise zur Gestaltung der Vorträge:
    Wer seine Folien mit LaTeX erstellen möchte findet hier einige Hinweise (einschließlich Rahmen-Datei als Vorlage).