You are here: Home Teaching Winter Term 2014/2015 Automatentheorie (Proseminar)

Einführung in die Automatentheorie

In der Vorlesung Theoretische Informatik lernen Sie endliche Automaten, Kellerautomaten und Turingmaschinen kennen. Zum einen werden diese aber nicht erschöpfend behandelt. Zum anderen sind das längst nicht alle Arten von Automaten, die bereits erforscht wurden. In diesem Proseminar wollen wir uns eingehender mit Automaten beschäftigen.
Veranstaltungsart Proseminar
Veranstalter Matthias Heizmann, Alexander Nutz, Christian Schilling
Kick-off meeting
Donnerstag 23.10.2014, 15:00-16:00 Uhr, Gebäude 052, Raum 00-016
Vorträge Montag 9.3.2015, 16:00-18:00 Uhr c.t., Gebäude 052, Raum 00-016
Sprache der Vorträge
Deutsch
ECTS
3

Aktuelles

  • Ein Zeitplan wurde hinzugefügt.
  • Die nächste Besprechung findet am 5. Dezember um 13 Uhr in Gebäude 052, Raum 00-016 statt. Bei dieser Besprechung werden die Seminarthemen vergeben.
  • Die Vorträge finden entsprechend den Wünschen der Mehrheit der Teilnehmer in Februar oder März statt. Der Termin wird in der nächsten Besprechung vereinbart.

Ablauf des Seminars

  • Da die Grundlagen des Seminarthemas in der Vorlesung Informatik III (Theoretische Informatik) gelegt werden, ist es Voraussetzung, dass Sie diese in diesem Semester besuchen oder bereits besucht haben.
  • Im Kickoff-Meeting werden die verfügbaren Themen vorgestellt.
  • Sie wenden sich mit einem Themenwunsch an einen der Betreuer. Der Betreuer kann Ihnen auch bei der Auswahl helfen.
  • Sie treffen sich mit ihrem Betreuer um die Literaturauswahl zu ihrem Thema zu besprechen und die Struktur Ihres Vortrags zu skizzieren.
  • Sie schreiben ein kurzes Proposal, in dem Sie kurz informell Ihren Vortrag vorstellen.
  • Sie schreiben einen Abstract (zwei bis drei Sätze zur Zusammenfassung) für Ihren Vortrag.
  • Sie geben Proposal und Abstract bis spätestens drei Wochen vor Beginn des Blockseminars bei ihrem Betreuer ab (via E-Mail).
  • Ihr Proposal wird von zwei anderen Teilnehmern kommentiert (engl. "Review").
  • Sie schreiben Reviews zu den Proposals zweier anderer Teilnehmer (binnen einer Woche).
  • Sie schicken bis spätestens eine Woche vor Beginn des Seminars Ihre Präsentationsfolien für den Vortrag an Ihren Betreuer.
  • Sie treffen sich kurz mit Ihrem Betreuer, um die Folien zu besprechen.
  • Sie halten einen Vortrag von ca. 20 Minuten Länge.
  • Sie hören auch die Vorträge der anderen Teilnehmer und beteiligen sich möglichst aktiv an der Diskussion.

Proposal

Das Proposal sollte etwa vier Seiten umfassen, in denen Sie Ihren geplanten Vortrag beschreiben. Es kann zum Beispiel folgende Punkte enthalten:

  • eine kurze Themeneinführung (der Reviewer kennt ihr Thema vermutlich nicht)
  • die Struktur des Vortrags
  • die Auswahl, welche Aspekte ihres Themas Sie eingehender behandeln, welche Sie weglassen möchten und eine Begründung
  • Beispiele, die Sie in Ihrem Vortrag vorstellen wollen (in vielen Vorträgen wird ein Algorithmus anhand eines Beispiels eingeführt), wieso gerade diese(s) Beispiel(e)?
  • welche Definitionen werden präsentiert, wieso?
  • welche Notation wird benutzt (oft gibt es verschiedene für die gleiche Sache), wieso?
  • werden Theoreme und eventuell Beweise dazu vorgestellt, wenn ja, welche und wieso?

