Informatik — Algorithmen und Datenstrukturen
Aufbauwissen Informatik: die O-Notation und Komplexitätsklassen, die wichtigen Datenstrukturen (Array, verkettete Liste, Stack, Queue, Hashtabelle, Baum, Graph, Heap), Such- und Sortieralgorithmen (binäre Suche, Merge Sort, Quicksort) mit ihrer Komplexität sowie Rekursion und die Prinzipien Greedy, Divide-and-Conquer und dynamische Programmierung. Aufbaudeck zu den Programmier-Grundlagen.
104 Karten Deutsch Sekundarstufe 2 CC-BY-4.0 von Kartomo gratis
Die Karten
Die ersten 30 von 104 Karten. Der Rest steht in der App.
-
Was ist ein Algorithmus?
Eine endliche, eindeutige Folge von Anweisungen, die ein Problem in endlicher Zeit löst.
-
Nenne fünf Eigenschaften, die ein Algorithmus erfüllen muss.
1. Finitheit (endet nach endlich vielen Schritten) 2. Eindeutigkeit (keine widersprüchlichen Anweisungen) 3. Ausführbarkeit (jeder Schritt ist durchführbar) 4. Allgemeinheit (löst eine Klasse von Problemen) 5. Determiniertheit (gleiche Eingabe → gleiche Ausgabe)
-
Ein Algorithmus heißt …, wenn er nach endlich vielen Schritten terminiert, und …, wenn gleiche Eingaben stets gleiche Ausgaben liefern.
finit · determiniert
-
Was bedeutet Determinismus bei einem Algorithmus?
Bei gleicher Eingabe liefert der Algorithmus immer die gleiche Ausgabe — jeder Schritt ist eindeutig festgelegt.
-
Welche Eigenschaft beschreibt, dass ein Algorithmus für eine ganze Klasse ähnlicher Probleme anwendbar ist?
-
Was misst die Zeitkomplexität eines Algorithmus?
Wie die Laufzeit des Algorithmus mit der Größe der Eingabe n wächst — unabhängig von konkreter Hardware.
-
Was ist die Big-O-Notation?
Eine mathematische Schreibweise, die das asymptotische Wachstum einer Funktion nach oben begrenzt. Sie beschreibt den Worst Case des Ressourcenverbrauchs.
-
Die Big-O-Notation beschreibt die … des Wachstums einer Funktion. Sie gibt an, wie sich die Laufzeit im … (Worst Case) verhält.
obere Schranke · schlimmsten Fall
-
Was ist der Unterschied zwischen Best Case, Average Case und Worst Case?
Best Case: günstigster Eingabefall (schnellste Laufzeit) Average Case: durchschnittliche Laufzeit über alle möglichen Eingaben Worst Case: ungünstigster Eingabefall (langsamste Laufzeit)
-
Welche Notation gibt die untere Schranke der Laufzeit an (Best Case)?
-
Wie lautet die Faustregel, um konstante Faktoren und niedrigere Terme in der Big-O-Notation wegzulassen?
Bei der Asymptotik interessiert nur das dominante Wachstum: 3n² + 5n + 7 → O(n²). Konstante Faktoren und additive Terme werden ignoriert.
-
Der Ausdruck 5n³ + 100n + 42 hat die Zeitkomplexität …, weil der kubische Term bei großem n dominiert.
O(n³)
-
Was ist der Unterschied zwischen Zeitkomplexität und Speicherkomplexität?
Zeitkomplexität: Wie viele Schritte/Operationen der Algorithmus benötigt. Speicherkomplexität: Wie viel zusätzlichen Arbeitsspeicher der Algorithmus benötigt.
-
Ein Algorithmus, der unabhängig von der Eingabegröße immer gleich viel Speicher braucht, hat eine Speicherkomplexität von …
-
Merge Sort hat eine Speicherkomplexität von …, weil es ein zusätzliches Array zum Zusammenführen benötigt. Quicksort hat im Schnitt O(…) Speicher für den Rekursionsstack.
O(n) · log n
-
Was bedeutet O(1) — konstante Komplexität?
Die Laufzeit ist unabhängig von der Eingabegröße n immer gleich. Beispiel: Zugriff auf ein Array-Element per Index.
-
Der Zugriff auf ein Element in einem Array per Index hat die Zeitkomplexität …, weil die Position direkt berechnet wird.
O(1)
-
Nenne zwei Beispiele für O(1)-Operationen.
1. Lesen/Schreiben eines Array-Elements per Index 2. Einfügen am Anfang eines Stacks (push) 3. Zugriff auf ein Element in einer Hashtabelle (average)
-
Was bedeutet O(log n) — logarithmische Komplexität?
Die Laufzeit wächst logarithmisch mit n. Bei jeder Iteration wird das Problem halbiert. Beispiel: binäre Suche.
-
Die binäre Suche hat eine Zeitkomplexität von …, weil das Suchintervall bei jedem Schritt … wird.
O(log n) · halbiert
-
Was bedeutet O(n) — lineare Komplexität?
Die Laufzeit wächst proportional zur Eingabegröße. Beispiel: lineare Suche — jedes Element wird einmal betrachtet.
-
Was bedeutet O(n log n) — linearithmische Komplexität?
Wächst etwas schneller als linear, aber deutlich langsamer als quadratisch. Typisch für effiziente Sortieralgorithmen wie Merge Sort und Quicksort (Average).
-
Merge Sort hat im Worst Case eine Zeitkomplexität von …. Quicksort hat im Average Case …, im Worst Case aber ….
O(n log n) · O(n log n) · O(n²)
-
Was bedeutet O(n²) — quadratische Komplexität?
Die Laufzeit wächst quadratisch mit n. Typisch für einfache Sortieralgorithmen mit zwei verschachtelten Schleifen (Bubble Sort, Selection Sort, Insertion Sort Worst Case).
-
Welchen Algorithmus kennzeichnet typischerweise eine O(n²)-Laufzeit?
-
Was bedeutet O(2ⁿ) — exponentielle Komplexität?
Die Laufzeit verdoppelt sich mit jedem weiteren Element. Solche Algorithmen sind für große n praktisch nicht verwendbar. Beispiel: naiver Fibonacci ohne Memoization.
-
Der naive rekursive Fibonacci-Algorithmus hat eine Zeitkomplexität von …, weil jeder Aufruf zwei weitere Aufrufe erzeugt. Mit dynamischer Programmierung sinkt dies auf ….
O(2ⁿ) · O(n)
-
Ordne die Komplexitätsklassen von schnellst nach langsamst: O(n²), O(1), O(n log n), O(log n), O(2ⁿ), O(n)
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
-
Was ist ein Array (Feld)?
Eine geordnete Sammlung von Elementen des gleichen Typs, die an aufeinanderfolgenden Speicheradressen gespeichert sind. Die Größe ist meist fest (statisch).
-
Welche Operationen unterstützt ein Array und mit welcher Komplexität?
Zugriff per Index: O(1) Suche (unsortiert): O(n) Einfügen/Löschen am Ende: O(1) amortisiert Einfügen/Löschen in der Mitte: O(n) wegen Verschieben