• Non ci sono risultati.

Docente: Alfredo De Santis Durata: 2 ore

N/A
N/A
Protected

Academic year: 2021

Condividi "Docente: Alfredo De Santis Durata: 2 ore"

Copied!
6
0
0

Testo completo

(1)

Matricola: Firma:

Universit` a di Salerno 14 gennaio 2013

Algoritmi

( Matricole congrue ad 1 mod 3)

Docente: Alfredo De Santis Durata: 2 ore

Nessun materiale ammesso per consultazione. Buon lavoro a tutti.

Il presente esame consiste di 6 pagine e 5 quesiti. Segnalare qualsiasi discrepanza alla commissione. Il numero in parentesi all’inizio di ciascun quesito corrisponde al numero di punti assegnati ad una risposta corretta.

Rispondere a tutti i quesiti.

Riservato alla commissione:

Punti

1 (9)

2 (24)

Totale Parziale

Punti

3 (18)

4 (25)

5 (24)

Totale Parziale

Totale (100)

Pagina 1 di 6

(2)

1. [9] Notazioni asintotiche.

Dire se se seguenti relazioni sono vere o false, motivando e provando le proprie affer- mazioni:

(a) n log √

n = Θ(n log n)

(b) log(n log n) = Θ(log n)

(c) 2

n

= Θ(3

n

)

Lo spazio per la risposta continua sulla prossima pagina

Pagina 2 di 6

(3)

2. [24] Si descriva ed analizzi un algoritmo che dati n punti nel piano determini una coppia con la pi´ u piccola distanza euclidea tra loro.

Lo spazio per la risposta continua sulla prossima pagina

Pagina 3 di 6

(4)

3. [18] Si descriva ed analizzi il problema della Schedulazione degli Intervalli (Interval Scheduling).

Lo spazio per la risposta continua sulla prossima pagina

Pagina 4 di 6

(5)

4. [25] Si descriva ed analizzi un algoritmo per la seguente variazione del problema dello zaino: Dati n oggetti di peso w

1

, w

2

, ..., w

n

e valore v

1

, v

2

, ..., v

n

ed uno zaino di capacit´ a W (tutti gli input sono > 0), trovare il massimo valore di un sottoinsieme degli oggetti il cui peso totale ´ e ≤ W , con la condizione che gli oggetti con indici consecutivi non possono essere presi insieme. (La variazione rispetto al problema del testo del corso, consiste nell’ulteriore vincolo che l’oggetto i-esimo e quello (i + 1)-esimo, per i = 1, ...n − 1, non possono essere entrambi nello zaino.)

Lo spazio per la risposta continua sulla prossima pagina

Pagina 5 di 6

(6)

5. [24] Flusso massimo e taglio minimo. Si descriva ed analizzi la relazione tra Flusso Massimo e Taglio Minimo in un grafo. (Si proceda definendo i due concetti, esplicitando la relazione ed infine provandola.)

Fine dell’esame

Pagine totali: 6

Punti totali: 100

Riferimenti

Documenti correlati

Si descriva come ottenere il cammino di costo minimo dal nodo a facendo uso della matrice OP T e chiarendo i passi effettuati. Fine dell’esame Pagine totali: 7 Punti

Si descriva il problema della schedulazione degli intervalli chiarendo quali sono gli input e quali gli output.. Si descrivano ed analizzino le diverse scelte greedy per la

(Si inizi definendo il concetto di inversione. Si proceda descrivendo l’algoritmo ed in particolare la procedura ricorsiva. Infine si analizzi l’algoritmo descritto.). Lo spazio per

Infine, si descriva come ottenere il cammino di costo minimo dal nodo u facendo uso della matrice OPT e chiarendo i passi effettuati. Lo spazio per la risposta continua sulla

Si descriva come ottenere il cammino di costo minimo dal nodo a facendo uso della matrice OP T e chiarendo i passi effettuati. Lo spazio per la risposta continua sulla prossima

(La variazione rispetto al problema visto a lezione, consiste nel superamento del vincolo che ogni oggetto poteva essere preso al massimo una sola volta.). Lo spazio per la

È prevista l’applicazione di una penale - nella misura giornaliera dell’uno per mille dell’importo di ciascun apparecchio - per ogni giorno di ritardo rispetto

euro, si propone un incremento di pari importo della previsione di competenza e di cassa del capitolo 113.905 Rimborso per viaggio e trasloco nella Macro Attività