Appunti del corso di Algoritmi e strutture dati

ALGORITMI E STRUTTURE DATI

ALGORITMO UTILIZZO DI MEMORIA TIPO DI COMPLESSITÀ COMPLESSITÀ FUNZIONAMENTO Insertion Sort in-place quadratica Θ(n²) confronto di un elemento con tutti i precedenti Bubble Sort in-place quadratica Θ(n²) confronto di elementi adiacenti Selection Sort in-place quadratica Θ(n²) confronto di due elementi selezionati Merge Sort out-of-place logaritmica Θ(n log n) divide et impera Heap Sort in-place Logaritmica Θ(n log n) rimozione dell'elemento massimo per creare un albero binario Quick Sort in-place logaritmica Θ(n log n) pivot che divide l'array in numeri < e > Counting Sort in-place lineare Θ(n + k) conta il numero di elementi uguali in un intervallo Radix Sort out-of-place lineare O(d(n + k)) ordinamento rispetto alle cifre significative Bucket Sort out-of-place lineare Θ(n²) divisione in buckets e uso di Insertion Sort ALBERO DI RICERCA ALBERO SPLAY ALBERO AVL ALBERO ROSSO-NERO IMPIEGO efficiente nella ricerca dei nodi efficiente nell'inserimento e nella cancellazione dei nodi efficiente nell'inserimento e nella cancellazione dei nodi COMPLESSITÀ Balance TheoremO(m log n + n log n) O(log n) O(log n) BILANCIAMENTO no sì sì caso 1 ZIG: rotazione a destra rotazione a destra / OPERAZIONI: caso 2 ZIG ZIG: rotazione a destra x2 rotazione a sinistra + rotazione a destra / caso 3 ZIG ZAG: rotazione a sinistra + rotazione a destra / /

Un ALGORITMO è un procedimento di calcolo teoricamente meccanizzatile costituito da una sequenza di passi computazionali (dettati dal modello di calcolo) che prende in ingresso un dato insieme di valori e produce un output.

• risolve un problema computazionale
• è efficiente (utilizza al meglio le risorse)
• non è ambiguo (non ha margine di interpretazione)
• è finito (ha un numero finito di istruzioni)
• è generale (può essere applicato ad ogni input)
• è determinato (si ha un solo risultato)

proprietà

La RAM (Random Access Machine) è una macchina sequenziale costituita da

• registri (memoria)
• nastro di input (sola lettura)
• nastro di output (sola scrittura)
• programma (gestito dal Program Counter)

che esegue delle istruzioni di calcolo

• assegnamento ←
• relazione di ordine ≤, <, =, >, ≥
• logica booleana (∧, ∨, ¬)
• costrutti condizionali (if- then-else)
• costrutti ciclici (while- do)
• somma (+)
• sottrazione (-)
• moltiplicazione (*)
• divisione (/)

L’EFFICIENZA di un algoritmo si studia utilizzando la scalabilità

COUNTING SORT

è un algoritmo di ordinamento in-place con complessità lineare

1. si calcola il valore massimo
2. viene creato un array C di dimensione pari all' intervallo dei valori e viene inizializzato a 0
3. per ogni elemento di A si incrementa il corrispondente elemento in C
4. viene creato un array B di dimensione pari ad A all'interno del quale scrive i valori dell'intervallo il numero di volte indicato in C

RADIX SORT

è un algoritmo di ordinamento out-of-place con complessità lineare

1. l'array viene ordinato rispetto alla cifra meno significativa (unità)
2. l'array viene ordinato rispetto alla seconda cifra significativa (decine)
3. ecc.

BUCKET SORT

è un algoritmo di ordinamento out-of-place con complessità lineare

1. l'array viene diviso in n buckets
2. ogni bucket viene ordinato con Insertion Sort
3. vengono concatenati tutti i buckets

ALGORITMOUTILIZZO DI MEMORIATIPO DI COMPLESSITÀCOMPLESSITÀ MEDIAFUNZIONAMENTOInsertion Sortin-placequadraticaθ(n²)confronto di un elemento con tutti i precedentiBubble Sortin-placequadraticaθ(n²)confronto di elementi adiacentiSelection Sortin-placequadraticaθ(n²)confronto di due elementi selezionatiMerge Sortout-of-placelogaritmicaθ(n log n)divide et imperaHeap Sortin-placelogaritmicaθ(n log n)rimozione dell'elemento massimo per creare un albero binarioQuick Sortin-placelogaritmicaθ(n log n)pivot che divide l'array in numCounting Sortin-placelineareθ(n)conta il numero di elementi uguali in un intervalloRadix Sortout-of-placelineareθ(n)ordinamento rispetto alle cifre significativeBucket Sortout-of-placelineareθ(n)divisione in buckets e uso di Insertion Sort

QUICK SELECT

è un algoritmo di selezione in-place con complessità lineare

1. viene determinato il pivot i
2. l'array viene diviso in
• A1: elementi < i
• A2: elementi = i
• A3: elementi > i
3. costrutto condizionale

   p < i ⇒ p ∈ A1

   p = i ⇒ p ∈ A2

   p > i ⇒ p ∈ A3

Gli ALBERI ROSSO-NERI

sono alberi binari di ricerca bilanciati dove ogni nodo possiede l'informazione sul proprio colore e rispetta le seguenti proprietà

• ogni nodo è rosso o nero
• la radice è sempre nera
• i valori None sono neri
• i figli di un nodo rosso sono neri
• ogni percorso da un nodo a un None ha lo stesso numero di nodi neri (black-height).

Nel caso dell'inserimento il nodo da inserire è rosso. Gli alberi rosso-neri hanno complessità O(log n).

Il DYNAMIC SELECT

è un algoritmo di selezione in-place con complessità media O(n) utilizzato per calcolare la media, la mediana, la moda, ecc.

1. viene selezionato un pivot
2. l' insieme viene diviso in due sottoinsiemi
   • insieme contenente gli elementi ≤ al pivot
   • insieme contenente gli elementi > al pivot
3. viene scelto su quale sottoinsieme continuare la selezione

L' ANALISI AMMORTIZZATA

è una tecnica di analisi che valuta la complessità di una sequenza di operazioni. Si utilizza quando le operazioni più costose sono poco frequenti, quindi il loro costo può essere ammortizzato dalle operazioni meno costose. Data una sequenza di operazioni il COSTO AMMORTIZZATO è T(m)/m. Per fare un'analisi ammortizzata ci sono 3 metodi:

1. METODO DELL'AGGREGAZIONE

   (o AGGREGATE ANALYSIS)

   1. calcolare la complessità O(f (m))
   2. dividere per m (il numero delle operazioni)