Vorlesung Datenstrukturen Algorithmen und Programmierung 2

In der Vorlesung DAP1 stand der Entwurf von Software, also Programmierung und Eigenschaften von Programmen, im Vordergrund. Ein Softwareprodukt ist aber erst dann rundum gut, wenn es effizient arbeitet. Daher behandeln wir in der Vorlesung DAP2 Datenstrukturen und Entwurfsmethoden für effiziente Algorithmen. Naive Lösungen algorithmischer Probleme können -praktisch unrealisierbar- sein, da die benötigten Ressourcen an Rechenzeit und/oder Speicherplatz nicht zur Verfügung stehen. Mit Hilfe des Einsatzes geeigneter Datenstrukturen und Methoden lassen sich viele algorithmische Probleme effizient lösen. Die Effizienz kann sich im praktischen Gebrauch erweisen und zuvor experimentell belegt werden. Besser ist es jedoch, ein Programm mit Gütegarantie herzustellen. Dies bedeutet den formalen Beweis dafür, dass die Datenstruktur bzw. der Algorithmus das Gewünschte leistet (Korrektheitsbeweis), sowie eine Abschätzung der benötigten Ressourcen (Analyse). Daher gehören zu dieser Vorlesung stets auch Korrektheitsbeweise und Analysen von Laufzeiten und Speicherplatzbedarf. Um für ein gegebenes Problem einen effizienten Algorithmus zu entwickeln, benötigt man das notwendige Handwerkszeug. Dieser soll in der Vorlesung vermittelt und für praktische Aufgabenstellungen ausgewertet werden. Die Umsetzung effizienter Algorithmen erfordert schließlich noch den Einsatz passender Datenstrukturen, denn geeignete effiziente Datenstrukturen bilden das Kernstück vieler effizienter Algorithmen. Die von uns behandelten Probleme sind so ausgewählt, dass es sich einerseits um wichtige und interessante Probleme handelt und andererseits bei der Lösung dieser Probleme allgemeine Prinzipien und Methoden erlernt werden können. Dazu gehören Sortieren und Suchen oder Graphenalgorithmen wie die Suche nach kürzesten Wegen. Weitere Angaben sind auch im Modulhandbuch für die Bachelor-Studiengänge zu finden: http://dekanat.cs.uni-dortmund.de/Studium/modulkataloge.html Literatur Die in der Vorlesung benutzten Folien werden online zur Verfügung gestellt. Introduction to Algorithms. Cormen, Leisserson, Rivest. MIT Press. Algorithm Design. Kleinberg, Tardos. Addison Wesley. (Ist etwas anspruchsvoller) Die in der Vorlesung benutzten Folien werden online zur Verfügung gestellt. Introduction to Algorithms. Cormen, Leisserson, Rivest. MIT Press. Algorithm Design. Kleinberg, Tardos. Addison Wesley. (Ist etwas anspruchsvoller) Lehrstuhl Informatik II Technische Universität Dortmund SoSe 2012 Bachelor Informatik Prof. Dr. Sohler Christian