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

[Progetto]Iperspazio

idee?
lfn

__________________
an arrow from the sun

bene, dalla prima lettura ho capito ben poco...
mi sembra un pò differente dai precedenti progetti...

help me

alla prima lettura non ho capito una bega... bene

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Wow questa volta il progetto mi piace

Da quanto ho capito ci sono 2 problemi principali da risolvere.

- La verifica della contenibilità.
Il Dispositivo 1 ha una forma ad n-lati lunghi (X1,...,Xn).
Il Dispositivo 2 ha una forma ad n-lati lunghi (Y1,...,Yn).
Per verificare se il Dispositivo 1 è contenibile nel Dispositivo 2 bisogna creare una sequenza di rotazioni (scambiando una delle coppie Xi,Xj del Dispositivo 1) tale da ottenere un risultato per cui ogni lato del Dispositivo 1 è più piccolo del corrispettivo lato del Dispositivo 2 (X1 < Y1, X2 < Y2, ... , Xn < Yn)

- Il calcolo dell'energia prodotta da un Amplificatore.
Usando la funzione contenibilità si creano delle sequenze di Dispositivi contenuti uno nell'altro e non ho capito bene come se ne calcola l'energia. Forse bisogna verificare che la lunghezza della sequenza sia maggiore o uguale al tempo necessario a creare energia T(D)

si sembra interessante anche a me
sul piano teorico sembrerebbe una cavolata, sul piano implementativo la vedo dura (visto che io e l'ansi c non andiamo d'accordissimo )
lfn

__________________
an arrow from the sun

mmmmm...................
mi pare che le cose siano MOLTO complicate ................... sempre peggio sigh !!!

Speriamo che non sia anche questo un problema np completo

non riesco neanhe a capire a che tipo di problemi (quindi algoritmi risolutivi) si avvicini... sono proprio asino

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

sequenze

Ciao a tutti,
io non ho capito quali dispostivi compongono le sequenze...cioè
se a<b<c<d<e<f, perchè nell'esempio viene creata la S1 con
a<b<c<d ???

grazie a chiunque mi possa rispondere

ragazzi ma che problema è? come si calcola una combinazione di punti ottimale in quel senso? che algoritmi usare?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Re: sequenze

Originally posted by full


Ciao a tutti,
io non ho capito quali dispostivi compongono le sequenze...cioè
se a<b<c<d<e<f, perchè nell'esempio viene creata la S1 con
a<b<c<d ???

grazie a chiunque mi possa rispondere

Ciao!
riguardo al mio post precedente continuo a non capire...
dunque:
pag.2
il dispositivo a è contenuto nei dispositivi b, c, d, e, f
mentre S1=a<b<c<d che sarebbe una sequenza....????

poi S2=g<e<f che sarebbe un altra sequenza?? arbitraria???

è questo che non capisco come scegliamo una sequenza?
dall'esempio 2 non riesco a capirlo...

boo!!

credo che ci vorrà un pò di tempo per decifrarlo.

ciao a tutti e buon lavoro!

Originally posted by full
Ciao!
riguardo al mio post precedente continuo a non capire...
dunque:
pag.2
il dispositivo a è contenuto nei dispositivi b, c, d, e, f
mentre S1=a<b<c<d che sarebbe una sequenza....????

poi S2=g<e<f che sarebbe un altra sequenza?? arbitraria???

è questo che non capisco come scegliamo una sequenza?
dall'esempio 2 non riesco a capirlo...

boo!!

credo che ci vorrà un pò di tempo per decifrarlo.

ciao a tutti e buon lavoro!

Originally posted by Polsy
si, sono sequenze date dal fatto che i dispositivi sono contenibili ...

Originally posted by marcomaria
le sequ di dispositivi vanno bene...Polsy che struttura dati useresti per rappresentare l'ampli? thanks!

bhe! direi che ora le cose sono un pò più chiare, dico solo che non capisco il senso di questo progetto, forse me lo devo studiare ancora meglio.
effettivamente avevo immaginato anche io la lista contenente i puntatori ai dispositivi, ma anche quest'ultimi potremmo rappresentare come liste.

