Seminar Theoretische Informatik

Belegnummer: 41.4262 Modulbeschreibung

Seminar Theoretische Informatik

Inhalt

In dem Seminar beschäftigen Sie sich speziellen Themen der Theoretischen Informatik. Sie beschaffen sich selbständig Literatur, arbeiten diese auf und präsentieren das Thema in einem Vortrag sowie in einer schriftlichen Ausarbeitung. Auf diese Weise lernen Sie neben Inhalten der Theoretischen Informatik auch das wissenschaftliche Arbeiten.

Dozenten

Dieses Seminar wird gemeinsam von Steffen Lange und Gunter Grieser veranstaltet.

Ablauf

Zu Beginn wählen Sie ein Thema aus. Jedes Thema wird gemeinsam von 2 Studenten bearbeitet. Sie suchen in Absprache mit Ihrem Betreuer Literatur zu dem Thema aus und arbeiten diese durch.

Abschlie√üend stellen Sie das Thema in einem 60 min√ľtigen Vortrag vor, wobei jeder Student 30 Minuten √ľbernimmt. Die Benotung des Vortrags erfolgt f√ľr jeden Studenten separat. Diese Note geht zu 40% in die Gesamtnote ein.

Au√üerdem stellen Sie das Thema in einer schriftlichen wissenschaftlichen Ausarbeitung dar. Die Ausarbeitung wird von beiden Studenten gemeinsam angefertigt. Die Benotung erfolgt f√ľr beide Studenten gemeinsam und geht zu 40% in die Endnote ein.

Au√üerdem w√§hlen Sie eines der anderen Themen aus und lesen die von Ihren Kommilitonen angefertigte schriftliche Ausarbeitung zu diesem Thema durch. Im Gespr√§ch mit den Betreuern fassen Sie das Thema kurz zusammen und wir unterhalten uns √ľber das Thema und die Ausarbeitung. Dieses Gespr√§ch wird ebenfalls bewertet und geht zu 20% in die Endnote ein.

Themen

  1. Programmäquivalenz und das Halteproblem

    • Unentscheidbarkeitsergebnisse
    • Entscheidbarkeitsergebnisse
    • Berechenbarkeitsmodelle: Turing-Maschinen, endliche Automaten, Kellerautomaten, Loop-Programme

  2. Lineare Optimierung und Approximationsalgorithmen

    • relaxierte Optimierungsprobleme
    • ganzahlige und rationale L√∂sungen von Optimierungsproblemen
    • deterministisches und randomisiertes Runden

  3. Approximationsalgorithmen mit absoluter und relativer
    G√ľtegarantie

    • NP-vollst√§ndige Optimierungsprobleme
    • G√ľte von Approximationsalgorithmen
    • St√§rken von Approximationsalgorithmen und deren Grenzen
    • Greedy-Algorithmen/Greedy-Heuristiken

  4. Deduktionskalk√ľle

    • Konnektionskalk√ľl
    • Tableauxmethode
    • Resolutionskalk√ľl

  5. Nichtstandard-Logiken

    • Default Logik
    • Description Logic

  6. Nichtklassische Berechnungsmodelle

    • DNA-Computing
    • Quantencomputing
    • Church'sche These vs. erweiterte Church'sche These

Termine


  • Do., 22.3. 8:30 Uhr bis 10:00 Uhr D14.015: Themenvergabe
  • 25.4.12 8:15 bis 10:00 Minivortr√§ge (5-10'), D14.403
  • 1.6. Abgabe Berichte + Folien
  • 12.6. 8:30 bis 11:30 D14/0.15: Vortr√§ge Teil 1
  • 13.6. 16:00 bis 19:00 D14/0.13: Vortr√§ge Teil 2
  • 21.6. zwischen 12 und 16 Uhr D14/0.10 (B√ľro van Beek) Fachgespr√§che

 

Downloads

Als Hilfestellung f√ľr Sie: unsere Notizen

Foliensatz des ersten Treffens

Wir schlagen vor, dass Sie diese Formatvorlagen von Springer (LNCS)  f√ľr Ihre Ausarbeitung verwenden.