Das Sortierproblem Datensätze sortieren Das Sortierproblem besteht darin, Datensätze eines gegebenen Datenbestands sortiert anzuordnen. Im Folgenden geht es darum, das Sortierproblem und seine Relevanz in der Informatik genauer zu betrachten. q Startseite 1. Komplexität von Algorithmen und Problemen - 1. Fallstudie - Sortieren / Präzisierung von Berechnungskomplexität - 1. Das Sortierproblem + 1. Einen Datenbestand durchsuchen + 2. Beschreibung des Sortierproblems + 3. Entwicklung von Sortierverfahren + 2. Sortieralgorithmen + 1. Sortieren durch Auswählen / Selectionsort + 2. Sortieren durch Einfügen / Insertionsort + 3. Sortieren durch Aufsteigen / Bubblesort + 4. Sortieren durch Zerlegen / Quicksort + 5. Anwendung der Sortieralgorithmen + 3. Laufzeitverhalten + 1. Laufzeitmessungen + 2. Systematische Bestimmung des Laufzeitverhaltens + 3. Zusammenfassung + 4. Aufwandsanalyse + 1. Beschreibung der Problemgröße + 2. Modellierung der Kosten + 3. Kostenanalyse für Sortieralgorithmen + 5. Asymptotisches Wachstumsverhalten + 1. Vergleich von Kostenfunktionen + 2. Asymptotisches Wachstumsverhalten als Vergleichskriterium + 3. Einordnung in Komplexitätsklassen + 6. Die Komplexität des Sortierproblems + 1. Zeitkomplexität von Problemen + 2. Beschreibung von Sortiervorgängen mit Entscheidungsbäumen + 3. Die Zeitkomplexität des Sortierproblems + 2. Fallstudie - Das Affenpuzzle / Praktische Anwendbarkeit von Algorithmen + 1. Das Affenpuzzle + 2. Komplexitätsaussagen + 3. Fallstudie - Primfaktorzerlegung / Praktische Anwendbarkeit von Algorithmen + 1. Primzahlen und das Faktorisierungsproblem + 2. Ein einfaches Faktorisierungsverfahren + 3. Laufzeitmessungen + 4. Aufwandsabschätzungen + 5. Komplexitätsbetrachtungen + 4. Fallstudie - Rundreiseprobleme / Schwer lösbare Probleme + 1. Rundreiseprobleme + 2. Rundreisealgorithmen + 3. Komplexitätsbetrachtungen + 4. Die Klassen P und NP + 5. NP-vollständige Probleme + 5. Fallstudie - Das Rucksackproblem / Lösen schwieriger Probleme mit Näherungsverfahren + 1. Das Rucksackproblem + 2. Eine einfacher Lösungsalgorithmus + 3. Komplexitätsbetrachtungen + 4. Lösung mit einem genetischen Algorithmus + 5. Implementierung des genetischen Algorithmus