vedremo

grazie polsy

Originally posted by Polsy
per l'amplificatore farei semplicemente una lista di sequenze che tengono i puntatori ai dispositivi coinvolti

ciao a tutti,
sto impazzendo sul problema del'ottimizzazione dell'energia, sembra un problema da gestire con la programmazione dinamica per diminuire la complessita, se ho n input le possibili combinazioni sarebbero n!, ma devo solo trovare quella ottima, con 4 elementi potrò avere al massimo una combinazione di 4 elementi.
Il problema è questo non riesco atrovare una ricorrenza che mi dia questa solozione ...............
avete ideee ??

ciao ragazzi,
dopo il suggerimento di polsy, mi sono venute in mente un bel pò di idee.

dunque il problema iniziale è trovare il dispositivo più grande(la matriosca) che conterrà all'interno tutti i dispositivi piu piccoli, è un semplice controllo di interi, non c'è bisogno nemmeno di fare rotazioni se li ordini in modo crescente.
il secondo grande problema è quello di massimizzare il valore di energia di ogni sequenza di dispositivi, e a mio parere lo si fa controllando che il T(D) di ogni dispositivo non superi U(D).ricordandoci che ogni volta che andiamo a sommare l'energia di un altro dispositivo, dobbiamo sommare il nuovo T(D) al vecchio e controllare che non sia maggiore del nuovo U(D) se così non fosse dobbiamo cercare un altra combinazione..se non c' è un altro modo allora invece del valore dell'energia sommeremmo 0.

so di non essere stata chiara ma io ho trovato la soluzione nell'esempio 2 e facendo delle prove..

per prima cosa capiamo bene dove dobbiamo arrivare con questo progetto e poi passiamo al codice.



buon lavoro a tutti

Sono d'accordo con te, io ho provato a fare l'albero delle ricorsioni dal tempo t0 con tutte le possibili combinazioni, le foglie sono la soluzione, basta verificare qual' è il valore + grande e confrontarlo con i singoli dispositivi.
Non riesco a fare la ricorsione da applicare all'algoritmo, non sto implementando ancora niente, non è il solito divide et impera perchè devo verificare tutte le combinazioni stando attento al vincolo t+T(Dk) <= U(Dk).
Questo è il dilemma !!!!!!!!!

il fatto è che io non riesco ad immaginarmi un albero delle ricorrenze, forse perchè io tendo ad avere un unica struttura dati e ad operare per controlli, ovvero quando andremo a fare le somme delle energie, dinamicamente cerchiamo quelle che rispettano ->t+T(D)<=U(D) altrimenti mettiamo 0..

non so se mi spiego..

ciao ragazzi, vedo che parlate dei dispositivi e degli amplificatori, questo vuol dire che la soluzione al problema del "contenibile" vi è chiara, beh io invece sto navigando nel buio, come fate a trovare che un dispositivo n-dimensionale è contenuto in un altro? intendo in modo efficiente, se abbiamo dispositivi a 100dimensioni come fate a calcolare se un dispositivo è contenuto in un altro? io pensavo ordinando i valori e poi controllando uno ad uno, cioè se ho P e Q ordino i loro spigoli e poi controllo le coppie dallo spigolo di indice 0 a quello di indice n-1.

ma non dimostro che funzioni perfettamente... e in più mi dice che è contenibile o meno ma no mi da la sequenza per cui funziona.

voi come avete fatto???

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Ciao a tutti, pensavo di aver capito ma rileggendo il progetto mi sono incasinato. Qualcuno puo' spiegarmi perche' nell' esempio 1 si dice che la sequenza piu' lunga e' a-b-c-d e si esclude a-b-e-f ?
Sono lunghe uguali, perche' sceglie la prima?

Originally posted by theJackal
Ciao a tutti, pensavo di aver capito ma rileggendo il progetto mi sono incasinato. Qualcuno puo' spiegarmi perche' nell' esempio 1 si dice che la sequenza piu' lunga e' a-b-c-d e si esclude a-b-e-f ?
Sono lunghe uguali, perche' sceglie la prima?

