.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Progetto] Incastri - Gennaio 2011 (http://www.dsy.it/forum/showthread.php?threadid=41351)

[Progetto] Incastri - Gennaio 2011

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

ottimo hanno dato molto tempo.

per che turno è il progetto?

Per tutti e due anche sul sito di aguzzoli è presente il progetto:

http://homes.dsi.unimi.it/~aguzzoli/algo.htm

vale pure per il serale? siccome a lezione non hanno detto nulla mi pare

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.

ok grazie

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

Per le tessere avevo pensato ad una lista bidirezionale... poi vedrò nella pratica quanto sia utile.

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

Io avevo pensato ad una lista bidirezionale per la costruzione della catena e una lista unidirezionale per tenere traccia delle varie tessere create...

credo sia conveniente un grafo implementato con liste di adiacenza dove queste ultime tracciano le tessere compatibili per la catena

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★ 。* 。 。 ° ˛˚
° 。 ° ˛˚˛ * _Π_____*。*˚ 。 ° ˛˚
˚ ˛ •˛•˚ */______/~＼。˚ ˚ ˛ 。 ° ˛˚
˚ ˛ •˛• ˚ ｜ 田田 ｜門｜ 。 ° ˛˚ 。 ° ˛˚
-----------------------------\\----------• ♥ ★ 。* 。
★* 。 • ˚˛ •˚ ˛ ˚ ˛ ˛ •**。。 ° \\*。*˚ 。 ° ˛˚
•。★˛ • 。* 。.˛ •...˛ •*。*。*。\\。˚ ˚ ˛ 。 ° ˛˚

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

qualcuno ha pensato a Dijkstra per formare le catene?

Già fatto per un calcolo generale dei cammini minimi(con 2-3heap) partendo da un simbolo qualunque. Mi manca formare le catene...

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

troppo difficile hehe ci rinuncio

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.

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

hum dijkstra non credo serva in ogni caso, basta visitare in ampiezza per trovare le catene

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!

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

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

Scusate ma voi usando i grafi come fate a ricavarvi il cammino più breve?

Come diceva asgar, facendo una ricerca bfs... oppure, se vuoi farti del male, usando dijkstra.

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

qualcuno ha già fatto le sottostringhe massime o la cacofonia?

Originally posted by CowBoy
Come diceva asgar, facendo una ricerca bfs... oppure, se vuoi farti del male, usando dijkstra.

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

Originally posted by asgar
qualcuno ha già fatto le sottostringhe massime o la cacofonia?

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

Output errato

... up

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

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!

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...

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

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

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

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

__________________
Perché, mentre il manganello può sostituire il dialogo, le parole non perderanno mai il loro potere; perché esse sono il mezzo per giungere al significato, e per coloro che vorranno ascoltare, all'affermazione della verità. E la verità è che c'è qualcosa di terribilmente marcio in questo paese. (V)

I popoli non dovrebbero aver paura dei propri governi, sono i governi che dovrebbero aver paura dei popoli. (T.J)

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.

Controllate la posta in arrivo!

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

Qualcuno ha fatto la discussione del progetto con Lonati?! A grandi linee come viene svolto, cosa vi ha chiesto?

__________________
.. ±·ø·±-`` MuSiC iS My LanGuAGe ´´-±·ø·± ..

Originally posted by CowBoy
Qualcuno ha fatto la discussione del progetto con Lonati?! A grandi linee come viene svolto, cosa vi ha chiesto?