Hilfsmittel Mathematik 2 SS11

Rekursionsgleichungen

Motivation

-Aufwandsberechnung rekursiver Algorithmen -da nicht direkt ablesbar ...

Computeralgebrasysteme(CAS)

-Begriffsdefinition -Funktionen -Einführung Maple -Beispiel Fibonacci ...

Raten und Einsetzen

-Intuitives Erraten der Bildungsvorschrift aus Wertetabelle -Beweis 3^(log(2,n))=n^(log(2,3))

Konstruktive Induktion

-Vermutung expon. Funktion -Induktionsanfang -Induktionsschritt -Beweis das Omega(...) für T(n) gilt

Iterationsmethode

-Expansion der Gleichung -Ableitung der Summenformel -log Umformung

Die Meistermethode

-Einleitung: T(n)= a * T(n/b) + f(n) -3 Fallunterscheidungen -Anwendung nach Fall 2 -Anwendung nach Fall 3 -wann nicht anwenden

Aufgaben

1. Computeralgebrasysteme
2. Raten und Einsetzen
3. Konstruktive Induktion
4. Iterationsmethode
5. Mastermethode

Lösungen