108.036 Theoretische Informatik
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2019S, VO, 2.0h, 3.0EC

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VO Vorlesung

Ziele der Lehrveranstaltung

Kenntnis der zentralen Begriffe, Resultate und Methoden der theoretischen Informatik

Inhalt der Lehrveranstaltung

Die Vorlesung beginnt mit einer Einführung in die Theorie endlicher Automaten
und formaler Sprachen. Wir lernen die Klassen der regulären und der
kontextfreien Sprachen kennen, sowie verschiedene Beschreibungsformalismen für
derartige Sprachen, insbesondere endliche Automaten und formale Grammatiken.
Im zweiten Teil, nach einem starken Sprung in der Ausdrucksstärke, beschäftigen
wir uns mit Berechenbarkeitstheorie, d.h. mit der Frage welche Funktionen
überhaupt prinzipiell berechenbar sind. Dazu verwenden wir die
Operatordarstellung partiell rekursiver Funktionen sowie Turingmaschinen. Wir
diskutieren die Church-Turing-These und beweisen die grundlegenden Resultate
der Berechenbarkeitstheorie. Im dritten Teil behandeln wir die
Komplexitätstheorie. Diese erhält man aus der Berechenbarkeitstheorie durch eine
Einschränkung der für eine Berechnung zur Verfügung stehenden Resourcen, z.B.
auf polynomiale Zeit. In dieses Gebiet fällt das P vs. NP - Problem das wir ins
Zentrum unserer Diskussion der Komplexitätstheorie stellen werden. In einem
vierten Teil beschäftigen wir uns abschließend noch mit den theoretischen
Grundlagen der Programmverifikation, was die Anwendung und Zusammenführung
einer Reihe von Resultaten aus den vorherigen Teilen erlaubt.

Vortragende

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Mo.14:15 - 15:4504.03.2019 - 24.06.2019 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Theoretische Informatik - Einzeltermine
TagDatumZeitOrtBeschreibung
Mo.04.03.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mo.11.03.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mo.18.03.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mo.25.03.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mo.01.04.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mo.08.04.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mo.29.04.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mo.06.05.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mo.13.05.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mo.20.05.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mo.27.05.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mo.03.06.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mo.17.06.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung
Mo.24.06.201914:15 - 15:45 Dissertantenraum (Freihaus, 8. Stock, grüner Bereich)Vorlesung

LVA-Anmeldung

Nicht erforderlich

Curricula

Literatur

Ein Skriptum zur Lehrveranstaltung ist erhältlich.

Begleitende Lehrveranstaltungen

Sprache

bei Bedarf in Englisch