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

Einführung in die Beweiskomplexität - Detailseite

  • Funktionen:
Grunddaten
Veranstaltungsart Vorlesung Veranstaltungsnummer 3313045
Semester SoSe 2020 SWS 3
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. 09:00 bis 11:00 wöch
Einzeltermine anzeigen
Erwin Schrödinger-Zentrum /Modul 1 - 1303 Rudower Chaussee 26 (RUD26) - (Unterrichtsraum) Berkholz findet statt     1000
iCalendar Export Mi. 11:00 bis 13:00 14tgl.
Einzeltermine anzeigen
Erwin Schrödinger-Zentrum /Modul 1 - 1307 Rudower Chaussee 26 (RUD26) - (Unterrichtsraum) Berkholz findet statt     1000
Gruppe 1:
 


Zugeordnete Person
Zugeordnete Person Zuständigkeit
Berkholz, Christoph
Studiengänge
Abschluss Studiengang LP Semester
Master of Education (ISS)  Informatik 1. Fach ( Vertiefung: mit LA-Option; POVersion: 2015 )   -  
Master of Education (GYM)  Informatik 1. Fach ( Vertiefung: mit LA-Option; POVersion: 2015 )   -  
Master of Education (ISG)  Informatik 1. Fach ( Vertiefung: mit LA-Option; POVersion: 2018 )   -  
Master of Education (ISS)  Informatik 2. Fach ( Vertiefung: mit LA-Option; POVersion: 2015 )   -  
Master of Education (BS)  Informatik 2. Fach ( Vertiefung: mit LA-Option; POVersion: 2015 )   -  
Master of Education (GYM)  Informatik 2. Fach ( Vertiefung: mit LA-Option; POVersion: 2015 )   -  
Master of Education (ISG)  Informatik 2. Fach ( Vertiefung: mit LA-Option; POVersion: 2018 )   -  
Master of Science  Informatik Hauptfach ( Vertiefung: kein LA; POVersion: 2015 )   -  
Master of Science  Wirtschaftsinformatik Hauptfach ( Vertiefung: kein LA; POVersion: 2016 )   -  
Zuordnung zu Einrichtungen
Einrichtung
Mathematisch-Naturwissenschaftliche Fakultät, Institut für Informatik
Inhalt
Kommentar

Die Beweiskomplexität (engl. propositional proof complexity) ist ein Forschungsgebiet innerhalb der theoretischen Informatik, das die Länge von Beweisen in aussagenlogischen Beweissystemen untersucht. Der Forschungszweig entstand aus der Frage heraus, ob die Klasse NP aller Entscheidungsprobleme mit Beweisen polynomieller Länge unter Komplement abgeschlossen ist (NP vs. co-NP Problem) und befasst sich heutzutage hauptsächlich mit der Verbindung zwischen Beweissystemen und Algorithmen für NP-schwere Probleme. Bekanntestes Beispiel hierfür ist der Resolutionskalkül, welcher die Grundlage für nahezu alle modernen SAT-Solver bildet.

Die Lehrveranstaltung bietet eine Einführung in das Forschungsgebiet und seine Methoden. Einen besonderen Schwerpunkt bilden hierbei die vielfältigen Verbindungen zu benachbarten Gebieten, wie der Logik, der künstlichen Intelligenz und der linearen Optimierung.

Strukturbaum

Die Veranstaltung wurde 1 mal im Vorlesungsverzeichnis SoSe 2020 gefunden:

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