Modulhandbuch MaTIN2012_Theoretische Informatik

---

Verantwortlich: Prof. Dr. Randerath

Modul

Anerkennbare Lehrveranstaltung (LV)

• F07 THI

Organisation

Bezeichnung Lang MaTIN2012_Theoretische Informatik MID MaTIN2012_THI MPID G

Zuordnung Studiengang MaTIN2012 Studienrichtung G Wissensgebiete G_VGTHI

Einordnung ins Curriculum Fachsemester 1 Pflicht G Wahl

Version erstellt 2012-05-04 VID 1 gültig ab SS 2013 gültig bis

Zeugnistext

de

Theoretische Informatik

en

Theoretical Computer Science

Unterrichtssprache

Deutsch

Modulprüfung

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

Beiträge ECTS-CP aus Wissensgebieten
G_VGTHI	5
Summe	5

Aufwand [h]: 150

---

Prüfungselemente

Vorlesung / Übung

Form Kompetenznachweis
bÜA	Präsenzübung und Selbstlernaufgaben

Beitrag zum Modulergebnis
bÜA	unbenotet

Spezifische Lernziele

Lerninhalte(Kenntnisse)

• Mathematische Grundlagen der Theoretischen Informatik (PFK.2 PFK.4)
• Einführung Theoretische Informatik mittels Endlicher Automaten (PFK.2, PFK.4)
• Typ2-,Typ1-, Typ0-Sprachen (PFK.2)
• Turingmaschinen (PFK.2)
• Berechenbarkeit (PFK.2)
• Entscheidbarkeit (PFK.2)
• Komplexitätstheorie und Algorithmik hartnäckiger Probleme (PFK.2, PFK_4)

Fertigkeiten

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

Exemplarische inhaltliche Operationalisierung

Die Bestimmung der Komplexität eines Algorithmus kann z.B. durch Analyse der Eingabeinstanz und des algorithmischen Kerns und Anwenden der O-Notation  vorgenommen werden.  Die Hartnäckigkeit eines algorithmischen Problems kann z.B. durch Anwenden einer geeigneten Reduktion auf ein etabliertes hartnäckiges Problem, wie beispielsweise dem aussagenlogischen Erfüllbarkeitsproblem, erreicht werden.