Appunti completi Algoritmica

Algoritmica e algoritmi corretti

L'obiettivo è progettare algoritmi che risolvono sempre e solo il problema in questione ed efficienti, ossia che lo fanno nel minor tempo possibile o, a parità di tempo, utilizzando il minor numero di celle di memoria.

Algoritmo

Un algoritmo è una sequenza di passi, ovvero operazioni elementari, univocamente determinati e non ambigui che, se svolti da un esecutore (nel nostro caso il calcolatore), portano alla soluzione di un problema. L’algoritmo è la specifica di un modo per risolvere il problema posto; a ogni problema possono essere associati moltissimi algoritmi, e noi vorremmo andare a trovare quello più efficiente.

Moltiplicazione egizia

def Molt(A, B):
    p = 0
    while A != 0:
        if A % 2 != 0:
            p = p + B
        A = A // 2
        B = B * 2
    return p

A * B = {A/2 * 2B se A è pari} / {[(A-1)/2] * 2B + B se A è dispari}. Costo in tempo: n².

Problema delle 12 monete

Si codifica come un albero di decisione (caso di pesare 4 monete per piatto). Grazie al numero di soluzioni del problema, riusciamo a trovare un limite inferiore al numero di passi richiesti da un qualsiasi algoritmo che lo risolva. Il principio di bilanciamento ci permette di migliorare l’efficienza complessiva dell’algoritmo.

RAM

"Random Access Machine" è uno schema astratto basato sull’architettura di Von Neumann, la cui idea è quella di memorizzare sia i programmi che i dati nella memoria come sequenze binarie. Consiste di:

• Processore di calcolo, il quale dispone di un’Unità centrale di elaborazione (per eseguire operazioni aritmetico/logiche) e di due registri:
• Contatore di programma, che contiene l’indirizzo di memoria della prossima istruzione da eseguire
• Accumulatore, dove vengono effettuate le operazioni elementari
• Infinite celle di memoria a cui si accede in tempo costante (memoria di dimensione illimitata)

Operazioni sulla RAM

• Operazioni aritmetiche: (+, -, *, /)
• Operazioni di confronto: (<, =, >)
• Operazioni logiche: (And, Or, Or Esclusivo, Not)
• Operazioni di trasferimento: (per spostare dati dalle celle di memoria all’accumulatore)
• Operazioni di controllo: (per passare il controllo da un’istruzione all’altra, ad esempio salti, chiamate di funzioni, ecc.)

Ipotesi del costo uniforme

Ogni operazione elementare richiede un tempo costante d’esecuzione. Conseguenza: il numero di operazioni elementari ci fornisce una misura del tempo di esecuzione (a meno di una costante, che non ci interessa specificare, perché vogliamo vedere il comportamento degli algoritmi, e non il tempo fisico di esecuzione).

Analisi della complessità della RAM

• Word model: I dati sono abbastanza piccoli da essere contenuti in una cella di memoria della RAM; le operazioni su questi dati sono considerate di costo costante.
• Bit model: I dati sono elaborati e/o crescono e non possono più essere contenuti in una cella di memoria della RAM; si conta anche il lavoro fatto sulle singole cifre.

Complessità computazionale concreta

Studia l'efficienza degli algoritmi e il costo della risoluzione dei problemi, facendo riferimento in primo luogo al tempo (irreversibile), ovvero al numero di passi eseguiti, e poi allo spazio (riutilizzabile), ovvero al numero di celle di memoria utilizzate, esclusi i dati d’ingresso del problema.

Complessità: 3 casi possibili di analisi

1. Complessità al caso pessimo: costo massimo su tutte le possibili istanze di dimensione n.
2. Complessità al caso ottimo: costo minimo su tutte le possibili istanze di dimensione n.
3. Complessità al caso medio: media del costo su tutte le possibili istanze di dimensione n.

La più interessante è quella al caso pessimo, per tre ragioni fondamentali:

• Fornisce un limite superiore al tempo di esecuzione su qualsiasi input (l’algoritmo non impiegherà mai più tempo di quello stabilito).
• Il caso pessimo è quello che solitamente si presenta di più nei vari problemi.
• Si comporta spesso in maniera molto simile a quella al caso medio, ma è più semplice da trovare.

Per confrontare l’efficienza di più algoritmi, si fa quindi sempre riferimento al loro costo in tempo al caso pessimo.

Ricerca di una chiave in un array

