Appunti algoritmi e strutture dati, parte 1

Formula di Binet

Rappresentazione: l'n-esimo numero di Fibonacci senza ricorsione.

Ricoresivamente, l'n-esimo numero di Fibonacci si ricava cosi:

• F ( n ) = { 1 se n = 1 , 2 , F ( n ) = F ( n - 1 ) + F ( n - 2 ) se n > 3, }

Formula di Binet:

∀ n ∈ ℕ F ( n ) = 1 5 ( Φ n - 1 Φ n )

Dimostrazione

Consideriamo un numero x, appartenente alla sequenza di Fibonacci, possiamo rappresentarlo come un segmento formato dalla somma di due segmenti a e b, costituenti F_n-1 e F_n-2: a : b =

A questo punto sostituiamo ab con Φ:

Induzione

Caso base n = 1,2

Ok.

Paso induttivo n≥3.

Assumo che la proprietà sia valida fino a n-1.

Per definizione F_m=F_m-1 + F_m-2 e per ipotesi induttiva

(1/√5) (Φ^m-1 + Φ^n-2 - Φ^m-2 - Φ^n-2) = (1/√5) (Φ^m-1 Φ^m-2 + Φ^m-2 - m^m-2) =

(1/√5) (Φ^m-1 - Φ^m-2) Φ^n-2) adesso è della forma (1/√5) (Φ^m Φ^m-1).

Bisogna dimostrare che Φⁿ Φ^n-1 - m² Φ^n-2 + ₁ ^m-2 =

Φ^m (Φ^n-1 + Φ^n-2 - Φ^n-2 - Φ^n-2) = Φ^m (1/2 + 1/2^n-2) =

Φⁿ (Φ + 1) = Φⁿ (Φ + 2) = Φⁿ (Φ₂ - Φ) = Φ^m (Φ/Φ₂) = Φⁿ

Nella dimostrazione per induzione bisogna usare tutte le potesi e riuscire ad arrivare nella forma della tesi.

Tradotto in termini informatici: Fib1 (int m) → int

return (Φ^m - Φ^m)

Questo algoritmo usa, però, numeri irrazionali che non sono rappresentabili nel mondo reale quindi il risultato sarà sempre un'approssimazione. Man mano che m è sempre più grande, il risultato si allontana sempre di più dal risultato effettivo.

Si definisce complessità di un algoritmo il numero di istruzioni che vengona eseguite per costituire la risposta.

Fib4 (int m) -> int

1. a=1, b=1
2. for i=3 to m do
3. c=a+b
4. a=b
5. b=c
6. return c

Tempo Lineare

Spazio Costante

Corretto SI

CRESCITA ASINTOTICA

Punti di interesse: Complessità, è una funzione della dimensione dei dati in ingresso (funzione di m);

Complessità asintotica, ossia per valori più grandi di m;

ignoriamo le costanti.

DEFINIAMO:

1. O(g(m)) = { f(m) | ∃c>0 ∃m₀∈ℕ ∃∀m>m₀: f(m) ≤ c∙g(m) }

GRAFICAMENTE:

ALTRE CLASSI DI COMPLESSITÀ

Definiamo: f(m) = o(g(m)) <=> ∀c > 0 ∃m₀∈ℕ ∀m ≥ m₀ : f(m) < c·g(m)

o(g(m)) ⊆ O(g(m))

f(m) = ω(g(m)) <=> ∀c > 0 ∃m₀∈ℕ ∃m ≥ m₀ : c·g(m) < f(m)

ω(g(m)) ⊆ Ω(g(m))

Vogliamo provare che O(g(m)) ∩ Ω(g(m)) = ∅

f(m) = O(g(m)) → ∀c > 0 ∃m₀∈ℕ ∀m ≥ m₀ : f(m) < c·g(m)

f(m) = Ω(g(m)) → ∃c' > 0 ∃m₁∈ℕ ∀m ≥ m₁ : f(m) ≥ c·g(m)

È evidente che f(m) < c·g(m) e f(m) ≥ c·g(m) non possono coesistere, quindi o(g(m)) ∩ Ω(g(m)) = ∅

UTILITÀ DEL LIMITE PER IDENTIFICARE LA CLASSE DI COMPLESSITÀ

DEFINIZIONE DI LIMITE DI UNA SUCCESSIONE

{aₙ} ⊆ ℝ lim aₙ = l, l∈ℝ

∀ε > 0 ∃m₀∈ℕ ∀m ≥ m₀ : |aₙ - l| < ε

PROPRIETÀ:

f(m) = o(g(m)) <=> lim_m→∞ f(m)/g(m) = 0

ossia f cresce più lentamente di g e il rapporto diventa sempre più piccolo man mano che m cresce.

Istruzioni Condizionali:

if condizione then

Body 1

else

Body 2

Bisogna valutare il tempo di "condizione", che potrebbe chiamare ulteriori funzioni, di Body 1 e Body 2.

T(m) = T(cond) + max { T(Body 1) , T(Body 2) }

Ci interessa il caso peggiore, quindi basta solo il Body più lungo.

Ciclo for:

for i=1 to n do

Body

T(m) = m • T(Body)

MyAlgorithm (int m) -> int

int i, j, a;

if (m > 2) then

a = 2   O(1) = tempo costante

for i=1 to m do

for j=1 to m do

a = a+(i+1)*(j+2)   n² volte viene eseguito

for i=1 to 16 do

a = a + MyAlgorithm(m/a)   16 volte

return a;

else

return & m-1;

T(m) = n² + 16T(m/a)