Einleitendes Beispiel

Berechnung von F_n, die n-te Fibonachi-Zahl:
F₀ = 0 ; F₁ = 1
F_n = F_n-1 + F_n-2 für alle $n\ge 2$

• 1.Methode: Funktionales Programmieren

  $$\begin{split} \text{f}(n):= \ \ \ & \text{ \underline{if} }... ...) + \text{ f}(n-2) \\ & \text{ \underline{fi} } \end{split}$$

  T(n): Zeitbedarf für die Berechnung von f(n):
  $\text{T}(n) = \text{T}(n-1) + \text{T}(n-2) \hspace{5mm} ; n\geq 2$
  T(0) = T(1) = 1
  $\Rightarrow$T(n) = c$_1\left(\frac{1+\sqrt{5}}{2}\right)^n +$c$_2\left(\frac{1-\sqrt{5}}{2}\right)^n$
  $\left \{ \begin{array} {l} n = 1 :\ \ \ \ \ \ \ 1 = \text{c}_1(\frac{1+\sqrt{... ...) \\ n = 0 :\ \ \ \ \ \ \ 1 = \text{c}_1 + \text{c}_2 \\ \end{array} \right.$
  c$_1 = \frac{1}{2} + \frac{\sqrt{5}}{10}$
  c$_2 = \frac{1}{2} - \frac{\sqrt{5}}{10}$
  $\Rightarrow$ T$(n) = (\frac{1}{2} + \frac{\sqrt{5}}{10})(\frac{1+\sqrt{5}}{2})^n + (\frac{1}{2} - \frac{\sqrt{5}}{10})(\frac{1-\sqrt{5}}{2})^n$
  
• 2.Methode: Dynamische Programmierung
  array: F[0:n] ; F[0] = 0 ; F[1] = 1

  $$\begin{split} &\text{ \underline{for} } i = 2 \text{ \under... ...xt{\ \ F}[i] = \text{ F}[i-1] + \text{ F}[i-2] \\ \end{split}$$

  Zeitbedarf :
  
• 3.Methode: Direkt (mit etwas mathematischer Arbeit)

  $$\begin{split} \text{F}(n):=\frac{1}{\sqrt 5}\left ( \left(\... ...n - \left(\frac{1-\sqrt 5}{2}\right)^n \right) \\ \end{split}$$

  Zeitbedarf:
  

Einleitung und Auffrischung  

• Was sind ,,kombinatorische`` Algorithmen?
• Maschinenmodelle
• Komplexitätsmaße
  • Probleme und Funktionen
  • Wachstumsverhalten von Funktionen
  • Rekursionsgleichungen
    • Multiplikatoren
    • Charakteristisches Polynom
    • Erzeugendenfunktionen
    • Transformation des Definitions- bzw. Wertebereichs