Riassunto esame Analysis of algorithms and data structures, Prof. Andrea Marino, libro consigliato Think Python: How to Think Like a Computer Scientist, Allen B. Downey

Jupyter notebook

Per installare: pip install notebook

Per eseguire: jupyter notebook

Possiamo creare nuovi notebook con la funzione "new" e da lì scrivere codice.

Shortcut b per inserire una nuova cella di IO.

Tipi di celle nei notebooks

• Di codice
• Di testo (o di documentazione): inserire nuova cella e poi shortcut m. Può contenere anche espressioni matematiche in stile LaTeX

La funzione help fornisce la documentazione riguardo un metodo o un oggetto instanziato.

È possibile utilizzare il tab completion sui notebooks, sia per i metodi che per gli import

Esempio: from math import <tab>

iPython magic commands

Piccole keywords che permettono di valutare il contenuto di una cella in modo leggermente diverso. La maggior parte comincia con %.

• %run myscript.py esegue uno script python all'interno del notebook e l'output dello script viene stampato nella cella
• %time <istruzione> misura il tempo di esecuzione di un’istruzione singola (esempio il sort di una lista)
• %timeit <istruzione> esegue il benchmark per un’istruzione, esegue multiple volte e fornisce la media
• %%timeit stessa cosa ma multilinea
• %magic lista di keywords

All’interno di un notebook le variabili In e Out contengono rispettivamente gli elenchi di tutti gli input e output del notebook. Utilizzare str(In) e str(Out) per avere le corrispondenti stringhe oppure In[1] e Out[1] per accedere allo specifico elemento.

La variabile _ contiene l'output dell'ultimo comando. È possibile sopprimere l’output di un comando aggiungendo un ; alla fine del comando stesso.

Con ! seguito da un comando shell (Linux o Windows) possiamo eseguire comandi shell direttamente all'interno del notebook (es. !pwd).

Gestione errori e debugging

Se uno script fallisce, solleva un'eccezione, che possiamo osservare nella traceback controllabile tramite il comando %xmode: Plain (solo la stack delle call dei metodi), Context (default), Verbose (molto dettagliato con i punti di jump tra i metodi).

Debugging, per quando leggere le traceback non basta: pdb (e la versione aumentata ipdb).

• L’interfaccia più comoda è il comando %debug che si riferisce alla precedente computazione e fornisce il suo debugging. È poi possibile muoversi sullo stack della traceback con up e down e anche stampare il valore di variabili con print(<nome_variabile>).

Analisi degli algoritmi

L’analisi degli algoritmi studia la complessità degli algoritmi, ovvero la loro efficienza. Vi sono molti modi diversi di risolvere uno stesso problema, spesso con complessità diverse.

Criteri di complessità

• Spazio: la memoria allocata da un algoritmo (dipende dall’input del problema)
• Tempo: tipicamente dipendente dall’implementazione, tempo di esecuzione di un algoritmo in Python misurato tramite la libreria time

La complessità è indicata tramite la notazione O-grande, ad esempio:

2 ≈ ( )

NB: è importante conoscere solo l’ordine di grandezza e non il valore esatto del numero di operazioni, in quanto al crescere di l’unica cosa che importa è l’ordine di grandezza, ovvero la porzione che incrementa più velocemente al crescere di.

Ad esempio, avendo il numero di passi 2() = 5 + 27 + 1005 1005 quando è piccolo il termine sembra essere prevalente, mentre quando è grande il termine prevale. Ciò significa che 2() ≈ ( )

Misure di complessità

• Caso peggiore: tempo di esecuzione nel caso in cui vengano forniti dati con i quali l’algoritmo si comporta peggio
• Caso medio: tempo di esecuzione considerando tutti i possibili insiemi di dati

Liste e dizionari

Assegnamenti e append: →()

Concatenazione: con la lunghezza della seconda lista usare append con for

Il metodo pop(0) è più lento di pop

Nei dizionari si accede agli elementi tramite chiave e non tramite indice come nelle liste.

Search, fetch, modificare o aggiungere un elemento è sempre ()

Copia

La copia invece è ()

Ricerca e sorting

La ricerca di uno specifico item in una lista (non necessariamente ordinata se la lista contiene numeri) è (), mentre in un dizionario è ()

In particolare la ricerca sequenziale ha un caso peggiore di O(n), mentre un caso medio che si contraddistingue se l’elemento è presente o meno all’interno della lista stessa:

• Se l’elemento è assente O(n)
• Se l’elemento è presente O(n/2)

La ricerca nel caso in cui la lista è ordinata viene effettuata tramite ricerca binaria, che ha O(log n) caso pessimo

Diversi algoritmi di sorting

