Algorithmen und deren Komplexität Flashcards
(41 cards)
Was ist eine Instanz für ein Problem?
eine mögliche Eingabe für ein spezifisches Problem
Was ist ein Algorithmus?
definiert eine Folge elementarer Anweisungen zur Lösung eines Problems
Was bedeutet Korrektheit im Bezug auf Algorithmen?
Ein Algorithmus stoppt für jede mögliche Eingabe
mit der korrekten Ausgabe
Sind Variablen im Pseudo-Code default lokal oder global?
lokal
Was ist call by value?
- Die Werte der tatsächlichen Parameter werden in die formalen Parameter der Funktion kopiert.
- Es gibt zwei Kopien von Parametern, die in verschiedenen Speicherorten gespeichert sind: die Originalkopie und die Funktionskopie.
- Änderungen, die innerhalb von Funktionen vorgenommen werden, spiegeln sich nicht in den tatsächlichen Parametern des Aufrufers wider.
Was ist call by reference?
- Anstatt die Werte von Variablen zu übergeben, übergeben wir die Adresse von Variablen (Speicherort von Variablen) an die Funktion.
- Tatsächliche und formale Argumente werden im selben Speicherort erstellt.
- Änderungen an tatsächlichen Parametern können innerhalb der Funktion vorgenommen werden und spiegeln sich in den tatsächlichen Parametern des Aufrufers wider.
Was ist beim Pseudo-Code default? call by value oder reference?
call by value
Wie gibt man Variablen als Parameter an, die dem Prinzip call by reference entsprechen sollen an?
mit einem & davor
Wie werden boolesche operatoren ausgeführt im Pseudo-Code?
Boole‘sche Operatoren werden träge ausgewertet (lazy evaluation), d.h. von links nach rechts bis der Ausdruck garantiert falsch oder wahr ist.
Worauf weißt das Schlüsselwort error im Pseudo-Code hin?
weißt auf nicht erfüllte Randbedingungen an die Eingabe hin, die dann zu einem Fehler und Abbruch führen
Was ist die formale Korrektheit von Algorithmen?
- Angabe von Vor- und Nachbedingung für jede Anweisung
- Schleifeninvariante: Bedingung, die vor, während (d.h. nach jeder Iteration) und nach Ausführung einer Schleife gültig ist
Was ist eine Schleifeninvariante?
Bedingung, die bei jedem Durchlauf gelten muss
vor, während (nach jeder Iteration) u. nach Ausf. einer Schleife gültig
Wovon hängt die physikalische Laufzeit ab?
- hängt stark vom Computer ab
- hängt von vielen Details der Eingabedaten ab
Welche Modellannahmen gibt es bei der Laufzeit?
- Uniformes Kostenmaß: Math. Operationen kosten unabhängig von der Größe der Operanden eine Zeiteinheit
- RAM-Modell
– Zugriff auf Daten kostet eine konstante Zeiteinheit
– Algorithmen werden sequentiell ausgeführt (nur ein Prozessor) - Statt der genauen Laufzeit wird eine Schranke angegeben
- Konstante Faktoren werden vernachlässigt.
Welche Modellannahmen gibt es bei dem Speicherplatz?
RAM-Modell: Speicherung eines elementaren Datenobjekts kostet unabhängig vom Wert konstanten Speicherplatz
Wie können wir die Effizienz eines Algorithmus unabhängig von Details der Eingabe bewerten?
Durch asymptotische Laufzeit:
* Wie verhält sich der Algorithmus bei immer größeren Instanzen?
Worauf bezieht sich eine Laufzeitanalyse, wenn nicht anders angegeben?
auf den Worst Case
Was ist O(g(n))?
die Menge der Funktionen, die nicht stärker wachsen als g (= hat die Bedeutung von ∈, mit O() ist manchmal eine Menge, manchmal ein Repräsentant gemeint)
Es gilt f, g = O(F).
Was gilt für f+g?
f + g = O(F)
Es gilt f = O(F) und c konstant.
Was gilt für c*f?
c*f = O(F)
Es gilt f = O(F) und g = O(f).
Was gilt für g?
g = O(F)
Es gilt f = O(F) und g = O(G).
Was gilt für f*g?
f*g = O(F*G)
Es gilt f = O(F*G).
Was gilt für f noch?
f = |F|*O(G)
Es gilt f = O(F) und |F| ≤|G|.
Was gilt für f noch?
f = O(G)
