Probe
1.03.2024
Zeit
1 Lektion
Hilfsmittel
Taschenrechner ohne Programmierfunktion
Gewichtung
1
-
Sie kennen die behandelten Algorithmen zum Suchen (lineare Suche und binäre Suche) und Sortieren (Selection-Sort, Insertion-Sort und Merge-Sort) von Daten und können diese an exemplarischen Beispielen von Hand durchführen.
-
Sie wissen was ein Suchalgorithmus ist weshalb diese so wichtig sind
-
Sie erstellen Pseudocode (Python-Ähnlicher Code) für die behandelten Algorithmen.
-
Sie bestimmen die Laufzeitverhalten von Algorithmen anhand deren Funktionsweise (Python-Code, Pseudocode oder Beschreibung der Funktionsweise) und beschreiben die Komplexistätsklasse mit der -Notation.
-
Sie kennen die Begriffe "Best-Case", "Worst-Case" und "Average-Case" und können mit diesen argumentieren.
-
Sie können rekursive Algorithmen nachvollziehen und die maximale Rekursionstiefe von einfachen rekursiven Algorithmen bestimmen.
-
Sie kennen die Bedeutung eines Stacks und können die Funktionsweise von rekursiven Algorithmen anhand eines Stacks erklären.
-
Sie können die Problematik des P-NP Problems erklären und die Bedeutung für die Informatik erläutern.
-
Sie wissen, wie Baum- und Graphenstrukturen für die Darstellung von Daten genutzt werden können, worin sich diese unterscheiden und wie Sie ein Suchproblem in einem Baum oder Graphen lösen können.
-
Sie können die Funktionsweisen von Breiten- und Tiefensuchen sowei des Dijkstra- und A*-Algorithmus erklären und anhand von Beispielen anwenden.
-
Sie kennen die Stärken und Schwächen der behandelten Algorithmen und können diese miteinander vergleichen.
-
Sie kennen mindestens ein NP-vollständiges Probleme (bspw. SAT oder TSP) und können erklären, warum diese so schwierig zu lösen sind.
Lernziele