Dies ist eine alte Version des Dokuments!
Inhaltsverzeichnis
Automaten, Sprachen und Komplexität
| Info | |
|---|---|
| Modultafel | https://www.tu-ilmenau.de/modultafeln/Informatik/Bachelor/2013/fach/11618/ |
| Website WS19/20 | https://www.tu-ilmenau.de/iti/lehre/lehre-ws-20192020/ask/ |
Material
Info zu Übungen / Bonuspunkte
Die Übungen bestehen aus Präsenz- und Bonusaufgaben, von denen die Bonusaufgaben abgegeben werden sollten. Diese erzeugen anteilig 10% Bonuspunkte (prozentual zur maximalen Klausurpunktzahl), was bedeutet, dass man mit 40% der Klausurpunkte und 10% Bonuspunkte ( ~100% Bonusaufgaben richtig) immer noch 50% der Punkte in der Prüfung erhält und evtl. dadurch besteht!
Der Abgabetermin ist der Vorlesung zu entnehmen ( WS19/20: bis 12 Uhr Montag zur Übung oder im Briefkasten vor Z1047 Stand WS 19/20 ).
Präsenzaufgaben dienen der Übung und werden mit den Bonusaufgaben in den Übungsstunden besprochen!
Klausur
WS19/20
Die Klausur dauerte 2,5h und umfasste insgesamt 150 Punkte.
- 1/3 der Punkte erzielt man durch das aufschreiben von Definitionen, von der jede 2-6 Punkte Wert ist.
- 1/6 der Punkte bekommt man auf NFA/DFA, die Umwandlung zwischen denen, Minimierung.
- Der Rest bestand aus der Anwendung von Algorithmen.
Einige Themen:
- CYK-Algorithmus
- Algorithmus zum Finden von erkennungsäquivalenten Zuständen
- Nichtlösbare Probleme
- Reduktion
- Definition rekusiv aufzählbar
- Definition Loop-Programm
- Definition Myhill-Nerode-Äquivalenz
- Beweis von Nicht-Kontextfreiheit (z.B. mittels Pumping-Lemma für kontextfreie Sprachen)
- Definition PDA
- Erstellung einer Turing-Maschine, um eine Binärzahl zu invertieren und führende Nullen zu entfernen.
Bis auf die Definition wurde kein Beweis mittels Pumping-Lemma gefordert.