Algoritmi e Programmazione Avanzata
Compito di teoria 19 dicembre 2006
Tempo: 30 minuti, NON è possibile consultare libri o appunti.
Esercizio 1
Si consideri una coda prioritaria implementata come heap. Si assuma che la priorità massima sia associata all'elemento con chiave minima. Sulla coda viene eseguita l'inserzione delle seguenti chiavi:
21 13 50 42 37 35 60 81 94 23 18 Si disegni la struttura dello heap risultante (sotto forma di albero).
Esercizio 2
Sia data la sequenza di interi, supposta memorizzata in un vettore:
4 8 19 12 15 5 4 1 0 13 10 9
Si eseguano i primi due passi dell’algoritmo di quicksort per ottenere un ordinamento ascendente. NB:
I passi sono da intendersi impropriamente, come in ampiezza sull’albero della recursione, non in profondità. Si chiede, pertanto che siano ritornate le 2 partizioni del vettore original e le due partizioni delle partizioni trovate al punto precedente.
Esercizio 3
Descrivere il problema della determinazione dell’ albero di copertura minimo, ed illustrare l'algoritmo di Kruskal. Cosa si intende per arco sicuro?
Algoritmi e programmazione avanzata
Compito di programmazione 19 dicembre 2006
Tempo: 60 minuti, è possibile consultare libri e appunti.
Si consideri una rete wireless formata da un insieme di nodi in grado di comunicare con i nodi adiacenti presenti nel raggio di copertura, pari ad L, dell’antenna utilizzata per la trasmissione/ricezione del segnale. In un file è specificata la posizione di ciascun nodo (x,y), dove x e y sono numeri interi compresi tra 0 ed M (inclusi).
Il grafo che rappresenta le connessioni della rete wireless ha come vertici i nodi della rete e come archi, le connessioni tra i nodi che si trovano ad una distanza inferiore ad L uno dall’altro. Si supponga di avere questo grafo già definito in memoria secondo una opportuna struttura dati a scelta dello studente.
Si scriva un programma in C che sia in grado di verificare se il grafo corrispondente alla rete wireless definita nel file è connesso oppure no. Ossia se per ogni coppia di nodi esiste un cammino che li collega.
Nel caso il grafo sia connesso si individui se esistono dei nodi critici, ossia dei nodi che, se spenti rendono la rete non connessa. Si stampi l’elenco dei nodi critici.
Altrimenti, se il grafo non è connesso, si stampino a video, secondo una opportuna formattazione, i nodi appartenenti a ciascuna componente connessa.
Esempio:
Nell’esempio indicato a destra, la rete è connessa.
I nodi che se eliminati rendono la rete non connessa sono i nodi B e D.
Nel programma che verrà consegnato al professore via email, si implementi anche la lettura dei dati da file e la costruzione del grafo, secondo i limiti di copertura di ciascun nodo.
N.B. Allo studente è richiesto di consegnare una copia dell’elaborato scritto al termine della presente prova d’esame.
Affinché lo scritto venga valutato lo studente dovrà realizzare su PC il programma funzionante ed inviare al docente (servetti@polito.it) il codice sorgente [ ENTRO il 15.01.2007 ] corredato da una breve relazione che illustri le eventuali modifiche apportate rispetto alla versione redatta in sede d’esame. Nella mail specificare come oggetto la sigla del corso ed il proprio numero di matricola, nella forma: [APA_NETTUNO + matricola].
A
B C
D E
F
