Hilfsmittel Mathematik 2 SS09

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2009-04-07T15:28:48+00:00. Aktuelle Version

Inhaltsverzeichnis

Rekurionsgleichungen

Motivation

Das Bestimmen des Aufwandes für Gleichungen, wie f(n)=n^2 oder f(n)=2\cdot n^2+12 stellt mit Hilfe der Asymptotischen Aufwandsordnungen kein Problem dar. Mann kann durch einfaches Ablesen die 2 gennanten Funktionen durch Verwendung der "Groß-Oh-Notation" in \mathcal{O}(n \rightarrow n^2) einordnen.

Aber wie verhält es sich mit rekursiven Gleichungen? Die Fibonacci-Zahlenfolge oder die Fakultät-Zahlenfolge sind typische Vertreter für rekursive Gleichungen und auch gern gewählte Beispiele.

Definition der Fibonacci-Zahlenfolge
F(0)=1
F(1)=1
F(n)=F(n-1)+F(n-2), mit n>2

Da es sich um eine rekursive Gleichung handelt ist es sichtlich schwer durch Betrachtung der Definition den Aufwand zu bestimmen. Auch durch die Betrachtung der der einzelnen Fibonacci-Zahlen( 1,1,2,3,5,8,13,21,34,55,...) ist der genaue Aufwand nicht zu ermitteln.

Die nachfolgenden Abschnitte erläutern verschiedene Methoden, die zur Ermittlung des Aufwandes für rekursive Gleichungen helfen.

Computeralgebrasysteme

Raten und Einsetzen

Das geschickte Raten(intelligent guesswork) behilft sich einer Wertetabelle und eines guten mathematischen Geistes, um den Aufwand einer rekursiven Gleichung zu ermitteln.

Sei die rekursive Gleichung T(n)=3\cdot T\left(\frac{n}{2}\right)+2, mit T(1)=1 gegeben.

Mit Hilfe der Wertetabelle sollen Funktionswerte durch geschicktes Einsetzen verschiedener Argumente ermittelt werden. Für das gewählte Beispiel bieten sich Zweierpotenzen an, Da man dann bei jedem Folgeschritt auf das Ergebnis des zuvor gewählten Argumentes zugreifen kann. Um T(2) zu berechnen muss man T(1) einsetzen, welchens gegeben ist. Um T(4) zu berechnen, muss man T(2) einsetzen, welches man in der Wertetabelle zuvor berechnet hat und so weiter.

Würde man n lediglich inkrementieren, so würde man spätestens bei n=3 , also T\left(\frac{3}{2}\right) ins Stocken geraten, da hierfür in der Wertetabelle (noch) kein Wert vorliegt.

rekursive Gleichung: T(n)=3\cdot T\left(\frac{n}{2}\right)+n , n=2^k
n Tn
1 1
2 3\cdot 1+2
4 3\cdot(3\cdot1+2)+4
3^2\cdot1+3\cdot2+2^2
8 3\cdot(3^2\cdot1+3\cdot2+2^2)+8
3^3\cdot1+3^2\cdot2+3\cdot2^2+2^3
16 3\cdot(3^3\cdot1+3^2\cdot2+3\cdot2^2+2^3)+16
3^4\cdot1+3^3\cdot2+3^2\cdot2^1+3\cdot2^3+2^4

Bei der Erstellung der Wertetabelle ist nicht die absolute Zahl von Interesse, sondern eine möglichst geschickte Anordnung der einzelnen Zahlen aus die der Term besteht, sodass wir das Wachstum vom n-ten Wert zu dem n+1-ten Wert ermitteln können. Hat man genug Werte ermittelt und ist einem das Verhalten von n zu n+1 klar, so versucht man das Ganze, z.B. mittels Summen- oder Produktdarstellung, kompakter zu beschreiben.

T(2^k)=\sum_{i=0}^k 3^{k-i}\cdot4^i

Danch gilt es, den enstandenen Ausdruck in eine explizite Form umzuwandeln, da man den Aufwand einer Gleichung in Summendarstellung wie bei rekursiven Gleichungen nur schwer ablesen kann.

