Algoritmica

Algoritmi

Algoritmi → specifica della procedura di soluzione di un problema arbitrario.

Descrizione di algoritmi

Descrizione a parole.

Descrizione a schema a blocchi: le istruzioni singole vengono inserite all'interno di un blocco rettangolare.

Noi useremo la rappresentazione a PSEUDOCODICE.

L'algoritmo sta a metà tra il problema e il programma.

Problema e programmazione

• Problema
• Alg 1 → programma
• Alg 2 → programma
• Alg 3 → programma

Descrizione con un programma di programmazione: C, C++, Java, Pascal.

Etimologia

→ dal matematico persiano Al Kwarizmi (800-900 DC), che scrisse delle procedure per risolvere le equazioni.

Algoritmi e specifica

Algoritmi ➞ specifica della procedura di soluzione di un problema.

La specifica è fatta per passi:

• Descrizione a parole
• Descrizione a schema a blocchi: le istruzioni singole vengono inserite all'interno di un blocco rettangolare.

Noi useremo la rappresentazione a PSEUDOCODICE.

L'algoritmo sta a metà tra il problema e il programma.

• Problema
• Alg 1 ➞ programma
• Alg 2 ➞ programma
• Alg 3 ➞ programma

Descrizione con un linguaggio di programmazione: C, C++, Java, Pascal.

Origini degli algoritmi

• Algoritmi ➞ dal matematico persiano Al Kwarizmi (800–900 DC) che scrisse delle procedure per risolvere le equazioni.
• Però l'algoritmo vero e proprio ha una testimonianza ancora più antica nel papiro di _ARMES del 700 ac (algoritmo usi standard per le moltiplicazioni).

Moltiplicazione egizia (A, B)

Ipotesi A > B

P = 0;
While (A > 0) {
    if (A % 2 != 0)
        P = P + B;
    A = A / 2;
    B = B * 2;
}
return P

L'unità aritmetologica (Il computer usa questo algoritmo).

Semplicità degli algoritmi

L'algoritmo deve essere scritto in un modo chiaro per l'esecutore.

Le istruzioni che useremo:

• [while condizione {blocco di istruzioni}]
• [for (i = 0; i < N; i++) {blocco di istruzioni}]

Strutture di controllo

• Interazione del sottoprogramma
• Prima istruzione
• Istruzione di ciclo
• Istruzione condizionale
• Istruzione return

If condizione {blocco di istruzioni} else {blocco di istruzioni}

Moltiplicazione egizia: perché funziona?

A/2 * 2B se A è pari. A/2 x 2B + B se A è dispari.

Scelta dell'algoritmo migliore

Si misura la bontà (complessità) di un algoritmo.

Computational complexity

Parametri più importati: tempo di computazione, spazio occupato.

Esercizio

12 monete, al più una è falsa - più leggera, più pesante.

Bilancia con due piatti.

Operazione di confronto: pesata.

È possibile stabilire qual è la moneta falsa con 3 pesate?

Dopo una pesata posso discriminare tra 3 situazioni diverse: 9, 27.

Occorrono 3 pesate per risolvere.

Dopo 1 pesata discrimino tra 3³ situazioni.

Pesata e discriminazione

Con 3 pesate 3³ = 27 > 25.

Stabilire un limite inferiore al numero di pesate.

Algoritmo ottimo

• 1/3 ; 5,6 ; 7,8,9 ; 10,11,12
• Alg. che termina con tre pesate in tutti i casi possibili.
• Nel caso ottimo 1 pesata.
• Nel caso peggiore 4 pesate.

Modello di riferimento

• Modello RAM (random access model)
• Von Neumann
• CPU (central processing unit)

Il computer ha programmi memorizzati che quando viene avviato esegue ogni comando passo passo.

Fetch and execute

L'istruzione del programma viene portata nell'unità di controllo.

A = A + B

Leggi A

Leggi B

Manda A e B alla ALU

Calcola A + B

Scrivi il risultato in A

Ipotesi: 1 dato è contenuto in una cella di memoria

Operazioni aritmetiche: +, -, *, / richieste tempo costante O(1)

Operazioni logiche: AND, OR, NOT

Operazioni confronto: =, ≠, >, <, ≥, ≤

Operazioni salto: condizionato, incondizionato

IF (condizione) {blocco1} else {blocco2}

Stato condizionato

FOR (i=0; i<u; i+1) {istr 1 istr 2 istr 3}

Stato incondizionato

Istruzioni pesanti -> quelle all'interno dei cicli.

For (I=0; I<N; I++) {blocco}

Il costo di blocco può cambiare ad ogni iterazione ed è ti all'iterazione i-esima.

Costo(blocco) = C => U: C

Valutare il while è più complicato perché non si sa quante volte avviene

While (guarda) {blocco} ti costo del blocco all'iterazione guarda verificato m volte

Esercizio

Leggi N elementi da input e controlla se corrispondono il dato Z.

