RICERCA OPERATIVA GRUPPO C

prova scritta intermedia del 12 febbraio 2002

Rispondere alle seguenti domande. Nelle domande a risposta multipla marcare a penna la lettera corrispondente alla risposta ritenuta corretta (una sola tra quelle riportate).

Ogni risposta esatta vale 2 punti.

1. L’involucro conico di un insieme S Í IRⁿ è

A) un qualsiasi cono contenente S

B) un cono poliedrale avente i punti di S come direttrici e il vertice nell’origine

C) il più piccolo poliedro contenente S

2. Un albero ricoprente i vertici di un grafo G

A) non può contenere alcuna clique di G

B) è un grafo bipartito

C) contiene solo cicli pari

3. In un ciclo una clique massimale

A) è sempre massima

B) è sempre dominante

C) è sempre ricoprente

4. I matching di un ciclo

A) godono in generale della proprietà di scambio

B) sono sempre perfetti

C) se massimali hanno tutti la medesima cardinalità

5. Il problema dello zaino

A) definisce un matroide

B) definisce un sistema di indipendenza

C) si risolve all’ottimo con il metodo greedy

6. Un grafo è privo di cicli

A) solo se è un albero

B) solo se non è connesso

C) solo se è bipartito

RICERCA OPERATIVA GRUPPO C

Risolvere i seguenti problemi. Ogni problema viene valutato da 0 a 6 punti.

7. Un computer opera con due processori. Lo scheduler del sistema operativo assegna i job ai processori in base alla loro durata (il job j ha durata p_j) con l’obiettivo di bilanciare il più possibile i carichi di lavoro, vale a dire, ridurre il più possibile la differenza tra la durata dei job assegnati al primo processore e quella dei job assegnati al secondo. Formulare tale problema in termini di ottimizzazione combinatorica indicando l’insieme universale U, la regione ammissibile Á e la funzione peso c. Dire anche se l’algoritmo greedy applicato a tale problema è in grado di individuare sempre una soluzione ottima (in caso contrario, mostrare un esempio di problema in corrispondenza al quale l’algoritmo fallisce).

l’insieme U è formato da	i job da schedulare
XÎÁ se e solo se	X è un insieme di job di peso < ½ å pj
"xÎU, c(x) vale	px
L’algoritmo greedy	trova l’ottimo |__|
	fallisce |__| , esempio: p1, p2, … = 7, 4, 4, 2, 2, 2 soluzione greedy: {7, 2} costo 1.5, ottimo {4, 4, 2} costo 0.5

8. Una delle funzioni del file system consiste nel riallocare periodicamente blocchi di dati in memoria. Tale funzione preleva n blocchi di dati contenenti a₁, a₂, …, a_n bytes e li trasferisce in m < n aree di memoria in grado di contenere b bytes ciascuna. I blocchi di dati hanno tipicamente un ordine logico, per cui l’ultimo record del primo blocco punta al primo record del secondo, l’ultimo record del secondo al primo del terzo e così via. Si vorrebbe riallocare i blocchi limitando al minimo il numero di puntamenti tra diverse aree di memoria. Descrivere il problema in termini di ottimizzazione combinatorica servendosi di un opportuno grafo G. Si indichi nella tabella seguente: l’insieme V dei vertici di G, l’insieme E dei suoi archi, l’insieme universale U, la famiglia Á delle soluzioni ammissibili e la funzione peso c.

ogni vÎV corrisponde a	un blocco di dati
uvÎE se e solo se	l’ultimo record di u punta al primo di v
l’insieme U è formato da	gli archi di G
XÎÁ se e solo se	eliminando X si ottengono al più m componenti, ciascuna di peso < b
"xÎU, c(x) vale	1 (min)

9. Dire se il seguente sistema di disequazioni lineari

2x₁ – x₂ – 4x₄ < 6

x₁ + x₂ + x₃ < 1

x₁ + 3x₃ > 6

x₁ + x₂ + 2x₃ < 2

ammette o no soluzioni in IR⁴, esibendo in caso affermativo una soluzione.

il sistema	non ammette soluzione | |
	ammette la seguente soluzione: x1 = 0, x2 = –2 , x3 = 2, x4 = –1