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 Informatik-Format Pdf_icon Wirtschaftsinformatik-Format Pdf_icon Digitale Medien-Format Pdf_icon Systems Engineering-Format Pdf_icon

System Engineering-Ansicht

Modultyp
Pflichtmodul Wahlbereich
Spezialisierungsbereich Anzahl Semesterwochenstunden CP Angeboten in jedem
V Ü S P Proj. ∑ Anzahl
Theoretische Informatik 2
2 2 0 0 0 4 6 angeboten in jedem SoSe
Theoretical Computer Science 2         Berechnung des Workloads
Vorgesehenes Semester ab 1. Semester
Lernziele

  • 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.

Lerninhalte

.

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
Prüfungsformen

MP, Fachgespräch, Klausur, ggf. mit Bonusprüfung
Dokumente (Skripte, Programme, Literatur, 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
Lehrende: Prof. Dr. C. Lutz, Prof. Dr. S. Siebertz Verantwortlich: Prof. Dr. C. Lutz
Zurück

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