• Bubble sort: scorre l’array al più n-1 volte, considerando due elementi adiacenti e scambiandoli se sono in ordine errato. Alla fine della prima passata l’ultimo elemento sarà il più grande, quindi verranno considerati solo n-1 elementi, e così via. Complessità: O(n2)
• Selection sort: simile al bubble sort, esegue lo stesso numero di confronti ma meno scambi. Scorre l’array n volte, selezionando il maggiore ogni volta e mettendolo in posizione corretta dalla fine. Gli scambi sono dipendenti dal posizionamento degli elementi. Complessità: O(n2)
• Insertion sort: scorre l’array considerando la prima porzione di array come array ordinato, cominciando da 1 elemento e arrivando a n. Inserisce l’elemento subito dopo il sottoarray ordinato al suo interno. Complessità: O(n2)
• Merge sort: divide et impera, divide ricorsivamente l’array, ordina le sottoparti e riunisce in un unico array. Complessità: O(n log n), utilizzando spazio O(n)
• Quick sort: trova il punto di split tramite due indici e i, dove i prende il valore subito dopo il pivot e l’ultimo elemento dell’array, scorrendo l’array confrontando gli elementi nei due indici con il pivot. >, < Quando i e j swappiamo i e j. Ripete questo processo fino a quando i e j si invertono tramite swap. Quando questo succede avremo trovato il punto di split. Viene quindi sostituito il pivot con j e il processo viene ripetuto sulle due metà a sinistra e destra del pivot. Complessità: caso medio O(n log n) e caso pessimo O(n2). Non richiede spazio aggiuntivo.

Hashing

Hash table = collection of items, in cui ogni posizione contiene un item indicizzato (con indice che comincia da 0). Il mapping tra l’item e il corrispondente indice è detto funzione hash: H: I → N

Il load factor delle hash table è indicato con λ ed è ottenuto tramite λ = n/m

Quando vogliamo cercare un item, è sufficiente utilizzare la hash function per processare l’indice per ottenere il corrispondente item e verificare se l’item è presente nella hash table. L’operazione di search ha costo O(1) in quanto è necessario un tempo costante per computare l’hash value e poi checkare l’item alla corrispondente location nella hash table.

NB: questa tecnica funziona solo se ogni item è mappato su un singolo indice. Questo caso è noto come funzione di hash perfetta (non richiesta espressamente per ottenere comunque le performance teoriche).

Nel caso in cui due item siano mappati sullo stesso indice e si ricerchi per quello specifico indice, avviene una collisione. Nel caso in cui sappiamo che gli item della hash table sono immutabili, possiamo costruire una funzione di hash perfetta semplicemente mappando ogni item con un indice. Per insiemi contenuti di item questo è ok, ma nel caso in cui lo spazio dei possibili item sia grande questo metodo diventa inefficiente, in quanto vi è un enorme spreco di spazio.

Goal

Costruire una funzione hash che minimizza le collisioni, sia facile da computare e distribuisca in modo uniforme gli item nella hash table.

Metodi

• Folding method: dividere gli item in porzioni uguali, sommarle insieme, modulo per la dimensione della hash table e trovare l’indice
• Mid-square method: elevare al quadrato l’item e poi estrarre una porzione delle cifre risultanti
• Character-based method: per stringhe, calcolare il valore intero di ogni carattere, sommare i valori pesati per la loro posizione nella stringa, modulo e si ottiene l’indice

Risolvere le collisioni

Posizionare correttamente il secondo item nel caso in cui due item abbiano lo stesso valore di hash. Siccome le funzioni di hash perfette sono possibili solo a livello teorico (e nel caso in cui il numero di elementi sia noto a priori e sia immutabile), la risoluzione delle collisioni è fondamentale.

Metodi per risolvere le collisioni

• Open addressing: proseguire sequenzialmente fino al primo spazio libero nella table a partire dalla cella che ha generato la collisione (ritornando ciclicamente al primo indice). Questo processo è chiamato linear probing. Questo metodo ha il problema di generare clusterizzazione, in quanto gli item tendono ad ammassarsi tutti attorno a dei centri. Nel caso in cui avvengano varie collisioni vicine, gli item tenderanno a posizionarsi in slot vicini. Per risolvere questo problema è sufficiente procedere skippando alcuni indici invece che procedere sequenzialmente.
• Metodo del rehashing: Hi+1 = (Hi + k) % m dove k è il numero di indici da skippare.
• Chaining: permette a molteplici item di avere un unico indice, dove vengono semplicemente salvati in una catena. Questo permette, nel caso di collisione, di dover cercare semplicemente lungo la catena e non lungo tutta la hash table.

Analisi delle performance di una hash table

Caso ideale e teorico, acquisibile solo se l’insieme di elementi è immutabile: O(1). Di base il comportamento di una hash table dipende dal suo load factor λ:

• Se λ è piccolo, allora gli item finiscono con più probabilità nel loro corretto indice di hash, senza generare collisioni
• Se λ è grande, allora gli item generano collisioni con più probabilità necessità di risolvere le collisioni oppure utilizzare il chaining per salvare gli elementi in catene corrispondenti allo stesso indice hash O(1 + λ)

In particolare, una ricerca con successo di un item impiega in media confronti, mentre una ricerca senza successo impiega in media O(1 + λ).

Usando la tecnica del chaining, i confronti medi nel caso di una ricerca con successo sono 1 + λ/2 e λ confronti se la ricerca è senza successo.

Alberi

Notazione

