Springe zum Hauptinhalt
Professur Theoretische Informatik
Ehemalige Professur Theoretische Informatik
Professur Theoretische Informatik 

Theoretische Informatik I

Wintersemester 2001/2002

Vorlesung: Theoretische Informatik I

SWS (V/Ü/P)

4/2/0

Vorkenntnisse

keine

Semesterempfehlung

5. oder 7.

Inhalt

Es werden algorithmische Lösungen für verschiedene Standardprobleme behandelt. Relativ breiten Raum nehmen die Graphalgorithmen ein. Bei ihnen geht es um das systematische Aufsuchen aller Knoten eines beliebigen, gerichteten oder ungerichteten Graphen. Als die beiden hauptsächlichen Lösungswege werden die Breitensuche und die Tiefensuche behandelt. Ferner werden verschiedene Verfahren für die Bestimmung kürzester Wege und von minimalen Spannbäumen in Graphen betrachtet. Weiterhin werden effiziente Algorithmen zur Lösung verschiedener anderer Probleme eingeführt. Bei den betrachteten Problemen handelt es sich um das Sortieren, das Auswahlproblem und die Matrizenmultiplikation. Eine generelle Strategie zum Vermeiden von Sackgassen im Problemlösungsprozess ist das Backtracking. Zur Beschränkung der möglichen Lösungswege bei einer Aufgabe werden Branch-and-Bound-Verfahren eingesetzt. Schließlich werden noch die lokale Suche in Graphen und das Dynamische Programmieren behandelt.

Literatur

Kingston, J.H.: Algorithms and Data Structures. Design, Correctness, Analysis. 2 Addison-Wesley, Harlow, 1998.
Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press, Cambridge, MA, 1994.
Aho; Hopcroft; Ullman: Data structures and algorithms
Ottmann; Widmayer: Algorithmen und Datenstrukturen

Links

Folien zur Vorlesung:Adjazenzlistendarstellung von Graphen
Breitensuche
Anwendungen der Breitensuche
Tiefensuche
Topologische Sortierung (DFS)
Starke Zusammenhangskomponenten (DFS)
Zweifache Zusammenhangskomponenten (ZHK)
Low-Array Algorithmus (DFS)
Floyd-Warshall Algorithmus
Dijkstra Algorithmus
Sortieralgorithmen
Branch and Bound - Traveling Salesman Problem
Branch and Bound - TSP - "neu
Multiplikation großer Zahlen
Matrizen-Multiplikation - Divide and Conquer
dyn. Programmieren - Handlungsreisenden-Problem
dyn. Programmieren - Matrizenmultiplikation
dyn. Programmieren - Probleme auf Worten
dyn. Programmieren - optimaler statischer BinSBaum
Greedy Algorithmen - Huffman Code

Folien zur Vorlesung im WS99/00:Teil 1
Teil 2

Algorithmen-Blätter:Tiefensuche
Kantentypen der Tiefensuche
Low-Array
Zweifache Zusammenhangskomponenten
Wurzel
Longpath
Floyd-Warshall-Algorithmus
Dijkstra-Algorithmus
Dijkstra-Algorithmus mit AVL-Baum
Kruskal-Algorithmus
Insertion-Sort
Bubble-Sort

Übungsaufgaben:1. ÜbungLösungen
2. ÜbungLösungen
3. ÜbungLösungen
4. ÜbungLösungen
5. ÜbungLösungen
6. ÜbungLösungen
7. ÜbungLösungen
8. ÜbungLösungen
9. ÜbungLösungen
10. ÜbungLösungen
11. ÜbungLösungen
12. ÜbungLösungen
13. ÜbungLösungen
14. ÜbungLösungen