Autore Topic: Esame 11/03/11  (Letto 1259 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline demiurgo86

  • Nuovo
  • *
  • *
  • Post: 22
  • Reputazione: 1
Esame 11/03/11
« il: 11 Marzo 2011, 10:37:24 »
1)Esercizio sulla modellazione -> (bozza traccia) dati un insieme I di utenti da 1 a m, un insieme J da 1 a n di localizzazione di p server (p<n) e una matrice di costo [m,n] in cui ogni elemento cij rappresenta il costo d'utilizzo del server j da parte dell'utente i, modellare il problema tenendo conto che tutti gli utenti devono raggiungere un server e che deve essere minimizzato il costo (io io ho scritto una boiata gigantesca nell'esercizio, me li merito 0 punti ma se in 15 minuti 20 persone chiedono informazioni sulla traccia significa che un problema di fondo c'è.....)
2)B&B di una funzione di max, in cui veniva chiesto il primo nodo da visitare con la best first, quali nodi chiudere conoscendo la z corrente, la correttezza dell'albero conoscendo il LB di un nodo padre
3)esercizio su Tabu list (sempre lo stesso pattern, non scrivo nulla)
4)definire le classi p e np e come sono legate tra loro
5)(facoltativo) idea di fondo del prepush flow

penso che a parte il primo esercizio, il resto va bene. spero almeno in un 20...non ho proprio voglia di rifarmelo  :-\

ps:se c'è qualcuno che oggi ha fatto l'esame, possiamo discutere sul primo e sul secondo esercizio?

Offline flowchart

  • Utente
  • *
  • Post: 51
  • Reputazione: 0
Re:Esame 11/03/11
« Risposta #1 il: 11 Marzo 2011, 11:45:29 »
io c'ero chiedi pure

una domanda ma un modello dove nella fo compaia il prodotto di due variabili non va bene?

Offline demiurgo86

  • Nuovo
  • *
  • *
  • Post: 22
  • Reputazione: 1
Re:Esame 11/03/11
« Risposta #2 il: 11 Marzo 2011, 11:51:00 »
guarda...di modellazione non ho mai capito un tubo e mai capirò nulla, ma ragionandoci su penso che alla fine è corretto. tra l'altro non ho neanche capito cosa diavolo volesse il problema...ho chiesto 3 volte a perboli e mi stava per mandare a quel paese già alla seconda...sarà che sono inceppato ma io proprio sta traccia non l'ho capita! cmq giusto per stare con l'anima in pace...il terzo punto del b&B...io ho scritto che era corretto...ma mi sa che ho scritto un'altra boiata...qual era la risposta giusta?
« Ultima modifica: 11 Marzo 2011, 12:17:26 da demiurgo86 »

Offline flowchart

  • Utente
  • *
  • Post: 51
  • Reputazione: 0
Re:Esame 11/03/11
« Risposta #3 il: 11 Marzo 2011, 11:53:03 »
io ho scritto che nulla si poteva dire


Offline demiurgo86

  • Nuovo
  • *
  • *
  • Post: 22
  • Reputazione: 1
