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

Modulnummer: Q06-11
Englischer Titel: Exact exponential algorithms for NP-complete problems
Leistungspunkte: 6
Lehrperson: Siebertz/Kratsch

Empfohlene Vorkenntnisse

Grundkenntnisse Algorithmik

Zwingende Voraussetzungen

keine

Inhalt

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.

Erforderliche Arbeitsleistungen für LP-Vergabe und Prüfungszulassung

- schriftlich eingereichte und/oder mündlich vorgetragene Lösungen zu Aufgaben
- aktive Teilnahme an Vorlesung und Übung

Lehrveranstaltungen

6 LP: 3-5 SWS

Vorlesung: 3 SWS
Übung: 1 SWS

Zugeordneter Vertiefungsschwerpunkt

Algorithmen und Modelle: ja
Modellbasierte Systementwicklung: nein
Daten- und Wissensmanagement: nein
Ohne Vertiefungsschwerpunkt: nein

Sprache im Modul

Deutsch: nein
Englisch: ja

Angeboten für Studiengänge

M. Sc.: ja
M. Ed.: ja
Wirtschaftsmaster: ja

Angeboten im

Wintersemester: ja
Sommersemester: nein

Turnus

Alle zwei Jahre