Domande Orale Bigi

Rispondi
Avatar utente
karjudev
Messaggi: 2
Iscritto il: 08/01/2019, 12:37

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?
Avatar utente
frabert
Messaggi: 3
Iscritto il: 15/12/2018, 11:23

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?
simone
Messaggi: 2
Iscritto il: 10/01/2019, 12:22

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
Avatar utente
fexed
Messaggi: 3
Iscritto il: 21/10/2018, 15:18

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
Avatar utente
michelezoncheddu
Messaggi: 6
Iscritto il: 01/11/2018, 15:46

  • Durante il branch & bound, quando posso chiudere in una volta sola tutti i nodi dell'albero?
    Spoiler: quando trovo una soluzione ammissibile per il problema di partenza migliore di tutte le previsioni più ottimistiche di tutti gli altri sottoproblemi.
  • Cos'è uno pseudoflusso? E uno minimale? Perché ci interessano nel problema del flusso di costo minimo?
  • Nel problema del flusso di costo minimo, quand'è che l'algoritmo va avanti ma senza arrivare mai a uno sbilanciamento nullo?
    Spoiler: quando i bilanci dei nodi non ammettono soluzione, per esempio, se richiedono più flusso della somma delle capacità degli archi entranti.
  • Com'è fatta una direzione di decrescita nell'algoritmo del simplesso duale?
GiuseppeD93
Messaggi: 1
Iscritto il: 13/01/2020, 12:55

Ciao Ragazzi, ho raccolto queste domande nel pre-appello 2020, spero che possano aiutarvi a studiare:

- Condizioni di Bellman e il significato delle vare condizioni
- Come usiamo le condizioni di Bellman in un algoritmo
- La distinzione dei vari algoritmi e le caratteristiche differenti dei due algoritmi (riferito alla domanda precedente)
- Dopo l'esecuzione dell'algoritmo dei cammini minimi esiste un modo per dire che ce n'è almeno un'altro?
- Simplesso duale e caratteristiche
- L'algoritmo (simplesso duale) potrebbe non finire mai, passando da una base all'altra all'infinito?
- Problema del commesso viaggiatore. Cos'è il k-albero e perché ci interessa nello studio dei cicli Hamiltoniani?
- Come si trova il k-albero di costo minimo algoritmicamente

- Basi e scarti complementari, relazione tra di loro
- La condizioni degli scarti complementari equivale a caratteristiche della FO?
- x(segnato) ammissibile ma y(segnato) non ammissibile, che conclusioni posso trarre?
- Se è degenere come faccio a trovare la soluzione?
- Come riconoscere un problema superiormente limitato?
- Dato un albero, come verificare l'ottimalità?
- Cosa sono i piani di taglio? Ambito in cui si usano.

in bocca al lupo
Avatar utente
CharAsd
Messaggi: 10
Iscritto il: 08/06/2021, 16:54

Ciao! ho raccolto queste domande nell'appello di giugno 2021. Spero possano aiutarvi :)


Esame 1:
- Condizioni di ottimalità per albero di copertura costo minimo
- Cammini minimi, condizioni di Bellman
-- In quale caso l'albero dei cammini minimi trovato è l'unico? Spoiler: le condizioni di Bellman sono soddisfatte per disuguaglianza
- Scarti complementari
-- ha valore solo per le soluzioni di base? Spoiler: no, direzioni di crescita
--- le direzioni di crescita sono sempre ammissibili? Spoiler: no, soluzioni degeneri
- Problema dello zaino

Esame 2:
- Flusso di costo minimo, pseudoflussi
-- come si determina uno pseudoflusso minimale? spoiler: non sono presenti cicli negativi
- Teoria della dualità: collegamento tra primale e duale, teoremi della dualità, teorema degli scarti complementari
- PLI: cos'è, rilassamento, piani di taglio
-- Perché i problemi di PLI sono "difficili"?
-- Problemi di PLI che sono "facili", quali sono? Spoiler: determinanti = 1, 0, -1
-- Abbiamo incontrato dei problemi di PLI in precedenza che abbiamo risolto facilmente?


In generale il prof è molto tranquillo e ti lascia riflettere sulla domanda. L'esame parte dagli argomenti sbagliati durante il compito se c'è qualcosa particolarmente rilevante.

PS: gli orali sono stati il pomeriggio dopo lo scritto quindi vi consiglio di prepararvi per entrambi, specialmente se ci sono pochi iscritti :D
Rispondi

Torna a “[RO] Ricerca Operativa”