Algorithmen und Komplexität 2015

Vorlesung an der DHBW Stuttgart, 2015.

Inhalte

Algorithmen sind eindeutig beschriebene Vorgehensweisen zum Lösen von bestimmten, wohldefinierten Problemen. Algorithmik beschäftigt sich mit den Eigenschaften, der Analyse, und dem Design von Alorithmen. Sie ist der Kern der Informatik.

In dieser Vorlesung beschäftigen wir uns mit dem Entwurf und der Evaluierung von Algorithmen. Wir untersuchen, wie man Stärken und Schwächen von bestimmten Algorithem charakterisieren kann, und lernen verschiedenen praktisch relevante Algorithmen und Datenstukturen kennen.

Fragestellungen sind z.B.

Wie kann ich in großen Datenmengen effizient suchen?
Wie finde ich den Weg von A nach B?
Warum ist Quicksort schneller als Sortieren durch Auswahl?
Wie kann ich die Laufzeit eines Algorithmus quantifizieren?

Im begleitenden Labor werden viele der Vorgestellten Algorithmen und Datenstrukturen in C umgesetzt.

Unterlagen zur Vorlesung

Folienskript (Fertig (!) (bis auf Typos))
Lösungen für das Zahlenreduktionsspiel
- Python-Programm
Für Neugierige: Snapshot von den Folien in Latex
Übungsaufgaben im Klausurstil
Die selben mit einigen Lösungen
Übungsklausur
Übungsklausur...mit Lösungen (Anmerkung zu 5. Heap auf Seite 12 korrigiert - danke!)

Unterlagen zum Labor

Foliensamlung (Hoffentlich fertig, Stand 10.7.2015)
- Vollversion
- Handout
Musterlösungen und Material
- Programme für Woche 1. Zum Auspacken und bauen unter Linux/OS-X/Cygwin: (g)tar xzvf WOCHE1.tgz; cd WOCHE1; make
- Programme für Woche 2
- Programm für Woche 3
- Woche 5: Navigieren im Labyrinth
  - Datentyp zum Einstieg: labsolve_defs.c
  - Beispiel-Labyrinthe
- Woche 6: Navigieren mit Terrain
  - Beispiel-Labyrinthe
    - testlab_t1.txt
    - testlab2_t2.txt
  - Lösungen:
    - Nur rechtwinklig
    - Diagonal erlaubt
  - Programm für Woche 5&Woche 6 (labsolve.c ist die einfachste Version, die ich hinbekam)
- Woche 7&8: Sortierolympiade
  - Testdateien
    - Zufällige Reihenfolge
    - Bereits sortiert
    - Absteigend sortiert
  - Programm für Woche 7&Woche 8 Implementiert sind qsort (C library), selection sort, quicksort, optimertes Quicksort, mergesort, heapsort.
- Woche 9: Binäre Suchbäume
  - Testrahmen
  - Kleines Testskript

DHBW Stuttgart, Prof. Dr. Stephan Schulz