__________________
an arrow from the sun

Originally posted by maynard80
trovare che un dispositivo n-dimensionale è contenuto in un altro?

si, anche io ho fatto cosi' per stabilire se D1<D2
adesso pero' sono a un punto morto...

ciao ragazzi!
matematicamente se un oggetto ha le dimensioni minori di un altro oggetto allora uno è contenibile nell'altro, quindi non penso ci sia altro modo più efficiente che ordinare le dimensioni e confrontare valore per valore, poi ovviamente bisognerà trovare un modo "carino" per far stampare i due dispositivi non in ordine crescente, bensì il "contenitore" andrà in output nello stesso modo in cui era in imput, mentre il più piccolo viene stampato con le posizioni ruotate ad hoc.

per avere un esempio guardate il primo esempio nelle righe di codice:
viene chiesto di verificare che alfa sia contenuto in beta, in output, dopo aver visto che le dimensini di alfa sono tutte minori delle dimensioni di beta, beta viene stampato così com'è senza rotazioni, mentre alfa è stato ruotato nel modo giusto.

tutto questo per dire che non è una buona soluzione ordinarli e basta, perchè poi bisognerà ritrovare le posizioni originali.

buon lavoro a tutti

secondo me il problema più grande è stabilire la sequenza più lunga tra le varie possibilità e poi tra queste combinazion la sotto sequenza più lunga possibile e così via.. sono due problemi in uno
lfn

__________________
an arrow from the sun

scusami ma se a casa hai n scatole vuote che non ti servono a nulla per il momento ma che non vuoi buttare via perchè pensi che ti serviranno in futuro cosa fai per non avere la casa in disordine??????

secondo me la soluzione è questa....pensaci bene perchè sembra difficile ma invece è intuitivo...



ciao!

qualcuno mi dice come faccio a trovare la sequenza piu' lunga?
sono disperato e non riesco a trovare la soluzione. Ci ho provato ma non so come comportarmi se trovo due sequenze lunghe uguali...aiutoooooooooooooo......

Originally posted by full
scusami ma se a casa hai n scatole vuote che non ti servono a nulla per il momento ma che non vuoi buttare via perchè pensi che ti serviranno in futuro cosa fai per non avere la casa in disordine??????

secondo me la soluzione è questa....pensaci bene perchè sembra difficile ma invece è intuitivo...



ciao!

__________________
an arrow from the sun

dunque ammeso che il modo per trovare i contenitori sia fissato, sinceramente la strada per rendere ottimizzato il lavoro dell'amplificatore certo non lo so... comecacchio faccio? e che algoritmi del libro si fa riferimento?

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

Ciao, io non voglio smontarvi, ma l'idea di ordinare le regioni per la funzione contenibile() non so se va bene. Vi riporto il testo:

