AuK/Hilfsmittel Mathematik 2 SS11

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
'''<b>Autor:</b>'''
 Bernd Schönlebe
 
== Rekursionsgleichungen (Differenzengleichung)==
=== Motivation === 
[[Datei:Droste.jpg|200px|thumb|right|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.

-Aufwandsberechnung rekursiver Algorithmen

-da nicht direkt ablesbar

...

=== Computeralgebrasysteme(CAS) === 
(5min.)

-Begriffsdefinition

-Funktionen

-Einführung Maple

-Beispiel Fibonacci

<code id="4b960fdc15037" rows="20" cols="90">(define fib
  (lambda (n)
    (if (< n 2)
         1
         (+ (fib (- n 1)) (fib (- n 2))))))</code>
<run id="4b960fdc15804">
(fib 5)
</run>

Und hier die Folge als Graph:

<gnuplot>
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>
</gnuplot>
...


=== 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 ===

# '''Computeralgebrasysteme(10min.)'''
# '''Raten und Einsetzen(20min.)'''
# '''Konstruktive Induktion(20min.)'''
# '''Iterationsmethode(20min.)'''
# '''Mastermethode(20min.)'''

...


=== Lösungen ===

...