Komplexität

grundlegendes Niveau (Grundkurs und Leistungskurs)

Klassifizierung von Problemen: Algorithmen mit polynomialer Laufzeit, Algorithmen mit exponentieller Laufzeit
Probleme und Funktionen: Problem als eine auf den natürlichen Zahlen definierte Funktion, Abzählbarkeit der Computerprogramme zur Lösung von Problemen, Überabzählbarkeit der Funktionen, Halteproblem

erhöhtes Niveau (Leistungskurs)

Probleme und Funktionen: Berechnung und Entscheidung, Diagonalisierung, weitere nicht entscheidbare Probleme

Lektionen

Fallbeispiel: Such- & Sortieralgorithmen

#	Lektion	Fachkonzept
1	Das Suchproblem - Brute Force, Binäre Suche
2	Das Sortierproblem
3	Sortieralgorithmen - Selectionsort
4	Laufzeitmessung
5	Aufwandsanalyse

Fallbeispiel: Primfaktorzerlegung

#	Lektion	Fachkonzept
1	Laufzeitverhalten der Primfaktorzerlegung

Die hier verwendeten Materialien stammen von der Seite inf-schule.de und stehen unter CC-BY-SA.