Pagina 1 di 1

Domande Orale Mastroeni

Inviato: 06/02/2016, 11:16
da InformateciBot
Apro questo thread per raccogliere solo le domande del Prof. Mastroeni. Nell 'altro mi sembra ci siano solo le domande di Pappalardo e facendo in questo modo credo che salti fuori una cosa più ordinata.

Per chi non lo sapesse il Prof. Mastroeni all ' inizio dell' orale vi chiede se volete aumentare il voto dello scritto o confermarlo, direi quindi di mettere una ( C ) accanto alle domande di un "orale di conferma" e una ( A ) accanto a quelle di un "orale di rialzo"

Orali della sessione invernale dell' A.A. 15/16

Esame1 ( A ) :
- Spiega a chi non sa nulla di Ricerca Operativa il teorema fondamentale della programmazione lineare
- Spiegare il significato di soluzione di base su grafi ( in particolare insiste sul significato delle basi e sulla tripartizione)

Esame2 ( A ) :
- Formulazione del problema del flusso massimo e suo duale (taglio di capacità minima), che relazione c'è tra i due?
- Enunciare il teorema MaxFlow - MinCut
- Teorema fondamentale della PL senza dimostrazione
- I vertici di un poliedro esistono sempre?

Febbraio 2017
Orale di oggi, 13 febbraio, il prof ci tiene molto ai modelli, vuole che tutto sia spiegato nei dettagli e
preferisce la scrittura dei teoremi/modelli su lavagna piuttosto che una spiegazione a voce,
quindi da stare attenti a scrivere per bene cosa significa ogni variabile/dato che viene usato.

Se vede che mancano le basi o non si sa spiegare cosa si è fatto nei compiti, l'orale dura poco e ti rimanda al prossimo appello altrimenti mediamente dura un bel po' (sui 40minuti circa) chiedendo un paio di cose su ogni argomenti svolto (PL, PLI, PL su reti).
Non da suggerimenti se non si sa arrivare a qualche argomento, quindi capitano spesso lunghi silenzi per poi cambiare domanda.

Ho letto dell'orale di conferma ma oggi non ne ha accennato, quindi non so se vale ancora.

Le domande che ha fatto, con relativo voto scritto/orale:

Esame 1 (Non passato):
- Modello del trasporto
- Modello del ciclo hamiltoniano
- Algoritmo di Kruskal per l'albero di copertura minimo
- (Domanda a scelta) Teorema degli scarti complementari

Esame 2 (Non passato):
- Modello del flusso di costo minimo
- Modello dell'albero di costo minimo
- Matrice di incidenza, cosa è, come si rappresenta e un esempio

Esame 3 (Partiva da 27, voto finale 28):
- Rifare il modello che ha sbagliato sul compito
- Teorema degli scarti complementari, significato e come si usa il teorema nel simplesso
- Teorema fondamentale e Teorema di rappresentazione dei poliedri
- Modello del trasporto
- Problema duale dell'albero di costo minimo

Esame 4 (Partiva da 28, confermato 28):
- Nell'albero del branch&bound quando si chiude un nodo, con quali criteri.
- Modello del Flusso massimo
- Condizioni di bellman, significato della tripartizione e uso nel simplesso per i flussi
- Teorema max-flow min-cut, relazione tra i due problemi
- Flusso e capacità di un taglio
- Dualità debole e forte, idea di dimostrazione della dualità debole

Aprile 2017
Orale relativo all'appello straordinario di aprile
Come gia' detto Mastroeni ci tiene molto ai formalismi e al rigore nelle dimostrazioni percio' state attenti a definire per bene tutto quello che scrivete.
Lascia anche parecchio tempo per pensare a una risposta e a volte ti lascia scrivere tutta la dimostrazione alla lavagna per poi spiegarla a voce una volta finito.
Il prof e' comunque molto magnanimo e largo di voti e spesso anche se l'esame va male ma si dimostra di sapere le basi conferma il voto dello scritto.

L'orale e' piuttosto lungo indipendentemente dal voto con cui si parte. Chiede praticamente sempre di correggere gli esercizi sbagliati allo scritto quindi rifatevelo a casa per bene.
Piu' o meno le domande sono le stesse gia' scritte sopra, ad ogni modo scrivo di seguito quelle che ricordo:
- Descrivere il modello di
- flusso di costo minimo (+ definire la matrice di incidenza)
- trasporto
- Dimostrare che l'algoritmo del simplesso primale in caso di soluzione di base non degenere non ottima al passaggio successivo fa crescere la funzione obiettivo (era una domanda "difficile" chiesta ad uno che partiva da 30L)
- Enunciare e dimostrare il teorema fondamentale della PL
- Enunciare il teorema della dualita' debole
- Dare delle condizioni di sufficienza affinche' un problema di PL abbia soluzione ottima finita
- Domande sulla regione ammissibile di un problema di PLI e relazione con un problema di PL
- Enunciare il teorema degli scarti complementari
- Dimostrare che l'algoritmo del simplesso si ferma in caso di ottimo illimitato superiormente

Gennaio 2018
All’inizio il professore ha guardato il compito e dal momento che avevo sbagliato una parte del taglio di Gomory, mi ha chiesto la definizione del piano di taglio e di taglio di Gomory con tutti i passaggi per arrivare al problema che ci permette di risolvere l’esercizio (problema primale -> problema rilassato -> duale ottenuto con le variabili di scarto). Come seconda domanda mi ha chiesto come si trovassero i teta del simplesso primale (la formula dei rapporti). Infine ha chiesto se fossero necessarie le regole anticiclo di Blend considerando che non ci sono soluzioni degeneri. La risposta corretta era “No” perché le regole anticiclo garantiscono un cambio di base ad ogni iterazione ma l’unico caso in cui si cambia base ma non il vertice è quando la soluzione è degenere e quindi teta = 0. Se non ci sono soluzioni degeneri teta è sempre maggiore di 0 e dunque necessariamente cambierò sempre vertice.

Ammesso 27, passato con 28.

Febbraio 2018
Queste sono le domande che mi ha fatto oggi (partivo da 29):
- Tema scritto sul flusso di costo minimo capacitato;
- Dimostrare con le curve di livello che dati due soluzioni ottime ce ne sono infinite
- Teorema fondamentale della programmazione lineare.

Giugno 2018
- Data una soluzione di base x come faccio a determinare se questa è o no la s.b. associata ad una determinata base? [Cioè data una x=(5,0) come faccio a stabilire che una s.b. associata alla base B={1,2}?];
- Def di Base;
- Def di soluzione di base;
- Il significato di soluzione di base degenere, perché la studiamo?
- Algoritmo del simplesso primale.

Luglio 2018 - Problema di flusso di costo minimo capacitato e condizioni di ottimalità per il flusso, quindi formulazione del problema, tripartizione T, L, U, dimostrazione che B = T u U u T' u L' è una base, problema duale del flusso di costo minimo (giusto il minimo indispensabile) per poi arrivare all'ottimalità (Bellman) (Pagine 141,142, 143, 144 e 145 del libro)
- Enunciato e dimostrazione teorema degli scarti complementari per problemi di programmazione di lineare