Appunti completi Algoritmica

Scansione lineare, scansione quadratica e doppio hash nelle tabelle hash

Ci si muove di 1 passo costante, sempre uguale a 1, cioè di una cella verso destra, in modo circolare (se si arriva alla fine della tabella, si riparte dalla prima posizione).

Svantaggio: formazione di CLUSTER (agglomerato) PRIMARI -> lunghi tratti di celle consecutive occupate -> comportano un degrado delle operazioni di inserimento (e di ricerca).

Scansione quadratica: Uguale alla scansione lineare, ma l'indice di scorrimento è elevato alla return(h+j**2)%n seconda, se ci scontriamo per la prima volta con una cella occupata.

Svantaggio: agglomerati secondari -> chiavi con lo stesso valore hash iniziali, seguono la stessa sequenza di scansione.

Doppio hash: In caso di collisione si genera un passo. Il passo si calcola in base alla chiave, e si return(h+j*passo)%n, con passo = 1+k%(n-1) moltiplica per l'indice di scorrimento.

Complessità tabelle hash:

Caso pessimo: T(n,m) con n = dimensione della tabella e m = numero di celle occupate.

Caso medio: costo

costante che dipende dal fattore di carico Ⲁ = m/n+1 < 1 ⲀT(n,m) ∈ O(1/1-Ⲁ), costante se è costante.

S(Ⲁ) = numero di accessi in una ricerca con successo

Grafi

Coppie di insiemi infiniti:

G = (V,E)

V = insieme dei vertici (nodi): rappresentano oggetti

E = insieme di archi (coppie di nodi): rappresentano relazioni tra oggetti

ùGrafo non orientato (senza frecce, insieme di coppie non ordinate)

Grafo orientato (con le frecce, insieme di coppie ordinate)

n = |v| = numero vertici->ordine del grafo

m = |E| = numero archi

Dimensione del grafo: |V| + |E| = n + m

Grafo sparso m = O(n)

Grafo denso m = (Teta(n^2)

Nei grafi non orientati gli archi sono adiacenti. Il grado del vertice (v) è il numero di archi incidenti su v.

v è un vertice isolato se S(v) = 0

Cammino di un grafo

Un cammino è una sequenza di vertici a 2 a 2 adiacenti collegati da un arco

Lunghezza di un cammino = numero di archi che lo compongono

Cammino semplice: composto da vertici tutti distinti (non attraversa alcun nodo)

più di una volta, quindi non contiene cicli annidati).

Ciclo=cammino che torna al punto di partenza

Distanza tra 2 vertici u,v: numero minimo di archi da percorrere per spostarsi da u a v.

Grafo completo (o Clique): Ogni coppia di vertici distinti è adiacente.

Grafo connesso: u e v sono connessi se esiste un cammino da u a v. Se ogni coppia di vertici è connessa.

Componente connessa di un grafo G: Sottografo G di G connesso e massimale: non può essere ulteriormente esteso. 3 componenti connesse.

Grado uscente di v= numero di archi che escono da v (non orientato)

Grado entrante di v=numero di archi che entrano in v.

Cammino orientato: ogni arco del cammino è orientato correttamente (nel verso "giusto").

Ciclo orientato: cammino orientato che torna nel punto di partenza.

Connesso: u e v sono connessi se esiste un cammino orientato da u verso v

Fortemente connesso: se ogni coppia ordinata di nodi è connessa

Grafo aciclico: orientato o non orientato,

alberi->richiede la gestione dei possibili cicli:

