Teile und Beherrsche

Question 1

Wie lautet der Ansatz von Divide and Conquer?

Answer 1

1. Teile - das Problem in Teilprobleme
2. Beherrsche - die Teilprobleme durch rekursives lösen
3. Kombiniere - die Lösungen der Teilprobleme zur Lösung des Gesamtproblem

Question 2

Wie ist die allgemeine Form einer rekurrenten Gleichung (Bei DaC)?

Answer 2

• a ist dabei die anzahl der Teilprobleme, b die größe der Probleme.
• T(n) = Laufzeit des Problems der Größe n und der Rekursive Aufruf
• D(n) = die Zeit zum teilen eines Problems der größe n
• C(n) = Zeit für das Mischen

Question 3

Welche Laufzeitkomplexität hat Merge-Sort?

Answer 3

O(n * lg (n))

Question 4

Wie setzt Merge-Sort divide and conquer um?

Answer 4

Teile - das unsortierte Array auf
Beherrsche - Löse Rekursiv die 2 Teilprobleme
Kombiniere - Merge die einzelnen Teilfelder die erzeugt wurden

Question 5

Wie ist eine Rekurrenz definiert?

Answer 5

Rekurrenzen bezeichnen Funktionen, die über folgende Bedingungen definiert sind:
* Besitzen einen oder mehrere Basis-Fälle
* sowie sich selbst, mit kleineren Argumenten

Question 6

Welche Methoden gibt es um eine Rekurrenz zu lösen?

Answer 6

Die Substitutionsmethode und die Master-Methode.
Die Rekursionsbaum Methode ist keine akzeptierte Lösung führt aber zu einer guten Vermutung

Question 7

Wann benutzt man die asymptotische Notation in Bezug auf Rekurrenzen?

Answer 7

• man die Lösung in asymptotische Notation ausdrückt
• man sich nicht um die Randbedingungen kümmert und die Basis-Fälle innerhalb des Substitutionsbeweises zeigt
• Sucht man nach einer asymptotischen Lösung sind die Basisfälle nicht von Interesse

Question 8

Welche Rekurrenzen können mit der Mastermethode analysiert werden?

Answer 8

Question 9

Wodurch ist Strassen’s Algorithmus besser als normale Matrixmultiplikation?

Answer 9

Durch das einsparen einer rekursiven multiplikation, wird sehr viel rechenzeit gespart, wodurch die Laufzeitkomplexität n^2.81 gebträgt