Re:Esame 11/03/11
« Risposta #4 il: 11 Marzo 2011, 12:00:27 »
lo sapevo -.- volevo scrivere che non si poteva dir nulla, ma dato che la volta scorsa ho scritto così e invece dovevo dire che c'era una relazione, allora a naso ho detto che anche questa volta c'era una relazione...mi sa bocciato :(

Offline flowchart

  • Utente
  • *
  • Post: 51
  • Reputazione: 0
Re:Esame 11/03/11
« Risposta #5 il: 11 Marzo 2011, 12:03:17 »
il primo ese credo di averlo toppato perche mi sa che la fo è non lineare..
il massimo per chi toppa il primo esercizio è un 18?

Offline demiurgo86

  • Nuovo
  • *
  • *
  • Post: 22
  • Reputazione: 1
Re:Esame 11/03/11
« Risposta #6 il: 11 Marzo 2011, 12:08:47 »
ma non credo, anche se non mi sembra che abbia mai parlato dei metodi di valutazione. guarda, ti posso dare un consiglio: cerca di pensare a tutti gli eventuali errori presenti nel compito, compreso il primo esercizio; quando esce il voto sul portale vai nel suo ufficio e potresti fare eventualmente un orale per alzare il voto!

Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Re:Esame 11/03/11
« Risposta #7 il: 11 Marzo 2011, 12:10:42 »
Se nella f.o. o in qualsiasi altro punto appare il prodotto di due variabili il modello è decisamente non lineare, quindi quell'esercizio è andato.
Se avete bisogno un riferimento per una possibile soluzione di quell'esercizio, da quel che ho inteso dal testo è semplicemente una porzione di un UFL (uncapacitated facility location), quindi lo trovate documentato in rete abbastanza facilmente (e pure sul libro).

Piccola nota:
Cercate di tenere un linguaggio non troppo colorito. Grazie.

« Ultima modifica: 11 Marzo 2011, 12:25:13 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 11/03/11
« Risposta #8 il: 11 Marzo 2011, 12:15:45 »
editato...

Offline flowchart

  • Utente
  • *
  • Post: 51
  • Reputazione: 0
Re:Esame 11/03/11
« Risposta #9 il: 11 Marzo 2011, 12:21:10 »
ho fatto una stronzata, in pratica mi danno zero non valutano nemmeno il resto del ragionamento giusto?

Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Re:Esame 11/03/11
« Risposta #10 il: 11 Marzo 2011, 12:24:27 »
Io posso solo ripeterti quello che ha detto più e più volte a lezione circa il non cadere nella non linearità.
Non so poi dirti come valuteranno. 

La possibilità di non ottenere punti in seguito a modello NL c'è, ma di più non saprei dire.




@Demiurgo: :thumbup:
« Ultima modifica: 11 Marzo 2011, 12:27:22 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 flowchart

  • Utente
  • *
  • Post: 51
  • Reputazione: 0
Re:Esame 11/03/11
« Risposta #11 il: 11 Marzo 2011, 12:25:17 »
grazie mille come sempre


Offline Caledor

  • Utente Senior
  • *
  • *
  • Post: 115
  • Reputazione: 3
  • Sesso: Maschio
Re:Esame 11/03/11
« Risposta #12 il: 11 Marzo 2011, 12:34:36 »
Anche io ho dato l'esame oggi.

Del punto tre del B&B però ho scritto che qualcosa si poteva dire della correttezza: il nodo padre ha LB 30, ma nessuno dei nodi figli ha UB >=a quello (erano tipo 28 e 25 se non sbaglio) quindi qualche errore ci deve essere (per chi non ha dato l'esame oggi il problema era un problema di massimo)...

Offline flowchart

  • Utente
  • *
  • Post: 51
  • Reputazione: 0
Re:Esame 11/03/11
« Risposta #13 il: 11 Marzo 2011, 12:36:57 »
ma quello è un criterio per la potatura, mica ti influisce sui bound

in un problema di massimo il lb è calcolato offline

Offline Caledor

  • Utente Senior
  • *
  • *
  • Post: 115
  • Reputazione: 3
  • Sesso: Maschio
Re:Esame 11/03/11
« Risposta #14 il: 11 Marzo 2011, 12:38:50 »
Il LB del nodo padre è una soluzione ammissibile  del problema. Tale soluzione perciò deve essere possibile in almeno uno dei due figli dato che insieme coprono tutte le soluzioni ammissibili del padre...

Offline flowchart

  • Utente
  • *
  • Post: 51
  • Reputazione: 0
Re:Esame 11/03/11
« Risposta #15 il: 11 Marzo 2011, 12:45:22 »
si ma il punto diceva cosa si puo concludere sui bound dei figli non chiedeva se i figli son corretti

Offline Caledor

  • Utente Senior
  • *
  • *
  • Post: 115
  • Reputazione: 3
  • Sesso: Maschio
Re:Esame 11/03/11
« Risposta #16 il: 11 Marzo 2011, 12:57:53 »
Beh ma se uno dei figli deve poter includere la soluzione del padre (che è 30) vuol dire che deve avere UB >= 30, quindi le due cose sono incompatibili -> o è sbagliato l'UB di almeno uno dei figli nell'ipotetico caso o il LB del padre.
« Ultima modifica: 11 Marzo 2011, 12:59:49 da Caledor »

Offline Wretched

  • Utente Fidato
  • *
  • *
  • *
  • Post: 219
  • Reputazione: 25
  • Sesso: Maschio
Re:Esame 11/03/11
« Risposta #17 il: 11 Marzo 2011, 15:22:43 »
1)Esercizio sulla modellazione -> (bozza traccia) dati un insieme I di utenti da 1 a m, un insieme J da 1 a n di localizzazione di p server (p<n) e una matrice di costo [m,n] in cui ogni elemento cij rappresenta il costo d'utilizzo del server j da parte dell'utente i, modellare il problema tenendo conto che tutti gli utenti devono raggiungere un server e che deve essere minimizzato il costo (io io ho scritto una boiata gigantesca nell'esercizio, me li merito 0 punti ma se in 15 minuti 20 persone chiedono informazioni sulla traccia significa che un problema di fondo c'è.....)
2)B&B di una funzione di max, in cui veniva chiesto il primo nodo da visitare con la best first, quali nodi chiudere conoscendo la z corrente, la correttezza dell'albero conoscendo il LB di un nodo padre
3)esercizio su Tabu list (sempre lo stesso pattern, non scrivo nulla)
4)definire le classi p e np e come sono legate tra loro
5)(facoltativo) idea di fondo del prepush flow

