64-330 Vorlesung Algorithmik

Lehrende: Prof. Dr. Matthias Rarey

Veranstaltungsart: Vorlesung

Anzeige im Stundenplan: ALG - VL

Semesterwochenstunden: 4

Credits: 6,0

Unterrichtssprache: Deutsch

Min. | Max. Teilnehmerzahl: - | 75

Kommentare/ Inhalte:
Die Entwicklung von Algorithmen zur Lösung von Problemen mit dem Computer ist zentraler Bestandteil der Informatik. Fundamentale Kenntnisse in dem Prozess des Algorithmenentwurfs sind in der Informatik unabdingbar. Jeder Informatiker sollte zudem eine Reihe von grundlegenden Algorithmen und Datenstrukturen kennen, um diese als Teillösungen für komplexe Fragestellungen gewinnbringend einsetzen zu können. Aufbauend auf AD1 und FGI werden weiterführende Algorithmen und die zugrunde liegenden Analysen präsentiert. Die wichtigsten Themengebiete des Moduls umfassen:

• Weiterführende Graphalgorithmen: All-Pairs / algebraische kürzeste Wege, Netzwerk-Flussalgorithmen, Matching
  
• Effiziente Datenstrukturen: Adaptive Suchbäume, Bionomial- und Fibonacci-Heaps, Treaps
  
• Effiziente numerische Verfahren und Lineare Programmierung
  
• Einführung in Algorithmische Geometrie: Schnittprobleme, Algorithmen und Datenstrukturen zur Raumanfrage, Konvexe Hüllen, Voronoi-Diagramme und Delauney-Triangulierung, kleinste umschließende Kreise
  

Lernziel:
Lernziel:
Die Vermittlung von Problemlösungskompetenz (Konzeptionalisierung und Realisierung) zur Lösung formalisierbarer, schwieriger Probleme meist kombinatorischer Struktur steht in diesem Modul im Vordergrund. Die Studierenden

•     erlernen Entwurfsmethoden für effiziente Datenstrukturen und Algorithmen
  
•     beherrschen effiziente Datenstrukturen und Algorithmen für ausgewählte Probleme
  
•     können Methoden zur Effizienzanalyse von Algorithmen und Datenstrukturen anwenden
  
•     erlernen selbständiges, kreatives Entwickeln von Algorithmen und Datenstrukturen
  
•     können die Qualität von Algorithmen und algorithmischen Ansätzen unter Effizienzaspekten einschätzen
  
•     können sich selbständig neue Algorithmen, Datenstrukturen und algorithmische Ideen und Analysen aneignen
  
•     können bekannte Algorithmen auf neue Problemstellungen übertragen und im Hinblick auf veränderte Anforderungen modifizieren
  
•     sind in der Lage, neue Algorithmen für anwendungsbezogene Problemstellungen zu entwickeln
  
•     können die Qualität von Algorithmen und algorithmischen Ansätzen im Hinblick auf Problemadäquatheit, Effizienz, Korrektheit, Vollständigkeit und praktische Verwertbarkeit beurteilen
  
• können grundlegende Beschränkungen von gegebenen Algorithmen erkennen
  
• können Informationsverarbeitungsproblemen in Hinblick auf ihre algorithmische Komplexität einschätzen
  

Literatur:
Die drei wichtisgsten Buecher:

• Thomas H. Cormen & Charles E. Leiserson & Ronald L. Rivest &
  
• Clifford Stein: Introductions to Algorithms, MIT-Press (2009), 3rd Edition
  
• M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational Geometry - Algorithms and Applications
  

Zusätzliche Hinweise zu Prüfungen:
Je nachdem, wie viele Leute teilnehmen, werden die Pruefungen muendlich oder schriftlich stattfinden. Dies wird in der Mitte des Semesters festgelegt.