Torna alla pagina di Algoritmi e strutture dati
:: Domande di Algoritmi ::
Teoria
- Descrivere i possibili approcci all'implementazione dei grafi, fornendo esempi e discutendo vantaggi e svantaggi
- Spiegare il concetto di complessità di un programma e descrivere le notazioni asintotiche (O, teta, omega, o, w)
- Discutere il problema del bilanciamento negli alberi binari di ricerca. Definire bilanciamento perfetto e bilanciamento AVL e le implicazioni fra essi. Discutere il mantenimento del bilanciamento AVL a seguito di operazioni di inserimento e cancellazione, descrivendo i controlli che devono essere fatti e le conseguenti azioni che devono essere compiute.
- Descrivere il problema dell’ordinamento. Si richiede inoltre di: descrivere gli algoritmi di ordinamento radix sort e bucket sort; mostrare lo pseudocodice di tali algoritmi ed un esempio di funzionamento; indicare la complessità del radix sort e la complessità nel caso peggiore, medio e migliore per il bucket sort.
- Descrivere il problema dell’esistenza degli archi con pesi negativi quando e perch´e creano problemi nella definizione e ritrovamento del cammino minimo (illustrare un esempio). Descrivere inoltre un algoritmo per il calcolo dei cammini minimi da sorgente unica e discuterne la complessità.
- Caratterizzare il problema del dizionario e discutere la applicazione di tecniche di hash per la sua soluzione. Discutere in particolare la differenza tra hashing interno ed esterno ed i criteri che si conosco per la gestione delle collisioni (ispezione lineare, ispezione quadratica, hashing doppio).
- Spiegare il concetto di Spanning Tree e di Minimum Spanning Tree e descrivere gli algoritmi di Prim e di Kruskal per il ritrovamento di un MST evidenziando gli aspetti comuni e le differenze e fornendo un semplice esempio di utilizzo dei due approcci.
- Discutere il problema della ricorsione: cosa si intende per ricorsione, le diverse tipologie di ricorsione e come sono strutturate le procedure ricorsive. Descrivere inoltre la tecnica di tail recursion.
- Descrivere le tecniche DFS e BFS per attraversare grafi e scrivere (pseudocodice) gli algoritmi per la BFS e la DFS. Che costo hanno? Indicare esempi di applicazione delle due tecniche di attraversamento per la risoluzione di problemi.
- Quando può cambiare l'altezza di un B-albero? Motivare la risposta fornendo anche degli esempi.
- Descrivere il concetto di B-albero, indicandone le proprietà. Discutere inoltre le operazioni di aggiunta di elementi.
- Dire che problemi risolve l'algoritmo di Dijkstra e che limitazioni (e a cosa sono dovute, perché ci sono) ha mostrando anche un esempio. Quanto costa l'algoritmo?
- Dire cosa sono i codici di Huffman e mostrare un esempio.
- Dire cosa rappresenta il fattore di bilanciamento di un nodo in un albero binario di ricerca. Descrivere inoltre le proprietà che devono essere soddisfatte da un albero rosso-nero e fornire un esempio di albero rosso-nero valido e un esempio di albero rosso-nero non valido.
- Nell'ambito delle reti di flusso, fornire la definizione formale delle proprietà di vincolo sulla capacità, antisimmetria e conservazione del flusso e dire cosa rappresentano.
- Notazioni asintotiche: definizione e proprietà. Concetto di complessità di un programma.
- ADT stack e code: definizioni, operazioni ed esempi di applicazione.
- Dire cosa si intende con ricorsione diretta e ricorsione indiretta e fornire degli esempi.
- Nell’ambito delle strutture dati per insiemi disgiunti, dire cosa si intende per euristica dell’unione pesata. Si rischiede inoltre di scrivere la procedura Union con tale euristica.
- Definire il tipo di dato insiemi disgiunti specificando quali sono le operazioni definite su di esso. Nel caso inoltre di rappresentazione con foreste, dire in cosa consiste l’euristica dell’unione per rango.
- Dare la definizione precisa di grafo delle componenti fortemente connesse. Si richiede inoltre di fornire un esempio.
- Definire il concetto di componente fortemente connessa in un grafo orientato e illustrare un approccio per la sua risoluzione.
- Spiegare le proprietà principali degli alberi rosso-neri e descrivere le operazioni di inserimento e le conseguenti operazioni per il mantenimento delle proprietà, mostrando degli esempi.
- Definire il concetto di grado di un nodo nel caso in cui il nodo faccia parte di un grafo orientato. Mostrare anche un esempio.
- Dire quale e la complessità dei seguenti algoritmi: insertion-sort, quicksort, DFS.
- Spiegare i concetti di: pila (stack), coda, coda di priorità, coda circolare, procedura ricorsiva.
- Si descriva in breve il funzionamento dell’algoritmo di visita in ampiezza (breadth-first) di un grafo, indicando in particolare quale complessit`a temporale ha e di quale struttura dati conviene servirsi nell'eseguirlo.
- In che cosa consiste l’approccio “divide et impera”? Nominare un algoritmo che se ne serva.
- Il vettore A = [ 8 6 3 10 7 4 ] pu`o rappresentare un max-heap? Motivare la risposta. Qualunque sia la risposta, fare un esempio di vettore che non sia uno heap (copiando A o modificandolo leggermente) e trasformarlo in uno max-heap usando la procedura Max-Heapify (mostrare passo-passo le modifiche effettuata dalla procedura).
- Dato un grafo G = (V,E) dire cosa si intende per sottografo di G e sottografo di G indotto da V';. Dire cosa `e V'; e mostrare un esempio di sottografo e sottografo indotto.
- Dire cosa si intende per albero binario di ricerca. Si richiede inoltre di descrivere l’operazione di cancellazione e di fornire un esempio per i diversi casi. Che complessità ha tale operazione?
- Nell’ambito delle tecniche di programmazione, confrontare la tecnica divide-et-impera con la di programmazione dinamica e specificare quando applicare la programmazione dinamica.
- Dire cosa si intende per profondità, livello ed altezza di un albero.
- Quante foglie ha un albero binario completo di altezza h? e Quanti nodi sono contenuti in un albero binario completo di altezza h?
- Definire il concetto di ordinamento topologico di un grafo orientato. Descrivere inoltre il funzionamento della “soluzione diretta” per la determinazione dell’ordine topologico.
- Dato un grafo orientato G, dire cosa si intende per chiusura transitiva di G. Descrivere a parole un possibile algoritmo per il calcolo della chiusura transitiva.
- Si descriva in modo sintetico e preciso cosa è uno heap e come può essere mantenuto attraverso un vettore.
- Dato un albero binario con N nodi, quale può essere la sua altezza minima? e quella massima?
Esercizi
Gli esercizi richiesti sono:
- Mergesort
- Quicksort
- Heapsort
- Hashing
- albero AVL
- B-albero
- DFS e BFS
- Componenti fortemente connesse
- Ordine topologico
- Prim
- Kruskal
- Bellman-Ford
- Dijkstra
- Floyd-Wharshall
- chiusura transitiva
- Ford-fulkerson
- grafo bipartito
- codici di Huffman
Torna alla pagina di Algoritmi e strutture dati
