Digicampus
Vorlesung: Algorithmen für NP-harte Probleme - Details
Sie sind nicht in Stud.IP angemeldet.
Lehrveranstaltung wird online/digital abgehalten.

Allgemeine Informationen

Veranstaltungsname Vorlesung: Algorithmen für NP-harte Probleme
Semester SS 2017
Aktuelle Anzahl der Teilnehmenden 2
Heimat-Einrichtung Theoretische Informatik
Veranstaltungstyp Vorlesung in der Kategorie Lehre
Erster Termin Dienstag, 25.04.2017 14:00 - 15:30
Voraussetzungen Teilnehmer der Vorlesung sollten über gute algorithmische Kenntnisse verfügen, insbesondere im Bereich Graphenalgorithmen.
Online/Digitale Veranstaltung Veranstaltung wird online/digital abgehalten.
Hauptunterrichtssprache deutsch
Literaturhinweise Ein englischsprachiges Skript wird auf der Internetseite des Lehrstuhls (https://www.informatik.uni-augsburg.de/thi/ ) zur Verfügung gestellt werden.
Sonstiges Aktuelle Informationen zu Veranstaltungen, Skript und Übungsblättern finden Sie auf der Internetseite des Lehrstuhls (http://www.informatik.uni-augsburg.de/thi/ ).
ECTS-Punkte 8

Räume und Zeiten

Keine Raumangabe
Dienstag: 14:00 - 15:30, wöchentlich
Donnerstag: 10:00 - 11:30, wöchentlich

Kommentar/Beschreibung

NP-harte Probleme können nach heutigem Wissen nicht in polynomieller Zeit auf einem üblichen Rechner gelöst werden. Ungeachtet dessen treten solche Probleme überaus häufig in der Praxis auf, z.B. bei vielen Planungsaufgaben, und es ist von großer ökonomischer Bedeutung, sie doch noch zu lösen, zumindest "so gut wie es geht". Die Vorlesung behandelt Methoden der Algorithmentheorie, die hierfür entwickelt wurden. Einige Stichpunkte: Approximationsalgorithmen, Branch-and-Bound, Parametrisierung. Es werden auch Grenzen dieser Methoden aufgezeigt.