Algorithmenentwurf Flashcards
Indunkion, Iteration, Rekursion, Methoden des Algorithmen-Entwurfs, Korrektheit und Verifikation, Effizienz und Komplexität von Algorithmen
Welche Herangehensweisen, wie Befehlsfolgen organisiert sind, gibt es?
1
- Iterativ
- Rekursiv
- Induktiv
Was sind Iterative Algorithmen?
1
- for (i = 1; i<= n; i++) (…)
- Mithilfe von Iterationen
- zB For-Schleife
Was sind Rekursive Algorithmen?
1
- 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
Was sind induktive Algorithmen?
1
- oft in Beweisführung
- Problem in Teilprobleme zerlegt
- allgemeine Regel wird aus Basisfall und wiederholbaren Schlussfolgerungen abgeleitet
Welche sind die wesentlichen Paradigmen, nach denen Algorithmen entworfen werden?
2
- Greedy
- Divide and Conquer
- Dynamic Programming
Was ist das Greedy-Paradigma?
2
- jeder Schritt: lokal beste Entscheidung
- wählt Option, die momentan am vorteilhaftesten erscheint (ohne langfristige Konsequenz zu berücksichtigen)
Nenne Beispiele für Greedy-Algorithmen
2
- Dijkstra-Algorithmus
- Kruskal-Algorithmus
- Prim-Algorithmus
Was ist das Divide and Conquer Paradigma?
2
- 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
Was ist die dynamische Programmierung?
2
- Extremfall von Divide and Conquer
- Teilprobleme werden Reihenfolge nach gelöst (zunehmende Größe)
- Ergebnisse werden abgespeichert undw iederverwendet
Was ist der Unterschied zwischen Greedy-Algorithmus und dynamischer Programmierung?
2
- Greedy: immer Verbindung zu Knoten der momentan am nächsten liegt
- Dynamisch: immer globales Problem wird betrachtet, nicht lokal
Was sind mögliche Fehlerquellen in Algorithmen?
3
- Sprach- o. Syntaxfehler
- Logische o. semantische Fehler
- Endlosschleifen
Was sind Sprach- oder Syntaxfehler?
- Code entspricht nicht Regeln der Grammatik o. Programmiersprache
Was sind logische o. semantische Fehler?
3
- falsche Verwendung eines Ausdrucks
- Programm läuft, aber nicht erwartetes Ergebnis
Was sind Endlosschleifen?
3
- Nicht terminierende Schleifen
- unpräzise / fehlerhafte Definition des Abbruchkriteriums
Was ist die Vor- und Nachbedingung?
3
- Zustand der Daten vor und nach Ausführung des Algorithmus
Was sind Theorem-Beweiser?
3
- Theorem-Beweiser basieren auf Algorithmen
- Hilft, mathematische Sätze (halb-)automatisch zu beweisen
Was bedeutet “Total Korrekt”?
3
- Korrekt: Algorithmus produziert Ausgabe
- Terminierung: Algorithmus hält garantiert nach endlich vielen Schritten an
Was ist Backtesting?
3
- Algorithmenkontrolle
- Funktionalität und Leistunsfähigkeit wird überprüft
- Bewertung von Algorithmen
Was ist die Definition des Ziels der Laufzeitbestimmung?
4
- Finden einer oberen asymptotischen Grenze, der sich die Laufzeit des Algorithmus in Abhängigkeit zur Berechnung notwendiger Rechenschritte annähert
Was bedeutet “obere asymptotische Grenze”?
4
- Maximale Laufzeit, die nicht überschritten werden kann
Was zeigt die Asymptotische Analyse?
4
- wie sich Laufzeit mit Größe der Eingabedaten verhält
- also: Worst-Case, wenn Eingabegröße sehr groß wird
Warum ist die Laufzeitanalyse wichtig?
4
- Um zu wissen, wie Algorithmus mit größeren Datenmengen skalieren wird
Welche Arten der Komplexität gibt es?
4
- Zeitkomplexität
- Platzkomplexität
Was ist Zeitkomplexität?
4
- Ausführungsdauer
Was ist Platzkomplexität?
4
- Speicherplatzbedarf
Was ist die O-Notation?
4
- Notation zur Beschreibung von asymptotischem Verhalten
- O(1), O(n), O(n^2)
Was ist O(1)?
4
- Aufwand immer konstant
- verändert sich nicht mit Eingabemenge
- immer gleiche Zeit und gleichen Speicherverbrauch
Was ist O(n)?
4
- Aufwand steigt linear mit Eingabemente
- verdoppelte Eingabemenge = verdoppelter Aufwand
Was ist O(n^2)?
4
- Aufwand wächst quadratisch zur Eingabemenge
- zB zwei vernestete For-Schleifen (bei drei For-Schleifen: O(n^3)
Welche Laufzeiten von Algorithmen gibt es?
4
- Doppelt logarithmisch
- logarithmisch
- linear
- quasi-linear
- quadratisch
- exponentiell
log(log(n))
4
doppelt logarithmisch
log(n)
4
logarithmisch
n
4
linear
n x log(n)
4
quasi-linear
n ^ 2
4
quadratisch
2 ^ n
4
exponentiell
Was ist P und NP?
4
- Komplexitätsklassen
Was ist Determinismus in der Informatik?
4
- wenn Wirkung und Reihenfolge der Einzelschritte eindeutig festgelegt wird
Was ist nominelle Zeit?
4
- theoretische Laufzeit eines Algorithmus unter idealisierten Bedingungen
- abstrakte, modellierte Zeit für Lösung eines Problems
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
Definiere P
4
- Polynominale Zeitkomplexität
- Laufzeit: O(n^k)
- Klasse der Probleme für die Computer schnell korrekte Lösung berechnen kann
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
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)
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)
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)
