Sommersemester 2009
Grundlagen der
theoretischen Informatik
Günter
Rote
Impressum
(18. 12.)
Die Noten sollten inzwischen vollständig im Campus-Management-System
eingetragen sein.
Bitte überprüfen Sie Ihre Einträge.
Für diejenigen Studenten, die nicht
im Campus-Management-System verwaltet werden, sind Scheine
ausgestellt worden. Die Scheine können ab 11. Januar 2010 im
Prüfungsbüro abgeholt werden, in dringenden Fällen auch schon
vorher im Sekretariat. Für eine kleine Zahl von
Studenten
wurde kein Schein ausgestellt, da die Kriterien für die Übungen
nicht erfüllt waren.
(14. 10./13. 10.)
Die Ergebnisse der zweiten Klausur
vom 9. 10. 2009
(PDF,
PostScript,
dvi,
Musterlösung),
sind zwischen Raum 112 und 113 (in der Nähe des Sekretariats)
ausgehängt.
Einsicht in die Nachklausur (und in die Klausur):
Mittwoch, 21. 10. 2009, 13:30–14:00 Uhr, Raum 051.
(1. 9./2. 10.)
Eine Woche vor der Nachklausur wird es am Freitag, den
2. Oktober um 13 Uhr ein Tutorium zur Wiederholung des Stoffes
geben.
Treffpunkt:
vor dem Seminarraum 005, Takustraße 9.
(23. 7.) Für diejenigen Studierenden, die im Campus-Management-System
eingetragen sind, ist die regelmäßige und aktive Teilnahme an
den Übungen dort eingetragen.
(13. 7.) Bitte evaluieren
Sie die Veranstaltung.
(10. 7.) Die Ergebnisse der Klausur
vom 8. 7. 2009
(PDF,
PostScript,
dvi),
sind zwischen Raum 112 und 113 (in der Nähe des Sekretariats)
ausgehängt.
Die Einsicht ist am Montag, den 13. 7., von 11:00-11:45 im
Hörsaal Informatik möglich.
(Später kann auch nich zur Nachklausureinsicht in die ursprünglichen
Klausur Einsicht genommen werden.)
Die Eintragung ins Campus-Management-System bzw. die Erstellung der
Scheine erfolgt erst nach der Nachklausur, sofern nicht in
Einzelfällen ein dringender Bedarf besteht (bitte bei der
Einsicht melden).
(8. 7.) Die Nachklausur ist am Freitag, den 9. 10. 2009 von 14-16 Uhr im
Hörsaal Physiologie, Arnimalle 22.
(17. 4.) Für Wiederholer ist die Anerkennung der
bestandenen Übungsteilnahme geregelt.
(17. 4.) Es wird möglicherweise noch eine weitere (neunte)
Übungsgruppe geben.
(16. 4.) Es gibt eine zusätzliche Übungsgruppe
donnerstags von 12-14 Uhr. Weiters gibt es im KVV zwei fiktive
"Termine": für diejenigen, die nur an der Klausur teilnehmen
wollen, und einen Überlauftermin für die, die sich aus
Platzgründen nicht zu einer "echten" Gruppe anmelden konnten.
Bitte melden Sie sich gegebenenfalls zu diesen Gruppen an
oder um.
(Wenn Sie sich noch nicht zu einer "echten Gruppe" anmelden
können, werden Sie nicht nervös. Wir werden schon noch
für alle Interessenten ein Plätzchen finden.)
Inhaltsübersicht, Literatur:
Siehe KVV-Seite
der Vorlesung. Die Vorlesung ist vom Umfang her dreistündig;
Ich werde sie mit vier Stunden pro Woche halten, bis entsprechend
viele Stunden zusammenkommen; anschließend wird vor dem
Semesterende die Klausur sein.
Anmeldung:
Bitte melden Sie sich im KVV-System
zu den Übungsgruppen an. (Diese Anmeldung ist für
Diplomstudierende ausreichend.)
(Wenn Sie sich noch nicht anmelden konnten, werden Sie nicht
nervös. Wir werden schon noch für alle Interessenten ein
Plätzchen finden.)
Zusätzlich zu dieser Anmeldung hat
für Studierende im Bachelorstudiengang
Informatik und für andere Bachelor- und
Masterstudiengänge die rechtsverbindliche An-
und Abmeldung mittels des Campus Managements
zu erfolgen. Über den aktuellen Status der Möglichkeiten
und Pflichten zur An- und Abmeldung gibt die Homepage des Campus
Managements Auskunft. Für Fragen ist ferner eine Hotline unter
838-77777 erreichbar.
Wiederholer: Wenn Sie
die Vorlesung zum zweiten Mal besuchen und bereits im
letzten Jahr zwei von den drei "Säulen" (Anwesenheit
und aktive Teilnahme sowie genügend Punkte bei den
Übungen) positiv absolviert haben, und nur die Klausur
bestehen müssen, dann melden Sie sich bitte für die zu
diesem Zweck eingerichtete fiktive Übungsgruppe
Sonntag 21-22 Uhr an
oder um.
Wenn Ihre beiden Säulen schon im Campus-Management-System
vermerkt sind (das ist in der Regel für Bachelor-Studierende
der Fall), dann brauchen Sie (außer der Anmeldung zur
Veranstaltung im Campus-Management-System) nichts weiter zu tun als
sich auf die Klausur vorzubereiten. Wenn Sie bei den Klausuren
durchgefallen sind, empfehle ich natürlich trotzdem das
Durcharbeiten der Übungsblätter und die Teilnahme an den
Übungen, um den Stoff besser zu verstehen.
Wenn Sie nicht im Campus-Management-System verwaltet werden (das
ist in der Regel für Diplom-Studierende der Fall), dann kommen
Sie bis 6. Mai 2009 vor oder nach der Vorlesung zu mir, um
Ihr Bestehen der zwei Säulen aktive und
körperliche Teilnahme mit mir auf meiner
Teilnehmerliste abzugleichen. (Schicken Sie mir bitte keine
elektronische Nachricht.) Übungszulassungen, die mehrere Jahre
zurückliegen, werden nicht anerkannt.
Übungen:
Die Übungszettel werden ausschließlich online
erscheinen und zwar hier auf dieser Seite. Die
Bearbeitungsdauer reicht gewöhnlich von Freitag (ca. 10 Uhr)
bis zum Montag (12:00 Uhr) der übernächsten Woche, also
10 Tage. Verspätet abgegebene Übungszettel zählen
als nicht bearbeitet.
Bearbeiten Sie die Übungen in
Zweiergruppen und geben Sie sie schriftlich (nicht per
e-mail) im Postfach der betreffenden Tutoren ab. Es gibt ein
Forum,
bei dem alle Fragen - speziell auch inhaltliche Fragen zu
Übungszetteln - beantwortet werden.
Übungszettel:
Alle Übungszettel in einer Datei (PDF, PostScript,
dvi).
- Übungszettel: freiwillige Vorübungen, ohne Abgabe.
(PDF, PostScript,
dvi).
- Übungszettel:
Ausgabe
17. 4. 2008, Abgabe bis 27. 4. 2009, 12 Uhr (PDF, PostScript, dvi).
Bewertet werden Aufgaben 6 und 8.
- Übungszettel: Ausgabe 22. 4. 2008, Abgabe bis 4. 5. 2009,
12 Uhr
(PDF,
PostScript,
dvi).
Bewertet werden Aufgaben 15b und 17.
- Übungszettel: Ausgabe 30. 4. 2008, Abgabe bis 11. 5. 2009,
12 Uhr
(PDF,
PostScript,
dvi).
Bewertet werden Aufgaben 19 und 21.
- Übungszettel: Ausgabe 8. 5. 2008, Abgabe bis 18. 5. 2009,
12 Uhr
(PDF,
PostScript,
dvi).
Bewertet werden Aufgaben 25 und 28.
- Übungszettel: Ausgabe 14. 5. 2008, Abgabe bis 25. 5. 2009,
12 Uhr
(PDF,
PostScript,
dvi).
Bewertet werden Aufgaben 33 und 36.
- Übungszettel: Ausgabe 20. 5. 2008, Abgabe bis Dienstag, 2. 6. 2009,
12 Uhr
(PDF,
PostScript,
dvi).
Bewertet werden Aufgaben 40 und 45.
- Übungszettel: Ausgabe 29. 5. 2008 (Aufgabe 50 korrigiert am 30. 5.), Abgabe bis 8. 6. 2009,
12 Uhr
(PDF,
PostScript,
dvi).
Bewertet werden Aufgaben 50 und 52.
- Probeklausur, 15. 6. 2009
(PDF,
PostScript,
dvi).
- Übungszettel: Ausgabe 14. 6. 2008, Abgabe bis 22. 6. 2009,
12 Uhr
(PDF,
PostScript,
dvi).
Bewertet werden Aufgaben 55 und 56.
- Übungszettel: Ausgabe 19. 6. 2008, Abgabe bis 29. 6. 2009,
12 Uhr
(PDF,
PostScript,
dvi).
Bewertet werden Aufgaben 62 und 63.
- Übungszettel mit Zusatzaufgaben: Ausgabe 27. 6. 2008,
Korrektur 29.6.: in Aufgabe 72 solle die Variable R statt E heißen.
freiwillige Abgabe bis 6. 7. 2009,
12 Uhr
Vorlesungstermine und Übungsgruppen:
Vorlesungen: Montag und Mittwoch, 10.15 Uhr bis 11.45 Uhr im
Hörsaal Informatik
Tutorien:
| Manuel Jain |
Montag 14–16 Uhr |
Takustraße 9, SR 051 |
| Johannes Kulick |
Dienstag 14–16 Uhr |
Arnimallee 2, SR Villa |
| Benjamin Bortfeldt |
Dienstag 16–18 Uhr |
Takustraße 9, SR 049 |
| Benjamin Bortfeldt |
Mittwoch 12–14 Uhr |
Arnimallee 3, Raum 005 |
| Klemens Kapp |
Mittwoch 12–14 Uhr |
Takustraße 9, SR 051 |
| Klemens Kapp |
Mittwoch 14–16 Uhr |
Takustraße 9, SR 049 |
| Manuel Jain |
Donnerstag 12–14 Uhr |
Königin-Luise-Straße 24-26, HS 06 |
| Romain Grunert |
Donnerstag 14–16 Uhr |
Takustraße 9, SR 051 |
| Johannes Kulick |
Donnerstag 14–16 Uhr |
Takustraße 9, SR 005 |
Die Tutorien beginnen in der zweiten Woche (20. 4.)
Tutorinnen und Tutoren: Benjamin Bortfeldt, Romain Grunert,
Manuel Jain, Klemens Kapp, Johannes Kulick
Klausuren:
Es gibt eine 90-minütige Abschlussklausur gegen Ende des
Semesters, und einen Wiederholungstermin in der Woche vor oder nach
dem Vorlesungsbeginn im Wintersemester. Als Hilfsmittel ist einzig
ein DIN-A4-Blatt (doppelseitig) mit Ihren eigenen handschriftlichen
Gedächtnisstützen erlaubt. Dieses ist mit abzugeben.
Scheinkriterien:
Folgende Kriterien müssen erfüllt werden, damit ein
Schein ausgestellt wird. Sie benötigen:
- Mindestens 60% der erreichbaren Gesamtpunkte der
Übungszettel. Von jedem Übungszettel werden jedoch nur
zwei Aufgaben bewertet. Die zu bewertenden Aufgaben werden nach der
Abgabe ausgelost.
- Mindestens 50% der erreichbaren Punkte bei der Klausur.
Ferner ist erforderlich:
- Regelmäßige Anwesenheit bei den Übungsgruppen
(höchstens 2x fehlen)
- Aktive Teilnahme (mindestens 1x eine Aufgabenlösung in den
Übungen vorstellen)
Die Scheine sind benotet. Die Note beruht nur auf dem
Klausurergebnis.
Vorlesungstermine und -inhalte:
- Mittwoch, 15. April 2009:
- Überblick: Sprachen, Automaten, Berechenbarkeit,
Entscheidbarkeit
- Turingmaschinen
- Beispiel: Akzeptieren der Sprache {
0n1n |
n≥1 }
- Church'sche These
- Montag, 20. April 2009:
- Beispiel: Turingmaschine zur binären Addition
- Programmiertechniken: Mehrere Spuren auf dem Band, Speicher von
Variablen mit endlichem Wertebereich als Teil des Zustandes
- Registermaschinen (kurz)
- Simulation einer Registermaschine durch eine Turingmaschine
- Alphabet, Wörter und formale Sprachen
- Produkt von Wörtern und Sprachen, Potenz, *-Operation
- Mittwoch, 22. April 2009:
- Konfiguration einer Turingmaschine, Nachfolgerrelation
- Mehrband-Turingmaschinen
- Entscheidbare (rekursive) und rekursiv aufzählbare
(semientscheidbare) Sprachen, berechenbare Funktionen
- Montag, 27. April 2009:
- Universelle Turingmaschinen
- Gödelnummerierung
- Unentscheidbarkeit der Diagonalsprache
- Die universelle Sprache
- Mittwoch, 29. April 2009:
- Halteproblem
- Formale Formulierung von Entscheidungsproblemen als formale Sprachen
- Reduktion zwischen Problemen (Sprachen), A≤B
- Das Post'sche Korrespondenzproblem (PKP)
- Montag, 4. Mai 2009:
- Mittwoch, 6. Mail 2009:
- (Deterministischer) endlicher Automat (DEA)
- Reguläre Sprachen
- Reguläre Ausdrücke
- Montag, 11. Mai 2009:
- Nichtdeterministischer endlicher Automat (NEA)
- Potenzmengenkonstruktion
- Darstellung regulärer Ausdrücke durch NEAs mit
ε-Übergängen
- Mittwoch, 13. Mail 2009:
- Elimination von ε-Übergängen
- Minimalautomat
- Montag, 18. Mai 2009:
- Nerode-Relation
- Pumping-Lemma: Anwendung
- Mittwoch, 20. Mail 2009:
- Pumping-Lemma: Beweis
- Abschlusseigenschaften regulärer Sprachen
- Substitutionen
- Montag, 25. Mai 2009:
- Grammatiken, die Chomsky-Hierarchie
- Typ-0-Sprachen
- Mittwoch, 27. Mai 2009:
- Typ-3-Sprachen sind reguläre Sprachen
- Kontextsensitive Grammatiken, Entscheidbarkeit
- Tiefenstruktur von Sprache
- Montag, 1. Juni 2009: Pfingstmontag
- Mittwoch, 3. Juni 2009:
- Kontextfreie Grammatiken
- Die Dyck-Sprache
- Syntaxbaum
- Linksableitung, Rechtsableitung
- Eindeutige Grammatiken
- Chomsky-Normalform (CNF)
- Montag, 8. Juni 2009: entfällt
- Mittwoch, 10. Juni 2009: entfällt
- Montag, 15. Juni 2009: unverbindliche Probeklausur
- Mittwoch, 17. Juni 2009: entfällt
- Montag, 22. Juni 2009:
- Chomsky-Normalform (CNF): Elimination von ε-Regeln
- Der Algorithmus von Cocke, Younger und Kasami für das Wortproblem in kontextfreien Sprachen
- Mittwoch, 24. Juni 2009:
- Erweiterte Backus-Naur-Form (EBNF) für die Syntax von Programmiersprachen
- Das Pumping-Lemma für kontextfreie Sprachen
- Abschlusseigenschaften kontextfreier Sprachen
- Montag, 29. Juni 2009:
- Kellerautomaten
- Akzeptieren durch leeren Keller oder durch akzeptierende Zustandsmenge
- Mittwoch, 1. Juli 2009:
- Kellerautomaten und kontextfreie Sprachen
- Abschluss gegenüber Durchschnitt mit regulären Sprachen
- Montag, 6. Juli 2009:
- Deterministische kontextfreie Sprachen
- Deterministische Zweiwege-Kellerautomaten
- Mittwoch, 8. Juli 2009: Klausur
(PDF,
PostScript,
dvi,
Musterlösung. Bei Aufgabe 4 ist ein
Fehler in der Lösung: Bei M12(2) sind
die Faktoren vertauscht: Es sollte
0*1(0+1)* heißen, und ebenso
bei M12(3) und dem
Lösungsausdruck
für L.)
- Freitag, 9. Oktober 2009: Nachklausur
(PDF,
PostScript,
dvi,
Musterlösung).