Vorlesung aus Algorithmen und Datenstrukturen, SS 2001

Aktuelle Hinweise

• Algorithmenbeschreibungsprache Jana (PDF, HTML)

Inhalt der Vorlesung

• Einleitung und Übersicht
• Grundbegriffe
• Struktur und Entwurf
• Algorithmen mit Gedächtnis
• Elementare, höhere und abstrakte Datenstrukturen
• Rekursive Algorithmen
• Komplexität von Algorithmen
• Verifikation von Algorithmen
• Algorithmen mit Zufallszahlen
• Sortier- und Suchalgorithmen
• Algorithmen auf Zeichenketten
• Exhaustionsalgorithmen
• Geometrie- und Graph-Algorithmen
• Die Welt der Algorithmen

Die Definition des Begriffs "Algorithmus"

• Pomberger
  Ein Algorithmus ist eine präzise, d.h. in einer festgelegten Sprache abgefaßte, endliche Beschreibung eines schrittweisen Problemlösungsverfahrens zur Ermittlung gesuchter Größen aus gegebenen Größen, in dem jeder Schritt aus einer Anzahl ausführbarer eindeutiger Aktionen und einer Angabe über den nächsten Schritt besteht. Ein Algorithmus heißt abbrechend, wenn er die gesucht Größe nach endlich vielen Schritten liefert, andernfalls heißt der Algorithmus nicht abbrechend. 
• Knuth
  • Ein Algorithmus muß nach endlich vielen Schritten enden.
  • Jeder Schritt eines Algorithmus muß exakt beschrieben sein; die in ihm verlangten Aktionen müssen präzise formuliert und in jedem Falle eindeutig interpretierbar sein.
  • Ein Algorithmus hat keine, eine oder mehrere Eingangsgrößen, d.h. Größen, die von ihm benutzt und deren Werte vor Beginn seiner Ausführung festgelegt werden müssen.
  • Ein Algorithmus hat eine oder mehrere Ergebnisgrößen, d.h. Größen, deren Werte in Abhängigkeit von den Eingangsgrößen während der Ausführung des Algorithmus berechnet werden.
  • Ein Algorithmus muß so geartet sein, daß die in ihm verlangten Aktionen im Prinzip von einem Menschen in endlicher Zeit mit Papier und Bleistift ausgeführt werden können.
• Aho, Hopcroft, Ullman
  Ein Algorithmus ist eine endliche Folge von Instruktionen, die alle eindeutig interpretierbar und mit endlichem Aufwand in endlicher Zeit ausführbar sind. Algorithmen enthalten Instruktionen zur Formulierung von (beliebig vielen) Wiederholungen anderer Instruktionen. Unabhängig von den Werten der Eingangsgrößen endet ein Algorithmus stets nach endlich vielen Instruktionsschritten. Ein Programm ist dann ein Algorithmus, wenn für alle möglichen Eingabewerte sichergestellt ist, daß keine Instruktion unendlich oft wiederholt wird.
• Kronsjö
  Ein Verfahren, beschrieben durch eine endliche Menge von eindeutig interpretierbaren Regeln, das eine endlich lange Folge von Operationen zur Lösung eines Problems oder einer speziellen Problemklasse beschreibt, wird Algorithmus genannt.
• Bauer, Goos
  Ein Algorithmus ist eine präzise, d.h. in einer festgelegten Sprache abgefaßte, endliche Beschreibung eines allgemeinen Verfahrens unter Verwendung ausführbarer elementarer (Vearbeitungs-) Schritte.
• Rechenberg
  Ein Algorithmus ist ein endliches schrittweises Verfahren zur Berechnung gesuchter aus gegebenen Größen, in dem jeder Schritt aus einer Anzahl ausführbarer eindeutiger Operationen und einer Angabe über den nächsten Schritt besteht.

Literatur

• A.V. Aho, J.E. Hopcroft, J.D. Ullman: Data Structures and Algorithms. Addison-Wesley, 1983.
• O.J. Dahl, E.W. Dijkstra, C.A.R. Hoare: Structured Programming. Academic Press, 1972.
• E. Horowitz, S. Sahni: Fundamentals of Computer Algorithms. Pitman, London, 1979.
• D.E. Knuth: The Art of Computer Programming. Addison-Wesley, 1973.
  • Vol. 1: Fundamental Algorithms.
  • Vol. 2: Seminumerical Algorithms.
  • Vol. 3: Sorting and Searching.
• R. Sedgewick: Algorithms. Addison-Wesley, 1983.
• N. Wirth: Algorithmen und Datenstrukturen. Teubner Studienbücher Informatik, 1986.
• G. Pomberger, G. Blaschek: Software Engineering, 2. Auflage,  Hanser Verlag, 1996.
• G. Pomberger, P. Rechenberg: Informatik-Handbuch, 2. Auflage, Hanser Verlag, 1999.