Si attuano due metodi di ricerca diversi a seconda se la sequenza è ordinata o meno.

Sequenza non ordinata

Ricerca lineare (o sequenziale): gli elementi dell’array vengono scanditi l’uno dopo l’altro sequenzialmente, confrontandoli con la chiave cercata. Il caso ottimo è quando la chiave si trova nel primo elemento, il caso medio quando si trova nell’elemento a metà array e il caso pessimo quando si trova nell’ultimo elemento o non si trova nell’array; la complessità è O(n), dato che è necessario scorrere tutto l’array. L’inserzione di nuove chiavi si realizza aggiungendole in fondo all’array con costo circa 1 e la cancellazione si realizza compattando gli elementi dell’array con costo circa n.

Sequenza ordinata

Ricerca binaria: Si va sull'elemento al centro dell'array: se esso è quello cercato, la ricerca è conclusa, altrimenti cerchiamo nella parte inferiore (se è minore del centro) o nella parte superiore (se è maggiore del centro) del vettore. Questo processo si ripete finché non si trova il numero o non è più possibile dividere a metà. Al caso ottimo basta 1 confronto; al caso medio/pessimo servono logn confronti.

Osserviamo che log₂n ci dice il numero di volte che n si deve dividere per due per arrivare a 1. Quindi se abbiamo una collezione di n = 1024 oggetti, una ricerca sequenziale, nel peggiore dei casi, deve visitarli tutti e, quindi, farà n confronti mentre la ricerca binaria fa: ⌈log₂n⌉ confronti (log₂1024=10).

Devi restituire elemento del dizionario chiave minima, come fare?

Prendo il nodo foglia più a sinistra perché so che è il minimo. Complessità: O(h), dipende dall'altezza dell'albero, uguale alla distanza dalla radice al nodo foglia più profondo; nel caso pessimo può essere, se con n nodi, alto n-1. Per garantire che la complessità sia log n bisognerebbe fare un albero binario 1-bilanciato.

Insertion Sort

Sorting: in gergo informatico, consiste nel disporre in ordine «crescente» n elementi fra cui è definita una relazione di ordinamento totale indicata con ≤. Algoritmo molto semplice, non è molto diverso dal modo in cui un essere umano, spesso, ordina un mazzo di carte. È un algoritmo in place, cioè ordina l'array senza doverne creare una copia, risparmiando memoria.

Questo algoritmo si basa sull'ipotesi che i primi i elementi contenuti nella porzione del vettore tra le posizioni 0 e i-1 siano ordinati. Si inserisce l'elemento A[i] tra questi nella posizione corretta, confrontandolo con gli elementi alla sua sinistra, ottenendo così l'ordinamento fino alla posizione A[i], e si ripete l'operazione per inserire ogni n a partire da i + 1 finché tutti gli n elementi siano stati «inseriti».

Si inizia con i = 1 (anziché i = 0) poiché un sottoinsieme di un solo elemento A[0] si considera ordinato.

Complessità:

• Caso ottimo: dati in ingresso ordinati in senso crescente, richiede n confronti. T(n)=Θ(n)
• Caso pessimo: dati in ingresso ordinati in senso decrescente, richiede n² confronti. T(n)=Θ(n²)
• T(n)=O grande(n)
• S(n)=O(1)

Selection Sort

Consiste nello scambio di due elementi nell’array. L’array viene diviso in due parti da un indice (detto cursore) che scorre dalla prima alla penultima posizione. A ogni passo si cerca l’elemento minimo tra quelli della seconda parte e si mette nella posizione indicata dal cursore.

Si basa sul principio di:

• Selezionare l’elemento più piccolo min
• Scambiarlo

Vantaggi:

• Algoritmo semplice, numero di spostamenti < n

Svantaggi:

• Algoritmo non ottimale, la complessità non dipende dai dati. Il numero di confronti è indipendente dall’ordine iniziale dell’array iniziale. T(n)=Θ(n²)
• S(n)=O(1)

Bubble Sort

È forse il metodo più usato quando si deve ordinare a mano uno scaffale di libri. Il metodo delle bolle consiste nello scorrere l’array effettuando scambi quando due elementi contigui non sono nell’ordine giusto. Dopo ogni passata si sposta il punto di arrivo della scansione.

Complessità:

• Il controllo viene eseguito n(n-1)/2 volte per cui l'algoritmo ha una complessità dell'ordine di n², anche il numero degli scambi, nel caso peggiore, può essere n².

