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]

Strukturbaum
Keine Einordnung ins Vorlesungsverzeichnis vorhanden. Veranstaltung ist aus dem Semester SS 2018 , Aktuelles Semester: SoSe 2024
  • Funktionen:
  • Zur Zeit kein Belegungszeitraum aktiv.
Theoretische Informatik    Sprache: Deutsch    Belegpflicht
Nr.:  3213     Vorlesung/Praktikum     SS 2018     8 SWS     Jedes Semester    
   Weitere Links: Webseite mit Videos zur Vorlesung von Prof. Ertel 
   Master-Studiengang: Masterstudiengang Informatik    
 
   Studiengang   Informatik, Abschluss 90,   ( 2. Semester ) - ECTS-Punkte : 10     - Kategorie : Pflichtfach    
   Zugeordnete Lehrperson:   Mauser
 
 
   Termin: Dienstag   09:45  -  11:15    wöchentl
Beginn : 20.03.2018   
      Raum :   G 001 (Raum nur in Absprache mit dem Sekretariat MD buchbar)   Gebäude G  
  Dienstag   08:00  -  09:30    wöchentl Durchf. Lehrperson:   Mauser       Raum :   H 143   Gebäude H  
  Mittwoch   17:45  -  19:15    wöchentl       Raum :   T 117   Gebäude T  
  Freitag   09:45  -  13:00    wöchentl       Raum :   V 108   Gebäude V/Laz1  
 
 
   Inhalt: 1 Logik
2 Formale Sprachen
3 Automaten
4 Petrinetze
5 Berechenbarkeitstheorie
6 Komplexitätstheorie
 
   Literatur: D. Hoffmann: Theoretische Informatik, Hanser, 2015
W. Ertel: Grundkurs Künstliche Intelligenz, Springer Vieweg, 2013
R. Socher: Theoretische Grundlagen der Informatik, Fachbuchverlag Leipzig, 2003.
J. Dassow: Logik für Informatiker, Teubner, 2005.
J. E. Hopcroft, R. Motwani, J. D. Ullman: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit, Pearson, 2011.
 
   Lernziele: Ziel des Faches Theoretische Informatik ist es, die theoretischen Grundlagen von Logik, formalen Sprachen, Automaten, Petrinetzen, 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. Die Möglichkeiten der Analyse von formalen Modellen werden anhand von Petrinetzen dargesetllt. 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:
o Zentrale Ergebnisse zu Aussagenlogik und Beweisverfahren verstehen. Die Prädikatenlogik erlernen. Den Resolutionskalkül beherrschen. Grenzen der Logik kennen lernen. Logikprogrammierung mit Prolog durchführen können.
o 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.
o Zentrale Ergebnisse zu endlichen Automaten und Kellerautomaten verstehen und anwenden können. Weitere Automatenmodelle kennen lernen und verwenden können, z.B. Transduktor.
o Formale Modellierung mit Petrinetzen beherrschen, insbesondere Geschäftsprozessmodellierung. Analysemethoden für Petrinetze anwenden können.
o 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.
o 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.
 
   Voraussetzungen: Programmieren, Grundlagen der Informatik, Mathematik-Grundlagen
 
   Leistungsnachweis: lt. aktueller SPO, gültig ab WS1718: PF benotet

Am Ende des Semesters findet eine 90-minütige Klausur statt. Durch Vorführen und Erklären von Übungsaufgaben können im Laufe des Semesters Bonuspunkte für die Klausur erworben werden.
 
   Module: Theoretische Informatik (IN)