fach:automaten-sprachen-und-komplexitaet:start
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
fach:automaten-sprachen-und-komplexitaet:start [2020-01-14 16:47] – clerie | fach:automaten-sprachen-und-komplexitaet:start [2023-01-11 12:07] (aktuell) – +Probeklausur WS15 yelteen | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
====== Automaten, Sprachen und Komplexität ====== | ====== Automaten, Sprachen und Komplexität ====== | ||
+ | |||
+ | Das Fach wird in der PO 2021 nicht mehr angeboten. Stattdessen gibt es " | ||
^ Info ^^ | ^ Info ^^ | ||
Zeile 13: | Zeile 15: | ||
Der Abgabetermin ist der Vorlesung zu entnehmen ( WS19/20: **bis 12 Uhr Montag zur Übung** oder im **Briefkasten vor Z1047** //Stand WS 19/20// ).\\ | 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! | 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, | ||
+ | * 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, | ||
+ | Bis auf die Definition wurde kein Beweis mittels Pumping-Lemma gefordert. | ||
+ | |||
+ | Siehe hierzu auch {{ : | ||
{{tag> | {{tag> |
fach/automaten-sprachen-und-komplexitaet/start.1579020459.txt.gz · Zuletzt geändert: 2022-03-26 22:59 (Externe Bearbeitung)