Giacomo Marciani

Un grafo è un’astrazione matematica usata per modellizzare relazioni fra coppie di oggetti. Un grafo G=(V,E), è definito da un insieme V(G) di n nodi, ed un insieme E(G) di m archi, ovvero coppie di nodi. I nodi rappresentano oggetti, mentre gli archi rappresentano le relazioni tra di essi. Esistono due tipologie di grafi: grafo indirettoanche detto grafo non ...

Le tecniche algoritmiche che prenderemo in esame, e delle quali mostreremo semplici applicazioni in problemi di valenza generale sono: divide et impera: risoluzione top-down di problemi con struttura ricorsiva. programmazione dinamica: risoluzione bottom-up di problemi con sottoproblemi interdipendenti. tecnica greedy: risoluzione di problemi di ottimizzazione locale.    

Uno Union-Find è un tipo di dato che permette di organizzare n elementi in insiemi nominali disgiunti, definito dalle seguenti operazioni: makeset: crea un insieme contenente unicamente l’elemento specificato, e il cui nome è proprio uguale a quell’elemento. union: unisce due insiemi disgiunti in un unico insieme, il cui nome sarà quello del primo insieme specificato. ...

Una coda con priorità è un tipo di dato che permette di mantenere il minimo in un insieme totalmente ordinato U di chiavi k, ed è definito dalle seguenti operazioni: insert: inserisce un elemento e di chiave k. findMin: restituisce l’elemento di chiave minima. deleteMin: rimuove il minimo. delete: rimuove un elemento e di chiave k specificata. increaseKey: incrementa ...

Una tabella è una struttura dati indicizzata che realizza un dizionario, supportando operazioni di inserimento cancellazione e ricerca in T(n)=O(1), a costo di un elevato spreco di memoria, oppure in Tm(n)=O(1), con ottimizzazione sull’utilizzo della memoria. Il fattore di carico esprime il riempimento di un vettore m-dimensionale contenente n elementi. L’hashing è una tecnica di indicizzazione ...