Einführung Flashcards
Welche Merkmale sind für die Analyse eines Algorithmuses wichtig?
- Leistung
- Korrektheit
- Modularität
- Wartbarkeit
- Funktionalität
- Robustheit
- Benutzerfreundlichkeit
- Erweiterbarkeit
- Zuverlässigkeit
Was sind die grundlegenden Merkmale für den Entwurf/Benutzung eines Frameworks für die Beschreibung und Analyse von Algorithmen?
- Darstellung in Pseudocode
- Benutzung der asymptotischen Notation zur Laufzeit-Analyse
- Technik zur Lösung eines Problems
Nenne mir zwei grundlegende Sortieralgorithmen.
- Insertionsort
- Mergesort
Was bedeutet Permutation im Sachzusammenhang eines Sortieralgorithmuses?
Man bezeichnet bei Sortieralgorithmen den Output als Permutation, da hier immer nach einer Bestimmten Reihenfolge gesucht wird.
Was ist mit “Schlüssel” gemeint?
Man bezeichnet den Index bzw. Zugriffswert eines Arrays bzw. einer Datenbank als Schlüssel.
Beschreibe mir den Insertionsort in Pseudocode.
Input: Array A mit der Länge n
Output: Sortiertes Array A
INSERTION-SORT(A, n)
for j = 2 to n do
|—key = A[j]
|—i = j - 1
|—while i > 0 & A[i] > key do
|—|—A[i + 1] = A[i]
|—|—i = i -1
|—end while
|—A[i + 1] = key
end for
Beschreibe mir den Insertionsort.
Es wird nach dem Vorbild von Spielkarten in der Hand sortiert.
Alle Karten liegen auf dem Tisch.
Nimm eine Karte auf die Hand.
Nimm solange weitere Karten auf und vergleiche sie mit dem Karten auf der Hand um die Korrekte position zu finden bis keine Karten mehr vorhanden sind.
Was ist eine Schleifeninvariante?
Eine Schleifeninvariante ist der Konstante Teil einer Schleife die vor und nach der Ausführung einer Schleife gültig sein muss (Teil der Bedingung).
Beschreibe den Vorgang eines Korrektheitsbeweises einer Schleife.
Vorgehen ist vergleichbar mir der vollständigen Induktion der Mathematik.
1. Basisfall/Indutkionsschritt gilt
2. Invariatne vor der ersten Iteration gilt
3. Invariante gilt von Iteration zu Iteration
Es wird kein lim gebildet, Reihenfolge der Schritte ist offen.
Beschreibe das RAM-Modell (Random-Access-Maschine)
- Sequenzielles durchlaufen
- keine Parallelität
- Identifizierung aller Aritmetischen vorgängen
Nenne mir die drei Fälle die bei einer Analyse betrachtet werden.
- Worst-Case
- Middle-Case
- Best-Case
Was ist mit Relativer und Absoluter Geschwindigkeit gemeint?
Relative Geschwindigkeit bezieht sich auf Algorithmen, die auf gleichen Maschinen laufen, Absolute Geschwindigkeit biezieht sich auf verschiedenen Maschinen.
Definiere die Klasse von Funktionen Θ (Theta).
Θ(g(n)) = f(n): Es existieren positive Konstanten c_1, c_2, und n_0 sodass, 0 ≤ c_1g(n) ≤ f(n) ≤ c_2g(n) für alle n ≥ n_0.
Beschreibe den Mergesort in Pseudocode.
MergeSort(A, p, r)
if p < r then
|— q = ⌊(p + r )/2⌋
|— MergeSort(A, p, q)
|— MergeSort(A, q + 1, r)
|— Merge(A, p, q, r)
end if
Initial call: MergeSort(A, 1, n)
⌊a⌋ = floor(a)
Welcher Sortieralgorithmus ist effizienter, Insertionsort oder Mergesort?
Interstionsort = Θ(n2)
Mergesort Θ(n lg(n))
Der Mergesort ist effizienter.
lg = log_2
