Hilfsmittel Mathematik 2 SS11

Autor:

Bernd Schönlebe

Rekursionsgleichungen (Differenzengleichung)

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" F_n :

F_n = F_{n-1} + F_{n-2},\!\,

mit den Startwerten

F_0 = 0 \quad\text{und}\quad F_1 = 1.

Grob gesagt ist ein Element die Summe seiner beiden Vorgänger. Hier ist der Aufwand linear, d.h. zur Berechnung von F_n werden n Schritte benötigt. Oder wenn wenn man n verdoppelt , verdoppelt sich die Anzahl der Schritte zur Berechnung. Aber wie ist der Verlauf der Ergebnisse? Wie groß werden die Ergebnisse wenn man n verdoppelt oder vervierfacht?

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>

Motivation

Da man aber nun trotzdem eine Abschätzung für den Aufwand (Schritte, Resourcen, etc. ) braucht und dieser meist nicht direkt ablesbar ist, hat man mehrere Mathematische Methoden entwickelt. Nun könnte man entweder empirisch oder theoretisch die Aufwandsfunktion ermitteln.Daraus entsteht z.B. T_1(n)=n^2 oder T_2(n)=2\cdot n^3+5\cdot n^2-12 und man kann daran bereits die Aufwandsordnung nach der Groß-O-Notation ablesen:T_1 liegt in \mathcal{O}(n^2). T_2 liegt in \mathcal{O}(n^3). Sobald man jedoch Algorithmen entwirft, entstehen Gleichungen wie z.B. T(n)=f(T(n-1)) und es ist nicht mehr so einfach den Aufwand abzulesen. Wie erhält man nun die explizite Form für T(n) das von keinem anderen T(i) abhängt? Also der Form T(n)=f(n) entspricht?

Computeralgebrasysteme(CAS)

Um solche schwierigen Aufgaben dem Mathematiker abzunehmen, hat man sich bequeme Werkzeuge entwickelt, welche diese Arbeit an den Computer delegieren. Es handelt sich um sogenannte Computeralgebrasysteme (kurz CAS). Das sind Programme, die neben dem numerischen auch das symbolische Rechnen beherrschen. Normalerweise würde ein Taschenrechner folgenden Bruch ¹/₃ als Dezimalzahl mit begrenzter Genauigkeit speichern und anzeigen. Ein Symbolischer Rechner dagegen wir es als Division zweier ganzer Zahlen speichern und davon, wenn gewünscht, die dezimale Anzeige ableiten. Außerdem wird im weiteren Verlauf der Rechnung mit diesem Symbol auch immer wieder die Division der beiden Zahlen eingesetzt, sodass das Ergebnis keine wachsende Ungenauigkeit erfährt. Aber natürlich können Sie inzwischen mehr als nur einen Bruch zweier ganzer Zahlen zu speichern. Hier ein Auszug:

-Termumformungen

-Termvereinfachung

-Gleichungslösen

-Extremwertbestimmung

-Graphische Kurvendarstellung

Es gibt verschiedene CAS (z.B. Maple, Mathematica, Matlab, Maxima) und jedes Softwarepaket geht unterschiedlich vor bei umformen von Gleichungen. Meist benutzt man sogenannte Z-Transformationen -Begriffsdefinition

-Funktionen

-Einführung Maple

-Beispiel Fibonacci

...

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

...