Autore Topic: Esame 14/02/2010  (Letto 828 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline Mithrandir

  • Maestro Geek
  • *
  • *
  • *
  • Post: 1.157
  • Reputazione: 44
  • Sesso: Maschio
  • Battlemage
Esame 14/02/2010
« il: 14 Febbraio 2011, 14:42:02 »
Traccia approssimata:
  • Modello di programmazione lineare;
  • Branch & Bound, problema di minimo, analisi dei nodi aperti;
  • Enunciare il principio di Bellman e fornire un esempio di applicazione;
  • Max Flow, 2 iterazioni di Ford-Fulkerson;
  • (facoltativo) Vantaggio della line search basata su sezione aurea rispetto a quella dicotomica.
Spoiler (click to show/hide)
Gandalf? Yes... that was what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now - at the turn of the tide.


Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Re:Esame 14/02/2010
« Risposta #1 il: 22 Febbraio 2011, 20:54:33 »
Sono usciti i voti.
Registrazione il 25/2, ore 15.00 in ufficio.
Spoiler: XKCD (click to show/hide)



Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

Corollario: Se il risultato non si annulla, sarà 2\pi

Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"

Offline Raptor

  • Utente Fidato
  • *
  • *
  • *
  • Post: 489
  • Reputazione: 11
  • Sesso: Maschio
    • rpt@altervista
Re:Esame 14/02/2010
« Risposta #2 il: 23 Febbraio 2011, 10:24:38 »
Sono usciti i voti.
Registrazione il 25/2, ore 15.00 in ufficio.
a me non è arrivato nulla  ::)

Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Re:Esame 14/02/2010
« Risposta #3 il: 23 Febbraio 2011, 10:35:53 »
Sono nella pagina progetto esami.
Spoiler: XKCD (click to show/hide)



Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

Corollario: Se il risultato non si annulla, sarà 2\pi

Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"

Offline Raptor

  • Utente Fidato
  • *
  • *
  • *
  • Post: 489
  • Reputazione: 11
  • Sesso: Maschio
    • rpt@altervista
Re:Esame 14/02/2010
« Risposta #4 il: 23 Febbraio 2011, 11:01:49 »
Sono nella pagina progetto esami.
grazie  :P

(ma che ci fa allora con le nostre mail? le vende agli spammer?)

Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Re:Esame 14/02/2010
« Risposta #5 il: 23 Febbraio 2011, 11:08:20 »
Credo che quelle servano in caso sia necessario un contatto diretto.

Suppongo inoltre che i prof credano che il messaggio associato alla pubblicazione del voto venga anche inoltrato per mail, cosa che sarebbe utile ma non accade (visto anche il messaggio di TSR)...
Spoiler: XKCD (click to show/hide)



Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

Corollario: Se il risultato non si annulla, sarà 2\pi

Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"

Offline demiurgo86

  • Nuovo
  • *
  • *
  • Post: 22
  • Reputazione: 1
Re:Esame 14/02/2010
« Risposta #6 il: 23 Febbraio 2011, 18:33:54 »
ciao
volevo avere un chiarimento su 3 esercizi dell'esame del 14:
1) esercizio sul b&b
          a) si considera il nodo piu promettente data la politica best first (il nodo con il minimo LB)
          b) si chiude il nodo (se non erro il numero 3) perchè aveva un LB uguale al minimo degli UB presenti (considerando quindi quest'ultimo bound come soluzione ottimale corrente del problema rilassato)
          c)poichè è un problema di minimo non si può dire nulla sul valore dell'UB del primo nodo
2)sezione aurea vs dicotomica
        ho scritto semplicemente che c'erano dei vantaggi a livello prestazionale in quanto ha una complessità                 computazionale minore
3)principio di bellman
        in soldoni ho scritto che dato un problema con una politica ottima anche i suoi sottoproblemi avranno una politica ottima. un esempio pratico lo si trova nella soluzione di problemi legati alla programmazione lineare.

Per quanto riguarda il secondo e il terzo punto, le risposte date sono esaustive (benchè corrette)? Nel primo punto, per quanto riguarda l'eventuale chiusura di nodi aperti, ho ritenuto di assegnare come soluzione il minimo degli UB: è corretto farlo o semplicemente, dato che non viene detto esplicitamente qual è il valore della soluzione, dovevo scrivere che non potevano essere chiusi nessuno dei nodi?

grazie di tutto!

