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

Komplexität Boolescher Funktionen - Detailseite

  • Funktionen:
  • Online Belegung noch nicht möglich oder bereits abgeschlossen
Grunddaten
Veranstaltungsart Seminar Veranstaltungsnummer 3313075
Semester WiSe 2021/22 SWS 2
Rhythmus Moodle-Link  
Veranstaltungsstatus Freigegeben für Vorlesungsverzeichnis  Freigegeben  Sprache deutsch
Belegungsfristen - Eine Belegung ist online erforderlich
Veranstaltungsformat Präsenz

Termine

Gruppe 1
Tag Zeit Rhythmus Dauer Raum Raum-
plan
Lehrperson Status Bemerkung fällt aus am Max. Teilnehmer
-.  bis  Block     findet statt     15
Gruppe 1:
Zur Zeit keine Belegung möglich

Studiengänge
Abschluss Studiengang LP Semester
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 1. Fach ( Vertiefung: mit LA-Option; POVersion: 2018 )   -  
Master of Education (ISG)  Informatik 2. Fach ( Vertiefung: mit LA-Option; POVersion: 2018 )   -  
Master of Science  Informatik Hauptfach ( Vertiefung: kein LA; POVersion: 2015 )   -  
Zuordnung zu Einrichtungen
Einrichtung
Mathematisch-Naturwissenschaftliche Fakultät, Institut für Informatik
Inhalt
Kommentar

In diesem Seminar befassen wir uns mit der Komplexität von booleschen Funktion in eingeschränkten Berechnungsmodellen, wie Schaltkreisen oder Entscheidungsdiagrammen.

Im Gegensatz zur klassischen Komplexitätstheorie, in der boolesche Funktionen bzw. Entscheidungsprobleme bezüglich ihres Ressourcenverbrauchs auf Turingmaschinen charakterisiert werden und Härtebeweise häufig auf unbewiesenen Annahmen, wie P≠NP, beruhen, können untere Schranken an die Größe von bestimmten Schaltkreisen und Entscheidungsbäumen, die konkrete Funktionen berechnen, ohne komplexitätstheoretische Annahmen bewiesen werden.

Ziel des Seminars ist es, verschiedene Berechnungsmodelle für boolesche Funktionen zu kennenzulernen und sich Techniken zum Beweisen unterer Schranken anzueignen.

Strukturbaum

Keine Einordnung ins Vorlesungsverzeichnis vorhanden. Veranstaltung ist aus dem Semester WiSe 2021/22. Aktuelles Semester: WiSe 2022/23.
Humboldt-Universität zu Berlin | Unter den Linden 6 | D-10099 Berlin