Lehrveranstaltungshandbuch Theoretische Informatik

---

Verantwortlich: Prof. Dr. Randerath

Lehrveranstaltung

Befriedigt Modul (MID)

• aktuelle
  • Ma TIN2012 THI

Organisation

Version erstellt 2013-05-13 VID 2 gültig ab SS 2013 gültig bis

Bezeichnung Lang Theoretische Informatik Englisch Theoretical Computer Science LVID F07_THI LVPID (Prüfungsnummer)

Semesterplan (SWS) Vorlesung 2 Übung (ganzer Kurs) 2 Übung (geteilter Kurs) Praktikum Projekt Seminar Tutorium (freiwillig)

Präsenzzeiten Vorlesung 30 Übung (ganzer Kurs) 30 Übung (geteilter Kurs) Praktikum Projekt Seminar Tutorium (freiwillig)

max. Teilnehmerzahl Übung (ganzer Kurs) 30 Übung (geteilter Kurs) Praktikum Projekt Seminar

Gesamtaufwand: 150

Unterrichtssprache

• Deutsch

Niveau

• Master

Notwendige Voraussetzungen

• Grundlagen der Automatentheorie und der Formalen Sprachen

Literatur

• Theoretische Informatik, J. Hromkovic, Teubner-Verlag
• Theoretische Informatik - kurzgefasst, U. Schöning, Spektrum-Verlag
• Theoretische Grundlagen der Informatik, R. Solcher, Hanser-Verlag

Dozenten

Wissenschaftliche Mitarbeiter

• tba

Zeugnistext

Theoretische Informatik

Kompetenznachweis

Form
sMP	100% (mündliche Prüfung)

Aufwand [h]
sMP	10

Intervall: 3/Jahr

---

Lehrveranstaltungselemente

Vorlesung / Übung

Lernziele

Lerninhalte (Kenntnisse)

• Mathematische Grundlagen der Theoretischen Informatik: Mengen undSprachen, Elementare Aussagen- und Prädikatenlogik, ElementareGraphentheorie, Asymptotische Analyse, Laufzeitanalysen
• Einführung Theoretische Informatik mittels Endlicher Automaten: Berechnungen,Konfigurationen, Akzeptierte Sprache, Determinismus und Nichtdeterminismus,Grammatik, reguläre Grammatik, reguläre Ausdrücke, Äquivalenz der Konzepte
• Typ2-,Typ1-, Typ0-Sprachen: kontextfreie, kontextsensitive, rekursiv-aufzählbare Sprachen, Chomsky-Hierarchie, das Wortproblem
• Turingmaschinen: Varianten von Turingmaschinen und deren Äquivalenz, Äquivalenz von linear beschränkten Automaten und Typ1-Grammatika,   Äquivalenz von Turingmaschinen und Typ0-Grammatika
• Berechenbarkeit: Turing-, While- und Loop-Berechenbarkeit, ChurchscheThese, Ackermannfunktion, universelle Turingmaschinen, Gödelnummereiner Turingmaschine
• Entscheidbarkeit: entscheidbare und semi-entscheidbare Probleme,Aufzählbarkeit, Reduktion von Problemen, das Halteproblem,unentscheidbare Probleme, das Theorem von Rice 
• Komplexitätstheorie und Algorithmik hartnäckiger Probleme: Komplexität vonAlgorithmen, Komplexitätsklassen, P=NP Problem, NP-vollständige Probleme,Approximationsalgorithmen, Lokale Suche

Fertigkeiten

• Die Studierenden beherrschen den Umgang mit Typ2-, Typ1- und Typ0-Sprachen sowie die zugehörigen  Maschinenmodelle
• Sie können mit formalen Modellen der Infomatik arbeiten
• Sie können die Kenntnisse der Berechenbarkeits-, Entscheidbarkeits- und Komplexitätstheorie auf praktische Probleme anwenden
• Sie sind in der Lage den Algorithmenbegriff zu präzisieren, die Tragweite von Algorithmen zu beschreiben und die Komplexität von Algorithmen zu bestimmen  
• Sie sind in der Lage die prinzipielle Lösbarkeit algorithmischer Probleme zu untersuchen

Begleitmaterial

• elektronische Vortragsfolien zur Vorlesung
• elektronische Übungsaufgabensammlung

Besondere Voraussetzungen

• keine

Besondere Literatur

• keine

Besonderer Kompetenznachweis

Form
bÜA	Präsenzübung

Beitrag zum LV-Ergebnis
bÜA	unbenotet

Intervall: 1/Jahr