ps: avendo svolto anch'io i temi d'esami degli anni precedenti, dò uno sguardo e controllo se i risultati si trovano con i miei (sicuramente avrò fatto qualche errore  ???)

Offline Mithrandir

  • Maestro Geek
  • *
  • *
  • *
  • Post: 1.157
  • Reputazione: 44
  • Sesso: Maschio
  • Battlemage
Re:Esame 14/02/2010
« Risposta #7 il: 23 Febbraio 2011, 18:48:32 »
c)poichè è un problema di minimo non si può dire nulla sul valore dell'UB del primo nodo
Puoi assegnare un valore plausibile per l'UB scegliendo un numero maggiore o uguale a quello degli UB dei figli.

ho scritto semplicemente che c'erano dei vantaggi a livello prestazionale in quanto ha una complessità computazionale minore
Avresti dovuto (e anche io avrei dovuto  ;)) citare il fatto che aumenta il fattore di riduzione dell'intervallo di valori in esame: non è più 1/2 come nella dicotomica.

3)principio di bellman
        in soldoni ho scritto che dato un problema con una politica ottima anche i suoi sottoproblemi avranno una politica ottima. un esempio pratico lo si trova nella soluzione di problemi legati alla programmazione lineare.
Credo che come esempio si aspettasse qualcosa come la ricerca di cammino minimo, cioè un caso più specifico che la "programmazione lineare".

Nel primo punto, per quanto riguarda l'eventuale chiusura di nodi aperti, ho ritenuto di assegnare come soluzione il minimo degli UB: è corretto farlo o semplicemente, dato che non viene detto esplicitamente qual è il valore della soluzione, dovevo scrivere che non potevano essere chiusi nessuno dei nodi?
No, gli UB sono tutti soluzioni ammissibili per cui il tuo ragionamento (lo stesso mio) dovrebbe funzionare.


Comunque finché non vedremo i compiti (con le sue correzioni) non posso dirti molto su cosa si aspettava che scrivessimo.
Spoiler (click to show/hide)
Gandalf? Yes... that was what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now - at the turn of the tide.


Offline demiurgo86

  • Nuovo
  • *
  • *
  • Post: 22
  • Reputazione: 1
Re:Esame 14/02/2010
« Risposta #8 il: 23 Febbraio 2011, 19:00:22 »
grazie per la risposta celere! più che altro sono curioso di capire dove ho potuto sbagliare. il compito era abbordabilissimo a mio parere (ma nonostante tutto mi sono ritrovato un respinto in progetto esami  >:( )

Offline demiurgo86

  • Nuovo
  • *
  • *
  • Post: 22
  • Reputazione: 1
Re:Esame 14/02/2010
« Risposta #9 il: 23 Febbraio 2011, 19:13:03 »
Puoi assegnare un valore plausibile per l'UB scegliendo un numero maggiore o uguale a quello degli UB dei figli.

Mi ricordo che all'esercitazione dell'ing. Perboli, disse chiaramente che in un problema di max possiamo ragionare sul valore di un UB del padre/figlio, ma non su un LB (quindi vale il duale per il problema di minimo).

Offline Mithrandir

  • Maestro Geek
  • *
  • *
  • *
  • Post: 1.157
  • Reputazione: 44
  • Sesso: Maschio
  • Battlemage
Re:Esame 14/02/2010
« Risposta #10 il: 23 Febbraio 2011, 19:21:45 »
La domanda 2.c non chiedeva di stimare una relazione fra gli UB (che non esiste), ma semplicemente di assegnare un valore plausibile all'UB del padre.
Comunque, ripeto, non ho nessuna certezza. Aspetto di vedere il compito.

PS: Dimenticavo di darti il benvenuto nel forum e invitarti a postare un topic nella sezione Presentazioni.
« Ultima modifica: 23 Febbraio 2011, 19:23:16 da Mithrandir »
Spoiler (click to show/hide)
Gandalf? Yes... that was what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now - at the turn of the tide.


Offline demiurgo86

  • Nuovo
  • *
  • *
  • Post: 22
  • Reputazione: 1
Re:Esame 14/02/2010
« Risposta #11 il: 23 Febbraio 2011, 19:27:14 »
O.T.
avevo cercato dopo l'iscrizione una sezione PRESENTAZIONI, ma evidentemente lo studio m'ha recato una cecità non indifferente! rimedio subito :)

Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Re:Esame 14/02/2010
« Risposta #12 il: 23 Febbraio 2011, 20:26:05 »
Sul B&B sono d'accordo, a parte per il terzo punto come ti ha già fatto notare Mith.

