Spreading excellence and disseminating the cutting edge results of our research and development efforts is crucial to our institute. Check for our educational offers for Bachelor, Master and PhD studies at the University of Innsbruck!

Algorithmen und Datenstrukturen SS 2009

Horizontal Tabs

General information
Language: 
German
Time: 
Fridays 12.15 - 15.00
Location: 
HS D

Das Ziel dieser Vorlesung besteht darin, eine breite Palette wichtiger und nützlicher Algorithmen vorzustellen: Verfahren zur Problemlösung, die sich auf einem Computer implementieren lassen.
Wir beschäftigen uns mit verschiedenen grundsätzlichen Anwendungsgebieten (Sortieren, Suchen, Graphen etc.) und konzentrieren uns dabei immer auf die grundlegenden Algorithmen, die man als Informatiker unbedingt kennen sollte. Verschiedene Datenstrukturen eignen sich besonders zur Umsetzung der jeweiligen Algorithmen, weshalb diese in Kombination vorgestellt werden. Darüber hinaus wird eine Technik eingeführt, die es erlaubt, die Effizienz verschiedener Algorithmen miteinander zu verleichen.
Grundlage der praktischen Übungen zu dieser Vorlesung ist die Programmiersprache C.

Mailinglist

Alle Teilnehmer der Lehrveranstaltung werden gebeten, sich bei der Mailingliste für diesen Kurs anzumelden, die zur Verbreitung kurzfristiger wichtiger Ankündigungen u.ä. dient.

Schedule

Fr 06.03.2009 Grundlagen
Fr 13.03.2009 Einfache Sortierverfahren: InsertionSort, SelectionSort, BubbleSort
Fr 20.03.2009 Spezielle (BucketSort) und höhere Sortierverfahren (MergeSort), Master-Theorem
Fr 27.03.2009 Höhere Sortierverfahren: QuickSort, HeapSort
Fr 03.04.2009 Suchen in Mengen: Hashing
Fr 24.04.2009 Suchen in Mengen: AVL-Bäume
Fr 29.05.2009 Suchen in Mengen: B-Bäume; Einführung Graphen
Fr 05.06.2009 Graphen: Kürzeste Pfade - Dijkstra, Bellman-Ford
Fr 12.06.2009 Graphen: Kürzeste Pfade - Floyd-Warshall, A*; Zufallspolygone
Fr 19.06.2009 Graphen: Minimum Spanning Trees, Topologische Sortierung
Fr 26.06.2009

Graphen: Touren - Euler, Hamilton, TSP

Fr 03.07.2009 Klausur, Anmeldung erforderlich!
Description: 

Analyse, Aufwandsquantifizierung und Implementierung von Algorithmen: zum Sortieren, zum Suchen in Mengen, in Bäumen und Graphen; Charakteristika effizienter Algorithmen und der zugehörigen Datenstrukturen

Exams: 

Die Ergebnisse der ersten Klausur vom 3. Juli 2009 finden Sie hier.
Die Ergebnisse der zweiten Klausur vom 5. Februar 2010 finden Sie hier.