Prove esame 2019/20 Algoritmi e strutture dati

N

 matricola (intero su 4 cifre)

 nome e cognome (stringhe di al massimo 20 caratteri)

 competenze (4 interi tra 0 e 100) nelle 4 tipologie (operaio, amministrativo, tecnico o informatico).

Esempio: è un dipendente molto adatto al ruolo di informatico (80 su

1234 Rossi Mario 10 60 30 80

100), abbastanza al ruolo di amministrativo (60 su 100), poco al ruolo di tecnico (30 su 100), per nulla al ruolo di

operaio (10 su 100).

L’azienda è organizzata in che la Direzione Generale sta ristrutturando. Gli dipendenti vanno ripartiti

Ddivisioni N

tra le dove svolgerà una sola delle 4 tipologie di lavoro con la relativa competenza. A tal fine, un

Ddivisioni,

secondo file (delle divisioni) contiene le richieste delle divisioni: la prima riga contiene il numero di divisioni,

D

seguono gruppi di 5 righe: l’i-esimo gruppo, corrispondente alla divisione identificata, su una riga, dalla

D i,

sigla (una stringa la massimo di 10 caratteri). Seguono 4 righe, associate ognuna a una delle 4 tipologie per le

quali la divisione fa una richiesta: detta la riga (la tipologia), questa contiene una terna di interi ,cmin e

j m ij ij

. (separati da spazi), che rappresentano, rispettivamente (per la divisione e la tipologia il numero minimo

r i j),

ij

di addetti, la competenza minima totale e competenza ottimale totale richieste.

Si scriva un programma C che, ricevuti sulla linea di comando i nomi di tre file:

 acquisisca in opportune strutture dati le informazioni contenute nei 2 file dei dipendenti e delle divisioni. Si

richiede di utilizzare un quasi ADT (dipendente_t) per un dipendente e un ADT di prima classe

(divisione_t) per una divisione. Le collezioni di dipendenti e di divisioni siano realizzate come vettori

dinamici(dipendenti e di tali strutture dati. L’ADT deve contenere la

divisioni) divisione_t

collezione dei dipendenti assegnati alla divisione stessa (a scelta come collezione di item dipendente_t

o di riferimenti a elementi del vettore la tipologia di lavoro che ogni dipendente svolgerà.

dipendenti)e

Per questo ADT si implementino esplicitamente le funzioni di creazione, distruzione, acquisizione della

divisione, inserimento di un dipendente e stampa/salvataggio su file

 legga un terzo file (delle associazioni) contenente, su righe, associazioni dipendente-tipologia-divisione,

N

mediante terne che specificano a quale divisione e con quale

<matricola><tipologia><sigla>

tipologia è stato assegnato il dipendente con quella matricola, verifichi se sono soddisfatti i vincoli di numero

minimo di addetti e di competenza totale minima richiesti per ogni tipologia di ogni divisione. La tipologia è

identificata tramite la lettera iniziale (o, Si calcoli inoltre lo scostamento complessivo medio, rispetto

a, t, i).

alla competenza richiesta (somma degli scostamenti per divisione e per tipologia diviso il numero di divisioni)

∑ ∑ −

=

Per competenza totale della divisione nella tipologia si intende la somma delle competenze in quella

c i j

ij

tipologia dei singoli dipendenti assegnati alla divisione con competenza

i j.

 calcoli un’attribuzione ottima di dipendenti alle divisioni tale da:

 soddisfare i vincoli minimi per numero di dipendenti e competenza totale per ogni tipologia di ogni

divisione

 minimizzare lo scostamento complessivo medio (si veda definizione al punto precedente).

Tale attribuzione sia memorizzata su un file di uscita, il cui nome è passato come parametro sulla riga di

comando, nel formato una coppia matricola-sigla per ogni riga.

 dopo aver generato la soluzione ottima del punto precedente, la elabori e la memorizzi nel vettore di collezioni

(divisioni): si ricorda che il tipodivisione_t prevede la possibilità di collezionare i dipendenti di una