1. BFS visita in ampiezza (Breadth First Search: scopre i vertici in ordine di distanza crescente dalla sorgente (corrisponde alla visita per livelli di un albero)
2. DFS visita in profondità (Depth first search) scende sempre più in profondità nel grafo (corrisponde alla visita anticipata degli alberi binari).

Esempi di problemi su grafi:

Modellazione di problemi reali: CLIQUE.

Stabilire se G contiene un sottografo completo di almeno k nodi (k>0). Trovare la clique di dimensione max.

Algoritmo:

• enumerazione di tutti i sottoinsiemi di k vertici
• si controlla se il sottoinsieme forma una clique

Costo esponenziale in n. Non si sa se si può fare meglio.

Problema del cammino (ciclo) Hamiltoniano.

Dato G=(V,E), trovare un cammino semplice (o un ciclo) che passa da tutti i vertici di G, una ed una sola volta.

Algoritmo enumerativo:

• si considerano le permutazioni degli n vertici (n!)
• per ogni permutazione si verifica se i

vertici sono a 2 a 2 adiacenti

Problema del ciclo Euleriano

Posto da Euclero nel XVII sec

Trovare se esiste, un percorso nel grafo G che attraversa tutti gli archi una ed una sola volta, etorna al punto di partenza.

Teorema di Eulero

G è connesso e tutti i vertici hanno grado pari. Il problema si risolve con una visita del grafo cheha costo lineare nel numero di vertici e archi.

T(n,m)=O(n+m)

n=numero nodi

m=numero archi

Teoria dell'informazione e codici codice

Per codificare in binario una sequenza di simboli si sceglie una serie di di 0 e di 1 detto codice.

Il codice è una serie di stringhe binarie che si assegnano in modo univoco un codice a ognisimbolo. Un codice non deve essere ambiguo: una stringa deve poter essere decodificata solo inunivocamente decifrabileun modo; deve essere quindi un prefisso libero, perché tutti i simboli devono poter essereseparati senza ambiguità.

Nella stringa codificata abbiamo l'alfabeto con qualsiasi combinazione, la stella di Kleene mi dicequante

Sono le possibili combinazioni. Codice istantaneo: codice univocamente decifrabile che può essere decodificato senza attendere simboli della parola successiva; per esserlo, nessuna parola del codice dev'essere prefisso di un'altra parola. Si può ottenere tagliando i rami dell'albero infinito costruito per il codice considerato: le parole del codice sono le foglie dell'albero ottenuto con il taglio. In caso non completo possano essere aggiunte altre foglie e i rami vengano bloccati, si parla di codice. L'alfabeto Morse è una codifica binaria (punto, linea) delle lettere dell'alfabeto inglese e delle cifre. I simboli più brevi sono assegnati alle lettere più frequenti.

Codice ASCII: Nella codifica ASCII, ogni carattere è codificato (rappresentato) con lo stesso numero di bit (8 bit) per carattere. Poiché ci sono 256 valori diversi che possono essere rappresentati con 8 bit, ci sono potenzialmente 256 caratteri.

leggere il codice del carattere successivo. I codici a prefisso possono essere alberi binari rappresentati come <ul>, in cui ogni foglia rappresenta un carattere, ogni arco sinistro è etichettato con 0 e ogni arco destro è etichettato con 1; in questi, il codice di ogni foglia è l'etichetta del percorso che la raggiunge a partire dalla radice.

Informazione: La quantità di informazione associata al verificarsi di un evento x, che ha una probabilità p, è I(X) = log2(1/p). Il logaritmo è in base 2 perché l'unità di misura è il bit.

Entropia: è la sommatoria della probabilità di tutti gli eventi di un sistema moltiplicati alla loro informazione. Preso un sistema, la sua entropia è l'informazione che esso produce in media.

Teorema di Shannon: per codificare un testo di lunghezza n prodotto da una sorgente S di entropia H(S) non si possono usare meno di n*H(S) bits. Di conseguenza,

L'entropia è sempre minore della lunghezza media del codice: sommatoria della probabilità con cui appare un carattere che va codificato x il numero di bit che codifica quel carattere. (Un testo si può comprimere fino a una lunghezza che corrisponde al suo contenuto di informazione).

Limiti della Teoria di Shannon

Da un punto di vista concettuale: L'informazione viene definita in base al fatto che un oggetto è stato selezionato in un insieme di possibili oggetti: non ha senso parlare di informazione di un singolo oggetto. Dal punto di vista della compressione dati: Utilizza solo proprietà statistiche di un testo.

Informazione e Compressione

Compressore ideale: Algoritmo che, per ogni testo T, produce un programma di lunghezza minima per T.

Teorema: Il compressore ideale non esiste.

Codice di Huffman: è stato pensato col principio di minimizzare la lunghezza dei caratteri che compaiono più frequentemente e assegnare i percorsi più

Il codice di Huffman è un algoritmo di compressione dei dati che permette di ridurre la dimensione di un testo codificando i caratteri con stringhe di lunghezza variabile. Questo algoritmo si basa sul principio che i caratteri più frequenti vengono codificati con stringhe più corte, mentre quelli meno frequenti con stringhe più lunghe.

La costruzione del codice di Huffman avviene considerando la frequenza dei caratteri presenti nel testo e ordinandoli in base a questa frequenza. Successivamente, vengono presi i due caratteri con la frequenza minore e vengono sommati, creando un albero binario con la radice data da questa somma. Questo processo viene ripetuto fino a ottenere un unico albero binario. Alla fine della codifica di Huffman, ogni carattere avrà un codice binario univoco. Inoltre, i codici ottenuti sono a prefisso, ovvero nessun codice è prefisso di un altro.

La decodifica di Huffman avviene una volta ottenuto il codice binario. Utilizzando l'albero binario costruito durante la codifica, è possibile ricostruire il testo originale.