Abstract

  • Der Abstract besteht aus einem Textabsatz, der Ihren Votrag vorstellt.
  • Wir werden eine Einladung zum Seminar an unseren Lehrstuhl schicken, für die wir die Abstracts verwenden.

Der Vortrag

  • Ziel Ihres Vortrags ist es Ihren Zuhörern (Bachelorstudenten, die nur die Grundlagen der Automatentheorie kennen) die Möglichkeit zu geben, etwas Neues zu einem interessanten Thema zu lernen. Die Vortragsnote ergibt sich daraus, wie gut Ihnen das gelingt.
  • Ziel eines Seminars ist es ein Thema für andere verständlich zu machen. Es geht also nicht in erster Linie darum, zu zeigen, wie gut Sie das Thema verstanden haben, sondern wie gut Sie es anderen nahe bringen. Letzteres beeinflusst Ihre Note nur insoweit es Ihnen bei Ersterem hilft.
  • Sie dürfen beliebige Quellen verwenden (müssen Zitate aber natürlich entsprechend markieren). Wenn Sie denken, dass Ihr Vortrag eine Neuzusammenstellung vorhandener Vorträge im Hinblick auf Ihr Publikum ist, könnte das genau das Richtige sein. Achten Sie aber darauf, dass im Internet vorhandene Vorträge auf ein anderes Publikum ausgerichtet sein können.
  • Falls Sie einverstanden sind, stellen wir ihre Präsentationsfolien auf diese Website. Behalten Sie dazu im Hinterkopf, dass dies unmöglich wird, falls Sie copyright-geschützte Bilder verwenden (es ist natürlich möglich, eine Version ohne diese Bilder hochzuladen). Selbstverständlich hat Ihre Entscheidung bezüglich der Veröffentlichung hier keinen Einfluss auf Ihre Note.

Review der Proposals

  • Geben Sie eine kurze Zusammenfassung ihres Vortragsthemas (um Missverständnisse möglichst früh auszuschließen).
  • Halten Sie sich nicht zurück mit Ihrer Kritik. Es ist unwahrscheinlich, dass ein Student eine schlechtere Note bekommt, weil Sie ein Problem aufgedeckt haben. Es ist wesentlich wahrscheinlicher, dass er eine bessere Note bekommt, weil er das Problem beheben kann.
  • Begründen Sie ihre Kritik (etwa "Definition x ist schwer zu verstehen, weil sie den Begriff y verwendet, der aber nicht erklärt wurde"). Sie können auch subjektive Aussagen treffen, sollten diese aber als solche ausweisen.
  • Folgende Fragen können ihnen bei Ihrem Review behilflich sein
Is das Proposal hinreichend gut formuliert, um verständlich zu sein?
Sind das Äußere und die Struktur des Proposals angemessen?
Wird die Verständlichkeit des Vortrags durch relevante Beispiele und Abbildungen unterstützt?
Ist die vorgeschlagene Votragsstruktur vernünftig und ausgewogen?
Sind alle Behauptungen, die der Autor macht, korrekt?
Ist die Begründung der Vortragsstruktur vollständig und nachvollziehbar?
Verwendet der Autor übliche Notationen und Begriffe? Wo würden Sie andere vorschlagen?
Ist die Zeitplanung des Autors realistisch? Ist der Vortrag zu lang oder zu kurz?

Benotung

Ihre Gesamtnote ergibt sich aus den Teilnoten wie folgt:

  • 10% Proposal
  • 20% Reviews
  • 70% Vortrag

Themen

Hopcrofts Minimierungsalgorithmus

Kongruenzen von Visibly Pushdown-Sprachen

Zeitplan

  • Montag 16.2.2015: Abgabe des Proposals
  • Montag 23.2.2015: Abgabe des Reviews
  • Montag 2.3.2015: Abgabe der Vortragsfolien
  • Montag 9.3.2015: Vorträge um 16 Uhr