Lernziele

Probe

1.03.2024

Zeit

1 Lektion

Hilfsmittel

Taschenrechner ohne Programmierfunktion

Gewichtung

1

info

• 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 $O(n)$-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.