The forum of the Computer Science students of the University of Pisa

Domande Orale Bigi

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:
  • 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
Esame 2:
  • 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.)
Esame 4:
  • 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?
Gruppo 2:

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?
Esame 3:
  • 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?
Gruppo 3:

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?
Esame 2:
  • 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?
Esame 3:
  • 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?
Usando Edmonds-Karp, come trovo un taglio di capacità minima?
Come trovo tutte le soluzioni di un problema di PL?
Dato un problema di PLI, perchè non si può semplicemente ridurre la regione del rilassamento a quella del reticolo e poi usare l'algoritmo del simplesso?
Salve a tutti io ho raccolto le seguenti domande dell'orale di Bigi:
-cos'è uno pseudoflusso e quando è minimale
-cos'è una direzione ammissibile per x
-cos'è il rilassamento
-vincolo di semi assegnamento
-formulare problema dello zaino
-condizioni ottimali per cicli/tagli su probleimi di flusso massimo
-Teorema Dualità forte
-Teorema Dualità debole
-problema flusso massimo
-Brench and bound commesso Viaggiatore
-Condizioni di Bellamn
-Proprietà algoritmo di Djikstra
-Come ti accorgi di avere cicli di costi negativi =(Bellman) se inserisco più di n-1 volte un nodo
-cos'è una Base
-cos'è una disuguaglianza valida
-Problema Flusso di costo minimo
-cos'è un piano di taglio
Confermo che il Bigi all'orale è molto tranquillo e paziente, ti aiuta ad arrivare alle cose e chiude un'occhio su imprecisioni (per esempio, personalmente ha detto "vabbé è uguale" quando ho scritto il verso sbagliato di una disequazione in una definizione).

Di seguito le domande che mi sono appuntato durante l'orale del 22/2.
  • - Simplesso Primale: come si individua la direzione di crescita. Esempio grafico in cui la direzione trovata dal simplesso primale non sia ammissibile.
    - Esempio (grafico) in cui sia il problema Prima che il Duale sono vuoti
    - Come individuo le soluzioni del rilassamento nel problema dello zaino
    - Dato uno sviluppo dell'albero di enumerazione in cui non ho tagliato nulla, dire quando, analizzando un singolo problema, posso chiudere tutto (spoiler: trovando una soluzione ammissibile migliore dell'attuale e di tutte le altre valutazioni trovate).
    - Flusso di costo minimo:
    • - Cos è uno pseudoflusso
      - cos è uno pseudoflusso minimale
      - perché ci interessano gli pseudoflussi minimali
      - illustrare l'algoritmo dei cammini minimi successivi
      - come trovo un ciclo di costo negativo nel grafo residuo (STP-L: guardo quante volte inserisco un nodo dentro Q, ogni nodo deve essere inserito al più n-1 volte)
    - relazioni tra soluzione di base complementari e teorema degli scarti complementari