T(2^k)=\sum_{i=0}^k 3^{k-i}\cdot4^i T(2^k)=\sum_{i=0}^k 3^{k}\cdot3^{-i}\cdot4^i T(2^k)=\sum_{i=0}^k 3^{k}\cdot\frac{1}{3^i}\cdot4^i T(2^k)=\sum_{i=0}^k 3^{k}\cdot\frac{4^i}{3^i} T(2^k)=\sum_{i=0}^k 3^{k}\cdot\left(\frac{4}{3}\right)^i

Anmerkung: Konstante Faktoren innerhalb der Summe können vor die Summe gestellt werden

T(2^k)=3^{k} \sum_{i=0}^k \left(\frac{4}{3}\right)^i

Formel: \sum_{i=m}^k (x)^i = \frac{x^m-x^{k+1}}{x^m-x}

T(2^k)=3^k\cdot\frac{\left(\frac{2}{3}\right)^0-\left(\frac{2}{3}\right)^{k+1}}{1-\frac{2}{3}} T(2^k)=3^k\cdot\frac{\left(\frac{2}{3}\right)^0-\left(\frac{2}{3}\right)^{k+1}}{\frac{1}{3}} T(2^k)=3^k\cdot3\cdot\Bigg(\left(\frac{2}{3}\right)^0-\left(\frac{2}{3}\right)^{k+1}\Bigg) T(2^k)=3^{k+1}\cdot\Bigg(1-\left(\frac{2}{3}\right)^{k+1}\Bigg) T(2^k)=3^{k+1}-2^{k+1}

Bis zum jetzigen Zeitpunkt haben wir immer mit T(2^k) gerechnet. Jedoch ist eine Funktion T:n \rightarrow T(n) gesucht. Zu Beginn wurde die Vereinbarung n=2^k getroffen. Da \log_a{b}=c \Leftrightarrow a^c=b muss k=\log_2{n} substituiert werden.

T(n)=3^{\log_2{n}+1}-2^{\log_2{n}+1} T(n)=3\cdot3^{\log_2{n}}-2\cdot 2^{\log_2{n}}

Formel: a^{\log_a{b}}=b

T(n)=3\cdot3^{\log_2{n}}-2\cdot n

Aus der obigen Formel ergibts sich das wir für 2^{\log_2{n}} einfach n schreiben können. Auf 3^{\log_2{n}} ist dies nicht direkt anwendbar. Daher muss man hier den Gedanken folgen, wie man die 3 in eine 2 umwandelt, um die obige Formel erneut anwenden zu können. Aus der Überlegung, dass 2^x=3 ist, kann man Schlussfolgern, dass x=\log_2{3} . Nun kann man anstatt 3, einfach 2^{\log_2{3}} einsetzen.

T(n)=3\cdot2^{\log_2{n}\cdot\log_2{3}}-2\cdot n T(n)=3\cdot n^{log_2{3}}-2\cdot n

Das Ergebnis lautet T(n)=\mathcal{O}\left(n^{\log_2{3}}\right).

Konstruktive Induktion

Iterationsmethode

Die Meistermethode

Folien

  • Die aktuellsten Folien zur Vorlesung:
Vortrag.pdf

Aufgaben

  1. Raten und Einsetzen
    • Ermitteln Sie die explizite Bildungsvorschrift für T(n)=3\cdot T(\frac{n}{4})+2n, T(1)=2 .
  2. Computeralgebrasysteme
    • Machen sie sich mit dem CAS Maple und den Funktionen rsolve(), simplify() und evalf() vertraut und lösen sie die Aufgabe 3.3 aus dem Buch.
  3. Iterationsmethode
    • Lösen sie folgende Gleichung mittels Iterationsmethode:
    • 3\cdot T(\frac{n}{2})+ cn; für n>1, sonst d.
  4. Mastermethode
    • Prüfen sie mittels Master-Theorem folgende Gleichungen:
    1. T(n)=3\cdot T(\frac{n}{2})+n^2
    2. T(n)=\sqrt{2}\cdot T(\frac{n}{2})+\log 2
  • und zum abspeichern ;)
Aufgaben.pdf

Lösungen