Algorithmen und deren Komplexität

Question 1

Was ist eine Instanz für ein Problem?

Answer 1

eine mögliche Eingabe für ein spezifisches Problem

Question 2

Was ist ein Algorithmus?

Answer 2

definiert eine Folge elementarer Anweisungen zur Lösung eines Problems

Question 3

Was bedeutet Korrektheit im Bezug auf Algorithmen?

Answer 3

Ein Algorithmus stoppt für jede mögliche Eingabe
mit der korrekten Ausgabe

Question 4

Sind Variablen im Pseudo-Code default lokal oder global?

Answer 4

lokal

Question 5

Was ist call by value?

Answer 5

• 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.

Question 6

Was ist call by reference?

Answer 6

• 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.

Question 7

Was ist beim Pseudo-Code default? call by value oder reference?

Answer 7

call by value

Question 8

Wie gibt man Variablen als Parameter an, die dem Prinzip call by reference entsprechen sollen an?

Answer 8

mit einem & davor

Question 9

Wie werden boolesche operatoren ausgeführt im Pseudo-Code?

Answer 9

Boole‘sche Operatoren werden träge ausgewertet (lazy evaluation), d.h. von links nach rechts bis der Ausdruck garantiert falsch oder wahr ist.

Question 10

Worauf weißt das Schlüsselwort error im Pseudo-Code hin?

Answer 10

weißt auf nicht erfüllte Randbedingungen an die Eingabe hin, die dann zu einem Fehler und Abbruch führen

Question 11

Was ist die formale Korrektheit von Algorithmen?

Answer 11

• 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

Question 12

Was ist eine Schleifeninvariante?

Answer 12

Bedingung, die bei jedem Durchlauf gelten muss

vor, während (nach jeder Iteration) u. nach Ausf. einer Schleife gültig

Question 13

Wovon hängt die physikalische Laufzeit ab?

Answer 13

• hängt stark vom Computer ab
• hängt von vielen Details der Eingabedaten ab

Question 14

Welche Modellannahmen gibt es bei der Laufzeit?

Answer 14

• 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.

Question 15

Welche Modellannahmen gibt es bei dem Speicherplatz?

Answer 15

RAM-Modell: Speicherung eines elementaren Datenobjekts kostet unabhängig vom Wert konstanten Speicherplatz

Question 16

Wie können wir die Effizienz eines Algorithmus unabhängig von Details der Eingabe bewerten?

Answer 16

Durch asymptotische Laufzeit:
* Wie verhält sich der Algorithmus bei immer größeren Instanzen?

Question 17

Worauf bezieht sich eine Laufzeitanalyse, wenn nicht anders angegeben?

Answer 17

auf den Worst Case

Question 18

Was ist O(g(n))?

Answer 18

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)

Question 19

Es gilt f, g = O(F).
Was gilt für f+g?

Answer 19

f + g = O(F)

Question 20

Es gilt f = O(F) und c konstant.
Was gilt für c*f?

Answer 20

c*f = O(F)

Question 21

Es gilt f = O(F) und g = O(f).
Was gilt für g?

Answer 21

g = O(F)

Question 22

Es gilt f = O(F) und g = O(G).
Was gilt für f*g?

Answer 22

f*g = O(F*G)

Question 23

Es gilt f = O(F*G).
Was gilt für f noch?

Answer 23

f = |F|*O(G)

Question 24

Es gilt f = O(F) und |F| ≤|G|.
Was gilt für f noch?

Answer 24

f = O(G)

Question 25

Was gilt für Polynome vom Grad m bei der O-Notation?

Answer 25

Ist p ein Polynom von Grad m gilt: p = O(N^m)

Question 26

Wofür steht bei dem O-Kalkül das O?

Answer 26

Question 27

Wofür steht bei dem O-Kalkül das o?

Answer 27

Question 28

Wofür steht bei dem O-Kalkül das Ω?

Answer 28

Question 29

Wofür steht bei dem O-Kalkül das ω?

Answer 29

Question 30

Wofür steht bei dem O-Kalkül das Θ?

Answer 30

Question 31

Wie schaut eine if-elseif-else Verzweigung im Pseudo-Code aus?

Answer 31

Question 32

Wie schaut eine while Schleife im Pseudo-Code aus?

Answer 32

Question 33

Wie schaut eine for-to/downto Schleife im Pseudo-Code aus?

Answer 33

Question 34

Wie schaut eine repeat-until Schleife im Pseudo-Code aus?

Answer 34

Question 35

Ist die Variable für eine for Schleife im Pseudo-Code noch nach Schleifenende definiert?

Answer 35

Ja, (C-Konvention)

Question 36

Wie schreibt man Kommentare im Pseudo-Code?

Answer 36

// Kommentar-Beispiel

Question 37

Wofür steht == im Pseudo-Code?

Answer 37

Vergleich von Ausdrücken

Question 38

Wofür steht = im Pseudo-Code?

Answer 38

Zuweisung von Werten

Question 39

Wie werden Feldelemente und Teilfelder angegeben?

Answer 39

Feldelemente: A[i]
Teilfelder: A[i..j]

Question 40

Wie funktioniert ein Scan-Line Verfahren?

Answer 40

Beispiel max-subarray-problem
* durchlaufe X von links nach rechts
* merke dir das bisherige Maximum maxtsum
* merke dir die rechte Randteilsumme

Question 41

Zähle die Funktionen für die O-Notation aus der Vorlesung nach Größenordnung aufsteigend auf.
* sqrt(n)
* log^2 n
* 2^n
* n
* n^2
* log n
* n^3
* n log n
* 1

Answer 41

• 1
• log n
• log^2 n
• sqrt(n)
• n
• n log n
• n^2
• n^3
• 2^n