divisione. Si salvi, usando la funzione di stampa/salvataggio (di cui al punto 1) dell’ADT divisione_t,

l’attribuzione ottima su un file di uscita, nello stesso formato del file delle associazioni (il terzo file, usato al

punto 2). 03MNO Algoritmi e Programmazione

Appello del 02/07/2019 - Prova di teoria (12 punti)

1. (1 punto)

Sia data la seguente sequenza di coppie, dove la relazione i-j indica che il nodo i è adiacente al nodo j: 3-6, 6-2, 0-8, 5-

3, 4-8, 4-7, 9-8, 3-5, 6-8, 9-0. Si applichi un algoritmo di on-line connectivity con weighted quickunion, riportando a

ogni passo il contenuto del vettore e la foresta di alberi al passo finale. I nodi sono denominati con interi tra 0 e 9.

2. (2.5 punti)

Si inseriscano in sequenza i seguenti dati, composti da una stringa e da un intero che ne rappresenta la priorità, in una coda

a priorità di indici inizialmente supposta vuota:

"ab" 20 "cfd" 32 "FF" 19 "aAd" 51 "rt" 28

Si ipotizzi di usare uno heap (priorità massima in radice, vettore di 5 celle) per la coda a priorità e che la tabella di hash di

dimensione 11 per la tabella di simboli abbia il seguente contenuto:

0 1 2 3 4 5 6 7 8 9 10

aAD FF cfd ab rt

51 19 32 20 28

3 2 1 0 4

Si disegnino lo heap e il vettore ai diversi passi dell’inserzione. Al termine si cambi la priorità di 28 a 60 e si

qp "rt"da

disegnino i corrispondenti heap e vettore qp.

3. (3 x 0.5 punti) 

Si disegni l'albero corrispondente alla seguente espressione in forma prefissa * A + B C / + D E F e si trasformi

l'espressione in forma infissa e postfissa.

4. (2 punti)

Si aggiungano al seguente BST le informazioni che permettono di realizzate l’operazione di select e, indicando i

passaggi, si identifichi la chiave di rango 8:

5. (2 punti)

Si ordini topologicamente il seguente DAG. Qualora necessario, si trattino i vertici secondo l'ordine alfabetico e si

assuma che la lista delle adiacenze sia anch'essa ordinata alfabeticamente.

6. (2+1 punti)

Si determinino per il seguente grafo orientato pesato mediante l'algoritmo di Bellman-Ford i valori di tutti i cammini

minimi che collegano il vertice J con ogni altro vertice (2punti). Si verifichi l’eventuale presenza di un ciclo a peso

negativo (1 punto).Si assuma, qualora necessario, un ordine alfabetico per i vertici e gli archi.

03MNO Algoritmi e Programmazione

Appello del 02/07/2019 - Prova di programmazione (12 punti)

1. (2 punti)

Si scriva un programma C che, dato un intero generi una matrice quadrata con tutti 0 sulla diagonale

N, NxN

principale, tutti 1 sulle 2 diagonali immediatamente sopra e sotto, tutti 2 su quelle sopra e sotto le precedenti, etc,

come nel seguente esempio per N=5 0 1 2 3 4

1 0 1 2 3

2 1 0 1 2

3 2 1 0 1

4 3 2 1 0

2. (4 punti)

Una lista linkata, accessibile mediante il puntatore alla testa, contiene una sequenza di caratteri

head1

alfanumerici. Si definisca il tipo link/nodo utilizzati e scriva una funzione C che generi una seconda

lista, accessibile mediante il puntatore alla testa, in cui sono state eliminate le eventuali

head2

sottosequenze di elementi delimitati da coppie di parentesi tonde (aperta all’inizio della sequenza, chiusa

alla fine della sequenza), sostituendole con un solo elemento asterisco “*”. Si assuma che la lista sia

corretta, cioè che non possa contenere coppie di parentesi che si “intersecano” e che per ogni parentesi

