Hilfsmittel Mathematik 2 SS11

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2011-03-30T12:57:10+00:00. Aktuelle Version

Inhaltsverzeichnis

Autor:

Bernd Schönlebe

Rekursionsgleichungen (Differenzengleichung)

Droste.jpg
Beispiel einer Rekursion in einer frühen Werbung um 1900

Bereits eine leicht verständliche Definition der Rekursion wirft eine scheinbar ebenso einfache Frage auf:

Rekursion
Siehe: "Rekursion".

Wie lange muss man "Rekursion" nachschlagen um die Definition zu erfahren? Bzw. wieviele Schritte werden benötigt? In diesem Fall sind es unendlich viele Wiederholungen, 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 vorhergehenden Fragen nicht so leicht beantworten, denn das Verhalten der Abruchbedingung ist unbekannt, aber immerhin ist es möglich, dass es zum Abbruch der Schleife kommt und somit eine Antwort gegeben werden kann. Ein Beispiel aus der Mathematik verdeutlich ein weiteres Problem:

Die Fibonacci Folge
Die Mathematische Definition der Fibonacci Folge Fn :
F_n = F_{n-1} + F_{n-2},\!\,
mit den Startwerten
F_0 = 0 \quad\text{und}\quad F_1 = 1.


Motivation

-Aufwandsberechnung rekursiver Algorithmen

-da nicht direkt ablesbar

...

Computeralgebrasysteme(CAS)

(5min.)

-Begriffsdefinition

-Funktionen

-Einführung Maple

-Beispiel Fibonacci



Und hier die Folge als Graph:
GNUPlot-Quelltext
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
...