Algorithmenentwurf Flashcards
Indunkion, Iteration, Rekursion, Methoden des Algorithmen-Entwurfs, Korrektheit und Verifikation, Effizienz und Komplexität von Algorithmen (46 cards)
1
Q
Welche Herangehensweisen, wie Befehlsfolgen organisiert sind, gibt es?
1
A
- Iterativ
- Rekursiv
- Induktiv
2
Q
Was sind Iterative Algorithmen?
1
A
- for (i = 1; i<= n; i++) (…)
- Mithilfe von Iterationen
- zB For-Schleife
3
Q
Was sind Rekursive Algorithmen?
1
A
- Rufen sich selbst auf, um Problem zu Lösen
- Art von Schleife
- Meist weniger effizient, da wiederholt gleiche Methode aufgerufen und Kontext gespeichert werden muss
- def Fakultaet(item n):
if n == 0 then return 1
else return Fakultaet(n-1) x n
4
Q
Was sind induktive Algorithmen?
1
A
- oft in Beweisführung
- Problem in Teilprobleme zerlegt
- allgemeine Regel wird aus Basisfall und wiederholbaren Schlussfolgerungen abgeleitet
5
Q
Welche sind die wesentlichen Paradigmen, nach denen Algorithmen entworfen werden?
2
A
- Greedy
- Divide and Conquer
- Dynamic Programming
6
Q
Was ist das Greedy-Paradigma?
2
A
- jeder Schritt: lokal beste Entscheidung
- wählt Option, die momentan am vorteilhaftesten erscheint (ohne langfristige Konsequenz zu berücksichtigen)
7
Q
Nenne Beispiele für Greedy-Algorithmen
2
A
- Dijkstra-Algorithmus
- Kruskal-Algorithmus
- Prim-Algorithmus
8
Q
Was ist das Divide and Conquer Paradigma?
2
A
- Problem wird in Teilprobleme zerlegt und isoliert
- zB Liste in zwei Hälften geteilt und getrennt sortiert / nach etwas durchsucht; Später Vergleich der Ergebnisse
9
Q
Was ist die dynamische Programmierung?
2
A
- Extremfall von Divide and Conquer
- Teilprobleme werden Reihenfolge nach gelöst (zunehmende Größe)
- Ergebnisse werden abgespeichert undw iederverwendet
10
Q
Was ist der Unterschied zwischen Greedy-Algorithmus und dynamischer Programmierung?
2
A
- Greedy: immer Verbindung zu Knoten der momentan am nächsten liegt
- Dynamisch: immer globales Problem wird betrachtet, nicht lokal
11
Q
Was sind mögliche Fehlerquellen in Algorithmen?
3
A
- Sprach- o. Syntaxfehler
- Logische o. semantische Fehler
- Endlosschleifen
12
Q
Was sind Sprach- oder Syntaxfehler?
A
- Code entspricht nicht Regeln der Grammatik o. Programmiersprache
13
Q
Was sind logische o. semantische Fehler?
3
A
- falsche Verwendung eines Ausdrucks
- Programm läuft, aber nicht erwartetes Ergebnis
14
Q
Was sind Endlosschleifen?
3
A
- Nicht terminierende Schleifen
- unpräzise / fehlerhafte Definition des Abbruchkriteriums
15
Q
A
16
Q
Was ist die Vor- und Nachbedingung?
3
A
- Zustand der Daten vor und nach Ausführung des Algorithmus
17
Q
Was sind Theorem-Beweiser?
3
A
- Theorem-Beweiser basieren auf Algorithmen
- Hilft, mathematische Sätze (halb-)automatisch zu beweisen
18
Q
Was bedeutet “Total Korrekt”?
3
A
- Korrekt: Algorithmus produziert Ausgabe
- Terminierung: Algorithmus hält garantiert nach endlich vielen Schritten an
19
Q
Was ist Backtesting?
3
A
- Algorithmenkontrolle
- Funktionalität und Leistunsfähigkeit wird überprüft
- Bewertung von Algorithmen
20
Q
Was ist die Definition des Ziels der Laufzeitbestimmung?
4
A
- Finden einer oberen asymptotischen Grenze, der sich die Laufzeit des Algorithmus in Abhängigkeit zur Berechnung notwendiger Rechenschritte annähert
21
Q
Was bedeutet “obere asymptotische Grenze”?
4
A
- Maximale Laufzeit, die nicht überschritten werden kann
22
Q
Was zeigt die Asymptotische Analyse?
4
A
- wie sich Laufzeit mit Größe der Eingabedaten verhält
- also: Worst-Case, wenn Eingabegröße sehr groß wird
23
Q
Warum ist die Laufzeitanalyse wichtig?
4
A
- Um zu wissen, wie Algorithmus mit größeren Datenmengen skalieren wird
24
Q
Welche Arten der Komplexität gibt es?
4
A
- Zeitkomplexität
- Platzkomplexität
25
Was ist Zeitkomplexität?
| 4
* Ausführungsdauer
26
Was ist Platzkomplexität?
| 4
* Speicherplatzbedarf
27
Was ist die O-Notation?
| 4
* Notation zur Beschreibung von asymptotischem Verhalten
* O(1), O(n), O(n^2)
28
Was ist O(1)?
| 4
* Aufwand immer konstant
* verändert sich nicht mit Eingabemenge
* immer gleiche Zeit und gleichen Speicherverbrauch
29
Was ist O(n)?
| 4
* Aufwand steigt linear mit Eingabemente
* verdoppelte Eingabemenge = verdoppelter Aufwand
30
Was ist O(n^2)?
| 4
* Aufwand wächst quadratisch zur Eingabemenge
* zB zwei vernestete For-Schleifen (bei drei For-Schleifen: O(n^3)
31
Welche Laufzeiten von Algorithmen gibt es?
| 4
* Doppelt logarithmisch
* logarithmisch
* linear
* quasi-linear
* quadratisch
* exponentiell
32
log(log(n))
| 4
doppelt logarithmisch
33
log(n)
| 4
logarithmisch
34
n
| 4
linear
35
n x log(n)
| 4
quasi-linear
36
n ^ 2
| 4
quadratisch
37
2 ^ n
| 4
exponentiell
38
Was ist P und NP?
| 4
* Komplexitätsklassen
39
Was ist Determinismus in der Informatik?
| 4
* wenn Wirkung und Reihenfolge der Einzelschritte eindeutig festgelegt wird
40
Was ist nominelle Zeit?
| 4
* theoretische Laufzeit eines Algorithmus unter idealisierten Bedingungen
* abstrakte, modellierte Zeit für Lösung eines Problems
41
Gib ein Beispiel für "nominelle Zeit"?
| 4
Ein Algorithmus hat nominell eine Laufzeit von O(n^2), auch wenn er in der Praxis aufgrund von Optimierungen schneller ausgeführt werden kann
42
Definiere P
| 4
* Polynominale Zeitkomplexität
* Laufzeit: O(n^k)
* Klasse der Probleme für die Computer schnell korrekte Lösung berechnen kann
43
Definiere NP
| 4
* Nichtdeterministische polynominale Zeitkomplexität
* zur Problemlösung: nichtdeterministischen Algorithmus
* wie Zahlenschloss: korrekte Lösung evtl schwer findbar; Richtige Lösung schnell überprüfbar
44
Was ist die Turingmaschine?
| 4
* theoretisches Konzept
* Band mit Feldern in denen Eingangsdaten abgelegt sind
* wenn Funktion durch TM berechenbar ist: "Turing-berechenbar" / "berechenbar
* vor Allem für Entscheidungsprobleme (ja/nein)
45
Aus was besteht die Turingmaschine?
| 4
* Unendliches Band (Speicher, kann beschrieben werden)
* Lesekopf (liest / schreibt Symbole auf Band)
* Zustandstabelle (Regeln bestimmen was Maschine abhängig von Zustand und gelesenem Symbol tun soll)
46
Was hat die Turingmaschine mit einem Algorithmus zu tun?
| 4
* theoretische Darstellung eines Algorithmus
* Wenn Problem mit Turingmaschine lösbar ist = dann theoretisch auch mit einem Computer(-algorithmus)