aperta esista una parentesi chiusa. Il prototipo della funzione sia:

link purgeList(link head1);

Esempio: data la lista ab ( a c g ) b e ( ) a ( x x ) f

la lista di output sarà: a b ( * ) b e ( * ) a ( * ) f

Ai fini dell'esercizio, non si può fare uso di funzioni di libreria.

3. (6 punti)

Sia dato un vettore di interi. Si definisce sottosequenza di di lunghezza (kN) un qualsiasi n-upla di

V N V k Y k

elementi di con indici crescenti, ma non necessariamente contigui i , i , · · · , i . La sottosequenza si dice bitonica

V 0 1 k-1

crescente/decrescente se i suoi elementi sono ordinati prima in modo crescente e poi decrescente. Esempio: la

sequenza 4, 5, 9, 7, 6, 3, 1 è bitonica.

Si scriva un programma C che, ricevuti come parametri il vettore V e l’intero N calcoli e visualizzi una qualsisasi

sottosequenza bitonica di lunghezza massima.

Esempio: se N=9 e V = [4, 2, 5, 9, 7, 6, 10, 3, 1] una sottosequenza bitonica di lunghezza massima 7 è 4 5 9 7 6 3 1.

Si osservi che una sequenza crescente è bitonica di lunghezza massima, come pure una sequenza decrescente.

Esempio: se N=5 e V = [1, 2, 3, 4, 5], essa stessa è una sequenza bitonica di lunghezza massima 5.

PER ENTRAMBE LE PROVE DI PROGRAMMAZIONE (18 o 12 punti):

 indicare nell’elaborato e nella relazione nome, cognome e numero di matricola.

 se non indicato diversamente, è consentito utilizzare chiamate a funzioni standard, quali ordinamento per vettori, funzioni su

FIFO, LIFO, liste, BST, tabelle di hash, grafi e altre strutture dati, considerate come librerie esterne.

 gli header file devono essere allegati all’elaborato (il loro contenuto riportato nell’elaborato stesso). Le funzioni richiamate,

inoltre, dovranno essere incluse nella versione del programma allegata alla relazione. I modelli delle funzioni ricorsive non sono

considerati funzioni standard.

 consegna delle relazioni (per entrambe le tipologie di prova di programmazione): entro venerdì 05/07/2019, alle ore 23:59,

mediante caricamento su Portale. Le istruzioni per il caricamento sono pubblicate sul Portale nella sezione Materiale). QUALORA

IL CODICE CARICATO CON LA RELAZIONE NON COMPILI CORRETTAMENTE, VERRÀ APPLICATA UNA

PENALIZZAZIONE. Si ricorda che la valutazione del compito viene fatta, senza la presenza del candidato, sulla base

dell’elaborato svolto in aula. Non verranno corretti i compiti di cui non sarà stata inviata la relazione nei tempi stabiliti.

03MNO Algoritmi e Programmazione

Appello del 02/07/2019 - Prova di programmazione (18 punti)

Un’Agenzia della Mobilità deve pianificare in quali dei Comuni del suo territorio posizionare delle stazioni di

ricarica pubbliche per veicoli elettrici. I dati noti sono:

 i Comuni del territorio coinvolto sono e sono identificati dagli interi tra 0 e

N N-1

 il loro numero di abitanti è memorizzato in un vettore di interi

pop N

 le loro distanze reciproche sono memorizzate in una matrice di interi.

dist NxN

Si vuole ottimizzare la localizzazione delle stazioni di ricarica in base a funzioni obiettivo diverse e indipendenti:

 funzione obiettivo 1: data una distanza intera massima determinare il numero minimo

distMax, stazMin

di stazioni di ricarica e la loro localizzazione in modo che tutti i Comuni distino meno di dalla

distMax

stazione di ricarica più vicina. In ogni Comune è localizzata al più una stazione

 funzione obiettivo 2: dato un numero fisso intero di stazioni di ricarica posizionabili sull’insieme del

te