Rekurionsgleichungen

Motivation

Computeralgebrasysteme

Raten und Einsetzen

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 .

Lösung zu 1:

n      T(n)

1. 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.
2. Iterationsmethode
   • Lösen sie folgende Gleichung mittels Iterationsmethode:
   • 3\cdot T(\frac{n}{2})+ cn; für n>1, sonst d.
3. 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