252-0851-00L  Algorithmen und Komplexität

SemesterHerbstsemester 2014
DozierendeT.  Holenstein
Periodizitätjährlich wiederkehrende Veranstaltung
LehrspracheDeutsch


KurzbeschreibungEinführung: RAM-Maschine, Datenstrukturen; Algorithmen: Sortieren, Medianbest., Matrixmultiplikation, kürzeste Pfade, min. spann. Bäume; Paradigmen: Divide&Conquer, dynam. Programmierung, Greedy; Datenstrukturen: Suchbäume, Wörterbücher, Priority Queues; Komplexitätstheorie: Klassen P und NP, NP-vollständig, Satz von Cook, Beispiele für Reduktionen.
LernzielNach dieser Vorlesung kennen die Studierenden einige Algorithmen und übliche Werkzeuge. Sie kennen die Grundlagen der Komplexitätstheorie und können diese verwenden um Probleme zu klassifizieren.
InhaltDie Vorlesung behandelt den Entwurf und die Analyse von Algorithmen und Datenstrukturen. Die zentralen Themengebiete sind: Sortieralgorithmen, Effiziente Datenstrukturen, Algorithmen für Graphen und Netzwerke, Paradigmen des Algorithmenentwurfs, Klassen P und NP, NP-Vollständigkeit, Approximationsalgorithmen.
SkriptJa. Wird zu Beginn des Semesters verteilt.