Sitzung: Jeden Freitag in der Vorlesungszeit ab 16 Uhr c. t. im MAR 0.005. In der vorlesungsfreien Zeit unregelmäßig (Jemensch da?). Macht mit!

TheGI 2 (Bachelor)

Version vom 7. September 2011, 08:43 Uhr von Jungnickel (Diskussion | Beiträge) (An das neue TheGI angepasst)

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.

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)