Vorlesung
Algorithmen und Datenstrukturen
|
| Lernziele
Die Studierenden verstehen die ineinandergreifende Beziehung zwischen Algorithmen und Datenstrukturen. Sie kennen die wichtigsten Datenstrukturen, ihre effektive Implementierung und wie die in der STL vorhandenen Datenstrukturen verwendet werden können. Sie beherrschen allgemein anwendbare Methoden zum Entwurf von Algorithmen und können die grundlegenden Techniken zur Analyse von Algorithmen anwenden. Sie wissen, dass es Grenzen gibt für die algorithmische Lösbarkeit von Problemen.
Inhalt
| 
| 1. Berechenbarkeit und Komplexität:Churche-These, Halte-Problem, asymptotische Notation,Komplexitätsklassen P, NP,NP-vollständig, NP-hart |
|
|
| 2. Einfache Datenstrukturen: Abstrakter Daten-Typ ADT, Listen, Keller, Schlangen, Bäume, Design der STL |
|
|
| 3. Sortieren: Merge-Sort, Heap-Sort, Quick-Sort, Shell-Sort, untere Schranke f. vergleichsbasiertes Sortieren (Entscheidungsbäume), count-Sort/Bucket-Sort, Radix-Sort, externe Sortierverfahren |
|
|
| 4. Suchen: lineare Suche, binäre Suche, Interpolations-Suche, Hash-Verfahren, AVL-Bäume, Rot-Schwarz Bäume, B-Bäume, Splay-Trees, Skip-Listen |
|
|
| 5. Graphen-Algorithmen: Darstellung von Graphen, Breiten und Tiefen-Suche, Euler-Wege, Hamilton-Wege, kürzeste-Wege (Bellman-Ford, Dijkstra-Algorithmus, Floyd-Warshall), minimale Spannbäume (Kruskal, Prim), Flüsse in Netzwerken (Ford-Fulkerson), Matching |
|
|
| 6. Entwurfs-Methoden: Divide and Conconquer, Dynamisches Programmieren, Greedy-Methoden, Back-Tracking, Branch and Bound, probabilistische Algorithmen, Approximations-Algorithmen |
|
|
| 7. String Matching Rabin-Karp, Knuth-Morris-Pratt, Boyer-Moor |
|
|
|
|
|
hs-ulm.de