[Progetto] Incastri - Gennaio 2011
Clicca QUI per vedere il messaggio nel forum |
| CowBoy |
Ciao a tutti,
apro questo 3d per discutere su qualsiasi aspetto relativo al progetto in oggetto(strutture dati, proposta funzioni, problemi, dubbi, ecc).
In bocca al lupo!!
Trovate il testo del progetto al seguente link:
code:
http://lonati.dsi.unimi.it/algo/1011/esami/incastri.pdf
* Valido per l'appello del 21 gennaio 2011.
* Data ultima di consegna: 14 gennaio 2011 ; le date dei colloqui saranno comunicate in seguito.
|
| zack1988 |
| ottimo hanno dato molto tempo. |
| Dazan |
| per che turno è il progetto? |
| Dazan |
| vale pure per il serale? siccome a lezione non hanno detto nulla mi pare |
| zack1988 |
| Mi sa che non è fatto con il nuovo prof. ma con il prof. Aguzzoli è un appello che riguarda l'anno scorso e non il corrente. |
| SanJuanWolf89 |
salve a tutti---ho appena iniziato a fare il progetto INCASTRI
quale struttura dati consigliate di utilizzare per memorizzare le tessere??
visto che non si tratta di interi io avevo pensato a una lista concatenata |
| CowBoy |
| Per le tessere avevo pensato ad una lista bidirezionale... poi vedrò nella pratica quanto sia utile. |
| Guccio |
| Io avevo pensato ad una lista bidirezionale per la costruzione della catena e una lista unidirezionale per tenere traccia delle varie tessere create... |
| asgar |
| credo sia conveniente un grafo implementato con liste di adiacenza dove queste ultime tracciano le tessere compatibili per la catena |
| CowBoy |
Sono d'accordo con asgar riguardo al grafo(l'ho già implementato), e visto che bisogna fare tante ricerche una struttura dati ad albero rb non sarebbe male per memorizzare le tessere.
Per le catene ci sono più soluzioni possibili, ma una volta che si arriva a formarle penso che ad ogni uno si accenderà la lampadina della soluzione migliore. :)
_______________________________________
★B u o n ★ 。 • ˚ ˚ ˛ ˚ ˛ • ♥ 。 ° ˛˚
•。 ★N a t a l e★ 。* 。 。 ° ˛˚
° 。 ° ˛˚˛ * _Π_____*。*˚ 。 ° ˛˚
˚ ˛ •˛•˚ */______/~＼。˚ ˚ ˛ 。 ° ˛˚
˚ ˛ •˛• ˚ ｜ 田田 ｜門｜ 。 ° ˛˚ 。 ° ˛˚
-----------------------------\\----------• ♥ ★ 。* 。
★* 。 • ˚˛ •˚ ˛ ˚ ˛ ˛ •**。。 ° \\*。*˚ 。 ° ˛˚
•。★˛ • 。* 。.˛ •...˛ •*。*。*。\\。˚ ˚ ˛ 。 ° ˛˚ |
| asgar |
| qualcuno ha pensato a Dijkstra per formare le catene? |
| CowBoy |
| Già fatto per un calcolo generale dei cammini minimi(con 2-3heap) partendo da un simbolo qualunque. Mi manca formare le catene... |
| asgar |
| troppo difficile hehe ci rinuncio |
| CowBoy |
Ti do ragione asgar... purtroppo le strutture dati dei grafi scritte dall'ALGOTeam non sono molto chiare. Mancano i commenti e chiarimenti del caso. Personalmente ci ho messo un po a decifrare il tutto. Praticamente ogni vertice viene rappresentato da un intero che parte da 0, con numerazione crescente. La lista/file di input deve contenere i dati in formato [id vertice partenza] [id arco(id vertice al quale collego il vertice di partenza)] [costo/distanza].
Il codice inoltre richiede che l'input venga letto da un file, ma si può modificare per far sì che legga una lista o altro...
Penso che sarebbe di grande aiuto se un giorno chi ha scritto il codice, aggiungesse anche dei commenti o delle descrizioni. |
| asgar |
| hum dijkstra non credo serva in ogni caso, basta visitare in ampiezza per trovare le catene |
| CowBoy |
Vero, la visita in ampiezza... ho fatto male a non frequentare quest'anno. Ho provato ad implementarla e funziona bene con i primi test.
Dijkstra basico con complessità O(n^2) mi funzionava bene ma quando ho cambiato implementazione usando gli 2-3heap per scendere a O(m+nlogn), il risultato finale era errato. Grazie asgar per questo suggerimento! |
| asgar |
| mah per ora più che vedere il tempo di calcolo o lo spazio occupato cerco di farlo funzionare hehe.. in effetti il mio fra cicli e non cicli ci mette un sacco a calcolare le catene. però si può sempre risolvere aggiungendo qualche puntatore ai nodi del grafo quindi per ora non me ne preoccupo |
| Guccio |
| Scusate ma voi usando i grafi come fate a ricavarvi il cammino più breve? |
| CowBoy |
| Come diceva asgar, facendo una ricerca bfs... oppure, se vuoi farti del male, usando dijkstra. |
| asgar |
| qualcuno ha già fatto le sottostringhe massime o la cacofonia? |
| Guccio |
Originally posted by CowBoy
Come diceva asgar, facendo una ricerca bfs... oppure, se vuoi farti del male, usando dijkstra.
Si ma così viene esplorato il grafo...ma per mantenere traccia di tutti i cammini possibili per poter scegliere il più breve? |
| Bomb |
li memo rizzi tutti e poi tieni quello che fa meno passi?
mah...mi sembra un po' dispendioso...però dijkstra lo è ancora di più...:mad |
| CowBoy |
Originally posted by asgar
qualcuno ha già fatto le sottostringhe massime o la cacofonia?
Usa un algoritmo chiamato "La sotto sequenza comune massima"(LCS - Longest common subsequence/substring)... ci sono vari modi di implementarlo. Il peggiore è quello ricorsivo(tempo esponenziale). Quello dinamico scende a O(n*m)... se proprio vuoi strafare ci sono alcune tecniche per renderlo ancora più veloce.
Ciao! |
| asgar |
Originally posted by CowBoy
Usa un algoritmo chiamato "La sotto sequenza comune massima"(LCS - Longest common subsequence/substring)... ci sono vari modi di implementarlo. Il peggiore è quello ricorsivo(tempo esponenziale). Quello dinamico scende a O(n*m)... se proprio vuoi strafare ci sono alcune tecniche per renderlo ancora più veloce.
Ciao!
mm non avevo visto il post.. ne ho fatto uno io che dipende dalla lunghezza delle due stringhe quindi credo dell'ordine di n*m, credo terrò quello, grazie cmq :) |
| CowBoy |
| Direi che ormai dovrei esserci... se qualcuno ha preparato file per testare il codice, posti pure qualche esempio per vedere se ci sono comportamenti anomali e sistemarli... |
| CowBoy |
ATTENZIONE!!! Leggete il seguente avviso:
7 gennaio 2011
La traccia del progetto "incastri", valida per l'appello di gennaio, presenta un errore all'interno dell'esempio conclusivo. L'istruzione "m gatto topo" deve essere ignorata in quando non esistono tessere con nome "gatto" quindi la riga di output "to" non va stampata.
http://lonati.dsi.unimi.it/algo/1011/?page=avvisi |
| xSharKMaNx |
Ciao a tutti,
volevo chiedere a chi ha frequentato il lab di algo con la Prof. Lonati come si è trovato.
Vedendo le sue slide sul JLI devo dire che sono fatte davvero bene.
Per la teoria cosa state utilizzando come materiale?
Grazie a tutti |
| Guccio |
| Il laboratorio con la Lonati vale la pena seguirlo, lei è molto preparata. Goldwurm è una chiavica...non spiega tanto bene ed è un po' soporifero; comunque non spiega con le slide fa tutto alla lavagna. On line se non sbaglio sul suo sito trovi delle dispense fatte da lui su quello che spiega, anche se non sono nello stesso ordine in cui espone le cose a lezione. Spero di esserti stato d'aiuto. |
| CowBoy |
| Controllate la posta in arrivo! |
| CowBoy |
| Qualcuno ha fatto la discussione del progetto con Lonati?! A grandi linee come viene svolto, cosa vi ha chiesto? |
| asgar |
Originally posted by CowBoy
Qualcuno ha fatto la discussione del progetto con Lonati?! A grandi linee come viene svolto, cosa vi ha chiesto?
chiede di spiegare le funzioni principali e vi fa ragionare su dei modi per migliorarle |
|
|
|
