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 

Foto: Matthias Friel

Theoretische Informatik II: Effiziente Algorithmen - Einzelansicht

Veranstaltungsart Vorlesung/Übung Veranstaltungsnummer 550421
SWS Semester SoSe 2021
Einrichtung Institut für Informatik und Computational Science   Sprache deutsch
Belegungsfristen 06.04.2021 - 10.05.2021

Belegung über PULS
06.04.2021 - 10.05.2021

Belegung über PULS
Gruppe 1:
     jetzt belegen / abmelden
    Tag Zeit Rhythmus Dauer Raum Lehrperson Ausfall-/Ausweichtermine Max. Teilnehmer/-innen
Einzeltermine anzeigen
Tutorium Di 10:00 bis 12:00 wöchentlich 13.04.2021 bis 20.07.2021  Online.Veranstaltung Prof. Dr. Kreitz  
Einzeltermine anzeigen
Übung Mi 08:00 bis 10:00 wöchentlich 14.04.2021 bis 21.07.2021  Online.Veranstaltung Glinzer ,
Prof. Dr. Kreitz
  40
Vorlesung -  bis  wöchentlich am   Prof. Dr. Kreitz   180
Gruppe 2:
     jetzt belegen / abmelden
    Tag Zeit Rhythmus Dauer Raum Lehrperson Ausfall-/Ausweichtermine Max. Teilnehmer/-innen
Einzeltermine anzeigen
Tutorium Di 10:00 bis 12:00 wöchentlich 13.04.2021 bis 20.07.2021  Online.Veranstaltung Prof. Dr. Kreitz  
Einzeltermine anzeigen
Übung Do 08:00 bis 10:00 wöchentlich 15.04.2021 bis 22.07.2021  Online.Veranstaltung Glinzer ,
Prof. Dr. Kreitz
  40
Vorlesung -  bis  wöchentlich am   Prof. Dr. Kreitz   180
Gruppe 3:
     jetzt belegen / abmelden
    Tag Zeit Rhythmus Dauer Raum Lehrperson Ausfall-/Ausweichtermine Max. Teilnehmer/-innen
Einzeltermine anzeigen
Tutorium Di 10:00 bis 12:00 wöchentlich 13.04.2021 bis 20.07.2021  Online.Veranstaltung Prof. Dr. Kreitz  
Einzeltermine anzeigen
Übung Do 10:00 bis 12:00 wöchentlich 15.04.2021 bis 22.07.2021  Online.Veranstaltung Glinzer ,
Prof. Dr. Kreitz
  40
Vorlesung -  bis  wöchentlich am   Prof. Dr. Kreitz   180
Gruppe 4:
     jetzt belegen / abmelden
    Tag Zeit Rhythmus Dauer Raum Lehrperson Ausfall-/Ausweichtermine Max. Teilnehmer/-innen
Einzeltermine anzeigen
Tutorium Di 10:00 bis 12:00 wöchentlich 13.04.2021 bis 20.07.2021  Online.Veranstaltung Prof. Dr. Kreitz  
Einzeltermine anzeigen
Übung Fr 12:00 bis 14:00 wöchentlich 16.04.2021 bis 23.07.2021  Online.Veranstaltung Glinzer ,
Prof. Dr. Kreitz
  40
  Bemerkung: Bitte die geänderte Zeit beachten (von zuvor 14-16 Uhr zu nun 12-14 Uhr)!
Vorlesung -  bis  wöchentlich am   Prof. Dr. Kreitz   180
Gruppe 5:
     jetzt belegen / abmelden
    Tag Zeit Rhythmus Dauer Raum Lehrperson Ausfall-/Ausweichtermine Max. Teilnehmer/-innen
Einzeltermine anzeigen
Tutorium Di 10:00 bis 12:00 wöchentlich 13.04.2021 bis 20.07.2021  Online.Veranstaltung Prof. Dr. Kreitz  
Einzeltermine anzeigen
Übung Do 08:00 bis 10:00 wöchentlich 15.04.2021 bis 22.07.2021  Online.Veranstaltung Dr. rer. nat. Böhne ,
Prof. Dr. Kreitz
  40
  Bemerkung: Für Lehramtsstudierende.
Vorlesung -  bis  wöchentlich am   Prof. Dr. Kreitz   180
Gruppe 6:
     jetzt belegen / abmelden
    Tag Zeit Rhythmus Dauer Raum Lehrperson Ausfall-/Ausweichtermine Max. Teilnehmer/-innen
Einzeltermine anzeigen
Tutorium Di 10:00 bis 12:00 wöchentlich 13.04.2021 bis 20.07.2021  Online.Veranstaltung Prof. Dr. Kreitz  
Einzeltermine anzeigen
Übung Fr 14:00 bis 16:00 wöchentlich 16.04.2021 bis 23.07.2021  Online.Veranstaltung Dr. rer. nat. Böhne ,
Prof. Dr. Kreitz
  40
  Bemerkung: Für Lehramtsstudierende.
Vorlesung -  bis  wöchentlich am   Prof. Dr. Kreitz   180
Kommentar

Die Theoretische Informatik beschäftigt sich mit den grundlegenden Fragestellungen der Informatik. Hierzu werden Computer- und Automatenmodelle idealisiert und mathematisch untersucht.

Die Automatentheorie und die Theorie der formalen Sprachen (Thema des ersten Semesters) ist grundlegend für die Entwicklung von Programmiersprachen und Compilern. Sie untersucht, mit welchen Techniken welche Arten von Sprachen effizient analysiert werden können.
Die Berechenbarkeitstheorie befasst sich mit den prinzipiellen Grenzen des Berechenbaren und der Relation zwischen verschiedenen Computer- und Programmiermodellen. Die Komplexitätstheorie untersucht Effizienz von Algorithmen im Hinblick auf Platz- und Zeitbedarf und kümmert sich insbesondere um die Frage, wie effizient man bestimmte Probleme lösen kann.

Gliederung der Theoretischen Informatik II
* Berechenbarkeitstheorie o Turingmaschinen
o Rekursive Funktionen
o Lambda-Kalkül und arithmetische Repräsentierbarkeit
o Die Churchsche These
o Berechenbarkeit, Aufzählbarkeit und Entscheidbarkeit
o Unlösbare Probleme

* Komplexitätstheorie
o Konkrete Komplexitätsanalyse
o Komplexitätsklassen
o Handhabbarkeit: das P - NP Problem o NP-vollständige Problem
o Jenseits von NP-vollständigkeit
o Pseudopolynomielle und approximierende Algorithmen
o Probabilistische Lösung nichthandhabbarer Probleme
o Programmverifikation und -synthese

Literatur . Hopcroft, R. Motwani, J. Ullman: Einfuehrung in die Automatentheorie, Formale Sprachen und Komplexitaetstheorie, Pearson 2002

Michael Sipser: Introduction to the Theory of Computation. 2. Auflage, PWS 2005

J
Voraussetzungen Erfolgreiche Teilnahme an Theoretische Informatik I ist sehr zu empfehlen
Leistungsnachweis Klausur zu Beginn des vorlesungsfreien Zeitraums

Strukturbaum
Keine Einordnung ins Vorlesungsverzeichnis vorhanden. Veranstaltung ist aus dem Semester SoSe 2021 , Aktuelles Semester: SoSe 2024