Domande orale Novellani e Mencarelli 25/26

[peppescala]

Novellani:
(parte sempre dalla prova o dalla parte in cui sei andato peggio e quindi può chiederti un'argomento a caso di quella parte)
cos’è un poliedro
inviluppo conico
tipi di facce e cos’è una base
esempio grafico di una base (gli ha mostrato un cubo e ha chiesto quale sia una base del genere per quella forma)
gli fa vedere un poliedro graficamente e gli chiede quale non sia una base ammissibile
teorema della dualità debole
variabili semicontinue
come si definisce una funzione lineare a tratti
parla dell’albero di copertura di costo minimo
quali sono i componenti per determinare un algoritmo di branch&bound
tecniche di esplorazione dell’albero (sempre riferito al B&B)
problema commesso viaggiatore
cammini aumentanti
come faccio a capire se una base primale è ammissibile

Mencarelli:
(chiede sempre argomenti relativi alla 2 e 3 parte del programma e ogni tanto, in base a come va l'esame, può chiederti di svolgere un esercizio breve di una delle prove o di un esame)
cos’è il simplesso primale
se è duale ammissibile allora lo è anche per il primale?
gli ha fatto vedere lo scritto
come si trova una base duale ammissibile
(gli ha fatto vedere un compito) pseudoflusso e sbilanciamenti

cosa vuol dire che uno pseudo flusso é minimale
algoritmo di kruskal
qual è la funzione obiettivo nel caso di flusso massimo (?)
parlare del simplesso duale
come calcolare la soluzione primale di base
come calcolare soluzione duale di base
teorema di decomposizione dei poliedri
direzione di recessione
direzione di linearità
se il poliedro ha direzioni di linearità cosa succede al poliedro
algoritmo di prim
perché è sicuro che alla fine dell’algoritmo di primm ottengo un albero di copertura di costo minimo
(compito 25/26) supponiamo che il grafo non è ordinato come facciamo a sapere che rispetta la condizione di ottimalita dei tagli
problema di flusso massimo
vincolo di conservazione del flusso
cos'è uno pseudoflusso minimale e il vettore degli sbilanciamenti
teorema dualità debole con dimostrazione
teorema dualità forte
cos'è il problema del commesso viaggiatore in particolare come funziona l'euristica e il rilassamento
come faccio a capire se la soluzione primale e duale sono degeneri
problema dei cammini minimi successivi
eliminazione dei cicli ci costo negativo
algoritmo del simplesso duale
cos'è l'1-albero
come capire se una base primale/duale è ammissibilile sia algebricamente che geometricamente
cosa succede se nel simplesso duale fo un cambio di base e ottengo una base degenere
SPT pseudo codice, varianti SPT
scarti complementari
problema dello zaino