Studierende können
- Endliche Automaten (aka finite state machines) erkennen, formal beschreiben und analysieren (K2, K4, K5)
- sind in der Lage, fundamentale Limitierungen von endlichen Automaten mathematisch rigoros zu beweisen (Stichwort: Pumping Lemma) (K4, K3, K6)
- Turing Maschinen erkennen, formal beschreiben und analysieren (K2, K4, K5)
- sind in der Lage, fundamentale Limitierungen von Turingmaschinen mathematisch rigoros zu beweisen (Stichwort: Halting theorem) (K4, K3, K6)
- die wichtigsten Komplexitätsklassen -- P, NP, PSPACE, PSIZE, P/poly EXP -- erkennen, formal beschreiben und bestehende Computing Challenges in diese einordnen (K2, K4, K5)
- den Zusammenhang zwischen NP und SAT (Stichwort: Cook-Levin theorem) intuitiv sowie rigoros erklären (K4, K5)
- eigenständig Karp-Reduktionen eines bestimmten NP-vollständigen Problems auf SAT durchführen (K3, K4, K6)
- Kenntnis von und Verständnis für die polynominelle Hierarchie und wie man einen Kollaps derselben für rigorose Implikationen einsetzt (K2, K3, K4, K5)
- Logische Schaltkreise erkennen, formal beschreiben und analysieren (K2, K4, K5)
- Komplexitätsaussagen vom Turingmaschinenmodell ins Schaltkreismodell übersetzen und umgekehrt (K2, K3, K4)
|
- logisch/mathematisches Denken
- Beweise nachvollziehen, appreciaten und selbst durchführen
- fundamentale Limits der Berechenbarkeit
- Landschaft der Komplexitätstheorie
- und wie man sie für Argumente einsetzen kann
- zwischen Software-Modell (Turing Maschine) und Hardware-Modell (logische Schaltkreise) wechseln
|
