AuK/Hilfsmittel Mathematik 2 SS11

Wiki-Quelltext dieser Seite.

== Rekursionsgleichungen ==

=== Motivation === 
(5min.)

-Aufwandsberechnung rekursiver Algorithmen

-da nicht direkt ablesbar

...


<language>Scheme</language>
=== Computeralgebrasysteme(CAS) === 
(5min.)

-Begriffsdefinition

-Funktionen

-Einführung Maple

-Beispiel Fibonacci

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

<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
21	10946
22	17711
23	28657
24	46368
25	75025
26	121393
27	196418
28	317811
29	514229
30	832040
31	1346269
32	2178309
33	3524578
34	5702887
35	9227465
36	14930352
37	24157817
38	39088169
</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 ===

...