Vantaggi:

• Algoritmo semplice, gli scambi vengono effettuati tra posizioni contigue

Svantaggi:

• Algoritmo non ottimale, forse il peggiore degli algoritmi comunemente usati: il numero di spostamenti può essere elevato. T(n)=O(n²)
• S(n)=O(1)

Notazione asintotica

Usata per esprimere il tempo (o lo spazio) di esecuzione in ordine della grandezza di un algoritmo, al crescere della dimensione dell’input.

Notazione O

(Limite asintotico superiore) "O grande", <: al crescere di n e a partire da un valore n₀ g(n) f(n), non sale mai al di sopra di a meno di una costante moltiplicativa. La usiamo per algoritmi di cui non conosciamo il comportamento, ma che sicuramente non superano f(n), o per algoritmi che non si comportano allo stesso modo per tutti gli insiemi di dati di dimensione n.

Notazione Ω

(Limite asintotico inferiore) "Omega grande", >: al crescere di n e a partire da un valore n₀ g(n) f(n)valore, non scende mai al di sotto di a meno di una costante moltiplicativa. La usiamo per indicare il limite inferiore al tempo di soluzione di un problema.

Notazione θ

(Limite asintotico stretto) "Teta", =: al crescere di n e a partire da un valore n₀, f(n) ha lo stesso andamento di a meno di costanti moltiplicative. La usiamo per indicare il tempo di un algoritmo di cui si conosce il comportamento e che, a pari valore di n, si comporta ugualmente per tutti gli insiemi di dati di dimensione n che si presentano. Quindi, se g(n) è di ordine θ(f(n)), allora g(n) è di ordine O(f(n)) e di ordine Ω(f(n)).

Tutte le costanti positive sono dell’ordine di 1. Elenco funzioni note per tasso di crescita crescente: Costanti -> Logaritmi -> Polinomi -> Esponenziali con base >1.

Esempi di programmazione ricorsiva

Un algoritmo ricorsivo richiama sé stesso su input di dimensione minore, o risolve direttamente il problema su input sufficientemente piccoli. Alcuni esempi:

Calcolo del fattoriale

Passo base 0! = 1 (chiusura), o n! = n*[(n-1)!] (semplificazione). La complessità è di ordine O(n). Il costo in tempo: T(n)= T(n-1)+O(1), dove T(n) è il costo di fattoriale n, T(n-1) è il costo del calcolo di fattoriale n-1 e O(1) è il costo del lavoro al di fuori della chiamata ricorsiva.

Stampa in binario

La rappresentazione di un intero positivo n è uguale alla rappresentazione di un intero positivo n/2, seguita da 0 se n è pari e da 1 se n è dispari. Complessità di ordine O(logn).

Calcolo dei coefficienti binomiali

(n k) = [n!/(n-k!)k!] per due interi 0 ≤ k ≤ n. Per un insieme arbitrario, è il numero di combinazioni semplici di n elementi in gruppi di m (numero di sottoinsiemi di cardinalità m). Per esempio, {a,b,c,d,e} vi sono (5 2) = 10, cioè ci sono 10 gruppi di due elementi. La somma su ogni riga i è pari a 2ⁱ, pari al numero di sottoinsiemi di un insieme di i elementi. Ogni elemento della riga i è la somma di due elementi della riga i-1 precedentemente memorizzati. T(n,m) = θ(nm).

Algoritmo ricorsivo risolvibile in tempo esponenziale

Torri di Hanoi in = 64 dischi

Regole

• Si sposta un disco alla volta
• Non si può mettere un disco di diametro maggiore su uno di diametro inferiore

3 passi:

1. Spostiamo ricorsivamente i primi n-1 dischi dal primo al terzo piolo, usando il secondo come piolo di appoggio
2. Spostiamo l’ultimo disco (rimanente) dal primo al secondo piolo
3. Spostiamo ricorsivamente i primi n-1 dischi dal terzo piolo al secondo, usando il primo come piolo di appoggio

Dimostrato che 2ⁿ-1 mosse sono necessarie.

Ricerca binaria ricorsiva

Complessità O(logn).

Paradigma del DIVIDE et IMPERA

Una tecnica adottata da molti algoritmi ricorsivi:

1. CHIUSURA: se il problema ha dimensione minore di una costante piccola, si risolve direttamente