Lehrveranstaltungshandbuch Theoretische Informatik


Verantwortlich: Prof. Dr. Randerath

Lehrveranstaltung

Befriedigt Modul (MID)

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

Diese Seite läuft auf FoswikiDas Urheberrecht © liegt bei den mitwirkenden Autoren. Alle Inhalte dieser Kollaborations-Plattform sind Eigentum der Autoren.
Ideen, Anfragen oder Probleme bezüglich Foswiki? Feedback senden