Algoritmi e strutture dati

Algoritmi e strutture dati

Martedì 29 settembre 2015 13:30
Appunti di Alessandro Sperotti

Passi per risolvere un problema

• Formulazione del problema
• Definire la soluzione
• Implementare la soluzione
• Testing
• Valutare la soluzione

Algoritmo

Sequenza finita di istruzioni, ciascuna delle quali ha un preciso significato e può essere eseguito in un tempo finito. Algoritmo -> "Metodo per risolvere un problema".

Caratteristiche fondamentali

Input, Output.

Algoritmo

• Un insieme di valori in input
• Un insieme di valori in output

Un algoritmo è corretto se produce un output corretto per il problema, ossia lo risolve. Per testare l'efficienza di un algoritmo bisogna testarlo su più casi, con valori diversi, non solo nel caso specifico del problema.

Esempio:

Problema -> Ordinare un insieme di numeri interi
Istanza -> S = {5, 1, 4, 6}
Output atteso -> S' = {1, 4, 5, 6}

Un algoritmo deve essere

1. Corretto
2. Efficiente (si valuta sia in termini di tempo, che spazio)
3. Comprensibile (questione più legata ai linguaggi di programmazione)

Fattori che influiscono sul tempo

1. Input
2. Qualità (come è stato scritto l'algoritmo)
3. Complessità delle istruzioni (istruzioni di base)
4. Complessità dell'algoritmo

Esprimiamo la complessità dell'algoritmo (numero istruzioni) attraverso la funzione T(n) con n che è la dimensione dell'input: n=10, T(n)=T(10).

Nel controllare la complessità dell'algoritmo si controllano 3 casi:

1. Caso migliore
2. Caso medio
3. Caso peggiore (il più importante)

Per valutare che l'algoritmo abbia un tempo efficiente anche nel caso di input con grandi numeri si valuta la complessità asintotica (tendenza di crescita di n).

Strutture dati

ADT (Abstract Data Type)

L'ADT è un modello matematico per i dati con un set di operazioni definite su quel modello.

Vantaggi:

1. Si sa esattamente come organizzare i dati.
2. Si pone ad "alto livello", slegato da linguaggi di programmazione.

Data Type (Tipo di Dato)

L'insieme di valori che può assumere una variabile del tipo specificato.

Data Structure (Struttura Dati)

Collezione di variabili (anche di tipo diverso) collegate in vario modo (usata per rappresentare ADT).

Varie strutture dati:

• Array: struttura dati che contiene dati tutti dello stesso tipo. Ogni array possiede un indice che identifica ogni cella, ed il contenuto della cella stessa. A[i] -> i-esima cella.
• Record: Struttura dati che può contenere dati di diversi tipi.
• Puntatore: è una cella che contiene un indirizzo di un'altra cella: permette di accedere ad un'altra cella in memoria.

Notazioni Asintotiche

Theta grande, O grande, Omega grande, O piccolo, Omega piccolo.

Proprietà

• Simmetria
• Transitività
• Riflessività

Classi

1. 1 -> Costo costante (l'algoritmo si comporta sempre allo stesso modo)
2. -> Costo logaritmico (quando guarda solo una parte del logaritmo)
3. N -> Costo lineare (legge tutto l'input solo una volta)
4. -> Polilogaritmico (viene scomposto il problema in piccoli sottoproblemi e viene risolto il più piccolo)
5. 2, 3 iN , N … N -> i-esima (vengono analizzati tutti gli input più volte a seconda dell'ordine)
6. N N² , k -> Costo esponenziale (vengono provate tutte le combinazioni dell'input per risolvere il problema)

Algoritmi e strutture dati Pagina 3

N N² , k -> costo esponenziale (vengono provate tutte le combinazioni dell'input per risolvere il problema)

Regola della Somma

La regola della somma vale per la regola del prodotto (vale anche per omega grande e theta grande).

Costo Algoritmo -> Regole calcolo

Considerando di aver n input, guardiamo le regole di calcolo durante il calcolo di costo dell'algoritmo:

• Singola Istruzione base: O(1)
• Sequenza di istruzioni: massimo costo fra istruzioni nella sequenza
• Costrutto if - then - else -> valore condizione O(1) + il ramo con il maggior costo (if o then)
• Ciclo: valore condizione uscita dal ciclo: costo singolo algoritmo x numero iterazioni

Esempio

Esercizi Algoritmi e strutture dati Pagina 4

ALGO 2° Lezione

Martedì 6 ottobre 2015 13:33

Costo di una chiamata a Funzione/Procedura

Vi sono due casi da distinguere:

1. La funzione non è ricorsiva: Il costo della funzione è uguale al costo del pezzo di codice che compone la funzione.
   • Se la funzione chiama un'altra funzione il costo totale è uguale al costo della funzione + il costo di ogni altra funzione chiamata.
2. La funzione è ricorsiva: consideriamo una funzione fattoriale di n:

If(n>1) Return 1; Else Return n*fattoriale(n-1)

In questo caso il costo si calcola tramite l'equazione di ricorrenza della funzione, ossia la seguente. T(n) = c + T(n-1)

Metodo di sostituzione

Supponiamo di avere un'equazione di ricorrenza: Supponiamo inoltre che la complessità di T(n) sia. Allora dobbiamo verificare che...

Supponiamo questa equazione di ricorrenza:

Per ogni "livello" dell'albero ne calcoliamo il costo: Possiamo osservare che ci saranno 3 chiamate ricorsive: quindi disegnamo un "albero".

Ogni livello viene tutto diviso per 4, quindi sappiamo che per calcolare il livello i-esimo usiamo la seguente formula:...

Per calcolare il numero di livelli pongo =

Per calcolare il costo di ogni livello utilizziamo la formula:...

Per calcolare il costo complessivo facciamo la somma del costo di ogni livello:...

Algoritmi e strutture dati Pagina 5

Master theorem

Questa formula è applicabile solo per alcuni casi:

• ○ In questo caso la complessità è uguale a...
• ○ In questo caso la complessità è uguale a...
• ○ In questo caso la complessità è uguale a...

Classi di problemi

La difficoltà dei problemi può essere catalogata in classi:

• Classe P: problemi risolti in tempo polinomiale (La maggior parte dei problemi rientrano in questa classe)
• Classe NP: problemi la cui soluzione viene verificata in tempo polinomiale
• Classe NPC: (NP-Completi) problemi molto difficili la cui soluzione viene verificata in tempo esponenziale

Strutture Dati

Liste

Una lista è una sequenza ordinata di 0 o più elementi di un dato tipo (Ordinato: significa che dato un elemento posso distinguere un elemento maggiore e uno minore). a , a , a …..a_n è la lunghezza della lista.

Operazioni:

• insert(x,L) -> inserisce un elemento x inizio della lista
• locate(x,L) -> dato un valore x, ne restituisce la posizione all'interno della lista L
• retrieve(p,L) -> data una posizione p, restituisce il valore x all'interno della lista L
• delete(p,L) -> cancella l'elemento nella posizione p all'interno della lista L
• next(p,L) -> restituisce la posizione successiva nella lista L
• previous(p,L) -> restituisce la posizione precedente
• first(L) -> restituisce il primo elemento della lista
• makenull(L) -> azzera la lista

Implementazione tramite Array

Operazioni:

• insert(x,p,L) -> inserisce l'elemento x (dello stesso tipo della lista) nella posizione p all'interno della lista.

if last>max_length return "lista piena" if(p>last+1) OR (p<1) return "posizione non valida" For q=last downto p (da last fino a p) //shifto in avanti

L[q+1]=L[q] //i valori dopo last L[p]=x //inserisco il valore nella pos last=last+1 //liberata

9 12 36 18 24 7 10 insert(13,4,L) max.length=10 last=7 Costo totale =

• locate(x,L) -> cerca l'elemento specificato all'interno di L e ne restituisce la posizione for q=1 to last if L[q]=x return(q) return "elemento non in lista" Costo totale: O(n)
• delete(p,L) If(p<last) OR (p<1) Return "posizione non valida" for q=p to last //shifto indietro i valori L[q]=L[q+1] //e sovrascrivo il valore da canc. last =last-1
• Retrieve(p,L) if(p>last) OR (p<1) Return "errore" return (L[p]) Il seguente algoritmo ha costo
• Next(p,L)
• Previous(p,L)
• First(L) tutte queste istruzioni hanno complessità
• Makenull(L) -> last=0

Implementazione tramite Puntatori

Consideriamo ogni cella come composta da 2 elementi:

• Il primo elemento sarà il contenuto reale della lista, l'elemento in se. (element.key)
• Il secondo elemento sarà un puntatore che conterrà l'elemento successivo della lista. (element.next)

Il primo elemento della lista si chiama head, mentre l'ultimo elemento della lista si chiama tail. (testa-coda)

• Insert(x,p,L) -> a differenza dell'insert per gli array, p è un puntatore ad una cella della lista: In sostanza, la cella precedente punta al nuovo elemento, e quest'ultimo punta alla cella successiva.

Algoritmi e strutture dati Pagina 7

temp=p.next allocate(p.next) p.next.Key=x p.next.next=temp

• Locate(x,L) p=L.head while p!=NULL if p.key==x p=p.next return p
• Locate&delete(x,L) p=L.head while p.next!=NULL If(p.next).key=x p.next=p.next.next Return p=p.next

Lista doppiamente linkata

In una lista doppiamente linkata non abbiamo solo un puntatore a next, ma anche a previous. Nelle liste doppiamente linkate è frequente l'uso di sentinelle, ossia elementi lasciati vuoti per gestire più facilmente le liste. Queste sentinelle contengono soltanto il puntatore all'elemento successivo e a quello precedente: utilizzando una sentinella possiamo considerare una lista linkata come "circolare".

• Delete(p,L) If p.previous != NULL p.previous.nest=p.nest If p.next!=NULL p.next.prevoius=p.previous

Stack

Lo stack è un tipo particolare di lista dove operazioni di insert e delete vengono eseguite a una sola estremità (TOP dello stack) LIFO -> Last In First Out. Come le liste, anche lo stack è implementabile tramite array o puntatori:

Implementazione tramite Array

L'array S[s1, … , max_length] contiene tutti elementi dello stesso tipo e contiene una variabile top che contiene l'indice dell'ultimo elemento inserito.

• Push(x,S) -> inserimento elemento al top (elemento in cima) S.top = S.top+1; S[S.top]=x;
• Pop(S) -> rimozione dell'elemento top If empty(S) -> error S.top = S.top -1 Return S[S.top+1];
• Makenull(s) -> svuota S S.top = 0;
• Empty -> lo stack è vuoto? If S.top == 0; Return(true); Else Return(False);

Implementazione tramite Puntatori

Ogni elemento punta a quello inserito prima di lui; vi è un particolare puntatore che punta a TOP.

Algoritmi e strutture dati Pagina 9

ALGO 3° Lezione

Mercoledì 7 ottobre 2015 10:37

Coda - Queue

Una coda è un tipo particolare di lista: si differenzia dalla lista per le operazioni di inserimento e rimozione di elementi. Al contrario della strategia LIFO utilizzata dallo stack, per la coda si utilizza la FIFO (First In First Out). In una coda gli inserimenti sono effettuati nell'estremità tail della coda, mentre le cancellazioni sono eseguite all'altra estremità della coda (head).

An An_n-1 An_n-2 … A₁
Tail head

Operazioni

• Enqueue(x,Q) inserisce x nella coda
• Dequeue(Q) rimuove l'elemento in posizione head
• Front(Q) restituisce il primo elemento nella coda
• Empty(Q) Controlla se la coda è vuota
• Makenull(Q) svuota la coda

Per l'implementazione è possibile farla sia tramite array che tramite liste linkate.

Implementazione tramite array in una coda

Q[1…. Max.length] Per gestire la coda creiamo una variabile head e una tail, che rispettivamente puntano alla testa e alla coda della coda.

Nel caso di un'operazione di dequeue, eliminiamo il contenuto attuale di head (opzionale) e spostiamo la variabile head di una posizione (più specificatamente, aumenta di valore). Nel caso di un'operazione di enqueue, viene inserito un elemento in posizione n+1, e viene spostata la tail di una posizione in avanti (dalla posizione n alla posizione n+1).

È possibile però che tail raggiunga max.length: ciò significa che la coda è piena? NO, perché nel caso di eliminazioni head sia in posizioni superiori a 1 (ossia non all'inizio dell'array) per ovviare a questa soluzione bisogna considerare la coda come una struttura circolare.

Implementazione di enqueue

Q[Q.tail]=x
Q.tail -> variabile tail
If Q.tail=Q.max.length AND empty=FALSE //coda circolare Q.tail=1 Else Q.tail=Q.tail + 1 //inserimento If Q.tail==Q.head CODA PIENA! Costo= o(1)

Implementazione di dequeue

x=Q.[Q.head]
If Q.head == Q.max.length
Q.head=1
Else Q.head = Q.head + 1 //rimozione

Implementazione tramite puntatori

È una classica lista con due puntatori in più: head e tail. Anche con questo tipo di implementazione la coda può essere circolare.

Stack e Ricorsione

Lo stack viene spesso utilizzato dai linguaggi di programmazione per gestire la ricorsione:

• Stack dei record di attivazione: contiene tutto ciò che serve a ciascuna procedura chiamata per operare correttamente. Nella ricorsione ogni funzione/procedura aggiunge un record di attivazione al top dello stack.
• Ricorsione: permette di descrivere in modo finito un insieme potenzialmente infinito di oggetti.

Per fare sì che la ricorsione termini ci deve essere un caso base (banale), ossia un caso che viene sempre raggiunto e non in modo ricorsivo. Ogni "passo" della ricorsione si dice "passo ricorsivo".

Le funzioni ricorsive possono essere riformulate in modo iterativo. Un caso particolare è la tail recursion, ossia una funzione ricorsiva ove è facile eliminare la ricorsione. Si ha questo tipo di ricorsione quando:

• Il parametro di attivazione è passato per argomento
• La chiamata ricorsiva è l'ultima istruzione

Algoritmi e strutture dati Pagina 11

Alberi

Un albero è una collezione di elementi detti nodi, uno dei quali costituisce la radice. I nodi sono relazionati fra loro tramite una relazione gerarchica.

Definizione ricorsiva (formale) di albero

• Un singolo nodo è un albero (e anche la root dell'albero stesso) se:
• Se n è un nodo e T₁, T₂, …, T_k sono alberi con radice n₁, …, n_k la struttura ottenuta definendo n genitore di n₁,…,n_k è un albero con radice n.

Un albero senza nodi è vuoto. Ogni nodo (tranne la root) ha solo un genitore.

Proprietà

• Ogni nodo n tranne la root, ha solo un genitore
• I nodi con lo stesso padre sono detti fratelli (sibling)
• Ogni nodo può avere zero o più figli
• Un nodo senza figli è detto foglia
• I nodi che non sono foglia e non sono radice sono detti nodi interni
• Il numero di figli di un nodo è il suo grado
• Una sequenza di nodi n₁ n_k tale per cui n₁ è genitore di n_k per 1<i<k è detta cammin