print ("inserisci il numero di elementi Ne2");
lead (N,Z);
trovato = false;
for (I=0; I<N; I++) {
    print ("inserisci il dato");
    lead (D);
    IF (D==Z)
        trovato = true;
    else
        print ("Z non appartiene all'insieme");
}

O(u) θ(u)

Nel 1600 algoritmo aveva lo stesso significato di matematica

Macchina di Turing (MdT) - È definita da un insieme di regole che definiscono il comportamento della macchina (in pratica un automa a stati finiti) e un nastro di input/output.

Il nastro può essere immaginato come tale.

Posso creare una MdT capace di simulare qualunque macchina. Sono numerabili e posso dire quale numero hanno (stabilita la l-iesima), sono goedelizzabili.

Con la macchina di Von Neumann si può effettuare qualunque tipo di calcolo

• Sia su dati numerici sia su testi che immagini.

Tesi Church-Turing

Tutte le funzioni sono calcolabili con la MdT. Non è dimostrabile per tutte le funzioni.

Quando si studia la complessità di un problema è bene cercare di valutare come questa cresce al variare delle dimensioni dello stesso.

Complessità quadratica

• Moti di matrici
• Somma di matrici

Complessità cubica - moltiplicazione di matrici

Complessità esponenziale

Algoritmi probabilistici

• Algoritmo Montecarlo - si ottiene un risultato probabilmente scorretto in un tempo finito
• Algoritmo LasVegas - si ottiene un risultato corretto in un tempo probabilmente piccolo
• Algoritmo Atlantic City - si ottiene un risultato probabilmente corretto in un tempo probabilmente piccolo

Complessità in spazio

Quanta memoria serve a risolvere un problema

print ("inserisci il numero di elementi Ne2")
read (N,2);
trovato = false;
for (I = 0; I < N; I + 1) {
    print ("inserisci dato D");
    read (D);
    if (D == 2)
        trovato = true;
}
if (trovato == true)
    print ("2 è stato trovato")
else
    print ("2 non è stato trovato");

Variabile booleana assume due valori

0 = falso 1 = vero

Il parametro N viene chiamato dimensione dei dati (input size)

La complessità di tempo è una funzione che specifica il numero di iterazioni in funzione della dimensione dei dati.

La complessità è data dal numero di cicli eseguiti.

O(1) ➡(1) ⬅ k= costante ciò indipendente dalla dimensione dei dati

La complessità di questo alg è di ordine Θ(1).

Algoritmo migliore che si ferma dopo aver trovato 2 (con while)

print ("...")
read (N,2)
trovato = false, j = 1
while (j <= N) && (trovato = false) {
    print ("inserisci dato D");
    read (D);
    if (D == 2)
        trovato = true;
    j + +;
}

Se prima la complessità era N in tutti i casi, questa volta:

Complessità secondo i vari casi

• Caso ottimo Θ(1)
• Caso pessimo Θ(N)
• Caso medio v/2 volte costo blocco = Θ(N)(1+2+...+N)/N = (N+1)N/2N = N+1/2

Facciamo riferimento a un array A di N elementi

A [0 3 5 5 2 8]

• 0 1 2 3 4 5 N-1
• Posizione dell'elemento
• Contenuto della -esima cella dell'array [0 3 5 5 2 5 11]
• A[2]=5
• 0 1 2 3 4 5 6

Cerca 2 in un array A di N elementi già in memoria

print ("inserire 2");
read (2);
L=0;
while (I<=U) && (A[I]!=2) {
    I ++;
}
if (L==U)
    print ("2 non appartiene all'insieme");
Θ(n)

• Organizzare il programma come sottoprogramma che stabilisca se Z appartiene o meno a un array A di N elementi.

Ricerca (A,N,Z)
L=0;
while ((L<N) && (A[L]!=0)
    L++;
if (L==U)
    return false;
else
    return true;

B e C sono già in memoria:

if (Ricerca (B,N,Z) && Ricerca (CM,Z))
    print ("Z∈B∩C")
else
    print ("Z∉B∩C")
O(u)

Tasso di crescita

Tutte le funzioni che crescono in maniera lineare {10u=53u+61/2u 1/5}⊖u O(u)

{3u²-514u²+6u-71/2 u² 3u}⊖u² O(u²)

Ordini di grandezza

• f(u)logu ≤ √u ≤ u ≤ ulogu ≤ u²
• u=100
• u²=10,000
• ulogu=1000
• u^k < … < k^u crescita esponenziale

Ordine di grandezza

O, Ω, O(F(u)) è l'insieme delle funzioni g(u) tali che esistano due costanti positive c e u₀: g(u) ≤ c·F(u) per u ≥ u₀

g(u) = 3u² + 6u + 5

O(u²)

O grande è un limite superiore a g(u)

Complessità asintotica

Ω(F(u)) è l'insieme delle funzioni g(u) tali che esistano due costanti positive c e u₀: g(u) ≥ c·F(u).

Ω è un limite inferiore(F(u)) se g(u) è O(F(u)) e Ω(F(u))

g(u) è (F(u)) è il limite esatto

Analisi complessità

• 7+3 è O(u)? Sì
• è O(u²)? Sì
• è Ω(u)? Sì
• è (u)? Sì
• è O(logu)? No
• è Ω(logu)? Sì

Ricerca di 2

Ricerca di un elemento in un insieme dato con il ciclo for ϴ(1) il numero di operazioni di un algoritmo si può esprimere

• Col ciclo while nel caso ottimo O(n) limite superiore
• Nel caso pessimo O(n)
• Si interrompe appena trova 2

Ordinamento

A={a₀,...,a_u-1}

A'={a'₀, a'₁,..., a'_u-1}

