Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- fach:automaten-sprachen-und-komplexitaet:start [2020-02-21 11:30] – [Info zu Übungen / Bonuspunkte] 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 ======
+Das Fach wird in der PO 2021 nicht mehr angeboten. Stattdessen gibt es "Automaten und formale Sprachen" im 3. FS und "Berechenbarkeit und Komplexität" im 4. FS.
 ^ Info                                                                                     ^^
@@ Zeile 15: / Zeile 17: @@
 ===== Klausur =====
-==== 2020 ====
+==== WS19/20 ====
-Die Klauser dauerte 2,5h und umfasste insgesamt 150 Punkte.
+Die Klausur dauerte 2,5h und umfasste insgesamt 150 Punkte.
-/3 der Punkte erzielt man durch das aufschreiben von Definitionen, von der jede 2-6 Punkte Wert ist.
+  * 1/3 der Punkte erzielt man durch das aufschreiben von Definitionen, von der jede 2-6 Punkte Wert ist.
-/6 der Punkte bekommt man auf NFA/DFA, die Umwandlung zwischen denen, minimierung.
+  * 1/6 der Punkte bekommt man auf NFA/DFA, die Umwandlung zwischen denen, Minimierung.
-Der Rest bestand aus der Anwendung von Algorithmen.
+  * Der Rest bestand aus der Anwendung von Algorithmen.
 Einige Themen:
-- CYK-Algorithmus
+  * CYK-Algorithmus
-- Nichtlösbare Probleme
+  * 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.
+Siehe hierzu auch {{ :fach:automaten-sprachen-und-komplexitaet:probeklausurws15.pdf |Probeklausur WS15}}
 {{tag>semester:ba03}}