.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Algoritmi] Progetto "RICHIAMI" (http://www.dsy.it/forum/showthread.php?threadid=17192)
Posted by Skilotto83 on 22-02-2005 16:38:
Originally posted by LjL
Sì, ma c'è da dire che o sono molto tonto io oppure riuscire a fare il calcolo *senza* una ricerca esaustiva non è proprio così facile! Adesso ci sono riuscito anch'io, ma ci ho messo veramente un bel po', e comunque la complessità in spazio e in tempo è O(n²), e sono sicuro che volendo si può diminuire... tu fai meglio di così? (tra l'altro O(n²) è per ogni automa; se devi far spostare tutti gli automi, O(n³))
devo ankora prendere confidenza con i tempi di esecuzione...
Kmq posso dire che il tempo per il calcolo di percorso e tortuosita' e relazionato solo an numero degli ostacoli sul piano...e non sul numero delle celle...il che è ottimo..
In particolare per il calcolo del percorso libero direi che il numero massimo di tentativi è pari a n ostacoli per 2(la x e la y) su cui si puo' sbattere...
La tortuosita' invece nn so di preciso...mi ha lasciato un po' di stucco il fatto che su percorsi molto complessi arrivo un percorso libero in x tentativi e per calolare invece la tortuosita' ci metto magari 10 volte di piu'...solo per riparmiare un "angolo" quindi per dim inuire di 1 la tortuosita' rispetto a quella del primo percorso libero trovato...__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)
MSN andrea.poretti(at)hotmail.it
Posted by LjL on 22-02-2005 16:57:
Originally posted by Skilotto83
devo ankora prendere confidenza con i tempi di esecuzione...
Non è una cosa particolarmente difficile, se non per la confusione tra O, o, @, W, w e compagnia...
Kmq posso dire che il tempo per il calcolo di percorso e tortuosita' e relazionato solo an numero degli ostacoli sul piano...e non sul numero delle celle...il che è ottimo..
Questo significa che la tua 'n' è il numero di ostacoli presenti e non il numero delle celle coinvolte. E, sì, questa sicuramente è una buona cosa.
(Per la verità, nel caso peggiore il numero degli ostacoli potrebbe essere uguale al numero delle celle, e in quel caso il tuo algoritmo si comporterebbe come un algoritmo dipendente dal numero delle celle. Ma questo è il caso peggiore...)
In particolare per il calcolo del percorso libero direi che il numero massimo di tentativi è pari a n ostacoli per 2(la x e la y) su cui si puo' sbattere...
Sarebbe a dire O(n). Il 2 va via perché è una costante -- è inutile indicarlo, perché di costanti ce ne possono essere tante che in generale tu non puoi conoscere (ad esempio la velocità del tuo processore).
La tortuosita' invece nn so di preciso...mi ha lasciato un po' di stucco il fatto che su percorsi molto complessi arrivo un percorso libero in x tentativi e per calolare invece la tortuosita' ci metto magari 10 volte di piu'...
Questo dipende ovviamente da che algoritmo hai usato. Se hai usato un algoritmo ricorsivo senza troppi fronzoli, può anche darsi che il calcolo della tortuosità sia esponenziale (anche se per la verità non ho controllato se sia davvero probabile inventarsi un algoritmo esponenziale).
Nel caso del mio algoritmo, c'è una sola funzione per calcolare la tortuosità *e* controllare l'esistenza di un percorso, e quindi entrambe le operazioni sono O(n²).
O(n²) significa, in soldoni, che per ogni ostacolo vado a controllare tutti gli altri ostacoli: n*n=n².
Quando in C vedi una cosa del genere:
for(i=0; i<n; i++) {
...for(j=0; j<n; j++) {
......EseguiOperazione(i, j);
...}
}
è probabile che l'algoritmo che stai vedendo sia O(n²) (cioè che si esegua in tempo proporzionale a n² nel caso peggiore) o che sia @(n²) (cioè che si esegua in quel tempo in tutti i casi).
Se dentro ai for() si sono dei 'break' è più probabile che sia O(n²), se non ce ne sono è più probabile @(n²).
solo per riparmiare un "angolo" quindi per dim inuire di 1 la tortuosita' rispetto a quella del primo percorso libero trovato...
Non ho ancora capito fino a che complessità si possa riuscire a portare il calcolo della tortuosità. Sicuramente può scendere sotto il mio O(n²).
Se il tuo algoritmo è di complessità superiore a O(n²), probabilmente potrebbe aiutarti un po' di programmazione dinamica.
Se è già O(n²), boh 
ho idea che la tecnica della "memoization" possa essere una soluzione (= programmazione dinamica + consideri solo i sottoproblemi interessanti).__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by mattcobain on 22-02-2005 18:59:
Originally posted by LjL
...interrompi pure, tanto il risultato non avrebbe nessun significato.
cosa che ho fatto....anche perché ormai era passato piu di un quarto d'ora e risultati zero..... 
insomma....posso benissimo smentire le cazzate dette quando pensavo di aver fatto un algoritmo supersonico 
Posted by Skilotto83 on 22-02-2005 19:03:
anke io usavo una sola funzione per il calcolo del percorso libero e della tortuosita'...
Ma poi ho pensato ke fosse inutile...
Quindi ho lasciato la vecchia funzione che fa la tortuosita' minima...
E ho fatto un'altra funzione molto piu' "lesta" che si ferma al primo percorso trovato...nn credi sia inutile che anche per il calcolo del percorso libero vada avanti finkè tra tutti i percorsi liberi nn ha trovato il meno tortuoso??
E' vero ke il mio algoritmo gia' smette di calcolare il percorso con tortuosita' minima quando si accorge di averne trovato uno piu' breve prima...nel senso che se il minimo è stato 3..se mentre cerca il percorso arriva a 3 lo scarta direttamente senza terminarlol...
Boh...
Kmq grazie per la lezioncina...mi è servita molto....
__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)
MSN andrea.poretti(at)hotmail.it
Posted by LjL on 22-02-2005 20:05:
Originally posted by Skilotto83
[snip]
E ho fatto un'altra funzione molto piu' "lesta" che si ferma al primo percorso trovato...nn credi sia inutile che anche per il calcolo del percorso libero vada avanti finkè tra tutti i percorsi liberi nn ha trovato il meno tortuoso??
Sì, è inutile. Ma siccome la mia funzione *non va* a cercare percorsi liberi (proprio nel senso che non ha neanche un concetto di "percorso"), nel mio caso non è detto che la tua obiezione sia valida.
E' vero ke il mio algoritmo gia' smette di calcolare il percorso con tortuosita' minima quando si accorge di averne trovato uno piu' breve prima...nel senso che se il minimo è stato 3..se mentre cerca il percorso arriva a 3 lo scarta direttamente senza terminarlol...
Ottimo... anche a me piacerebbe riuscire a fare questo (cercare prima percorsi con tortuosità 1, e solo se ne ce ne sono cercarne con tortuosità 2, ecc.), ma per ora non ce l'ho fatta.
Io però, come ho già detto, non calcolo "percorsi" e quindi la cosa sarebbe un po' complicata da fare, anche se un'idea di come potrei farlo ce l'ho.
Se al contrario del mio il tuo algoritmo "calcola percorsi" (ed è, suppongo, ricorsivo), probabilmente per te è più difficile evitare di riesaminare lo stesso sottoproblema più di una volta, cosa che io evito, ma d'altra parte è più facile evitare di esaminare sottoproblemi inutili, cosa che io non evito.
Penso che, volendo strafare, la soluzione più utile sia per me sia per te sia quella della memoization. In pratica consiste nell'usare un algoritmo ricorsivo, ma tenendosi una tabella dove ci si segnano le soluzioni ai sottoproblemi già visti.
Se hai un po' di tempo ti consiglio di pensarci su un pochino: se il tuo algoritmo è già più che dignitoso, cosa che mi sembra che sia, IMHO lo potresti veramente rendere ottimo o quasi ottimo.
["Ottimo" nel senso di "il migliore possibile", ovviamente]__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by Skilotto83 on 22-02-2005 21:10:
Originally posted by LjL
Sì, è inutile. Ma siccome la mia funzione *non va* a cercare percorsi liberi (proprio nel senso che non ha neanche un concetto di "percorso"), nel mio caso non è detto che la tua obiezione sia valida.
Ottimo... anche a me piacerebbe riuscire a fare questo (cercare prima percorsi con tortuosità 1, e solo se ne ce ne sono cercarne con tortuosità 2, ecc.), ma per ora non ce l'ho fatta.
Io però, come ho già detto, non calcolo "percorsi" e quindi la cosa sarebbe un po' complicata da fare, anche se un'idea di come potrei farlo ce l'ho.
Se al contrario del mio il tuo algoritmo "calcola percorsi" (ed è, suppongo, ricorsivo), probabilmente per te è più difficile evitare di riesaminare lo stesso sottoproblema più di una volta, cosa che io evito, ma d'altra parte è più facile evitare di esaminare sottoproblemi inutili, cosa che io non evito.
Penso che, volendo strafare, la soluzione più utile sia per me sia per te sia quella della memoization. In pratica consiste nell'usare un algoritmo ricorsivo, ma tenendosi una tabella dove ci si segnano le soluzioni ai sottoproblemi già visti.
Se hai un po' di tempo ti consiglio di pensarci su un pochino: se il tuo algoritmo è già più che dignitoso, cosa che mi sembra che sia, IMHO lo potresti veramente rendere ottimo o quasi ottimo.
["Ottimo" nel senso di "il migliore possibile", ovviamente]
Purtroppo non ho molto tempo..quindi non saprei...
Piuttosto se posso chiederti una cosa....
Per gli automi come sai uso un array...
La fase di inserimento è fatta utilizzando la strcmp...
Ho pensato che i casi che ho si equivalgono....
Se inserisco in prima posizione ho risparmiato confronti della strcmp, ma ho bisogno di shiftare tutto l'array...
Se invece inserisco in ultima pos nn shifto nulla ma ho dovuto fare tutti i confronti con la strcmp...
Quindi il tempo è n/2 nel caso medio...no??
E la ricerca??
è lineare per forza...quindi n?
In quanto devo confrontare ogni posizione con strcmp fino al nome richiesto...no??__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)
MSN andrea.poretti(at)hotmail.it
Posted by LjL on 22-02-2005 21:37:
Originally posted by Skilotto83
Piuttosto se posso chiederti una cosa....
Come al solito mi sono un attimo dilungato (anche perché ci ragionavo mentre scrivevo...).
Se vuoi saltarti tutta la menata e leggere la conclusione, cerca ***.
Per gli automi come sai uso un array...
La fase di inserimento è fatta utilizzando la strcmp...
Ho pensato che i casi che ho si equivalgono....
Se inserisco in prima posizione ho risparmiato confronti della strcmp, ma ho bisogno di shiftare tutto l'array...
Se invece inserisco in ultima pos nn shifto nulla ma ho dovuto fare tutti i confronti con la strcmp...
Mi sa che qui ti sei espresso male da qualche parte.
In un array non si inserisce *mai* in prima posizione (o quantomeno non mi viene in mente neanche un caso plausibile).
Inserire in prima posizione ha costo O(n).
O si inserisce in ultima posizione (O(1)) o si inserisce nella posizione giusta, cioè tenendo gli elementi in ordine (O(n)).
Quindi non capisco cosa fai e che cosa invece pensi potrebbe essere meglio fare.
I casi che vedo io sono questi due:
- o inserisci in coda all'array (cioè alla fine), così l'inserimento ti costa poco, ma poi la ricerca ti costa O(n) dato che devi cercare linearmente tra n elementi,
- o inserisci nel punto giusto, così poi quando hai bisogno di ritrovare un elemento puoi fare una ricerca binaria (o dicotomica o come la vuoi chiamare), che se non ricordo male dovrebbe costarti solo O(lg(n)).
In pratica puoi:
- inserire ogni automa in tempo O(1) e cercare in tempo O(n)
- inserire in tempo O(n) e cercare in tempo O(lg(n))
Tieni conto che i tempi per l'inserimento si riferiscono a un *singolo* inserimento.
Se alla fine hai n elementi, significa ovviamente che hai inserito n elementi... quindi il costo *totale* degli inserimenti è O(n) nel primo caso e O(n²) nel secondo.
Anche i tempo per la ricerca si riferiscono ad una singola ricerca. Ma se tu sai che avendo n automi avrai sicuramente fatto n inserimenti, non puoi sapere a priori quante ricerche farai basandoti solo sul numero degli automi.
Supponi però di fare n ricerche, tanto per fare una supposizione: allora i due casi, in totale, diventeranno
- inserimento in O(n) e ricerca in O(n²)
- inserimento in O(n²) e ricerca in O(n*lg(n)).
In entrambi i casi il tempo totale è O(n²), ma nel secondo c'è un logaritmo che nel primo non compare.
*** Quindi, se il mio ragionamento è corretto, asintoticamente quello che fai è indifferente, ma su numeri piccoli tende ad essere migliore la prima scelta -- cioè, inserisci in coda all'array e poi fai una ricerca lineare.
Quindi il tempo è n/2 nel caso medio...no??
O(n). È vero, nel caso medio tenderai a fare n/2 operazioni, ma 1/2 è una costante e quindi scompare dalla notazione asintotica O().
E la ricerca??
è lineare per forza...quindi n?
In quanto devo confrontare ogni posizione con strcmp fino al nome richiesto...no??
Solo se l'array non lo tieni ordinato. Se è ordinato puoi fare una ricerca binaria, che è meno che lineare, ma l'analisi - anche se piuttosto campata per aria - che ho fatto sopra sembra suggerire che non ne vale la pena.__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by Skilotto83 on 22-02-2005 21:53:
non ci siamo capiti...
io l'array lo tengo sempre ordinato...
Pero' vista questa situaziuone...
potrebbe essere che per inserire trovo subito la posizione corrette...e allora ci ho messo poco per inserire, perchè ho fatto pochio confronti con strcmp per trovare il punto corretto di inserimento...pero' devo far shiftare tutte le altre posizioni successive per far posto al nuovo automa...
Potrebbe essere invece che la posizione giusta per il nuovo automa è l'ultima...allora ho fatto tutti i confronti con strcmp ma nn devo shifare nulla...
Kapito??
La ricerca è un altro discorso...
Sparisce la questione dello shift...
E imane solo che per cercare nell'array ordinato devo kmq scorrere con tante strcmp fino alla posizione esatta...
Quindi come dovrebbero essere i tempi??
Kmq se permetti tu ne sai di brutto...
__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)
MSN andrea.poretti(at)hotmail.it
Posted by Skilotto83 on 22-02-2005 21:56:
e kmq la ricerca dicotomica nn ho fatto in tempo a implementarla...
e poi...
Quando ti ho detto del numero di tentativi per il percorso libero che era 2volte il numero di ostaoli mi hai detto che quindi è O(n)...si puo' considerare il tempo di esecuzione della funzione trovapercorsolibero??
Perkè nn mi sembra che sia un analisi corretta...il numero di tentativi nn fa il tempo di esecuzione...giusto??
__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)
MSN andrea.poretti(at)hotmail.it
Posted by LjL on 23-02-2005 00:39:
Originally posted by Skilotto83
non ci siamo capiti...
io l'array lo tengo sempre ordinato...
Ah, ok. Però ho l'impressione che se poi non usi un binary search per la ricerca, tenerlo ordinato sia una cattiva idea. Comunque di questo ne parlo nella risposta all'altro messaggio.
Pero' vista questa situaziuone...
potrebbe essere che per inserire trovo subito la posizione corrette...e allora ci ho messo poco per inserire, perchè ho fatto pochio confronti con strcmp per trovare il punto corretto di inserimento...pero' devo far shiftare tutte le altre posizioni successive per far posto al nuovo automa...
Potrebbe essere invece che la posizione giusta per il nuovo automa è l'ultima...allora ho fatto tutti i confronti con strcmp ma nn devo shifare nulla...
Kapito??
Più o meno hai ragione - *se* fai finta che strcmp() impieghi sempre lo stesso tempo, hai una complessità @(n) sia se inserisci all'inizio sia se inserisci alla fine.
Però strcmp() impiega un tempo dipendente dalla lunghezza delle stringhe da comparare; in particolare strcmp() è O(n).
Supponi che *tutti* gli automi abbiano nomi di 1000 cifre: è facile rendersi conto che in questo caso costa molto meno inserire all'inizio che alla fine.
Comunque, anch'io nella risposta che ti avevo dato avevo fatto finta che la lunghezza delle stringhe fosse insignificante.
Il fatto che, almeno in teoria, può non essere insignificante è proprio il motivo per cui io ho usato un albero.
La ricerca è un altro discorso...
Sparisce la questione dello shift...
E imane solo che per cercare nell'array ordinato devo kmq scorrere con tante strcmp fino alla posizione esatta...
Quindi come dovrebbero essere i tempi??
O(n). Nel caso peggiore dovrai scorrere fino alla fine, e nel caso medio dovrai comunque scorrerere n/2 posizioni.
Con una ricerca binaria puoi ridurre questo tempo a O(lg(n)) (sempre se mi ricordo giusto), che è un gran bel miglioramento.
Kmq se permetti tu ne sai di brutto...
Ahah, insomma... diciamo che quando si scende un po' troppo nella matematica a me vien voglia di scappar via, però se non fosse per la matematica queste cose mi interessano... e poi Torelli ha un modo talmente assurdo di spiegare che seguirlo è quasi divertente 
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by LjL on 23-02-2005 00:53:
Originally posted by Skilotto83
[B]e kmq la ricerca dicotomica nn ho fatto in tempo a implementarla...
In questo caso mi sa che puoi anche fare a meno di tenere l'array ordinato.
Se lo tieni ordinato, appena trovi un automa col prefisso giusto, sai già che gli altri che hanno lo stesso prefisso si trovano tutti immediatamente dopo quello.
Questo è vero, ma non fa cambiare molto le cose: il tempo per la ricerca è O(n), e sarebbe O(n) anche se gli automi non li tenessi ordinati.
Non tenendoli ordinati, in compenso, passaresti da un tempo O(n) per ogni inserimento a un tempo O(1), che sicuramente una brutta cosa non è.
Quindi, secondo me, è il caso che o implementi la ricerca binaria oppure fai a meno di tenere gli automi ordinati.
Oppure scrivi nella relazione "tengo gli automi ordinati per permettere una ricerca binaria, anche se non ho fatto in tempo a implementarla" Non so se il prof. apprezzi; io apprezzerei, dato che fa capire almeno che sei conscio della cosa.
e poi...
Quando ti ho detto del numero di tentativi per il percorso libero che era 2volte il numero di ostaoli mi hai detto che quindi è O(n)...si puo' considerare il tempo di esecuzione della funzione trovapercorsolibero??
Perkè nn mi sembra che sia un analisi corretta...il numero di tentativi nn fa il tempo di esecuzione...giusto??
Boh. Dipende da che cos'è un "tentativo", cosa che penso tu non mi possa spiegare dettagliatamente prima che sia finito il tempo per il progetto.
Se un "tentativo" è una cosa che impiega un tempo costante (= ci metti sempre lo stesso tempo a fare *un* tentativo), allora se fai n tentativi (o 2*n, o 3*n, o 1000*n) la tua funzione è O(n) o @(n).
Altrimenti, la complessità della tua funzione dipende dalla complessità dell'operazione "fai-un-tentativo".
Esercizio: qual è la complessità di questa funzione?
void PerdiTempo(int n) {
...int i, j;
...if(n>256) printf("Piu' di 256\n");
...else printf("Meno di 257\n");
...for(i=0; i<n; i++) {
......for(j=0; j<n; j++) {
.........printf("Perdo un po' di tempo...\n");
......}
...}
...for(i=0; i<n; i++) {
......printf("Ne perdo ancora un po'...\n");
...}
}__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by elpampero on 24-02-2005 08:06:
Scusate, ma il prof risponde sia che il progetto vada bene sia che vada male?
Posted by mark on 24-02-2005 08:28:
Originally posted by elpampero
Scusate, ma il prof risponde sia che il progetto vada bene sia che vada male?
dovrebbe, altrimenti non puoi fare l'orale__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....
Posted by elpampero on 24-02-2005 08:30:
Molto bene...Aspetto un paio di giorni e poi lo contatto
Posted by mattcobain on 24-02-2005 08:36:
Originally posted by elpampero
Scusate, ma il prof risponde sia che il progetto vada bene sia che vada male?
ma perché, manda una mail di risposta!?
non basta il calendario degli orali per capire se devi farlo o meno?
e la risposta, se la manda, entro quanti giorni!? io il progetto l'ho inviato il 22....
