Hilfsmittel Mathematik 2 SS11

Autor:

Bernd Schönlebe

Rekursionsgleichungen

Motivation

(5min.)

-Aufwandsberechnung rekursiver Algorithmen

-da nicht direkt ablesbar

...

Computeralgebrasysteme(CAS)

(5min.)

-Begriffsdefinition

-Funktionen

-Einführung Maple

-Beispiel Fibonacci

Und hier die Folge als Graph:

set xlabel "n"
set ylabel "T(n)"
set data style lines
plot \
<dataset>
0	0
1	1
2	1
3	2
4	3
5	5
6	8
7	13
8	21
9	34
10	55
11	89
12	144
13	233
14	377
15	610
16	987
17	1597
18	2584
19	4181
20	6765
</dataset>

...

Raten und Einsetzen

(20min.)

-Intuitives Erraten der Bildungsvorschrift aus Wertetabelle

-Beweis 3^(log(2,n))=n^(log(2,3))

...

Konstruktive Induktion

(20min.)

-Vermutung expon. Funktion

-Induktionsanfang

-Induktionsschritt

-Beweis das Omega(...) für T(n) gilt

...

Iterationsmethode

(20min.)

-Expansion der Gleichung

-Ableitung der Summenformel

-log Umformung

...

Die Meistermethode

(20min.)

-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(10min.)
2. Raten und Einsetzen(20min.)
3. Konstruktive Induktion(20min.)
4. Iterationsmethode(20min.)
5. Mastermethode(20min.)

...

Lösungen

...