LTI
LTI

Proseminar: Proofs from THE BOOK

  • Leitung:
    PD Dr. Hanjo Täubig
  • Modul: IN0013,
  • Bereich:
    2 SWS Proseminar im Bereich Informatik III (Theoretische Informatik)
  • Anmeldung:
    Die Anmeldung erfolgt über das Matching Tool.
  • Zeit:
    Das Proseminar wird als Blockveranstaltung in 2 Blöcken abgehalten:
    • Samstag 24.06.2017 10-16 Uhr (MI 03.11.018)
    • Samstag 15.07.2017 10-16 Uhr (MI 03.11.018)
    Die erste Veranstaltung findet am Donnerstag, dem 27.04.2017 um 14:15 Uhr im Seminarraum 03.11.018 statt. Dann wird der organisatorische Rahmen besprochen, die Themen verteilt und die Termine der beiden Blockveranstaltungen festgelegt.
    Der Seminarraum 03.11.018 ist donnerstags 14-16 Uhr für die Proseminar-Teilnehmer reserviert. Hier können die Teilnehmer gemeinsam an den Folien und Ausarbeitungen arbeiten und mit dem Seminarleiter die dabei auftretenden Probleme diskutieren.
  • Schein:
    Einen Seminarschein erhält, wer einen Vortrag gehalten, eine Ausarbeitung geschrieben und regelmäßig aktiv am Seminar teilgenommen hat.
  • Hörerkreis:
    Studierende im Grundstudium der Informatik
    Studierende im Bachelorstudiengang Informatik
    Studierende mit Nebenfach Informatik
  • Voraussetzungen:
    Voraussetzung für die Teilnahme am Proseminar sind neben Interesse an Algorithmen, auch Englischkenntnisse, die ausreichend für die Bearbeitung der überwiegend englischsprachigen Literatur sein müssen.

Zusammenfassung

Das Ziel eines Proseminar ist einerseits die vertieften inhaltlichen Auseinandersetzung mit einem Thema. Andererseits dient ein Proseminar aber auch dazu, die Fähigkeiten im Ausarbeiten und Halten von Vorträgen zu verbessern, und wir werden versuchen, Sie dabei zu unterstützen. Dazu gehören aus aktuellem Anlass auch die Grundlagen wissenschaftlichen Arbeitens, beispielsweise das korrekte Zitieren.

Dieses Proseminar wendet sich an Studierende, die Freude an eleganten Beweisen haben. Der Schwerpunkt liegt auf dem Gebiet der Diskreten Algorithmischen Mathematik. Unsere Arbeitsvorlage ist das Buch Proofs from THE BOOK / Das BUCH der Beweise von M. Aigner und G. M. Ziegler.

Der herausragende Mathematiker Paul Erdős, der unzählige Arbeiten insbesondere, aber keinesfalls ausschließlich, über den Einsatz von Zufall in der Kombinatorik vorgelegt hat, sprach gerne von einem metaphysischen Buch, in das die schönsten Beweise eingetragen würden. 'Proofs from the Book' wurde nach seinem Tod im Jahre 1996 ihm zu Ehren veröffentlicht. Es dokumentiert eine Reihe von Problemen die sich, wiewohl einfach zu formulieren und zu begreifen, oft Jahrzehnte jedem Lösungsversuch entzogen haben, bis jemand die richtige Idee hatte.

Mögliche Themen

Jeweils einzelne Kapitel aus dem Buch Das BUCH der Beweise bzw. Proofs from THE BOOK, z.B.
  1. Drei Anwendungen der Eulerschen Polyederformel
  2. Ein Lob der Ungleichungen
  3. Schubfachprinzip und doppeltes Abzählen
  4. Cayleys Formel für die Anzahl der Bäume
  5. Das Dinitz-Problem
  6. Ein Fünf-Farben-Satz
  7. Der Satz von Turán
  8. Kommunikation ohne Fehler
  9. Von Freunden und Politikern
  10. Die Probabilistische Methode

Themenverteilung

  • 1. Termin: 24.06.2017, 10:00-16:00 Uhr
    • Sechs Beweise für die Unendlichkeit der Primzahlen
      Arijan Klepica
    • Der Zwei-Quadrate-Satz von Fermat
      Simon Zelenski
    • Geraden in der Ebene und Zerlegungen von Graphen / Drei Anwendungen der Eulerschen Polyederformel
      Stephan Kellner
    • Der Fundamentalsatz der Algebra
      Lion Steger
    • Gut genug gemischt?
      David Glavas
    • Cayleys Formel für die Anzahl der Bäume
      Jan Waidner
    • Das Dinitz-Problem
      Maik Dannecker
  • 2. Termin: 15.07.2017, 10:00-16:00 Uhr
    • Ein Fünf-Farben-Satz
      Christopher Heumann
    • Der Satz von Turán
      (optional plus Von Freunden und Politikern)
      Mohamed Karim Abbes
    • Kommunikation ohne Fehler
      Bernhard Hempfer
    • Die Probabilistische Methode
      François Aubet
    • Analyse von Union/Find-Datenstrukturen
      Konstantin Pervunin

Literatur

Das BUCH der Beweise / Proofs from THE BOOK

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. 45(±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 6 ± 1 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