Vorlesung Theoretische Informatik

Organisatorisches

Dozent: Dr. Alois Heinz
Semester: viertes (Bachelor) / fünftes (Diplom) Fachsemenster Software Engineering
Umfang: vierstündig (mit Übungen)
Vorkenntnisse: Programmieren (Java), Grundlagen der Informatik, Mathematik, Algorithmen und Datenstrukturen
Prüfung: zweistündige Klausur 
Zeit und Ort: Dienstag, Vorlesung 09.45-11.15 Uhr, Übung 11.30-13.00 Uhr, jeweils in A109
Vorlesungsbeginn: Dienstag, den 04.10.2011, um 09.45 Uhr in A109  

Material

Inhalt

Diese Informatik-Vorlesung gibt eine Einführung in die theoretische Informatik. Es werden Antworten auf die Fragen gegeben, was man unter Berechenbarkeit versteht und welche Komplexitätsklassen man unterscheiden kann. Wir betrachten verschiedene Automatenmodelle sowie ihre Sprachklassen, das sind die von ihnen lösbaren Probleme. NP-vollständige Probleme sind etwa besonders schwer oder praktisch kaum lösbare Probleme, und das Halteproblem ist ein Beispiel für ein nicht lösbares Problem. 

Leistungsnachweis

Es werden theoretische und praktische Aufgaben gestellt. Diese sind zu lösen und werden in den Übungen besprochen. Den Leistungsnachweis für die Veranstaltung gibt es nach bestandener Klausur.

Erfahrungsgemäß sind besonders diejenigen Studierenden erfolgreich in der Klausur, die während des Semesters selbst Aufgaben gelöst haben.

© aph
last modified: 10/2011