Algoritmica

Algoritmi - specifica della procedura di soluzione di un problema aritmetico

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

• alg 1 - programma
• alg 2 - programma
• alg 3 - programma

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

ETIMOLOGIA - dal matematico persiano AL KWARITSMI (800-900 dc)

Però l'algoritmo vero e proprio ha una testimonianza ancora più antica nel papiro di AKMES del 200 AC (algoritmo non standard per le moltiplicazioni).

Questo algoritmo basava le operazioni su moltiplicazioni e divisioni per due, questo perché, utilizzando l'abaco, facevano solo divisioni intere.

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

13

13

75

25

325

Unità aritmetologica (Il computer usa questo algoritmo)

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
• }

istruzione del sottoprogramma

prima istruzione

istruzione di ciclo

istruzione condizionale

istruzione return

Istruzioni pesanti

• quelle all'interno dei cicli

Se costo (blocco) = c ⇒ u ⋅ c

Il costo del blocco all'iterazione guarda verificato m volte

O(u) ϴ(u)

Ordine e Theta di u

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)

Ω(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

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

ricerca di 2

Ricerca ordinamento

L'inferiore

Limite inf. per l'ordinamento è Ω(u log u)

(Alve per animare l'algoritmo)

Funzionano anche con elementi ripetuti

INPUT: 3, 3

OUTPUT: 3, 3, 3

L'algoritmo è stabile se mantiene la posizione relativa degli elementi ripetuti

u = 1

Quante soluzioni? Numero delle permutazioni

Tutte le possibili soluzioni di K! K non esiste

u! + 1 soluzioni

Operazione base: confronto tra elementi

dopo 1 confronto si aprono 3 vie

dopo t confronti si aprono 3^t vie

3^t ≥ u+1, log₃ 3^t ≥ log₃ (u+1), t ≥ log₃ (u+1) =

Ω(log u)

limite inferiore