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

Exakte Exponentialzeit-Algorithmen für NP-vollständige Probleme - Detailseite

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

Termine

Gruppe 1
Tag Zeit Rhythmus Dauer Raum Raum-
plan
Lehrperson Status Bemerkung fällt aus am Max. Teilnehmer
Fr. 09:00 bis 11:00 wöch Erwin Schrödinger-Zentrum /Modul 1 - 1305 Rudower Chaussee 26 (RUD26) - (Unterrichtsraum)   fällt aus     1000
Fr. 11:00 bis 13:00 14tgl. Erwin Schrödinger-Zentrum /Modul 1 - 1305 Rudower Chaussee 26 (RUD26) - (Unterrichtsraum)   fällt aus     1000
Gruppe 1:
 

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 (BS)  Informatik 2. Fach ( Vertiefung: mit LA-Option; POVersion: 2015 )   -  
Master of Education (ISS)  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  Wirtschaftsinformatik Hauptfach ( Vertiefung: kein LA; POVersion: 2016 )   -  
Zuordnung zu Einrichtungen
Einrichtung
Mathematisch-Naturwissenschaftliche Fakultät, Institut für Informatik
Inhalt
Kommentar

Until today we do not know how to solve NP-complete problems quickly, that is, in polynomial time. In fact, it is a widely accepted assumption that P is not equal to NP, and hence, we assume that we will never be able to find polynomial-time algorithms for these problems. NP-complete problems are considered equivalent up to polynomial time reductions. Nevertheless, their exponential-time properties vary widely.

The lecture covers the most common algorithmic techniques that are employed to solve NP-complete problems significantly faster than via exhaustive search. These techniques include dynamic programming, the inclusion-exclusion principle, measure and conquer, fast subset convolution and local search. These methods are applied to solve problems of strong
practical relevance, such as partition problems, covering and coloring problems, TSP, Hamilton Path, SAT, and many more.

Participants should have a strong interest in theoretical computer science and design and analysis of algorithms. The course is self-contained in the sense that all relevant concepts will be introduced in the lectures.

Bemerkung

Die Vorlesung findet in Englisch statt.

Strukturbaum

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