a'₀ ≤ a'₁ ≤ ... ≤ a'_u-1 - ordinamento in ordine non decrescente

Selection Sort

• Problema del sorting
• u=10
• μ=8 3 2 1
• μ = valore del minimo
• indiceMin = posizione del minimo
• 1 3 5 2 7 8 5 1 0 8 7
• Cerco il prossimo minimo e così via

SelectnnSort (A, u):
for (i=0; i<u-1; i++) {
    minimo = A[i];
    indiceMin = i;
    for (j = i+1; j<u; j++) {
        if (A[j] < minimo) {
            minimo = A[j];
            indiceMin = j;
        }
    }
    A[indiceMin] = A[i]; 
    A[i] = minimo;
}

Iterazione ciclo i-esimo

Dopo l'iterazione del ciclo i-esimo i elementi sono ordinati.

Operazione principale è il confronto tra elementi.

Numero di confronti

• 0 u-1
• 1 u-2
• 2 u-3
• ... u-2 1

Il numero di confronti è uguale alla somma dei primi u-1 numeri.

n° confronti = (u-1) + (u-2) + (u-3) = u (u-1) / 2 = (u²)

InsertionSort

InsertionSort (A, u):
for (i=1; i<u; i++) {
    prossimo = A[i];
    j=i;
    while (j > 0) && (A[j-1] > prossimo) {
        A[j] = A[j-1];
        j = j-1;
        A[j] = prossimo;
    }
}

1. 2 5 6 8 3
2. 0 1 2 3 4
3. 0 1 22 5 6 8
4. 2 5 6 8
5. 2 5 6 8
6. 2 5 6 8
7. 2 3 5 6 8

Caso ottimo

• i\ conf
• 0 1
• 1
• 1
• 1
• u-1 1

Caso pessimo

• i\ conf
• 0 1
• 1
• 2
• 3
• u-1 u-1

Complessità di InsertionSort

• O(u²)
• {O(u)O(u²)InsertionSort}
• Caso ottimo O(u)
• Caso pessimo O(u²)
• 1 SelectionSort O(u²)
• 2 InsertionSort O(u²)
• Limite inferiore al numero di confronti

Discriminazione tra situazioni diverse

Dopo i confronti si può discriminare tra 3! situazioni diverse.

Abbiamo un numero variabile di elementi.

abc acb bac bca cab cba

u=3 u^obbligatori=6

Binary Search

k) des = cen-1;
else su = cen+1;
}
}}
sin=0 des=7
3 5 9 12 15 16 20 25
0 1 2 3 4 5 6 7
k=5
cen=3
des=3-1=2
cen=(sin+des)/2=0+2/2=1
k=17
cen=3
sin=3+1=4
cen=(4+7)/2=5

sin=5+1=6
cen=(6+7)/2=6
A[cen] 20!=17
des=6-1=5
sin=6
des=5

Uso del ciclo while

While viene usato quante volte occorre a un u° di essere diviso per 2, finché non è uguale a 1

u u u u u2 2 2 2 2 -1

u=1.:1. u=2.: logu=log2=1

Complessità della ricerca binaria

Ricerca binaria O(logu)

Ricerca binaria è un algoritmo di ricerca ottima perché limite inferiore N(logu) e l'algoritmo ha complessità O(logu)

Algoritmi ricorsivi

Un algoritmo ricorsivo è un algoritmo che richiama se stesso.

u1:=u(u-1)(u-2)...1

u1:=u(u-1)

REAIT(u) IF U=1 else return u x REAIT(u-1)

u x(u-1) x REAIT(u-2)

Fattoriale con algoritmo

FATT(u):
F=1;
for (L=1; <=u;L++) 
    F=FxL;
return F;

Cosa fa il computer in corrispondenza di una chiamata ricorsiva?

1. Copia l'esecuzione della procedura chiamante e valori delle variabili dei parametri.
2. Esegue la procedura chiamata a partire dall'inizio.

Quando l'esecuzione di una chiamata si termina si rientra nel corpo della procedura chiamante ripristinando i valori congelati dal punto di interruzione.

Ricerca di K

Ricerca binaria s_in ≤ A[c] ≤ K k ≥ A[c] si considera la parte destra k RicBinRic (a, k, sin, des)

if (sin == des) {
    if (k == a[sin]) 
        return sin;
    else 
        return -1;
}
cen = (sin + des) / 2;
if (k