Domande Orale Bigi
Inviato: 09/01/2019, 17:47
Ho creato questo thread per condividere con voi le domande dell'orale di Bigi.
Il professore convoca ad una data ora un piccolo gruppo (3-4 persone), mostra loro i compiti e poi li chiama uno alla volta alla lavagna. Fa domande che traggono spunto dal compito dello studente che sta interrogando, e poi lo rimanda a posto chiamando il successivo. Quando ha finito l'intero gruppo dà i voti a tutti.
L'orale si svolge in modo molto tranquillo e il Bigi tende a farti arrivare alla soluzione se non ci riesci da solo, ma comunque le domande si fanno sempre più difficili man mano che si va avanti con gli orali.
Io ho svolto l'orale il 9 gennaio 2019, le domande che mi sono segnato sono state:
Gruppo 1:
Esame 1:
Esame 2:
Esame 1:
Il professore convoca ad una data ora un piccolo gruppo (3-4 persone), mostra loro i compiti e poi li chiama uno alla volta alla lavagna. Fa domande che traggono spunto dal compito dello studente che sta interrogando, e poi lo rimanda a posto chiamando il successivo. Quando ha finito l'intero gruppo dà i voti a tutti.
L'orale si svolge in modo molto tranquillo e il Bigi tende a farti arrivare alla soluzione se non ci riesci da solo, ma comunque le domande si fanno sempre più difficili man mano che si va avanti con gli orali.
Io ho svolto l'orale il 9 gennaio 2019, le domande che mi sono segnato sono state:
Gruppo 1:
Esame 1:
- Condizioni di Bellman
- Come si caratterizza l'ottimalità di un albero di copertura di costo minimo?
- Enunciato del Teorema degli Scarti Complementari
- Dove si usa questo teorema negli algoritmi del simplesso? (Spoiler: per verificare l'ottimo) Scrivere l'algoritmo del simplesso primale
- Modello del Problema del Flusso Massimo
- Come si usa il Branch and Bound applicato al Problema del Commesso Viaggiatore?
- Relazione di dualità dei problemi [math] (Primale standard) e [math] (Duale standard)
- Quali sono le possibili situazioni in cui si possono trovare [math] e [math]? (Spoiler: Limitato - Limitato, Vuoto - Illimitato ecc.)
- Algoritmo del Simplesso Duale. Quando si ha un cambio di base degenere?
- Problema dello Zaino: Come si trova la soluzione del rilassamento?
- Data la soluzione di un problema di PL, come posso verificare che è ottima? (Spoiler: con gli scarti complementari)
- È possibile che nell'albero dei cammini minimi finisca l'arco di costo massimo di tutto il grafo?
Esame 2:
- Modello del Problema del Bin Packing
- Cammino Aumentante nel Problema del Flusso Massimo
- Che cos'è una Base? Definire le soluzioni di base
- Quando una soluzione di base si dice degenere?
- Modello del Problema dello Zaino
- Modifica il problema dello zaino per includere i seguenti vincoli:
- "Se prendo l'oggetto 1 non posso prendere l'oggetto 2"
- "Se prendo l'oggetto 3 devo prendere anche l'oggetto 1"
- "Se prendo sia 1 che 2 allora devo prendere anche 3"
- Cos'è una soluzione di base duale?
- Nell'algoritmo del simplesso duale com'è fatta una direzione di decrescita?
- Quando è che il problema
[math]
e il problema
[math]
Sono equivalenti?
Esame 1:
- Albero di Copertura di Costo Minimo
- Nell'albero di copertura è possibile che si debba inserire quello di costo massimo?
- Teorema degli scarti complementari
- Nella coppia asimmetrica, se un problema è vuoto, è possibile che anche il duale sia vuoto?
- Dato un problema (disegnato alla lavagna) con regione ammissibile vuota, puoi trovare una funzione obiettivo che non dia soluzioni duali ammissibili?
- Per il problema del Commesso Viaggiatore che relazione c'è tra un ciclo hamiltoniano e un k-albero?
- Nel problema del Flusso di Costo Minimo cos'è uno pseudoflusso?
- Quando uno pseudoflusso è minimale? Perché ci interessano gli pseudoflussi minimali?
- Come è collegata la ricerca del cammino di costo minimo e la ricerca dello pseudoflusso minimale? Perché quando faccio l'algoritmo trovo lo pseudoflusso di costo minimo?
- Che caratteristica deve avere lo pseudoflusso iniziale?
- Considerando il problema primale standard della PL, cos'è una direzione di crescita? Come si verifica che esiste una direzione di crescita? La direzione che si trova nel simplesso potrebbe non essere ammissibile? (Spoiler: sì, se siamo in una base degenere) Fare un esempio grafico di direzione di crescita non ammissibile
- Nel Problema dello Zaino come si può trovare una soluzione ammissibile?
- Modello del Problema del Flusso di Costo Minimo. Che ipotesi pongo sui bilanci dei nodi?
- Posso trasformare questo problema in un problema in cui tutti i bilanci sono 0 a parte due? (Spoiler: sì, usando una sorgente e un pozzo fittizi)
- Se volessi imporre, fissati due archi, che se sul primo passa flusso, non deve passare flusso nemmeno sull secondo
- Condizioni di Bellman per l'Albero dei Cammini Minimi
- Dato un albero che soddisfa le condizioni di Bellman come si verifica che è unico?
- Nell'algoritmo del Simplesso Duale come si individua una direzione di decrescita? Quando la direzione è ammissibile?