Die Informatik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Verwaltung des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Informatik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Mathematik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Universität Bremen
Zeige Systems Engineering-Format Pdf_icon Informatik-Format Pdf_icon Wirtschaftsinformatik-Format Pdf_icon Digitale Medien-Format Pdf_icon

Informatik-Ansicht

Theoretische Informatik 2


Theoretical Computer Science 2
Modulnummer
IBGT-THI2
Bachelor
Pflicht/Wahl
Wahl Basis Ergänzung
Sonderfall
Zugeordnet zu Masterprofil
Sicherheit und Qualität
KI, Kognition, Robotik
Digitale Medien und Interaktion
Modulbereich : Mathematik und Theoretische Informatik
Modulteilbereich : (keine Angabe)
Anzahl der SWS
V UE K S Prak. Proj.
2 2 0 0 0 0 4
Kreditpunkte : 6 Turnus

angeboten in jedem SoSe

Formale Voraussetzungen : -
Inhaltliche Voraussetzungen : -
Vorgesehenes Semester : 4.Semester
Sprache : Deutsch
Ziele :
  • Formale Grundlagen und elementare Fragestellungen der Informatik kennen und die fundamentale Rolle der Theorie in der Informatik verstehen.
  • Konzepte zur formalen Beschreibung und Analyse von Informatiksystemen kennen.
  • Beherrschung der grundlegenden Methoden aus den Bereichen der Berechenbarkeit und Komplexität.
  • Beherrschung elementarer Beweistechniken und Beweise selbst durchführen können.
  • Probleme analysieren, von spezifischen Gegebenheiten abstrahieren und formale Modelle in mathematischen Definitionen darstellen können.
  • Algorithmen für diese Probleme kennen und auf neue Problemvarianten anwenden können.
  • Korrektheit von Algorithmen beweisen und Eigenschaften von Algorithmen analysieren können.
  • Eigenständig und in Gruppen Lösungsstrategien für formale Problemstellungen entwickeln können und Lösungen verständlich präsentieren.
Inhalte :

.

1 Berechenbarkeit:

  • Turingmaschinen
  • Linear beschränkte Automaten
  • Grammatiken der Typen 0 und 1, Abschlusseigenschaften
  • LOOP-Programme und WHILE-Programme
  • Primitiv rekursive Funktionen und -rekursive Funktionen
  • Unentscheidbarkeit
  • Unentscheidbare Probleme für Turingmaschinen
  • Satz von Rice
  • Postsches Korrespondenzproblem
  • Äquivalenzproblem kontextfreier Grammatiken
  • Semi-Entscheidbarkeit und Rekursive Aufzählbarkeit
  • Universelle Turingmaschinen
  • Reduktionen

.

2 Komplexität:

  • Zeit- und Platzbeschränkte Turingsmaschinen
  • Komplexitätsklassen P, NP, PSpace, ExpTime
  • P vs NP-Problem
  • NP-Vollständigkeit
  • NP-vollständige Probleme aus verschiedenen Gebieten
  • Komplemente und coNP
  • Approximation NP-harter Probleme
  • Satz von Savitch

Lehrveranstaltung(en):

  • 03-IBGT-THI2 Theoretische Informatik 2: Berechenbarkeit und Komplexität
Unterlagen (Skripte, Literatur, Programme usw.) :
  • J.E. Hopcroft, R. Motwani, J.D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson Studium 2011
  • J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation (3rd edition). Pearson Education, 2014
  • C. Lutz: Theoretische Informatik, Skript 2. Teil
Form der Prüfung : MP, Fachgespräch, Klausur, ggf. mit Bonusprüfung
Arbeitsaufwand
Präsenz 56
Übungsbetrieb/Prüfungsvorbereitung 124
Summe 180 h
Lehrende: Prof. Dr. C. Lutz, Prof. Dr. S. Siebertz Verantwortlich Prof. Dr. C. Lutz
Zurück

Zeige Systems Engineering-Format Pdf_icon Informatik-Format Pdf_icon Wirtschaftsinformatik-Format Pdf_icon Digitale Medien-Format Pdf_icon