Lernbereich 3: Komplexität von Algorithmen und Berechenbarkeit (Leistungskurs)

Kennen des erweiterten Algorithmusbegriffes

Eigenschaften von Algorithmen; → Kl. 8, LB 1

Beurteilen der Effizienz und Komplexität von Algorithmen

Sortieralgorithmen, Suchalgorithmen; Problem des Handlungsreisenden, Vierfarbenproblem, Brücken-Problem, Primfaktorzerlegung

Beurteilen der Effizienz und Komplexität von Algorithmen: Komplexitätsklassen

Beurteilen der Effizienz und Komplexität von Algorithmen: Nachweis der Komplexität

Zeit- oder Aufwandskomplexität

Kennen von Grenzen der Berechenbarkeit

technisch und theoretisch

Kennen von Grenzen der Berechenbarkeit: algorithmische Unlösbarkeit

Halteproblem

Kennen von Grenzen der Berechenbarkeit: P-Probleme

Kennen von Grenzen der Berechenbarkeit: NP-Probleme

Rucksackproblem, Problem des Handlungsreisenden, Hamiltonkreis; exponentieller Aufwand; Näherungslösungen; Churchsche These

Beurteilen von Entscheidungsproblemen

berechenbare und nicht berechenbare Funktion; entscheidbare und unentscheidbare Menge