Hilfsmittel Mathematik 2 SS11

Autor:

Bernd Schönlebe

Rekursionsgleichungen (Differenzengleichung)

Beispiel einer Rekursion in einer frühen Werbung um 1900

Eine leicht verständliche Definition der Rekursion an sich, wirft schon eine scheinbar ebenso einfache Frage auf:

Rekursion

Siehe: "Rekursion".

Wie lange muss man "Rekursion" nachschlagen um die Definition zu erfahren? In diesem Fall würde man sie nie erfahren, denn es handelt sich um einen Infiniten Regress. Im folgendem Beispiel ist schon eine Abbruchbedingung mit eingebaut:

Rekursion

Wenn Sie es noch nicht verstanden haben, Siehe: "Rekursion".

Hier kann man die vorhergehende Frage nicht so leicht beantworten, denn das Verhalten der Abruchbedingung ist unbekannt.

Motivation

-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

...