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 logscale y
set xlabel "n"
set ylabel "T(n)"
set ytics(1,10,100,1000,10000,100000,1000000,10000000)
plot [n=0:8]10*2**n,10000*2**n,10**n
</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 ===

...