Was ist ein Rekursiver Algorithmus?
Methode zur Problemlösung, bei der eine Funktion sich selbst aufruft, um kleinere Instanzen des Problems zu bearbeiten.
Was ist wenn Input n = 1 ist bei einem rekursiven Algorithmus?
direkt effizient berechenbar
sog. Base case
Was macht Divide-and-Conquer?
- Grosse Input Werte teilen
- Teilaufgaben lösen
- Gesamtlösung durch Teillösungen rekonstruieren.
Wie sieht ein Rekurisionsbaum aus? Beispielsweise für die Berechnung der Summe der ersten 5 zahlen.
Rechenkomplexität von mergeSort von John von Neumann
Was ist die Schwierigkeit bei der Analyse von rekursiven Algorithmen?
Anzahl Rechenschritte zählen von Algorithmus ist nicht einfach möglich, da Funktion mehrmals aufgerufen wird.
Allgemeine Darstellung der Anzahlrechenschritte von Divide-and-Conquer Algorithmen
Was sagt a aus bei dieser Darstellung?
Wie oft die Rekursion ausgelöst wird
Was sagt b aus bei dieser Darstellung?
Um wieviel der Input jeweils verkleinert wird
Was sagt c*n^k aus in dieser Darstellung?
Wie viel Rechenschritte für die Aufräumarbeiten notwendig sind
Was kann man mit diesem Satz herausfinden?
In welcher Komplexitätsklasse der rekurisve Algorithmus ist.
Lineare Rekursionbeziehungen, was ist anders?
Input wird nicht durch bestimmte Zahl aufgeteilt sondern um bestimmte Anzahl verkleinert.
Bspw.
Von welchem Grad ist diese Rekursionsbeziehung?
Von welchem Grad ist diese Rekursionbeziehung?
Von Grad 2
Was ist F(n)?
Anzahl Rechenschritte für Aufräumarbeiten
Homogen –> Keine Rechenschritte für Aufräumarbeiten
Inhomogen –> Rechenschritte für Aufräumarbeiten notwendig
Für homogene Rekursionsbeziehungen wird zwischen Grad x und Grad y unterschieden
k = 1 –> Lösung direkt
k >= 2 –> Lösung mittels quadratischer Gleichung
Wie muss eine inhomogene Rekursionbeziehung gelöst werden?
- allgemeine Lösung für homogenen Teil bestimmen
- T partikulär Ansatz machen
- Zusammenfügen und Paramter bestimmen
