TheGI 2 (Bachelor)
History Lesson!
Dieser Artikel spiegelt sehr wahrscheinlich nicht mehr den aktuellen Stand wider, könnte aber trotzdem von Interesse sein.
Dieser Artikel spiegelt sehr wahrscheinlich nicht mehr den aktuellen Stand wider, könnte aber trotzdem von Interesse sein.
Musterklausuren
Bitte beachte die Hinweise zu Altklausuren.
Entsprechung in der (alten) StuPO 90: TheGI 1 (StuPO90) (Ja, richtig: Hier gab es eine Drehung).
(Dort findet ihr Klausuren und mehr)
Theoretische Grundlagen der Informatik 2: Berechenbarkeit und Komplexität ist eine Pflichtveranstaltung im zweiten Semester des Studiengangs Informatik nach neuer Bachelor-StuPO. Sie besteht aus 2 SWS Vorlesung und 2 SWS Übung und entspricht 6 ECTS-Leistungspunkten.
Inhalt
- Automaten (DFA; NFA; Untermengenkonstruktion; reguläre Sprachen)
- Kellerautomaten (PDA; DPDA; kontextfreie Sprachen)
- Turing-Maschinen (DTM; NTM; Akzeptierbarkeit)
- Berechenbarkeit ((Un)entscheidbarkeit; entscheidbare Sprachen; Wortproblem; Halteproblem; Reduktion)
- Komplexität (Zeit- und Platzaufwand; Komplexitätsklassen; P vs. NP)
Tipps und nützliche Infos
- Der Schöning ist der Beste Leitfaden zur Vorlesung.
- Vorlesungsmitschriften aus dem SS 2011 gibt es unter http://pub.cebe.cc/uni/thegi2/
