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

Informatik-Ansicht

Theoretische Informatik 2


Theoretical Computer Science 2
Modulnummer
BA-601.02
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 : 601 Grundlagen der Theoretischen Informatik
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 :
  • Fundamentale Konzepte und Ergebnisse aus den Gebieten Berechenbarkeit, Komplexität und Prädikatenlogik kennen und verinnerlicht haben.
  • Verschiedene Berechnungsmodelle kennen und die Grenzen der Berechenbarkeit einschätzen können.
  • Die Komplexität von typischen Informatik-Problemen einschätzen können und sensibilisiert sein für die Existenz schwieriger Probleme.
  • Induktionsbeweise über die Struktur von Zahlen, Wörtern, Berechnungssequenzen und/oder ähnliche Strukturen nachvollziehen und selbständig durchführen können.
  • Selbständig Algorithmen entwerfen und formal spezifizieren können.
  • In Gruppen Probleme analysieren und gemeinsam Lösungsstrategien entwickeln und präsentieren können.
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
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 2, Skript
Form der Prüfung : i. d. R. Bearbeitung von Übungsaufgaben und Fachgespräch
Arbeitsaufwand
Präsenz 56
Übungsbetrieb/Prüfungsvorbereitung 124
Summe 180 h
Lehrende: Prof. Dr. C. Lutz u.a. Verantwortlich Prof. Dr. C. Lutz
Zurück

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