"Un dispositivo n-dimensionale D1 `e contenibile in un dispositivo n-dimensionale D2 se esiste una sequenza
di rotazioni semplici di D1 alla fine della quale R(D1) = hx1; : : : ; xni, R(D2) = hy1; : : : ; yni e xi < yi per
ogni i 2 f1; : : : ; ng. Se D1 `e contenibile in D2 allora scriviamo D1 C D2."

Dice chiaramente che D1 è contenibile in D2 SE ESISTE UNA SEQUENZA DI ROTAZIONI DI D1, quindi D2 non deve essere toccato.

ciao a tutti,
dunque è vero che la D2viene stampata nel modo originale, ma non è vietato ordinarla in un altra struttura.
quindi secondo me bisogna fare tutte le operazioni possibili che ci vengono in mente per capire se un dispositivo è contenibile in un altro ma sempre tenendo in memoria la forma del dispositivo originale..

forza ragazzi che abbiamo appena una settimana per tradurre tutte queste parole in codice!

buon lavoro!!

Originally posted by WebSpid
... ma l'idea di ordinare le regioni per la funzione contenibile() non so se va bene. ...

ciao, vi dico a che conclusioni sono arrivato, dunque per il problema di D1 dentro D2 si potrebbe utilizzare delle code di min/max priorità, poi per gli scambi si può trovare un algoritmo di scambio.
Per la sequenza massima si utilizza la relazione d'ordine non completamente ordinata, si crea un tabella di adiacenze e si trova l'albero ricoprente massimo.
Per il terzo algorimo sono completamente al buio................
se non riesco entro un paio di giorni mollo ...... comunque per me il progetto è decisamente troppo complesso........

io abbandono.. se poi qualcuno riesce a farlo, dopo l'orale, metta il progetto grazie
lfn

__________________
an arrow from the sun

ma tanto per sapere...tra di noi c'e' qualcuno che ha trovato una soluzione per la ricerca dell'energia massima nella sequenza?

io mi sto' scervellando ma...forse e' da applicare a qualche struttura dati e tutto e' piu' semplice!

__________________
"basta un paio de scarpe nove, e poi gira' tutto er munno"
>> www.javalab.it - www.jobcrawler.it - www.aboutdebian.com/install3.htm<<
Linux user #354593

sto impazzendo per cercare un modo di calcolare
l' energia di un ampli! Qualche idea?

per l'energia dell'amplificatore bisogna usare la programmazione dinamica.
partite dallo pseudo-codice del knapsack 0-1 con le seguenti analogie : valore dell'oggetto->energia, peso->intervallo temporale e poi dovete introdurre una modifica in modo che gli oggetti vengano "presi" solo se la somma del loro T(D) e dei T(D) dei dispositivi che fino a quel momento formavano la sequenza ottima sia minore dell'U(T) di quel dispositivo.

In questa analogia col knapsack il vostro "peso massimo" dello zaino sara' la massima U(D) dei dispositivi della sequenza che state prendendo in considerazione.

buona lavoro

Ciao,
ho analizzato knapsack e non so se va bene. Questo algoritmo è ottimale se considera le frazioni, altrimenti è comunuqe vincolato fino alla sequenza meno l'ultimo analizzato. Per esempio la prima seq dell'amp è a -> b -> c -> d e deve risultare la seq c -> d -> a -> b per il massimo valore, quindi occorre tenere conto di n sequenze possibili.

Che casino questa energia!

Inoltre dovrei usare una matrice enorme per conservare i valori dell'energia e degli indici dei dispositivi inclusi nella sequenza.
Se ho capito male e qualcuno l'ha implementato con successo si faccia vivo a rincuorarmi! Grazie

mi faccio vivo

Il knapsack binario è effettivamente una buona soluzione, in quanto o prendi tutto "l'oggetto" oppure non lo prendi. Inoltre non c'è bisogno di implementare alcuna matrice dei risultati, basta memorizzare i risultati parziali in una variabile temporanea ed incrementarla quando necessario (cioè quando il risultato dell'elaborazione è > della var temporanea).

__________________
Computer Science: solving today's problems tomorrow.

consegnato...speriamo vada bene
per curiostia' vorrei sapere chi ha consegnato d'altro...

noi siamo in 2 (io e un altro amico)...poi?

__________________
"basta un paio de scarpe nove, e poi gira' tutto er munno"
>> www.javalab.it - www.jobcrawler.it - www.aboutdebian.com/install3.htm<<
Linux user #354593

io ho consegnato...

che delusione....

ciao ragazzi..innanzi tutto complimenti a chi ha consegnato.
io ho passato tutti i giorni davanti al pc, la soluzione sembrava essere vicinissima e invece c'erano dei bug che non capivo.
io alla fine hio utilizzato una lista con nodi che contenevano puntatori ad array (per le regioni).alla fine ho trovato che se questi dispositivi (nodi della lista) erano ordinati in senso crescente era un giochino vedere le sequenze, basta partire dal più grande e vedere quel'è il prossimo nodo più grande che contiene...e così via. visto così era semplice ma non riusci vo ad ordinare la lista!!!!!!!

al prossimo appello!!

e in bocca al lupo a chi a consegnato!!

Ciao a tutti,
io ho consegnato e secondo me tutto dipende dalle strutture che si sono utilizzate. Io per esempio non ho usato nemmeno una lista!
Per quanto riguarda la funzione contenibile, rimango dell'idea che non va bene ordinare le due sequenze, perchè poi come si fa a scrivere la prima dopo le dovute rotazioni? Io ho implementato una funzione rotazione che di volta in volta ruota il primo dispositivo e controlla che sia contenibile nel secondo; se così fosse, mi stampa la prima regione dopo le n rotazioni.
Per quanto riguarda il calcolo dell'energia, secondo me più che il knapsack andava visto un qualcosa come il PD-SingleMachine che ordina job con costo, tempo di esecuzione e tempo di deadline. Ovviamente lo si semplifica e, dopo aver ordinato ogni sequenza in base a E/T e a U, si sfrutta il fatto che ogni volta la somma dei T sia minore all'ultimo U.
Secondo me è stato un progetto interessante, ma forse uno dei più difficili in assoluto!

anche io ho consegnato... speriamo!
Avevo fatto anche il progetto precedente, non consegnandolo perchè l'ultimo giorno mi è andato in segfault (e gdb era molto utile in tal senso: mi dava un "?"), questo è decisamente più difficile per quanto riguarda le funzioni da implementare anche se l'altro richiedeva un pò di più attenzione alla struttura dati.

__________________
Computer Science: solving today's problems tomorrow.

Originally posted by WebSpid
...Per quanto riguarda la funzione contenibile, rimango dell'idea che non va bene ordinare le due sequenze, perchè poi come si fa a scrivere la prima dopo le dovute rotazioni? ...Per quanto riguarda il calcolo dell'energia, secondo me più che il knapsack...

sono usciti i calendari degli orali...

26 GIUGNO ore 10 nello studio (P 105) del Prof. Torelli

Doni Marco
Ranzani Paolo


30 GIUGNO ore 14.30 nello studio (P 105) del Prof. Torelli

Musumeci Corrado
Rocchietti Luca
Schito Elia


solo 5 persone? è stata una strage o lo hanno provato in pochi?
in bocca al lupo per l'orale a tutti i candidati.

Ciao Kivan, ma dove hai reperito queste informazioni? Come faccio a sapere se ho passato il progetto e in che turno di orale sono? Grazie

Originally posted by WebSpid
Ciao Kivan, ma dove hai reperito queste informazioni? Come faccio a sapere se ho passato il progetto e in che turno di orale sono? Grazie

__________________
There are two ways of constructing a software design:
one way is to make it so simple that there are obviously no deficiencies;
the other way is to make it so complicated that there are no obvious deficiencies.
(C.A.R. Hoare)

Ciao punto zip, io non sono con Torelli, quindi per me l'orale è il 29. Ma mi chiedevo se è possibile sapere prima dell'orale se si è passato il progetto. Grazie

a me lo ha comunicato il prof. Fiorentini via mail.
con Torelli se sei nel calendario significa che il progetto è accettato, non so con Aguzzoli se è lo stesso...

ciao

no, le scorse volte ha messo un avviso sul sito. Direi che è il caso di aspettare ancora tutto oggi, e poi mandargli una mail...

__________________
Computer Science: solving today's problems tomorrow.

in bocca al lupo per l'orale a tutti i candidati.

__________________
"basta un paio de scarpe nove, e poi gira' tutto er munno"
>> www.javalab.it - www.jobcrawler.it - www.aboutdebian.com/install3.htm<<
Linux user #354593

Ancora niente con Aguzzoli

Originally posted by WebSpid
Ancora niente con Aguzzoli

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

ciao a tutti,
oggi ho sostenuto l'orale con Torelli e direi che è andato benino.. ho preso 30

Le domande che mi ha fatto:

-descrivere l'algoritmo quicksort, soffermandosi sulla procedura e la richiesta in termini di tempo, spazio e in particolare di memoria stack sulla ricorsione.
-tabelle hash e nello specifico descrivere il funzionamento dell'hash doppio con tempi di esecuzione
-analisi ammortizzata e nello specifico la tecnica degli accantonamenti nell'esempio delle tabelle dinamiche

in bocca al lupo ai tre ragazzi che sosterranno l'orale il 30

KiVan sei un maledetto lamerrrrrrrr!!!

cmq gg!

__________________
SEPHIROT
mi piacciono i bluvelvet menosi - http://www.menschenfreundlicher.ch/ - "secondo me basta copiarlo in notepad"

kivan .always:lamer. altro che .always:banned.

complimentoni

ciao,
volevo sapere se Torelli chiede il pseudo codice e i teoremi con le dimostrazioni
Grazie

lo pseudo codice e le dimostrazioni matematiche non le chiede...

a Torelli interessa davvero soltanto che una persona abbia capito gli argomenti, e insiste magari nei punti dove lo studente è stato più vago e impreciso per capire se la conoscienza di quella parte è solida o meno.

cmq è importante che tu sappia i costi in termini di tempo e spazio dei vari algoritmi e procedure nei casi peggiore, medio e migliore spiegando anche il perchè del costo (quindi se un algoritmo richiede n log n spiegare cosa contribuisce come n e cosa come log n)

le domande di solito sono tre : una su un algoritmo di ordinamento (insertion sort - mergesort - heapsort - quicksort - counting sort..) una su una struttura dati (tabelle hash, alberi di ricerca, alberi rb, b-alberi ..) e poi una domanda sugli argomenti rimasti (analisi ammortizzata, programmazione dinamica, algoritmi greedy)

Un consiglio, se non sapete rispondere alla domanda cercate di ragionare in base a cio' che vi dice il professore, alla fine è molto buono e non pretende che si sappia tutto a memoria... gli basta anche un ragionamento fatto bene per capire se avete capito

Ciao Kivan, quanto dura + o - l'orale? Il voto lo registri poi subito? E' una media di scritto, progetto e orale?

con Torelli l'orale dura circa 30-40 minuti, poi conta un altro quarto d'ora con Fiorentini a cui devi spiegare le strutture e gli algoritmi ... il voto poi è una media tra orale e progetto.

da quello che ho letto pero' tu sei con l'altro professore quindi non so darti informazioni sul suo esame e le sue votazioni..

ciao

Ma a Fiorentini devi spiegare strutture e algoritmi usati nel progetto o in generale? Io non ho ben capito se l'orale è fondamentalmente sul progetto o sulla teoria in generale. Secondo te cosa conviene ripassare di teoria per l'orale e cosa invece è da ripassare inerente al progetto?
Grazie Kivan.

a fiorentini devi parlare esclusivamente del tuo progetto e delle scelte che hai fatto.
con torelli invece parli solo della teoria in generale e non parli del progetto.

per l'orale devi ripassare tutto quello che ha spiegato (che ho messo in un paio di post sopra) per l'orale del progetto non devi ripassare nulla... solo sapere quello che hai fatto...

Qualcuno sa dirmi se Fiorentini chiede la complessità (caso medio/migliore/peggiore) degli algoritmi?

__________________
baibai,
e!ia.
--Essere superstiziosi porta male--

in quelli che hai usato nel progetto si, avresti dovuto scriverli proprio nella relazione al progetto...

andata: 25!

orale schifosissimo...ma del resto non ho mai avuto fortuna negli esami :-)

- Quicksort
- B-alberi
- Programmazione Dinamica

metto in tasca e bom....studiero' le cose che mi serviranno piu' avanti!

le altre domande (che ho sentito...me ne sono perse un paio che ero a discutere il progetto) invece sono state
-Heap, MergeSort
-Hash
-Algoritmi greedy (codice di huffman), Matroidi.

in bocca al lupo per il prossimo a tutti

__________________
"basta un paio de scarpe nove, e poi gira' tutto er munno"
>> www.javalab.it - www.jobcrawler.it - www.aboutdebian.com/install3.htm<<
Linux user #354593