Quelltext der Seite Inf13 - Lernbereich 4: Algorithmen, Komplexität und Berechenbarkeit (ca. 32 Std.)

Zurück zur Übersicht >>> [[LehrplanPLUS G9 - Informatik]] 

===Lehrplantext===

'''Kompetenzerwartungen:''' Die Schülerinnen und Schüler ...

*  erläutern den Begriff Turing-Berechenbarkeit und zeigen für einfache Funktionen (z. B. Inkrement einer Binärzahl, Summe binärer Zahlen) durch Angabe einer passenden Turingmaschine, dass diese Funktionen Turing-berechenbar sind. Sie präzisieren den Algorithmusbegriff und nennen die Äquivalenz verschiedener Berechnungsmodelle (Church-Turing-These).
* bewerten durch Zeitmessungen und Zählverfahren (z. B. Zählen der Aufrufe bei der Ausführung rekursiver Algorithmen, Zählen der zeitkritischen Anweisungen) den Laufzeitaufwand von Algorithmen.
* beschreiben das asymptotische Laufzeitverhalten von Algorithmen unter Verwendung der Landau-Notation.
* begründen, dass ein hoher Laufzeitaufwand sicherheitsrelevant sein kann, z. B. bei der Ermittlung eines Passworts mit dem Brute-Force-Verfahren.
* entwerfen Algorithmen zur Lösung von Problemen und implementieren ausgewählte Beispiele. Dazu wenden sie geeignete Strategien an, wählen passende Datenstrukturen und nutzen ggf. die Möglichkeit, ein Problem auf ein anderes zurückzuführen (z. B. das SAT-Problem auf das Cliquenproblem); sie betrachten dabei auch Algorithmen, die Näherungslösungen liefern, z. B. zur Lösung des Handlungsreisendenproblems.
* vergleichen und beurteilen Algorithmen zur Lösung eines Problems u. a. hinsichtlich des Laufzeitverhaltens und schätzen die Komplexität des betrachteten Problems ab.
* beschreiben die Definition der Komplexitätsklassen P und NP sowie die Bedeutung der Fragestellung P≟NP, insbesondere für moderne Verschlüsselungsverfahren.
* erläutern das Halteproblem als Beispiel für Probleme, die nicht berechenbar sind. 

'''Inhalte zu den Kompetenzen:'''

* Berechenbarkeit: Turing-berechenbar, Algorithmus, Church-Turing-These
* Laufzeitaufwand von Algorithmen (linear, quadratisch als Beispiele für polynomiales Laufzeitverhalten, exponentiell, logarithmisch), Best Case, Average Case, Worst Case
* Algorithmen: u. a. die Sortieralgorithmen Bubblesort, Mergesort
* Landausche O-Notation
* Lösungsstrategien: Brute-Force, Greedy, Divide and Conquer, Zurückführen auf ein bereits gelöstes Problem
* Probleme: Sortierproblem, SAT-Problem, Handlungsreisendenproblem, Rucksackproblem, Cliquenproblem
* Komplexität von Problemen, Komplexität von Algorithmen
* Mengen P und NP
* Halteproblem

==Ergänzendes Unterrichtsmaterial==