Zur Seitennavigation oder mit Tastenkombination für den accesskey-Taste und Taste 1 
Zum Seiteninhalt oder mit Tastenkombination für den accesskey und Taste 2 
Startseite    Anmelden     
Logout in [min] [minutetext]

Theoretische Informatik - Detailansicht

  • Funktionen:
  • Zur Zeit kein Belegungszeitraum aktiv.
Grunddaten
Veranstaltungsart Vorlesung/Praktikum Langtext
Veranstaltungsnummer 3213 Kurztext
Semester SoSe 2021 SWS 8
Erwartete Teilnehmer/-innen Max. Teilnehmer/-innen
Rhythmus Jedes 2. Semester Studienjahr
Hyperlink  
Sprache Deutsch
Belegungsfrist Hauptbelegungszeitraum    01.03.2021 - 26.03.2021   
Termine Gruppe: [unbenannt] iCalendar Export für Outlook
  Tag Zeit Rhythmus Dauer Raum Raum-
plan
Lehrperson Status Lernziele fällt aus am Max. Teilnehmer/-innen
Einzeltermine anzeigen
iCalendar Export für Outlook
Di. 09:45 bis 13:00 woch          
Einzeltermine anzeigen
iCalendar Export für Outlook
Mo. 14:15 bis 17:30 woch          
Gruppe [unbenannt]:
Zur Zeit kein Belegungszeitraum aktiv.
 


Zugeordnete Person
Zugeordnete Person Zuständigkeit
Schneider, Markus, Professor
Laut SPO für
Abschluss Studiengang Semester Kategorie ECTS
Master mit vorausg. Absch Informatik 2 - 2 Pflichtfach 10
Prüfungen / Module
Prüfungsnummer Prüfungsversion Modul
8002 8 Theoretische Informatik
9303 9 Theoretische Informatik
Zuordnung zu Einrichtungen
Masterstudiengang Informatik
Inhalt
Kurzkommentar
  • Alle Materialien werden im zugeordneten Moodle-Kurs zur Verfügung gestellt. 
  • Einschreibeschlüssel wird per E-Mail bekannt gegeben.
Inhalt
I Formale Sprachen
1. Sprache und Grammatik
2. Endliche Automaten und Reguläre Sprachen
3. Kontextfreie Sprachen

II Berechenbarkeit
4. Die Turing-Maschine
5. Entscheidbarkeit
6. Unentscheidbarkeit
7. Turing-Maschinen und Sprachklassen
8. Alternative Berechnungsmodelle

III Komplexitätstheorie
9. Komplexität Messen
10. Effizienz
11. NP-Vollständigkeit
12. Zusammenhänge von Raum und Zeit

IV Logik
13. Aussagenlogik
14. Prädikatenlogik
Literatur

M. Sipser(2012).
Introductiontothe Theory of Computation. 3.Aufl. Cengage Learning

Das Standardwerk aus dem angelsächsischen Raum und daher in Englisch verfasst. Unser Skriptum ist stark an diesem Buch orientiert und für einige Beweise wird darauf verwiesen. Das Buch enthält eine Vielzahl an Beispielen und Übungen und ist umfangreich illustriert.

   
D. Hoffmann (2015).
Theoretische Informatik, Hanser

Prof. Ertel hält die Vorlesung Theoretische Informatik nach diesem Buch. Neben den Themen aus diesem Skript enthält es auch ein Kapitel über Logik. Es behandel Formale Sprachen und Endliche Automaten sequenziell, wohingegen wir beide Theorien parallel aufbauen.

Lernziele

Ziel des Faches Theoretische Informatik ist es, die theoretischen Grundlagen von Logik, formalen Sprachen, Automaten, Berechenbarkeit und Komplexitätstheorie zu vermitteln.

Die Prädikatenlogik als wichtige Grundlage für formale Verfahren in Programmverifikation, Hardwaredesign und künstlicher Intelligenz wird von Grund auf als formale Sprache mit deklarativer Semantik eingeführt. Der für automatische Beweiser und Verifikationssysteme wichtige Resolutionskalkül wird ausführlich behandelt.

Es wird ein vertieftes Verständnis von formalen Sprachen und Maschinenmodellen als Voraussetzung für die Entwicklung von Suchmaschinen, Lexern, Parsern und Compilern vermittelt. Weiter werden die Grenzen der Berechenbarkeit erlernt. Die Studierenden sollen verstehen, dass es Funktionen gibt, die ein Computer prinzipiell nicht berechnen kann. Die berechenbaren Sprachen werden schließlich in der Komplexitätstheorie in Klassen eingeteilt.

Im Einzelnen werden folgende Kompetenzen vermittelt:

  • Die Chomsky-Hierarchie verstehen. Formale Sprachen mit Hilfe von Grammatiken erzeugen können. Zentrale Ergebnisse zu regulären und kontextfreien Sprachen beherrschen und nutzen können, insbesondere Pumping-Lemmata, reguläre Ausdrücke und CYK-Algorithmus. Anwendungsmöglichkeiten formaler Sprachen wiedergeben können. Abschlusseigenschaften und Entscheidbarkeitsergebnisse für die verschiedenen Sprachtypen kennen.
  • Zentrale Ergebnisse zu endlichen Automaten und Kellerautomaten verstehen und anwenden können. Weitere Automatenmodelle kennen lernen und verwenden können.
  • Verschiedene Konzepte und Varianten von Turingmaschinen und deren Ausdrucksmächtigkeit erlernen und anwenden können. Zusammenhänge verschiedener Berechenbarkeitsbegriffe und Programmiersprachenkonzepte erlernen. Zusammenhang von Turingmaschinen und Computern sowie die Church'sche These verstehen. Zentrale Entscheidbarkeitsbegriffe und deren Zusammenhänge herleiten können. Grenzen der Berechenbarkeit bzw. algorithmischen Lösbarkeit und das Halteproblem verstehen. Unentscheidbarkeit von Problemen mit Reduktion beweisen können.
  • Algorithmische Komplexität nach dem O-Kalkül beherrschen. Zentrale Ergebnisse zu Komplexitätsklassen für Probleme (Komplexitätstheorie) erlernen. Grenzen der effizienten Berechenbarkeit und das SAT-Problem verstehen. NP-Vollständigkeit von Problemen mit polynomieller Reduktion beweisen können.
  • Zentrale Ergebnisse zu Aussagenlogik und Beweisverfahren verstehen. Die Prädikatenlogik erlernen. Den Resolutionskalkül beherrschen. Grenzen der Logik kennen lernen.
Voraussetzungen Programmieren, Grundlagen der Informatik, Mathematik-Grundlagen
Leistungsnachweis lt. aktueller SPO, gültig ab WS1718: PF benotet (Testat + M)

Am Ende des Semesters findet eine mündliche Prüfung statt. Durch Vorführen und Erklären von Übungsaufgaben (Testate) können im Laufe des Semesters Bonuspunkte für die mündliche Prüfung erworben werden.

Strukturbaum
Die Veranstaltung wurde 1 mal im Vorlesungsverzeichnis SoSe 2021 gefunden:
Informatik (Master)  - - - 1