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

Domande orale Passacantando

queste sono alcune domande per l'orale di Mauro Passacantando in data 08/01/2019, l'esame e' alla lavagna:

- definizione di albero di copertura.
- modello del problema dei cammini minimi.
- condizioni di bellman, formula e a cosa servono.
- in un problema di PL cosa e' una base.
- come si calcola la soluzione duale.
- definizione del problema del commesso viaggiatore(modello) .
- come trovi ciclo hamiltoniano di costo minimo.
- cosa e' un k-albero e un'esempio.
- enunciato del lemma di farkas.
- definizione di direzione di recessione.
- cos'e' un taglio di gomory (formula e definizione).
- parte frazionaria di un numero.
- quando puoi chiudere un nodo su branch and bound(sia problemi di max e min).
- cos'e' un problema di copertura (modello) come trovare soluzione ammissibile (con tecniche euristiche).
- quando una soluzione base e' degenere (sia primale che duale).
- modello problema partizione di costo minimo, a che serve il problema.
- modello problema riempimento , a che serve.
- modello problema di copertura, dove si utilizza.
- cammino aumentante su cammini minimi successivi.
- enunciato teorema di scarti complementari.
- esempio di un problema di PL con duale ammissibile(analitico e geometrico).
- cos'e' un taglio in un grafo e che correllazione con flusso massimo.
- teorema max-flow-min-cut.
- cosa fa l'algoritmo simplesso duale ad ogni iterazione(stesso con primale).
- valore soluzione y nella nuova base duale che relazione c'e' con la vecchia base.
- se ho x e y soluzioni ammissibili quando gli scarti complementari sono rispettati.
- come sfruttare un grafo aciclico per trovare un albero di cammini minimi.
- forma generale di un problema di PLI.
- come modificare l'algoritmo di djistra per sapere solo cammino dal nodo scelto a destinazione non interessano tutti.
- modello flusso costo minimo.
- modello TSP.
- modello albero di copertura di costo minimo.
- disegna un grafo di flusso massimo e trova un taglio di capacita minima.
- cono di recessione cos'e' e un esempio.
- risolvere un problema di PL (metodo analitico e geometrico).
- condizioni di ottimalita PL e PLI.
- condizioni ottimalita flusso di costo minimo.
- condizioni ottimalita branch and bound.
- quando possiamo dire che un flusso e' massimo.


da anche esercizi da risolvere spiegando il ragionamento.

Teorema di rappresentazione dei poliedri
- formulare un esempio

Differenza tra un Ciclo Hamiltoniano e un r-albero

Branch and Bound
- Domanda: se Vi(P) = 50, Vi(P)=70, e all' i-esimo livello dell'albero ogni nodo ha Vi(P[i,j) compreso fra 50 e 70 non ammissibile per P, posso aggiornare Vi(P)? come?
- Modello flusso max
- Teorema max flow min cut (v=u(Ns,Nt)) e teorema generale (v=x(Ns,Nt)≤u(Ns,Nt))
- Come si trova il flusso sul taglio
- Teorema fondamentale della PL e disegnare un poliedro con i vertici e senza vertici (un poliedro è senza vertici quando lineal(P) ≠ 0)
- Disegnare un albero di copertura dove la sol è ottima per il problema dell’albero di copertura dei costi minimi e non è soluzione ottima dell’albero dei cammini minimi. Io ho disegnato un albero con archi (1,2)(2,3)(3,4) con costi 3, 2, 1 mentre i costi degli archi (1,3) e (2,4) rispettivamente 5 e 2.