penso che a parte il primo esercizio, il resto va bene. spero almeno in un 20...non ho proprio voglia di rifarmelo  :-\

ps:se c'è qualcuno che oggi ha fatto l'esame, possiamo discutere sul primo e sul secondo esercizio?

Ho anch'io ho dato l'esame oggi. Vi riporto le risposte che ho dato per confronto:

Es1:
Come scritto da Cosmos il primo esercizio era una variante del problema Uncapacitated Facility Location:

\\x_{ij} = \text{frazione di domanda dell'utente i che viene servita nel punto di servizio j} \\ \quad y_j = \text{1 se viene localizzato un server nel punto j, 0 altrimenti}

 min \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij} x_{ij} \\ \\ \sum_{j=1}^{n} x_{ij}=1 \quad \forall i  \quad \quad \quad \text {Vincoli di soddisfazione della domanda}\\\\ x_{ij}\leq y_j \quad \forall i, j  \quad \quad \quad \text { Vincoli di apertura dei server}\\\\\sum_{j=1}^{n} y_j \leq p \quad \quad \quad \quad \quad \text { Vincolo di disponibilità dei server}\\\\ x_{i,j} \geq 0 \\\\y_j \in \{0,1\}

Es2:
Per il secondo esercizio si sceglieva il nodo 3, mi pare (quello con UB=28), si chiudevano 4 e 5 per assenza di soluzione migliorante e il LB=30 sul nodo 1 rendeva gli UB di 3 e 4 sbagliati per il motivo che ha detto Caledor.

Es3:
Sull'esercizio 3 la prima soluzione migliore del vicinato era tabù ma veniva presa come nuova soluzione corrente perchè rispettava il criterio di aspirazione. La tabù list si aggiornava di conseguenza.

Per quanto riguarda la non linearità nel modello credo proprio che lo conti totalmente sbagliato se formulato in modo non lineare. Non ricordo se nel testo era specificato espressamente di formulare un modello di PL o se fosse implicito, ma da quel che mi ricordo (e come  avveniva anche per il corso di Programmazione Matematica) lo considera un errore grave.
« Ultima modifica: 11 Marzo 2011, 17:58:49 da Wretched »
Cosa sono gli ingegneri se non gli Umpa Lumpa della scienza?

Offline flowchart

  • Utente
  • *
  • Post: 51
  • Reputazione: 0
Re:Esame 11/03/11
« Risposta #18 il: 11 Marzo 2011, 15:35:51 »
ma lb=30 era sul nodo  1 o 2?

Offline Wretched

  • Utente Fidato
  • *
  • *
  • *
  • Post: 219
  • Reputazione: 25
  • Sesso: Maschio
Re:Esame 11/03/11
« Risposta #19 il: 11 Marzo 2011, 15:49:11 »
A me pare sul nodo 1 ma aspetterei una conferma anche da altri. Non sono molto affidabile da quel punto di vista, sbagliare a leggere le tracce è una cosa che mi riesce da dio...  ::)
Cosa sono gli ingegneri se non gli Umpa Lumpa della scienza?