Sulla PNL mi sentirei di dire che la risposta data sia sbagliata. Le due tecniche hanno praticamente la medesima complessità.
Ciò che è migliore nella seconda è il fattore di riduzione, oltre ad un piccolo vantaggio operativo dato dal richiedere una sola osservazione (dopo la prima iterazione) per ogni passo, mentre la prima ne richiede sempre due.

Per Bellman a grandissime linee ci può stare l'introduzione che hai dato, ma poi ti sei tirato una zappata sui piedi. La PD è applicabile solo a quei problemi che godono di certe qualità strutturali (problemi autosimili e politica ottima), ma ciò capita per un insieme ristretto di problemi, quindi citare vagamente i problemi di PL in generale è sbagliato.

Questo almeno dal mio punto di vista.
Spoiler: XKCD (click to show/hide)



Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

Corollario: Se il risultato non si annulla, sarà 2\pi

Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"

Offline demiurgo86

  • Nuovo
  • *
  • *
  • Post: 22
  • Reputazione: 1
Re:Esame 14/02/2010
« Risposta #13 il: 25 Febbraio 2011, 17:59:26 »
Sono andato a ricevimento dal professore tadei, il quale m'ha mostrato gli errori del compito:
1° esercizio -> completamente sbagliato (ho messo solo costanti senza variabili -.- sono un pollo)
2° esercizio -> b&b TUTTO CORRETTO, tranne per la parte degli UB. effettivamente si doveva dire che il nodo padre doveva assumere un valore maggiore o uguale di uno dei suoi nodi figli (altrimenti non avrebbe avuto senso un  branch). per il resto tutto ok
3° esercizio -> la definizione di bellman che ho dato era corretta, ma non aveva  capito cosa intendessi dire per sottoproblemi ottimi. m'ha fatto un piccolo orale in cui m'ha fatto dire la definizione, un esempio di applicazione e voleva che glielo spiegassi (su questa parte ho glissato poichè avevo appena finito da 15 minuti l'esame di strategia e innovazione)
4°esercizio -> il massimo flusso tutto corretto...tranne l'ultima parte in cui come un fesso ho sbagliato a fare il grafo di scarto, e non mi sono accorto che la soluzione non era ottima (cosa che io invece avevo scritto)

il prof aveva rivalutato la domanda su bellman, ma per rabbia (nei miei confronti OVVIAMENTE) ho detto che lo ripetevo l'11 marzo.
in ogni caso li ho visti molto disponibili (almeno di persona lo sono...per email non tanto -.- ). qualcuno di voi ha l'intenzione di ripeterlo e ha voglia di esercitarsi / ripetere qualcosa?

Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Re:Esame 14/02/2010
« Risposta #14 il: 26 Febbraio 2011, 11:12:29 »
...in ogni caso li ho visti molto disponibili (almeno di persona lo sono...per email non tanto -.- )...

In effetti per mail non è che si sprechi moltissimo (esperienza personale), ma come prof. non gli si può dire nulla. È decisamente uno dei migliori che abbia avuto.
Di persona, poi, è decisamente disponibile.

...qualcuno di voi ha l'intenzione di ripeterlo e ha voglia di esercitarsi / ripetere qualcosa?

Per tutti quelli che hanno scritto in questo topic, Metodi è andata!
« Ultima modifica: 26 Febbraio 2011, 11:14:08 da Cosmos »
Spoiler: XKCD (click to show/hide)



Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

Corollario: Se il risultato non si annulla, sarà 2\pi

Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"

Offline demiurgo86

  • Nuovo
  • *
  • *
  • Post: 22
  • Reputazione: 1
Re:Esame 14/02/2010
« Risposta #15 il: 26 Febbraio 2011, 19:05:27 »
allora a qualcuno di voi posso chiedere due gentilezze? per caso potrei avere in prestito per 1-2 max 3 giorni il libro degli esercizi e/o qualche esercizio sulla modellazione?

Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Re:Esame 14/02/2010
« Risposta #16 il: 26 Febbraio 2011, 19:47:21 »
Io sono tornato a casa, e non sarò a Torino nell'immediato futuro.
Ti linko però un pdf recuperato a suo tempo per integrare il materiale già disponibile.
Spero possa esserti utile in quale modo...

--> R.O.
Spoiler: XKCD (click to show/hide)



Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

Corollario: Se il risultato non si annulla, sarà 2\pi

Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"