Algorithmen und Datenstrukturen I

Semester: WI/2 
Umfang /SWS): 2 + 2 

Inhalt:

1. Grundlegendes zum Begriff Algorithmus 
  1.1 Charakterisierung des Begriffs Algorithmus 
  1.2 Grenzen der Algorithmisierbarkeit

2. Iterative Algorithmen 
  2.1 Beispiele Fakultät, ggT, Matrizenmultiplikation

3. Analyse von Algorithmen 
  3.1 Komplexitätsmaße, Größenordnungen der Komplexität 
  3.2 Das Scan-Line-Prinzip zur Gestaltung linearer Algorithmen 
  3.3 Möglichkeiten der Behandlung schwieriger Probleme 

4. Rekursion 
  4.1 Baumdarstellung rekursiver Algorithmen 
  4.2 Betrachtungen zur Effizienz der Rekursion 
  4.3 Das Teile-und-Herrsche-Prinzip

5. Sortieren 
  5.1 Bestimmung der Komplexität von Sortierverfahren 
  5.2 Sortieren von Arrays: Sortieren, durch Einfügen, Auswählen und Austauschen
       (Bubblesort, Shakersort),Quicksort 
  5.3 Sortieren von sequentiellen Files: natürliches Mischen 

6. Beispiele für das Teile-und-Herrsche-Verfahren 
  6.1 Türme von Hanoi, Permutationen, Fraktale Strukturen