Algorithmen In diesem Kapitel Grundlagen Rekursive Algorithmen Standardalgorithmen Komplexität von Algorithmen und Problemen Berechenbarkeit q Startseite 2. Algorithmen 1. Grundlagen + 1. Algorithmusbegriff + 1. Ein Suchproblem + 2. Anforderungen an ein Lösungsverfahren + 3. Fachkonzept - Algorithmus + 4. Darstellung von Algorithmen + 5. Bausteine von Algorithmen + 6. Algorithmen im Alltag + 7. Übungen + 2. Bedeutung - früher und heute + 1. Fallstudie - Ägyptische Multiplikation + 1. Rechnen mit Hieroglyphen + 2. Ein Multiplikationsverfahren + 3. Ein Multiplikationsalgorithmus + 4. Implementierung des Multiplikationsalgorithmus + 5. Bedeutung des Multiplikationsalgorithmus + 2. Fallstudie – PageRank + 1. Das Ranking-Problem + 2. Ein Lösungsansatz + 3. Das Zufallssurfermodell + 4. Modellerweiterung + 5. Ein Ranking-Algorithmus + 6. Gesellschaftliche Bedeutung + 7. Exkurs: Google + 3. Fallstudie - Turnierplanung + 1. Turnierplanung als Problem + 2. Ein Verfahren zur Turnierplanung + 3. Algorithmen zur Turnierplanung + 4. Automatisierung geistiger Tätigkeiten + 3. Korrektheit und Aufwand + 1. Korrektheit von Algorithmen + 1. Das Wechselwegnahmeverfahren + 2. Eine Verhaltensbeschreibung + 3. Korrektheit als Problem + 4. Korrektheit testen + 5. Korrektheit mit Python testen + 6. Korrektheit verifizieren + 7. Fachkonzept - Korrektheit + 8. Übungen + 2. Effizienz von Algorithmen + 1. Algorithmen zur ggT-Berechnung + 2. Laufzeit messen + 3. Aktionen zählen + 4. Fachkonzept - Effizienz + 5. Übungen 2. Rekursive Algorithmen + 1. Problemlösen durch Problemreduktion + 1. Einstieg - Die Türme von Hanoi + 2. Erkundung - Lösung für drei Scheiben + 3. Erkundung - Strategien für mehr als drei Scheiben + 4. Fachkonzept - Rekursive Problemreduktion + 5. Exkurs - Implementierung in Python + 2. Fallstudie - Selbstähnliche Figuren + 1. Einstieg - Eine selbstähnliche Figur + 2. Exkurs - Turtle-Grafik + 3. Übungen + 1. Hinweise - Quadratbaum + 3. Fallstudie - Rekursive Verarbeitung von Listen + 1. Einstieg - Geschachtelte Listen + 2. Fachkonzept - Liste als rekursive Datenstruktur + 3. Übungen + 4. Anwendung - Verarbeitung geometrischer Objekte + 4. Rekursive Verarbeitung natürlicher Zahlen + 1. Einstieg - Wege im Galton-Brett + 2. Fachkonzept - Natürliche Zahlen als rekursive Datenstruktur + 3. Übungen + 4. Anwendung - Operationen auf natürlichen Zahlen + 5. Rekursion und Berechnungsaufwand + 1. Exkurs - Rekursive Berechnungen mit hohem Aufwand + 2. Exkurs - Grenzen der rekursiven Verarbeitung + 6. Rekursion und Iteration + 1. Exkurs - Umwandlung rekursiver Algorithmen in iterative Algorithmen + 2. Exkurs - Umwandlung iterativer Algorithmen in rekursive Algorithmen 3. Standardalgorithmen + 1. Suchen + 1. Ein Suchproblem + 2. Entwicklung von Suchalgorithmen + 3. Lineare Suche + 4. Binäre Suche + 5. Aufwandsanalyse + 6. Anwendung der Suchalgorithmen + 2. Sortieren + 1. Das Sortierproblem + 2. Entwicklung von Sortieralgorithmen + 3. Sortierverfahren + 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 + 4. Laufzeitverhalten + 5. Aufwandsanalyse + 3. Stapel + 1. Einstieg - Auswertung von Rechentermen + 2. Konzept - Stapel + 3. Exkurs - Implementierung einer Stapel-Klasse + 4. Anwendung - Auswertung von Rechentermen + 4. Schlangen + 1. Einstieg - Warteschlangen + 2. Konzept - Schlange + 3. Exkurs - Implementierung von Schlangen in Python + 4. Übungen + 5. Graphen und ihre Verarbeitung + 1. Vernetzte Strukturen + 1. Einstieg - Routenplanung + 2. Fachkonzept - Graph + 3. Exkurs - Graphen in Anwendungssituationen + 4. Glossar - Begriffe rund um Graphen + 5. Exkurs - Soziale Netzwerke im Internet + 6. Übungen + 2. Implementierung von Graphen + 1. Repräsentation von Graphen + 1. Repräsentation mit einer Nachbarschaftstabelle + 2. Implementierung einer Nachbarschaftstabelle + 3. Repräsentation mit Nachbarschaftslisten + 4. Implementierung von Nachbarschaftslisten + 2. Eine Klasse zur Verwaltung von Graphen + 3. Eine erweiterte Klasse zur Verwaltung von Graphen + 3. Kürzeste Wege in Graphen + 1. Das Problem + 2. Der Algorithmus von Moore + 3. Der Algorithmus von Dijkstra + 4. Implementierung der Algorithmen + 5. Routenplaner + 4. Rundreisen in Graphen + 1. Das Problem + 2. Ein einfacher Lösungsalgorithmus + 3. Implementierung des Lösungsalgorithmus + 4. Anwendbarkeit des Algorithmus + 5. Näherungsverfahren + 6. Implementierung der Näherungsverfahren + 6. Binäre Suchbäume + 1. Ein Objekt in einer Datenmenge suchen + 1. Finde einen eigenen Algortihmus + 2. Der naive Suchalgorithmus + 3. Der binäre Suchalgorithmus + 4. Ein verallgemeinerter Vergleich + 2. Exkurs: Datenstrukturen + 1. Was ist eine Datenstruktur? + 2. Arrays + 3. Einfach verkettete Listen + 4. Doppelt verkettete Listen + 5. Was hat das mit unserer Suche zu tun? + 3. Binärbäume + 1. Die Datenstruktur Binärbaum + 2. Klassendiagramm des Binärbaums + 3. Eine mögliche Implementation + 4. Andere Algorithmen auf Binärbäumen + 1. Einen Knoten in einen Binärbaum einfügen + 2. Einen Knoten aus einem Binärbaum löschen + 3. Einen Binärbaum traversieren - Tiefensuche + 5. Exkurs: Brauchen wir den Schlüssel? + 4. Vertiefungen + 1. Allgemeine Bäume + 2. Die Speicherabbildungsfunktion + 3. AVL- und Splay trees + 4. B-Bäume 4. Komplexität von Algorithmen und Problemen + 1. Fallstudie - Sortieren / Präzisierung von Berechnungskomplexität + 1. Sortieralgorithmen + 1. Sortieren durch Auswählen / Selectionsort + 2. Sortieren durch Einfügen / Insertionsort + 3. Sortieren durch Aufsteigen / Bubblesort + 4. Sortieren durch Zerlegen / Quicksort + 2. Laufzeitverhalten + 1. Laufzeitmessungen + 2. Systematische Bestimmung des Laufzeitverhaltens + 3. Zusammenfassung + 3. Aufwandsanalyse + 1. Beschreibung der Problemgröße + 2. Modellierung der Kosten + 3. Kostenanalyse für Sortieralgorithmen + 4. Asymptotisches Wachstumsverhalten + 1. Vergleich von Kostenfunktionen + 2. Asymptotisches Wachstumsverhalten als Vergleichskriterium + 3. Einordnung in Komplexitätsklassen + 5. 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. Ein einfacher Lösungsalgorithmus + 3. Komplexitätsbetrachtungen + 4. Lösung mit einem genetischen Algorithmus + 5. Implementierung des genetischen Algorithmus 5. Berechenbarkeit + 1. Das Halteproblem + 1. Endlosschleifen + 2. Das Halteproblem + 3. Automatisierte Programmanalyse + 4. Ein seltsames Halteanalyseprogramm + 5. Lösbarkeit des Halteproblems + 6. Zusammenfassung - Lösbarkeit des Halteproblems + 2. Lösbarkeit von Problemen + 1. Das Neun-Punkte-Problem + 2. Lösungen zum Neun-Punkte-Problem + 3. Lösbarkeit des Neun-Punkte-Problems + 4. Algorithmische Lösbarkeit von Problemen + 3. Turingmaschine als Berechnungsmodell + 1. Auf den Spuren von Alan Turing + 2. Ein Marienkäfer als Turingmaschine + 3. Präzisierung der Turingmaschine + 4. Turingmaschinen-Berechenbarkeit + 5. Eine universelle Turingmaschine + 6. Turingmaschine als Berechnungsmodell + 4. Weitere Berechnungsmodelle + 1. Registermaschine als Berechnungsmodell + 2. While-Programmiersprache als Berechnungsmodell + 3. Church-Turing-These + 5. Grenzen der Berechenbarkeit + 1. Aufzählung aller Turingmaschinen + 2. Existenz nicht berechenbarer Funktionen + 3. Das Halteproblem + 4. Fleißige Biber + 5. Ein Blick in die Geschichte
