TheGI 2 (Bachelor)

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.

Alte Klausuren werden vom Veranstalter ausgegeben und sind auch in den alten Kursen im ISIS-Archiv verfügbar.

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

Die vom Veranstalter angebotenen Hilfestellungen (Großübungen, Fachmentorien, Quizze und Sprechstunden) sollten genutzt werden um den Inhalten der Veranstaltungen besser folgen zu können.

Persönliche Kommentare

Entsprechung in der (alten) StuPO 90: TheGI 1 (StuPO90) (Ja, richtig: Hier gab es eine Drehung).
(Dort findet ihr Klausuren und mehr)