Übung Algorithmen und Datenstrukturen WS 09/10

Schwerpunkt Tutorial Visualisierung Folien aus der Übung
Syntaxdiagramme, Rücksprungalgorithmus und EBNF syndia2.pdf j-Algo Syntax
EBNF
formale Sprachen (1)
formale Sprachen (2)
Regeln zur Bestimmung von Objektsprachen regeln.pdf keine EBNF
formale Sprachen (1)
formale Sprachen (2)
Fixpunktsemantik von Kristian Scholze keine Syntax
formale Sprachen (2)
pulsierender Speicher puls.pdf oder
von Kristian Scholze
j-Algo keine
C-Programmierung kein Algorithmus bekannt:-(
Tipp:
  • Hinweise durchlesen: cprog.pdf
  • Gegebenfalls ein Buch lesen, z.B. "C als erste Programmiersprache. Vom Einsteiger zum Profi" von Goll,
    öckl und Dausmann
  • Aufgaben des C-Kurses lösen
  • Alte Klausuraufgaben lösen. Aufgaben ohne Lösung entweder selber testen, oder Lösungsvorschlag an den Tutor des Vertrauens senden.
Compiler und Debugger. Für die meisten Platformen ist der gcc und gdb verfügbar. Windowsnutzer können dazu z.B. Dev-C++ nutzen.
Tutorials und Nachschlagewerke sind hier verlinkt.
keine
Sortieralgorithmen (Quick-, Shell- und Heapsort) sort.pdf Aufgaben- generatoren und -löser von Andreas Ecke: Quicksort, Shellsort, Heapsort Sortieren (1)
Sortieren (2)
Knuth-Morris-Pratt kmp.pdf j-Algo Knuth-Morris-Pratt
AVL-Bäume avl.pdf j-Algo AVL-Bäume
topologische Sortierung graphen.pdf keine Graphen(1)
Tiefensuche (DFS) und Breitensuche (BFS)
Floyd-Warshall-Algorithmus floyd.pdf j-Algo (als algebraisches Pfadproblem) Graphen(2)
Dijkstra-Algorithmus dijkstra.pdf j-Algo Graphen(2)
Algebraisches Pfadproblem keins j-Algo Algebraisches Pfadproblem
Iterative Verfahren von Kristian Scholze keine Iterative Verfahren
Backtracking Backtracking ist eine allgemeine Lösungsstrategie, daher gibt es kein festes Vorgehen.
Tipps:
  • Wikipedia lesen: Backtracking
  • AGS 10.10, 10.12 und 10.13 anschauen. Hierbei besonders bei allen Aufgaben auf die Definitionen der Teillösung, Gesamtlösung, Erweiterung zulässig, Erweiterung der Teillösung und Anfangslösung achten.
  • Das Verfahren ist im wesentlichen eine Tiefensuche. (Insbesondere beim Aufstellen der Berechnungsbäume sichtbar.)
Kein "allgemeines" bekannt. Für das Labyrinthproblem ist z.B. hier etwas zu finden.