AGNES -
Lehre und Prüfung online
Studierende in Vorlesung
Anmelden

Einführung in die Komplexitätstheorie - Detailseite

  • Funktionen:
Grunddaten
Veranstaltungsart Vorlesung Veranstaltungsnummer 3313027
Semester WiSe 2019/20 SWS 4
Rhythmus Moodle-Link  
Veranstaltungsstatus Freigegeben für Vorlesungsverzeichnis  Freigegeben  Sprache deutsch
Belegungsfrist Es findet keine Online-Belegung über AGNES statt!

Termine

Gruppe 1 iCalendar Export iCalendar Export
  Tag Zeit Rhythmus Dauer Raum Raum-
plan
Lehrperson Status Bemerkung fällt aus am Max. Teilnehmer
iCalendar Export Di. 15:00 bis 17:00 wöch
Einzeltermine anzeigen
Erwin Schrödinger-Zentrum /Modul 1 - 1307 Rudower Chaussee 26 (RUD26) - (Unterrichtsraum) Köbler findet statt     1000
iCalendar Export Mi. 13:00 bis 15:00 wöch
Einzeltermine anzeigen
Erwin Schrödinger-Zentrum /Modul 1 - 1307 Rudower Chaussee 26 (RUD26) - (Unterrichtsraum) Köbler findet statt     1000
Gruppe 1:
 


Zugeordnete Person
Zugeordnete Person Zuständigkeit
Köbler, Johannes , Prof. Dr.
Studiengänge
Abschluss Studiengang LP Semester
Bachelor of Science  Info, Mathe und Physik Monobachelor ( Vertiefung: kein LA; POVersion: 2019 )   -  
Bachelor of Science  Informatik Beifach ( POVersion: 2009 )   -  
Bachelor of Arts  Informatik Kernfach ( POVersion: 2004 )   -  
Bachelor of Arts  Informatik Kernfach ( POVersion: 2010 )   -  
Bachelor of Science  Informatik Kernfach ( Vertiefung: kein LA; POVersion: 2015 )   -  
Bachelor of Science  Informatik Kernfach ( Vertiefung: mit LA-Option; POVersion: 2015 )   -  
Bachelor of Science  Informatik Monobachelor ( POVersion: 2009 )   -  
Bachelor of Science  Informatik Monobachelor ( Vertiefung: kein LA; POVersion: 2015 )   -  
Bachelor of Arts  Informatik Zweitfach ( POVersion: 2004 )   -  
Bachelor of Arts  Informatik Zweitfach ( POVersion: 2010 )   -  
Bachelor of Science  Informatik Zweitfach ( POVersion: 2010 )   -  
Bachelor of Science  Informatik Zweitfach ( Vertiefung: mit LA-Option; POVersion: 2015 )   -  
Bachelor of Science  Informatik Zweitfach ( Vertiefung: kein LA; POVersion: 2015 )   -  
Bachelor of Arts  Informatik Zweitfach ( Vertiefung: kein LA; POVersion: 2015 )   -  
Bachelor of Arts  Informatik Zweitfach ( Vertiefung: mit LA-Option; POVersion: 2015 )   -  
Bachelor of Arts  Informationsman. & -tech. Monobachelor ( POVersion: 2012 )   -  
Bachelor of Arts  Informationsman. & -tech. Monobachelor ( Vertiefung: kein LA; POVersion: 2015 )   -  
Bachelor of Arts  Informationsman. & -tech. Monobachelor ( Vertiefung: kein LA; POVersion: 2017 )   -  
Zuordnung zu Einrichtungen
Einrichtung
Mathematisch-Naturwissenschaftliche Fakultät, Institut für Informatik
Inhalt
Kommentar

Die Komplexitätstheorie beschäftigt sich mit der Frage, welcher Aufwand, etwa an Rechenzeit oder Speicherplatz, erforderlich ist, um bestimmte algorithmische Probleme zu lösen. Dieses Modul ist eine Einführung in die Themen und Methoden der Komplexitätstheorie. Im Mittelpunkt stehen dabei die grundlegenden Zeit- und Platzkomplexitätsklassen.

Konkrete Inhalte des Moduls sind: Hierarchiesätze, NP-Vollständigkeit und die P vs NP-Frage, Orakelmodelle und die polynomielle Hierarchie, deskriptive Komplexität und der Satz von Fagin, Platzkomplexität und der Satz von Savitch, die Klassen L, NL und PSPACE.

Strukturbaum

Die Veranstaltung wurde 1 mal im Vorlesungsverzeichnis WiSe 2019/20 gefunden:

Humboldt-Universität zu Berlin | Unter den Linden 6 | D-10099 Berlin