TheGI 2 (Bachelor)

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

Musterklausuren

Bitte beachte die Hinweise zu Altklausuren.

• 2007 Zwischenklausur
• 2007 Endklausur
• 2007 Zwischenklausur Nachschreibetermin
• 2007 Endklausur Nachschreibetermin
• 2008 Zwischenklausur
• 2008 Endklausur
• 2008 Zwischenklausur Nachschreibetermin
• 2008 Endklausur Nachschreibetermin
• 2009 Zwischenklausur
• 2009 Endklausur
• 2009 Zwischenklausur Nachschreibetermin
• 2009 Endklausur Nachschreibetermin
• 2010 Zwischenklausur
• 2010 Endklausur
• Ab SoSe 2011 gab es einen Wechsel der Lehrveranstalter

Fehler in den Lösungen an uns melden

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/