AlgorithmenIn diesem KapitelGrundlagenRekursive AlgorithmenStandardalgorithmenKomplexität von Algorithmen und ProblemenBerechenbarkeitqStartseite2. Algorithmen1. 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. Übungen2. 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 Algorithmen3. 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äume4. 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 Algorithmus5. 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