• Nodo: unità fondamentale di grafi e alberi, può avere un nome “key” e un contenuto “payload”
• Arco: connette due nodi (padre e figlio nel caso di alberi, due semplici nodi nel caso di grafi)
• Radice: nodo in un albero che non ha archi entranti
• Cammino: lista ordinata di nodi connessi da archi
• Figli: insieme di nodi che hanno archi entranti provenienti dallo stesso nodo padre
• Padre: nodo genitore di tutti i nodi a cui è connesso con archi uscenti
• Sottoalbero: insieme di nodi e archi tali che i nodi comprendono un genitore e tutti i suoi discendenti e gli archi sono tutti archi dell’albero che hanno entrambi gli estremi in
• Nodo foglia: nodo senza figli
• Livello: il livello di un nodo è il numero di archi che è necessario attraversare dal nodo radice
• Altezza: numero massimo di archi attraversabili, corrispondente al livello massimo di qualsiasi nodo nell’albero

Definizione formale di albero: insieme di nodi e di archi che connettono coppie di nodi tali che:

• Esiste un nodo chiamato radice
• Ogni nodo eccetto la radice è connesso da un arco esattamente ad un altro nodo, dove è il genitore di quest'ultimo
• Esiste un solo cammino dalla radice ad ogni nodo

Nel caso in cui ogni nodo abbia al più due figli si parla di albero binario.

Definizione ricorsiva: un albero è vuoto o consiste di un radice e zero o più sottoalberi, ciascuno dei quali è ancora un albero. La radice di ciascun sottoalbero è connessa alla radice dell’albero genitore da un arco.

Rappresentazioni degli alberi

• Tramite lista, in cui la posizione contiene la chiave del padre del nodo con chiave. La radice in questa rappresentazione ha come chiave se stessa
• Tramite lista di liste con una struttura ricorsiva. In questa rappresentazione utilizziamo la forma ricorsiva [nodo, [sottoalbero sinistro], [sottoalbero destro]] per ogni nodo

Modi di visitare un albero

• Anticipata: il nodo viene esaminato nel momento in cui ci si arriva, e poi ricorsivamente si richiama
• Posticipata: il nodo viene esaminato quando si sono visitati interamente i suoi figli

Linked list

Lista di elementi in cui ogni elemento è costituito da:

• Valore
• Puntatore all’elemento successivo della lista linkata

Può essere vista come albero unario (in cui ogni nodo ha solo un sottoalbero e non due, sinistro e destro).

Grafi

Notazione

• Vertice: unità fondamentale di un grafo, con chiave e eventuale informazione addizionale chiamata payload
• Arco: unità che connette due vertici, mostrando la relazione tra essi. Possono essere bidirezionali o unidirezionali (rispettivamente, grafi indiretti e grafi diretti)
• Peso: gli archi possono avere un peso a essi associato, che indica il costo per passare da un vertice a un altro
• Cammino: sequenza di vertici che sono connessi da archi. Formalmente definito come una sequenza tale che con 1 ≤ i ≤ n - 1. La lunghezza del cammino è il numero di archi attraversati dal primo all’ultimo vertice. Il peso del cammino è la somma di tutti i pesi degli archi attraversati
• Ciclo: in un grafo diretto, un ciclo è un cammino tale per cui il primo e l’ultimo vertice del cammino coincidono. Un grafo in cui non è presente alcun ciclo è chiamato grafo aciclico. Un grafo diretto e senza cicli è chiamato grafo aciclico diretto (Directed Acyclic Graph)

Definizione formale di grafo: una coppia (V, E), con V insieme di vertici e E insieme di archi. Ogni arco è una tupla (u, v) dove u, v ∈ V. Nel caso di grafi pesati, gli archi sono triple (u, v, w) dove w è il peso associato all’arco.

Un sottografo è una coppia (V', E'), dove V' ⊆ V e E' ⊆ E, tali che E' ⊆ V' × V'.

Matrice di adiacenza

Matrice dove n è il numero di vertici in V, in cui ogni entry rappresenta la presenza o meno di un arco (u, v). Nel caso in cui sia pesato, possiamo inserire direttamente il peso dell’arco nella entry.

Pro: molto semplice da costruire e mantenere, ottima nel caso in cui il numero di archi sia alto.

Contro: nel caso in cui sia sparso, ovvero vi sia la maggior parte di nodi assenti, la matrice di adiacenza sarà per lo più vuota, sprecando quindi molto spazio.

Grafi in cui gli archi sono proporzionali a n2 sono rari!

Lista di adiacenza

Metodo più efficiente della matrice di adiacenza per memorizzare la struttura di un grafo. Memorizziamo come una lista di oggetti vertice, in cui ogni oggetto memorizza l’id del vertice e la lista di vertici a cui esso è collegato.

Nella nostra implementazione useremo un dizionario, in cui ogni vertice collegato ha come valore a esso associato il peso dell’arco:

{0: {1: 5, 5: 2}}

Dove:

• 0 è il nome del vertice
• 1 e 5 sono i vertici collegati a 0 con pesi rispettivi di 5 e 2