.dsy:it. Pages (4): « 1 2 [3] 4 »
Show 150 posts per page

.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 Teju on 21-02-2005 22:45:

Originally posted by p2p
e secondo te si legge il codice di tutti?
io allo scorso progetto avevo fatto un paio di errori correggibili con l' aggiunta di 1 riga di codice,era uno sbaglio su un controllo di stringhe ... beh, me l ha rifiutato!se l' avesse letto probabilmente si sarebbe accorto che l' output era errato per una banalita', non credi?

Sottoscrivo: non legge il codice ne' la relazione... :D
Sul codice mi spiace, xkè l'avevo messo tuto bene, sulla relazione un po' meno xkè l'avevo scritta proprio alla cane!! :D :D

__________________
Teju.it - Una vita da raccontare

Posted by LjL on 21-02-2005 23:27:

Originally posted by Skilotto83
Il problema era quello...
solo ke è un kaso limite..siete sikuri ke va konsiderato spostamento...??
Non è il kaso si mandare una mail al prof??
io il progetto lo faccio con aguzzoli e nn con fiorentini...il mio progetto nn dice nulla a riguardo...


Sicuro sicuro sicuro non lo posso essere, però per quanto mi riguarda un caso limite è un caso valido a meno che non venga detto esplicitamente il contrario...
Se vogliamo parlare di casi limite, io considero anche gli ostacoli che degenerano in rette o punti come validi.

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by LjL on 21-02-2005 23:29:

Originally posted by Teju
Sottoscrivo: non legge il codice ne' la relazione... :D
Sul codice mi spiace, xkè l'avevo messo tuto bene, sulla relazione un po' meno xkè l'avevo scritta proprio alla cane!! :D :D


Ma comunque non c'è la famosa "discussione del progetto"? Il che dovrebbe significare che almeno durante quella una sbirciatina al codice e/o alla relazione dovrà pur darla...?

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by mattcobain on 22-02-2005 08:41:

Originally posted by LjL
Sicuro sicuro sicuro non lo posso essere, però per quanto mi riguarda un caso limite è un caso valido a meno che non venga detto esplicitamente il contrario...
Se vogliamo parlare di casi limite, io considero anche gli ostacoli che degenerano in rette o punti come validi.


idem...anchio considero tutti i casi limite, compresi ostacoli che possono essere rette oppure punti....dopotutto dalla descrizione matematica che ha dato di ostacoli, anche questi casi ne rientrano e quindi non li considererei nemmeno caso limite, ma casi da trattare....
per il segnale che può trovarsi in un punto già occupato da un automa, anche questo non mi sembra un caso limite...infatti sul testo si dice esplicitamente che il segnale non può trovarsi all'interno o sul bordo di un ostacolo (altrimenti non sarebbe raggiungibile da nessun automa) e non si dice nient'altro....quindi dato che automi possono trovarsi sullo stesso punto, penso proprio che anche un segnale possa trovarsi nella posizione già occupata da un ostacolo....
cmq ormai ho stampato il codice, 14 pagine, non ho alcuna voglia di contattare il prof e chiedergli conferma....ho fatto così e amen! :D non mi sembra affatto un errore, piuttosto un controllo in piu!

Posted by virtual on 22-02-2005 08:51:

Quanto impiega il vostro programma ad eseguire tutto l'input delle specifiche?

Il mio 37 secondi su PIII 1GHz.

Posted by Teju on 22-02-2005 09:04:

Originally posted by LjL
Ma comunque non c'è la famosa "discussione del progetto"? Il che dovrebbe significare che almeno durante quella una sbirciatina al codice e/o alla relazione dovrà pur darla...?

Il prof prende il vostro codice, lo compila, prova diversi input che si è precedentemente preparato, si assicura che il programmino funzioni con tutti, poi, all'orale, ti chiede come hai implementato certe funzioni e lì, insieme a te, magari da un occhio al codice...:shock:

__________________
Teju.it - Una vita da raccontare

Posted by Teju on 22-02-2005 09:07:

Originally posted by Teju
Il prof prende il vostro codice, lo compila, prova diversi input che si è precedentemente preparato, si assicura che il programmino funzioni con tutti, poi, all'orale, ti chiede come hai implementato certe funzioni e lì, insieme a te, magari da un occhio al codice...:shock:

Ecco, mi è venuto in mente: per darvi la certezza di quanto detto! L'appello scorso un mio amico che aveva implementato un metodo di collisioni automi-blocchi molto bello, è riuscito a prendere decisamente meno di un altro che faceva un for con il controllo su ogni spostamento di uno di un automa rispetto a una lista dove si trovavano gli ostacoli, ovvero x ogni spostamento di n, faceva n controlli di collisione contro l'1 del mio compagno...
L'altro è riuscito a intortarsi meglio il prof e ha preso decisamente di più....

__________________
Teju.it - Una vita da raccontare

Posted by Skilotto83 on 22-02-2005 09:14:

Allora modifiko anke io il codice considerando buona la situazione di automa sul punto di segnale...
Per i tempi di esecuzione.....

Virtual...
Kome fai a calcolare il tempo?
Dopo ke hai battuto il komando fai partire il cronometro???
Ma siamo proprio sikuri ke l'out deve essere kome ho gia' kiesto, e quindi bisogna andarselo a guardare tra i vari komandi dati???
Non è ke voleva memorizzassimo l'out per poi darlo tutto insieme con il comando 'f'??
Kmq...io ho fatto un programmino di input in VisualBasic...gli passo il file da linea di comando....
il mio è istantaneo in tutte le operazioni....anche con i famosi input da -10000 etc etc...quindi direi che il tempo è quello del programmino per inserire input...nn attendo mai il risultato di un calcolo...sara' ke l'algoritmo per il calcolo del percorso e tortuosita' è una bomba...:D
Certo che ci pensavo ieri...chi ha risolto con ricerca esaustiva su una ricerca di percorso da (-10000,-5000) a (10000,5000) ci mette un botto....deve spararsi migliaia di celle...

Ma la relazione???
Kome la fate???
Mettete parti di codice?? Fate il calcolo preciso di tutte le procedure? Oppure una cosa alla buona??

__________________
"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 Teju on 22-02-2005 09:19:

Originally posted by Skilotto83
Allora modifiko anke io il codice considerando buona la situazione di automa sul punto di segnale...
Per i tempi di esecuzione.....

Occhi che cmq sia ANSI-C! :-D Usa il Gcc come compilatore lui...

Originally posted by Skilotto83
Ma la relazione???
Kome la fate???
Mettete parti di codice?? Fate il calcolo preciso di tutte le procedure? Oppure una cosa alla buona??

Descrizione della struttura dati utilizzata, con motivazione "sensata", e brevissima descrizione di ogni procedura scritta.

__________________
Teju.it - Una vita da raccontare

Posted by elpampero on 22-02-2005 09:39:

io faccio così:
richiami<input.txt
e in output ho esattamente quello che devo avere...

Posted by Skilotto83 on 22-02-2005 09:48:

Originally posted by Teju
Occhi che cmq sia ANSI-C! :-D Usa il Gcc come compilatore lui...


Descrizione della struttura dati utilizzata, con motivazione "sensata", e brevissima descrizione di ogni procedura scritta.


infatti devo controllare...
io ho fatto tutto con visual studio...dovrebbe essere ok no??
e ho anche diviso il prog in 4moduli .c ...
main.c, automi.c ostacoli.c totuosita'.c....
e i 3 moduli automi.h, ostacoli.h tortuosita'.h...
dovrebbe andar bene...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 mark on 22-02-2005 10:09:

Originally posted by virtual
Quanto impiega il vostro programma ad eseguire tutto l'input delle specifiche?

Il mio 37 secondi su PIII 1GHz.



cosa impiega 37 secondi ?

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

Posted by p2p on 22-02-2005 10:50:

Virtual anche io ho un P3 1Ghz con 512 Mb di Ram ma mi impiega pochi secondi a far girare il tutto, l unico problema è l' istruzione
t 1000 2000 01 che mi manda probabilmente in loop la ricorsione... pero' spero di riuscire a correggerlo, il resto è ok

Posted by Skilotto83 on 22-02-2005 10:51:

raga..aiuto...
Ho scaricato gcc per compilare il mio progetto...
se uso il comando gcc -o etc etc...tutto bene...compila e funziona...
se invece uso gcc -ansi -o etc etc....succede un disastro...200 errori!!!!!!!!!
Ke kazzo è????
Deve compilare giusto con il comando -ansi???

__________________
"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 virtual on 22-02-2005 10:54:

Originally posted by Skilotto83
Virtual...
Kome fai a calcolare il tempo?


Con la libreria <time>

Posted by elpampero on 22-02-2005 11:25:

Skilotto controlla che i commenti siano /*XXX*/ e non //

Posted by p2p on 22-02-2005 11:35:

Originally posted by elpampero
Skilotto controlla che i commenti siano /*XXX*/ e non //


infatti con l opzione -ansi anche i commenti stile C++ vengono indicati come errore,inoltre alcune dichiarazioni di variabili interne a funzioni vengono segnalate.
Io ho compilato da subito con -Wall -ansi -pedantic per evitare questo genere di sorprese, cmq vedrai che sono stupidate,comincia dall' inizio con calma e non cambiare troppe cose in una volta sola,anzi fatti proprio un backup e lavora sulla copia...

Posted by Skilotto83 on 22-02-2005 12:10:

Originally posted by p2p
infatti con l opzione -ansi anche i commenti stile C++ vengono indicati come errore,inoltre alcune dichiarazioni di variabili interne a funzioni vengono segnalate.
Io ho compilato da subito con -Wall -ansi -pedantic per evitare questo genere di sorprese, cmq vedrai che sono stupidate,comincia dall' inizio con calma e non cambiare troppe cose in una volta sola,anzi fatti proprio un backup e lavora sulla copia...


infatti sono i commenti..si ma è assurdo...
kmq...cosa fa in piu' wall e pedantic??

__________________
"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 p2p on 22-02-2005 12:55:

Wall e pedantic danno un sacco di info utili che magari con una compilazione normale non verrebbero notati,tipo passaggi di parametri o altro che ti fanno risparmiare un sacco di errori

Posted by Petrik22 on 22-02-2005 13:39:

Question aiutooooooooooooooooooooooooo

scusate raga, ma come cazzo avete risolto il problema della gestione degli spostamenti degli automi in base al segnale?????
volgio dire, mi sono creato una lista con tutti gli automi e relative distanze dal segnale dato. Ora, come caxxo si fa a ordinare sta lista a seconda delle distanze per scegliere quelle minime???:?:?:?
secondo: come fate a evitare gli ostacoli???
:shock::shock::shock::shock::shock:
:wall: :pc:

__________________
lol

Posted by Skilotto83 on 22-02-2005 13:40:

ok...basta ke nn servano per rispettare delle specifiche...
Tutte le info su passaggiu di paramentri etc le ho funzionalissime con visual studio...
Ora compila e linka corretto con:
gcc -ansi -o Richiami Automi.c Obsts.c Percorso.c Main.c
Quindi sono a posto..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 p2p on 22-02-2005 13:41:

Originally posted by Skilotto83
ok...basta ke nn servano per rispettare delle specifiche...
Tutte le info su passaggiu di paramentri etc le ho funzionalissime con visual studio...
Ora compila e linka corretto con:
gcc -ansi -o Richiami Automi.c Obsts.c Percorso.c Main.c
Quindi sono a posto..giusto???


giusto. -ansi per rispettare le specifiche ansi basta.

Posted by p2p on 22-02-2005 13:46:

Re: aiutooooooooooooooooooooooooo

Originally posted by Petrik22
scusate raga, ma come cazzo avete risolto il problema della gestione degli spostamenti degli automi in base al segnale?????
volgio dire, mi sono creato una lista con tutti gli automi e relative distanze dal segnale dato. Ora, come caxxo si fa a ordinare sta lista a seconda delle distanze per scegliere quelle minime???:?:?:?
secondo: come fate a evitare gli ostacoli???
:shock::shock::shock::shock::shock:
:wall: :pc:

basta che scorri la lista e mentre la scorri memorizzi in una var int la distanza minore, tipo:
nodo *p;
int minimo;

for (p=testa_lista; p!=NUL; p=p->next)
if(minimo > p->distanza)
minimo = p->distanza;

alla fine avrai in minimo il valore minimo tra le varie distanze,e li ti bastera' aggiornare le coordinate degli automi,quindi riscorri la lista e poni
if(p->distanza == minimo)
aggiorna le coordinate;

ti consiglio di fare un po di prove con printf nel ciclo for e printf dell valore finale per renderti conto se stai facendo bene.

Posted by Petrik22 on 22-02-2005 13:49:

bene, capito.
pero per la questione degli ostacoli come la mettete?

__________________
lol

Posted by LjL on 22-02-2005 13:55:

Originally posted by Teju
Ecco, mi è venuto in mente: per darvi la certezza di quanto detto! L'appello scorso un mio amico che aveva implementato un metodo di collisioni automi-blocchi molto bello, è riuscito a prendere decisamente meno di un altro che faceva un for con il controllo su ogni spostamento di uno di un automa rispetto a una lista dove si trovavano gli ostacoli, ovvero x ogni spostamento di n, faceva n controlli di collisione contro l'1 del mio compagno...
L'altro è riuscito a intortarsi meglio il prof e ha preso decisamente di più....


Più che intortare, non è che (dubbio che mi stava giá venendo ieri) il prof prova il programma con un po' di input, come hai detto tu, e tutti questi input sono di dimensioni relativamente *piccole*?

Io ho cercato di fare in modo che il mio algoritmo fosse il più efficiente possibile *asintoticamente*, ma poi è chiaro che se gli dai in input tre valori in croce è meglio un programma scritto nel modo più banale possibil!

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by p2p on 22-02-2005 13:58:

Originally posted by LjL
Più che intortare, non è che (dubbio che mi stava giá venendo ieri) il prof prova il programma con un po' di input, come hai detto tu, e tutti questi input sono di dimensioni relativamente *piccole*?

Io ho cercato di fare in modo che il mio algoritmo fosse il più efficiente possibile *asintoticamente*, ma poi è chiaro che se gli dai in input tre valori in croce è meglio un programma scritto nel modo più banale possibil!

io non so se tu ambisci a un 30 ma ti assicuro che la cosa fondamentale è che funzioni e che dia l output corretto sui suoi esempi, vai a vederti qualche orale e poi dimmi tu...

Posted by LjL on 22-02-2005 13:58:

Originally posted by virtual
Con la libreria <time>


O semplicemente col comando "time" di Unix:

time ilmioprogramma <ilmioinput

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by LjL on 22-02-2005 14:03:

Originally posted by p2p
io non so se tu ambisci a un 30 ma ti assicuro che la cosa fondamentale è che funzioni e che dia l output corretto sui suoi esempi, vai a vederti qualche orale e poi dimmi tu...


Non è che ambisco al 30, però mi darebbe un po' fastidio l'idea di prendere *meno* punti con un programma più efficiente che con uno meno efficiente! :(
Certo che quello di andare a vedere qualche orale non è un cattivo consiglio... vedo grande saggezza in te ;)

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by LjL on 22-02-2005 14:05:

Originally posted by p2p
infatti con l opzione -ansi anche i commenti stile C++ vengono indicati come errore,inoltre alcune dichiarazioni di variabili interne a funzioni vengono segnalate.

[snip]


Notare però che i cosiddetti "commenti stile C++" sono previsti in C dallo standard C99. Non lo sono però dal C89, che per ora è ancora quello di riferimento per GCC.

Se vogliamo proprio cavillare, comunque, sul testo c'è scritto che il codice deve essere ANSI, non c'è scritto *quale* revisione dell'ANSI! :D

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by LjL on 22-02-2005 14:09:

Originally posted by virtual
Quanto impiega il vostro programma ad eseguire tutto l'input delle specifiche?

Il mio 37 secondi su PIII 1GHz.


Ehm... non per farti preoccupare ma mi sa che c'è qualcosa che potresti rivedere =)
Per quell'input il mio programma impiega circa un decimo di secondo, su un K6 a 350MHz.

Il mio programma comincia a non farcela più (gli manca RAM, ho 256Mb) quando si superano i 2000 automi o i 1000 ostacoli.

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by LjL on 22-02-2005 14:14:

Originally posted by Skilotto83
[snip]

Certo che ci pensavo ieri...chi ha risolto con ricerca esaustiva su una ricerca di percorso da (-10000,-5000) a (10000,5000) ci mette un botto....deve spararsi migliaia di celle...

[snip]


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³))

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by p2p on 22-02-2005 14:20:

voi avete un idea di perchè la mia funzione va in loop con t 1000 2000 01 mentre con tutti gli altri input va?
quale potrebbe essere la causa??
sto facendo un po' di prove con valori diversi e gia' un t 50 100 01 va in loop...va in loop per valori un po' troppo grossi...se sono piccoli ok altrimenti va in loop...:?

Posted by LjL on 22-02-2005 14:35:

Originally posted by p2p
voi avete un idea di perchè la mia funzione va in loop con t 1000 2000 01 mentre con tutti gli altri input va?
quale potrebbe essere la causa??
sto facendo un po' di prove con valori diversi e gia' un t 50 100 01 va in loop...va in loop per valori un po' troppo grossi...se sono piccoli ok altrimenti va in loop...:?


Non ne ho idea anche perché non so (e non voglio sapere!) che algoritmo usi... non so, prova il comando 't' sullo stesso automa con tutte le coordinate da 0 in poi (facendo in modo che il rettangolo descritto da automa e punto di richiamo sia un quadrato), e guarda qual è esattamente il punto in cui comincia a bloccarsi.

Se usi una funzione ricorsiva, potrebbe essere un problema di stack, altrimenti potrebbe essere comunque un problema di memoria di qualche genere (magari vai a scrivere dove non dovresti, ma per input piccoli le probabilità che il sistema se ne accorga sono basse).

Potrebbe esserti d'aiuto un debugger.

Tra l'altro per fare prove con input un po' grossi ti consiglio il mio programmino, che se per altri tipi di test non è un granché, sulla "quantità" è abbastanza utile :)

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by elpampero on 22-02-2005 14:59:

scusate ma su windows come faccio a calcolarmi il tempo di esecuzione?

Posted by LjL on 22-02-2005 15:09:

Originally posted by elpampero
scusate ma su windows come faccio a calcolarmi il tempo di esecuzione?


O ti guardi come si usano le funzioni che sono state citate, oppure
http://groups-beta.google.com/group...da01bf1525cc09a

Anche se così ad occhio non mi sembra un approccio di gran precisione.

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by elpampero on 22-02-2005 15:11:

il problema è che se io faccio
TIME programma<input mi da come output "ora specificata non valida.
Tuttavia ho provato a fare un test con cifre molto grandi e ci impiega sicuramente meno di un secondo

Posted by LjL on 22-02-2005 15:18:

Originally posted by elpampero
il problema è che se io faccio
TIME programma<input mi da come output "ora specificata non valida.
Tuttavia ho provato a fare un test con cifre molto grandi e ci impiega sicuramente meno di un secondo


Grazie, il comando time su Windows fa un'altra roba :)
Le funzioni a cui mi riferivo sono quelle di cui parlava qualcun altro, non io, quelle nell'header time.h o quel che è.
Fondamentalmente all'inizio della main() devi guardare che ora è, e alla fine del main() guardi di nuovo e fai la differenza.

In quel thread che ho indicato comunque c'è un metodo più semplice basato su un file .BAT.

P.S. per curiosità, per input *quanto* grandi ci mette meno di un secondo (e che processore hai)?

P.P.S. se ci mette meno di un secondo, comunque, i valori che puoi ottenere col file .BAT sicuramente non saranno molto significativi...

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by mattcobain on 22-02-2005 15:22:

Originally posted by virtual
Quanto impiega il vostro programma ad eseguire tutto l'input delle specifiche?

Il mio 37 secondi su PIII 1GHz.


37 secondi sull'input del prof?!?!?!
e la madonna!!!!!

cmq il mio, l'input del prof lo esegue in 0.03 secondi...il mio pc (non deridetemi :D ) è un malconcio pentium 2, 450 Mhz con 196 KB di ram.... sono all'antica!!! :lol:
e poi, cosa davvero strana, per fare invece l'input che ho postato qui, ci metto 0 secondi!!! per far arrivare il tempo a 0.03 devo copiare ed incollare le stesse righe di input almeno una 50ina di volte, ogni volta ricreando il piano!!!!
ho fatto un mega algoritmo della madonna supersonico (considerando su che pc lo sto facendo girare) oppure è una cosa normalissima!?!?! :)

Posted by LjL on 22-02-2005 15:30:

Originally posted by mattcobain
37 secondi sull'input del prof?!?!?!
e la madonna!!!!!

cmq il mio, l'input del prof lo esegue in 0.03 secondi...il mio pc (non deridetemi :D ) è un malconcio pentium 2, 450 Mhz con 196 KB di ram.... sono all'antica!!! :lol:


Figurati, io ho un 350MHz e solo perché me l'hanno regalato (altrimenti 233MHz)...
Certo, i 196 *kilo*byte di RAM un po' perplesso mi lasciano :D


e poi, cosa davvero strana, per fare invece l'input che ho postato qui, ci metto 0 secondi!!! per far arrivare il tempo a 0.03 devo copiare ed incollare le stesse righe di input almeno una 50ina di volte, ogni volta ricreando il piano!!!!
ho fatto un mega algoritmo della madonna supersonico (considerando su che pc lo sto facendo girare) oppure è una cosa normalissima!?!?! :)


Boh, è un po' strano che tu ci metta di meno col tuo input che con quello del prof, dato che il tuo sembra più grosso...

Tieni conto che time ha una certa granularità, e anch'io devo avere input di una certa dimensione prima di superare gli "0 secondi".

Io comunque per l'input del prof ci metto 0.05 secondi (tempo reale) e 0.005 secondi (tempo utente).
Per il tuo input, 0.1 e 0.005 rispettivamente.
[Non sono i numeri veri che mi vengono fuori, sono medie fatte a occhio su 4-5 esecuzioni, dato che i valori cambiano parecchio di volta in volta]
[Compilato con gcc -O3]

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by LjL on 22-02-2005 15:34:

Piuttosto comunque, quanto ci mettete voi per quest'input generato col programmino mio solito?

9182c0a200o200s200p200e200t200

Io ci metto 15 secondi (350MHz).

P.S. 15 secondi tolto il tempo per stampare l'output a video, cioè guardando il "tempo utente" sul comando time, o sopprimendo in qualche modo l'output (su Unix, aggiungendo >/dev/null alla linea di comando, su Windows, boh, forse >NIL: o >NUL: )
Ricordatevi anche di aggiungere 'f' alla fine dell'input, dato che il mio programma non lo mette ;)

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by mattcobain on 22-02-2005 15:36:

Originally posted by LjL
...Boh, è un po' strano che tu ci metta di meno col tuo input che con quello del prof, dato che il tuo sembra più grosso...



esatto, proprio quello mi ha fatto rimanere stranito!!!!
cmq ho riprovato piu volte e mi da sempre cosi....come ho detto, per fargli raggiungere un tempo nell'ordine degli 0.03 secondi devo copiare l'input e incollarlo una 50ina di volte, ogni volta facendogli ricreare il piano!!!!

e anche quello del prof....vero che la libreria time da valori non sempre uguali, ma anche qui, provando e riprovando, ottengo sempre o 0.03 o 0.04 secondi.....niente piu, niente meno!!!

ma fico....magari ho fatto davvero un buon lavoro!!! :cool:

boicottiamo i supercomputeroni degli ultimi 2 anni....torniamo ai 486!!! :D

Posted by LjL on 22-02-2005 15:47:

Originally posted by mattcobain
ma fico....magari ho fatto davvero un buon lavoro!!! :cool:


Se non fai dipendere il tempo di calcolo dalla distanza tra automi e richiamo, secondo me hai già fatto un buon lavoro.
Prova anche con input più grossi però, per vedere effettivamente come cresce la complessità... io ad esempio ho provato degli input che non fanno altro che creare n automi, con n da 0 a 2000 in incrementi di 10 (nel mio programma la creazioni di un'automa non è un'operazione O(1)).

Il grafico che mi viene fuori fa vedere una cosa che sembra proprio una parabola, come mi aspettavo.
Ad esempio:
500 automi = 0.5 secondi
1000 automi = 1.8 secondi
1500 automi = 4.23 secondi
2000 automi = 7.5 secondi


boicottiamo i supercomputeroni degli ultimi 2 anni....torniamo ai 486!!! :D [/B]


E chi se ne è mai andato? :D
Ok magari dai 486 me ne sono andato, però i quattro computer che uso sono un 350MHz, un 200MHz, un altro 200MHz e un 36MHz ;)

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by mattcobain on 22-02-2005 15:53:

Originally posted by LjL
Piuttosto comunque, quanto ci mettete voi per quest'input generato col programmino mio solito?

9182c0a200o200s200p200e200t200

Io ci metto 15 secondi (350MHz).

P.S. 15 secondi tolto il tempo per stampare l'output a video, cioè guardando il "tempo utente" sul comando time, o sopprimendo in qualche modo l'output (su Unix, aggiungendo >/dev/null alla linea di comando, su Windows, boh, forse >NIL: o >NUL:)
Ricordatevi anche di aggiungere 'f' alla fine dell'input, dato che il mio programma non lo mette ;)


maledetto, stai mettendo in crisi il mio pc :D
è tipo da 6 minuti che sto aspettando i risultati, ma ancora è qui che macina...poveraccio!!!! :lol:
anche perché non ho mica soppresso l'output....mica ho capito come si fa....
ma si, ormai aspetterò i risultati, magari domani riuscirò a postarli!!!!! :D

Posted by Petrik22 on 22-02-2005 16:07:

panico!!!

Posted by LjL on 22-02-2005 16:19:

Originally posted by mattcobain
maledetto, stai mettendo in crisi il mio pc :D
è tipo da 6 minuti che sto aspettando i risultati, ma ancora è qui che macina...poveraccio!!!! :lol:
anche perché non ho mica soppresso l'output....mica ho capito come si fa....
ma si, ormai aspetterò i risultati, magari domani riuscirò a postarli!!!!! :D


Ihihihi... be', di sicuro se aggiungi ">filequalsiasi" alla linea di comando l'output finisce su filequalsiasi, il che potrebbe essere comunque più veloce che farlo stampare sulla console.

Comunque stampando su console io ci metto 20 secondi. Vedete che non conta solo il tempo di esecuzione sui bassi numeri? :) O meglio, se conta o no non lo sappiamo, dato che non sappiamo che tipo di input propinerà il prof ai nostri programmi... però il senso del corso di algoritmi, sempre che io l'abbia capito, è quello di insegnarci a scrivere algoritmi asintoticamente buoni.

Se ti può consolare del fatto che il mio programma sembra meno complesso in tempo del tuo, è probabile che in spazio il tuo sia il sogno di ogni automa rispetto al mio :) Specialmente se usi liste dinamiche...

P.S. Oh, a proposito, hai detto "macina"? Sarebbe a dire semplicemente che è lì a calcolare, o macina nel senso che macina il disco fisso? Se è la seconda vuol dire che il tuo algoritmo è subottimale in *spazio* e non in tempo, o in altre parole che finisci la RAM e il sistema è costretto a usare lo swap. Se è così interrompi pure, tanto il risultato non avrebbe nessun significato.

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

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..... :look:
insomma....posso benissimo smentire le cazzate dette quando pensavo di aver fatto un algoritmo supersonico :D

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

:D

__________________
"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...:twisted::twisted::twisted:

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


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

Posted by elpampero on 24-02-2005 08:42:

Infatti..direi di aspettare un paio di giorni e vedere. ieri gli ho consegnato personalmente il progetto e sembrava che conoscesse già il mio nome. questo mi fa pensaer che avesse già controllato il programma e che, mancando una risposta, sia ok.

Posted by fdecollibus on 24-02-2005 10:23:

scusatemi ragazzi, ma sapete se il progetto si può consegnare anche se l'output non corrisponde all'input? E' vero che in questo caso si viene automaticamente bocciati?

Posted by elpampero on 24-02-2005 10:25:

Mi sembra che il prof abbia detto così..pero' puoi provare comunque...

Posted by Motomax on 24-02-2005 10:25:

Ciao
Io lo messo nella sua casella di posta.....sapete se è affidabile oppure NO?

Posted by fdecollibus on 24-02-2005 10:26:

praticamente, da quello che ho capito, a questo esame, se l'input corrisponde all'output (ovvero con un programma adeguato dietro) si è praticamente promossi automaticamente, è vero?

Posted by elpampero on 24-02-2005 10:30:

Forse detta così è un po' esagerata..però se fai il progetto ti sei tolto un bel peso..credo...

Posted by fdecollibus on 24-02-2005 10:36:

io l'ho fatto ma il mio input non corrisponde all'output! Non credo neanche di consegnarlo!

Posted by elpampero on 24-02-2005 10:38:

Ma scusa se l'hai fatto prova a fare un po' di debug..magari è un errore banale. Metti in giro un pò di printf e vedi cosa succede. Se sei riuscito ad implementare le ultime due funzioni sei a buon punto

Posted by fdecollibus on 24-02-2005 10:41:

lo sto facendo da giorni ma non funzionano come devono forse ho fatto un errore di base nella struttura del percorso. Praticamente il metodo percorso prende la minima x1 tra gli ostacoli del piano e la minima y1 e prova a reistanziarsi a minimax1-1 e alla sua y2 e alla minimay1-1 e alla sua y2, e poi all'intersezione tra y2 e y1. Di li in poi il metodo richiama se stesso. La tortuosità è il numero di volte minimo che questo programma si richiama. Eppure non va.

Posted by mark on 24-02-2005 10:43:

Originally posted by fdecollibus
io l'ho fatto ma il mio input non corrisponde all'output! Non credo neanche di consegnarlo!



se l'output è ok al 90% io lo invierei comunque, e lascerei la valutazione finale al prof ;)

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

Posted by elpampero on 24-02-2005 10:45:

Infatti..Ma perchè calcoli gli le coordianate degli ostacoli?

Posted by fdecollibus on 24-02-2005 10:51:

non è ok al 90%. Sballa tutte le tortuosità.
Calcolo le coordinate degli ostacoli più vicini e vedi come evitarli, se posso evitarli. Mi sembrava un ragionamento corretto.

Posted by mattcobain on 24-02-2005 11:39:

Originally posted by Motomax
Ciao
Io lo messo nella sua casella di posta.....sapete se è affidabile oppure NO?



non so se è affidabile, fatto sta che anchio ieri l'ho lasciata nella sua casella di posta ed era aperta!!! :look:
cmq appena avevo messo la copia cartecea, dopo neanche un minuto ho visto il prof arrivare mentre io andavo via e mi è sembrato di aver sentito il rumore che apriva la cassetta e prendeva le copie che conteneva....cmq il fatto che era aperta mi puzzava abbastanza!

Posted by Teju on 24-02-2005 13:00:

Dovete mandargli anche una copia via mail del codice e della relazione!!!

__________________
Teju.it - Una vita da raccontare

Posted by mattcobain on 24-02-2005 13:02:

Originally posted by Teju
Dovete mandargli anche una copia via mail del codice e della relazione!!!


si chiaro...l'abbiamo letto tutti il testo del progetto!!! ;)

cmq grazie per il promemoria!

Posted by Teju on 24-02-2005 13:14:

Originally posted by mattcobain
si chiaro...l'abbiamo letto tutti il testo del progetto!!! ;)

cmq grazie per il promemoria!

E allora basta, state tranquilli: se ha ricevuto la mail farà i suoi test e poi vi manda una mail di conferma o di non conferma per l'orale...
Probabilmente aspetta la data di chiusura del progettino prima di mandare le mail agli studenti che han già consegnato. :-D

__________________
Teju.it - Una vita da raccontare

Posted by Skilotto83 on 24-02-2005 13:38:

ragazzi...
lo so ke nn è nulla di grave....
ma a voi se stampate il codice del progetto quanto vi viene...??
io sono a 40pagine!!!
un po' è il mio metodo di fare....
Uso tante funzioni anhe per calcolare un solo valore, ma il codice guadagna leggibilita'...
E poi dichiaro sempre le variabili e alla riga successiva gli assegno un valore, senza fare tutto direttamente...

__________________
"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 mattcobain on 24-02-2005 14:47:

io ho stampato in 13 pagine tutto il codice, le righe (commenti compresi, moooolti) sono 1230 circa
naturalmente ho diminuito il carattere a 7, ma è leggibile....
poi ognuno ha il suo modo di scrivere....io ad esempio se devo inizializzare ed assegnare un valore lo faccio subito nella sua dichiarazione....oppure se ci sono cicli con una sola istruzione ometto le parentesi, uso spesso l'operatore ternario anzichè if-else.....ecc...ecc...

Posted by Skilotto83 on 24-02-2005 16:30:

ridotto a 7 anche il mio....
25pagine...compresi i moduli.h e un botto di commenti...
Cosi' va meglio....

__________________
"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 Granito on 24-02-2005 17:33:

Ciao Skilotto!! L'ho finito anch'io...
Ho utilizzato una semplice struttura a liste puntate, e mi è uscito intorno alle 14 pagine (in word). Speriamo di beccarci alla discussione allora!
Granito

__________________
Statistica non è un esame, ma un accanimento terapeutico...staccatemi la spina!!!

Posted by Jacoposki on 24-02-2005 18:52:

sigh... in chiusura e ancora non va... a meno di miracoli dell'ultima ora se ne riparla ad aprile. E' stato bello... anzi no :(

Non so gli altri, ma a me i quattro giorni che non ci hanno dato avrebbero fatto non poco comodo.

Amen

__________________
Mai sottovalutare l'ampiezza di banda di una station wagon piena di nastri lanciata a tutta velocità lungo l'autostrada. - Andrew S. Tanenbaum - Reti di Calcolatori

Posted by LjL on 24-02-2005 19:14:

18 pagine, carattere 9, pagina in orizzontale.
Decisamente troppo lungo e anche troppo brutto per i miei gusti, ma spero che Fiorentini lo giudichi meglio di me ;)

E spero anche che il termine del "24 compreso" fosse rigoroso, dato che l'ho infilato nella sua casella verso le 18:30 e gli devo ancora mandare l'e-mail :D

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by Polsy on 24-02-2005 19:28:

Originally posted by LjL
18 pagine, carattere 9, pagina in orizzontale.
Decisamente troppo lungo e anche troppo brutto per i miei gusti, ma spero che Fiorentini lo giudichi meglio di me ;)

E spero anche che il termine del "24 compreso" fosse rigoroso, dato che l'ho infilato nella sua casella verso le 18:30 e gli devo ancora mandare l'e-mail :D

allora forse sei tu quello che ho incrociato oggi cercando la casella di aguzzoli...

cmq questo progetto è stato un parto...non mi sono mai sbattuta tanto x nessuna materia da quando è iniziata l'università :S

Posted by Skilotto83 on 24-02-2005 19:47:

Originally posted by LjL
18 pagine, carattere 9, pagina in orizzontale.
Decisamente troppo lungo e anche troppo brutto per i miei gusti, ma spero che Fiorentini lo giudichi meglio di me ;)

E spero anche che il termine del "24 compreso" fosse rigoroso, dato che l'ho infilato nella sua casella verso le 18:30 e gli devo ancora mandare l'e-mail :D


hai pm...se hai voglia di rispondere...
Kmq io gli ho mandato ieri una mail chiedendo gentilemnte sela copia cartacea si puo' lasciare domani mattina...e mi ha detto ok.,..
ora gli mando la mail..

__________________
"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 24-02-2005 19:58:

Originally posted by Polsy
allora forse sei tu quello che ho incrociato oggi cercando la casella di aguzzoli...

cmq questo progetto è stato un parto...non mi sono mai sbattuta tanto x nessuna materia da quando è iniziata l'università :S


Forse eri quella che stava parlando col custode prima che gli chiedessi io per la casella di Fiorentini. Comunque se il tizio che hai visto non si tagliava la barba da troppo, ma veramente troppo tempo, ero io :D

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by Polsy on 24-02-2005 20:34:

Originally posted by LjL
Forse eri quella che stava parlando col custode prima che gli chiedessi io per la casella di Fiorentini. Comunque se il tizio che hai visto non si tagliava la barba da troppo, ma veramente troppo tempo, ero io :D

hmmm :S no...mi sa ke era qualcun altro...

Posted by LjL on 25-02-2005 01:23:

Secondo voi quand'è che si può cominciare a postare i progetti qui sopra? Solo dopo tutti gli orali o anche prima?

A parte questo... cos'ho imparato da questo progetto? (Tema di Italiano, terza elementare). Magari sono cose utili anche per qualcun altro di voi...
- Probabilmente è meglio scrivere, subito, un programma che funziona, piuttosto che farsi il sangue marcio per trovare un buon algoritmo senza nel frattempo mettere giù una linea di codice. Così si finisce per consegnare all'ultimo momento (se va bene) e per scrivere un programma che tutto sommato non è poi così più efficiente rispetto a uno che si è cominciato a scrivere *subito*. Se poi il prof guarda solo se va.....
- assert() è una Cosa Buona(tm). Anche se spesso e volentieri quando fallisce un'asserzione non si ha la più pallida idea di *perché* sia fallita, intanto comunque si *sa* che da qualche parte un errore c'è. Poi comunque i debugger sono lì per quello. Morale: appena viene in mente "ehi ma qui la variable tale sarà sempre minore della variable talaltra", metterci un'assert().
- I debugger sono Cosa Buona(tm). Questo non l'ho scoperto solo in questo progetto, ma comunque per un bel po' di tempo mi sono rifiutato di imparare a usare un debugger. Ma il tempo perso per guardarsi i comandi di GDB è niente rispetto agli errori che ti aiuta a trovare. Un semplice "where" in GDB ti fa quantomeno capire *dov'è* che quella cacchio di assert() era fallita (sempre se sai che prima devi scrivere "break abort", perché il programma non esca dopo l'assert())
- Per trovare memory leak e puntatori che si perdono nella nebbia dei tempi, usare Valgrind. Inutile stare a perdere tempo con GDB o con tecniche casereccie varie
- Tanto va la gatta al lardo che ci lascia lo zampino

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by elpampero on 25-02-2005 08:42:

Scusate ma Fiorentini ha risposto a qualcuno di voi?

Posted by mattcobain on 25-02-2005 09:01:

a me personalmente non ancora

Posted by elpampero on 25-02-2005 09:04:

Mi viene il dubbio che non risponda. Se è andato bene ti trovi nell'elenco degli esami orali..

Posted by Timido on 25-02-2005 09:12:

Mha qualcuno sà più o meno se oggi pubblicherà le date dell'orale?

Posted by elpampero on 25-02-2005 09:16:

Non ne ho idea. Speriamo!

Posted by Timido on 25-02-2005 09:43:

Ciao qualcuno potrebbe dire cortesemente i capitoli da studiare dall libro? "indroduzzione agli algoritmi" grazie in anticipo........visto che io non ho potuto seguire le lezionei mi farebbe un enorm cortesia

Posted by elpampero on 25-02-2005 09:49:

Qui trovi tutto:
http://homes.dsi.unimi.it/~torelli/argomenti04.html

Posted by elpampero on 25-02-2005 13:22:

Mi ha risposto il prof dicendomi che il codice è abbastanza corretto ma che ci sono degli erroretti... Vado comunque all'orale :-)

Posted by Timido on 25-02-2005 13:25:

anche a me mi ha risposto cosi:

Il progetto e' poco efficiente (con input allegato non termina)

L' operazione e e' corretta, con t si hanno errori
(gia' con gli input del testo) ed e' troppo lenta
(provi a eseguire l'input allegato sostituendo e con t)

per l'orale consulti il sito.



Però sul sito non trovo nulla e voi§??

Posted by elpampero on 25-02-2005 13:27:

Penso che tra un po' metterà fuori le date degli orali

Posted by mattcobain on 25-02-2005 13:36:

ha risposto anche a me con un
" Il progetto funziona correttamente
Per l'orale consulti la pagina del corso "
però ancora non sono usciti i calendari...che cmq penso proprio usciranno qui http://homes.dsi.unimi.it/~torelli/algoritmi.html

Posted by elpampero on 25-02-2005 13:49:

mattcobain, proveresti con questo input e mi dici qual è l'output?

c
o -11 -7 -3 -5
o -12 -3 -8 -1
o -6 -3 -1 -1
o -12 2 -11 7
o -9 4 -3 7
o 0 -6 12 -4
o 18 -5 14 -4
o -6 2 -1 10
o -11 9 -8 10
o -2 6 1 9
o 8 2 12 4
o 15 2 20 6
o 4 -10 16 -8
o 18 -2 19 0
o 3 4 7 7
o 9 6 12 8
o 14 8 17 10
o 21 7 22 8
o 3 9 6 11
o 11 -2 12 -1
o 18 -8 22 -7
o 8 10 12 12
o 5 12 6 13
o 14 12 15 13
o 19 10 22 11
o 1 -2 8 1
o 15 -3 16 -2
o -4 -11 0 -9
a -12 -12 100
t -8 0 100
t 0 -8 100
t 22 0 100
t 14 0 100
t 0 0 100
t -2 -4 100
t 2 2 100
t 0 1 100
t 2 5 100
t 2 10 100
t 8 9 100
t 22 13 100
t 23 13 100
o 13 2 14 3
t 22 13 100
a -12 12 101
t 16 0 101
t 0 0 101
t 14 -7 101
t 23 -12 101
t 22 -9 101
a 23 9 110
t 0 0 110
t 0 -3 110
t 13 4 110
t -12 -11 110
a 22 -10 111
t 14 0 111
t -12 12 111
t -7 0 111
f

Posted by mark on 25-02-2005 13:59:

con quale metodo avete rispolto il problema ?

ricorsione oppure "dijkstra" o metodi similari ?

solo una curiosità, non mi interessa il codice :)

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

Posted by Timido on 25-02-2005 14:42:

ma secondo voi con una risposta cosi cosa vuole?
che gli rimando il progetto modificato?

Il progetto e' poco efficiente (con input allegato non termina)

L' operazione e e' corretta, con t si hanno errori
(gia' con gli input del testo) ed e' troppo lenta
(provi a eseguire l'input allegato sostituendo e con t)

per l'orale consulti il sito.

Posted by elpampero on 25-02-2005 14:45:

Non credo proprio.. Penso voglia motivarti il suo "poco efficiente".
Comunque penso che sia andata perchè ti dice di consultare il sito per l'orale

Posted by LjL on 25-02-2005 14:51:

Originally posted by Timido
[B]ma secondo voi con una risposta cosi cosa vuole?
che gli rimando il progetto modificato?


Be', non lo so, però penso che male non possa fare.
Almeno, non credo che un'email in più gli rovini la vita (anche perché se ci metti solo il progetto e non la relazione il file occupa pure poco).
Digli qualcosa del tipo "mettendo in pratica i Suoi suggerimenti, ho modificato il codice e le allego per conoscenza il nuovo codice"... cercando comunque di non fargli pensare che vuoi che non consideri più il codice originale.

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by LjL on 25-02-2005 14:54:

Originally posted by elpampero
mattcobain, proveresti con questo input e mi dici qual è l'output?

[snip]


Se ti può interessare il mio output è così (a parte gli acapo):

-1 1 3 3 3 1 5 3 5 6 8 6 1 13 -1 3 6 8 9 -1 3 3 6 2 9 5

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by elpampero on 25-02-2005 15:10:

OK. mi sballa su due valori infatti Fiorentini mi ha detto che il codice è abbastanza corretto...MA STI ORALI?????

Posted by Timido on 25-02-2005 15:59:

qualcuno ha news sugli orali??

Posted by luca8684 on 25-02-2005 16:00:

Originally posted by Timido
qualcuno ha news sugli orali??


:alsono: :nono:

__________________
{¯`·._)-•°o.O`·._.·´¯`•¸·´¯).·´¯`·-> IN DA EEKS <-·´¯`·.(¯`·¸•´¯`·._.·´O.o°•–(¯`·._}

Posted by superfabius on 25-02-2005 16:18:

free(fiorentini)

Posted by elpampero on 25-02-2005 16:31:

Scusate ma se ti dice di guardare il sito per l'orale vuol dire che si è ammessi?

Posted by Timido on 25-02-2005 16:32:

Bhè penso di si!

Posted by mattcobain on 25-02-2005 17:06:

Originally posted by LjL
Se ti può interessare il mio output è così (a parte gli acapo):

-1 1 3 3 3 1 5 3 5 6 8 6 1 13 -1 3 6 8 9 -1 3 3 6 2 9 5


giusto...quoto LjL ;)

Posted by Timido on 25-02-2005 17:50:

Va bhè mi sà che oggi le date non le mette.......mi sà che se ne parla lunedi oppure terrà buone quelle indicate da noi...voi che dite??

Posted by mattcobain on 25-02-2005 18:03:

dai, diamogli tempo....dopotutto la scadenza per i progetti era ieri, ed oggi ha provato i programmi di tutti ed ha mandato le relative mail!!!!
e poi chissà, magari deve parlanre con torelli per stilare insieme i calendari, quindi un po di pazienza...dopotutto ha anche lui la sua vita, non è che passa tutto il giorno a lavorare dai!
penso cmq che magari anche stasera, oppure domani sicuramente, i calendari saranno on-line...
impossibile che li mettà lunedi, considerando che potrebbe essere già un giorno da "appello" nel caso ci siano volontari per quella data...quindi dovrebbero mettere on-line prima i calendari, almeno da avvertire quelle persone se devono effettivamente presentari il 28 oppure se ,in mancanza di altri volontari, sono stati spostati alla data successiva...

Posted by alessiolennon on 25-02-2005 18:51:

perchè che mail avete ricevuto voi?????

io non ho ricevuto niente ancora.

__________________
I don't believe in magic, life is automatic (noel gallagher)
cheers

Posted by LjL on 25-02-2005 18:52:

Originally posted by mattcobain
impossibile che li mettà lunedi, considerando che potrebbe essere già un giorno da "appello" nel caso ci siano volontari per quella data...quindi dovrebbero mettere on-line prima i calendari, almeno da avvertire quelle persone se devono effettivamente presentari il 28 oppure se ,in mancanza di altri volontari, sono stati spostati alla data successiva...


Ah è un appello "volontario" quello del 28? Wow... forse dovrei venire a lezione ogni tanto...

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by mattcobain on 26-02-2005 08:53:

Originally posted by LjL
Ah è un appello "volontario" quello del 28? Wow... forse dovrei venire a lezione ogni tanto...


è un appello "volontario" nel senso che nel testo del progetto diceva espressamente ad ognuno di indicare nella mail del progetto, il giorno in cui si preferiva fare l'appello....i giorni erano il 28, il 4, l'8 e l'11....è chiaro a questo punto che se nessuno a scelto il 28 come giorno, sicuramente quella data salterà (com'è successo per l'appello scorso, anche li c'erano più date a scelta, ma alcune sono saltate perché non c'era nessun "volontario" per quel giorno)....oppure, piuttosto che portare di una data "in avanti" chi preferiva dare l'appello per esempio il 4, sposterà magari l'eventuale unico "volontario" del 28 alla data successiva, cioè il 4, facendo ancora saltare il 28...non so se mi spiego....

Posted by elpampero on 26-02-2005 09:42:

Tutto chiaro ma, visto che non saremo più di 12 persone, sarebbe stato carino da parte del prof farci vedere il calendario...giusto per regolarci. VISTO CHE LUNEDI' INIZIANO ANCHE LE LEZIONI!!!!

Posted by Timido on 26-02-2005 09:45:

bhè forrei sperare che tengano vede quella da noi seganlate.....se no per me diventa un casino visto che lavoro anche...

Posted by Teju on 26-02-2005 09:59:

Originally posted by superfabius
free(fiorentini)

:D :D :D

__________________
Teju.it - Una vita da raccontare

Posted by Granito on 26-02-2005 11:01:

Ciao amici,
scusate la domanda, ma per la discussione del progetto, com'è che funziona, e quando sarebbe?? Grazie mille!!!
Granito

__________________
Statistica non è un esame, ma un accanimento terapeutico...staccatemi la spina!!!

Posted by Skilotto83 on 26-02-2005 11:30:

ma sapete per caso se anche aguzzoli manda una mail??

__________________
"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 Granito on 26-02-2005 14:52:

Infatti io sono con Aguzzoli...chi ha notizie, faccia sapere.
Ciao
Granito

__________________
Statistica non è un esame, ma un accanimento terapeutico...staccatemi la spina!!!

Posted by mattcobain on 26-02-2005 15:31:

Originally posted by elpampero
Tutto chiaro ma, visto che non saremo più di 12 persone, sarebbe stato carino da parte del prof farci vedere il calendario...giusto per regolarci. VISTO CHE LUNEDI' INIZIANO ANCHE LE LEZIONI!!!!


bhe, non è tutta colpa del prof fiorentini, dato che le date usciranno sul sito di torelli, quindi come avevo detto, probabilmente si staranno dando da fare, e l'ultima mossa, quella di publicare i calendari, spetta al prof torelli, dato che compariranno sul suo sito!!!

Posted by Oracle on 26-02-2005 16:39:

Come siete messi con la parte teorica ? :wall:

__________________
Divide et impera

Posted by mattcobain on 26-02-2005 17:23:

male!

Posted by Polsy on 26-02-2005 17:31:

sono una cretina...ho mandato ad aguzzoli il programma senza cancellare le printf ke avevo usato x debuggare! :ueee:
gli ho mandato una mail chiedendo venia...speriamo sia comprensivo... :look:

Posted by mark on 27-02-2005 09:35:

potrei anche sbagliarmi ma l'automa (00), al contrario di quanto specificato dal prof, non dovrebbe essere in grado di raggiungere il punto

e 10 11 00

in quanto l'ostacolo

o 7 11 8 12

gli sbarra la strada

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

Posted by mattcobain on 27-02-2005 10:26:

Originally posted by mark
potrei anche sbagliarmi ma l'automa (00), al contrario di quanto specificato dal prof, non dovrebbe essere in grado di raggiungere il punto

e 10 11 00

in quanto l'ostacolo

o 7 11 8 12

gli sbarra la strada


non posso smentirti perché non ho voglia di mettermi a fare il disegnino :D , cmq magari prova a controllare meglio, dubito possa essere sbagliato....
cmq cominciano a girarmi gli zebedei, ma quando li mettono fuori sti calendari?!!? non è possibile dai!!!! c'è gente che potrebbe essere d'appello domani ed ancora non ne ha la certezza!!!!

Posted by mark on 27-02-2005 10:30:

Originally posted by mattcobain
non posso smentirti perché non ho voglia di mettermi a fare il disegnino :D , cmq magari prova a controllare meglio, dubito possa essere sbagliato....
cmq cominciano a girarmi gli zebedei, ma quando li mettono fuori sti calendari?!!? non è possibile dai!!!! c'è gente che potrebbe essere d'appello domani ed ancora non ne ha la certezza!!!!




basta che usi quello che avevi già fatto

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

Posted by mattcobain on 27-02-2005 10:39:

Originally posted by mark
basta che usi quello che avevi già fatto


il progetto che ho fatto da lo stesso output di quello del prof, poi abbiamo constatato con altri ragazzi che funziona anche con l'input che avevo postato qualche pagina fa, e poi funziona anche con un input postato da elpampero qualche post fa....
io intendevo che per vedere se davvero non è raggiungibile devo farmi un disegnino, perché non ci sarebbe altro modo di accorgersene se con il programma mi dice che un percorso esiste mentre in realtà non esiste (ok, come al solito non riesco a spiegarmi e faccio giri di parole)
cmq penso che il mio progetto, come quello di altri, sia funzionante correttamente....prova a ricontrollare l'affermazione che hai fatto su

Posted by mark on 27-02-2005 10:57:

Originally posted by mattcobain
il progetto che ho fatto da lo stesso output di quello del prof, poi abbiamo constatato con altri ragazzi che funziona anche con l'input che avevo postato qualche pagina fa, e poi funziona anche con un input postato da elpampero qualche post fa....
io intendevo che per vedere se davvero non è raggiungibile devo farmi un disegnino, perché non ci sarebbe altro modo di accorgersene se con il programma mi dice che un percorso esiste mentre in realtà non esiste (ok, come al solito non riesco a spiegarmi e faccio giri di parole)
cmq penso che il mio progetto, come quello di altri, sia funzionante correttamente....prova a ricontrollare l'affermazione che hai fatto su




si capisce benissimo quello che intendi

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

Posted by mattcobain on 27-02-2005 12:24:

Originally posted by mark
potrei anche sbagliarmi ma l'automa (00), al contrario di quanto specificato dal prof, non dovrebbe essere in grado di raggiungere il punto

e 10 11 00

in quanto l'ostacolo

o 7 11 8 12

gli sbarra la strada



allora, ho controllato....l'automa 00 raggiunge il punto
e 10 11 00

perché l'ostacolo o 7 11 8 12 viene inserito nel piano dopo aver dato il comando " e 10 11 00 "

Posted by mark on 27-02-2005 12:35:

Originally posted by mattcobain
allora, ho controllato....l'automa 00 raggiunge il punto
e 10 11 00

perché l'ostacolo o 7 11 8 12 viene inserito nel piano dopo aver dato il comando " e 10 11 00 "



hai ragione, mi era sfuggita tale particolarità :)

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

Posted by mattcobain on 27-02-2005 12:37:

Originally posted by mark
hai ragione, mi era sfuggita tale particolarità :)

;)

cmq....quando avremo sti dannati calendari!?!?!? qualcuno percaso ha mandato una mail a qualche prof!?
se si, vi hanno risposto?!
appena torno a casa quasi quasi gliene mando una, sia a torelli, sia a fiorentini!!!!
cavolo non è possibile....anche per sapere a che cavolo di ore e dove ci saranno gli appelli!!!

Posted by elpampero on 27-02-2005 14:00:

Penso ormai che li metteranno domani e che rimaranno le date da noi richieste

Posted by mattcobain on 27-02-2005 14:37:

il fatto è che alcuni potrebbero non aver avuto preferenze....tipo io, che a parte il 28 che ho escluso, avevo lasciato al prof la scelta della data....
vabé....

Posted by Oracle on 27-02-2005 14:49:

Probabilmente il prof tarda perchè nessuno ha scelto il 28 ;-)

__________________
Divide et impera

Posted by Motomax on 28-02-2005 14:43:

ma qualcuno che ha detto che il programma non andava tanto beno gli avete rimandato un altra versione?

Posted by Oracle on 28-02-2005 16:07:

Originally posted by Motomax
ma qualcuno che ha detto che il programma non andava tanto beno gli avete rimandato un altra versione?


No io personalmente non gli ho mandato niente mi aspetto di commentare le inesattezze all'orale

__________________
Divide et impera

Posted by Motomax on 28-02-2005 16:09:

ma l'orale come funziona ti interroga prima fiorentini e poi torelli??? oppure solo uno?

Posted by Oracle on 28-02-2005 16:17:

Originally posted by Motomax
ma l'orale come funziona ti interroga prima fiorentini e poi torelli??? oppure solo uno?

Non l'ho ancora fatto ma ho letto in altri TD che ti interrogano tutti e due.
Prima che yoruno ci riprenda :D tieni presente che c'è un TD apposto relativo alle domande e alla modalità di conduzione dell'orale.

__________________
Divide et impera

Posted by mattcobain on 01-03-2005 08:30:

oh ragazzi, mi è venuto l'atroce dubbio che forse i calendari siano usciti da qualche altra parte (tipo in forma cartacea o chissà dove e chissà per quale motivo) visto che ormai siamo al primo di marzo e ancora niente.... qualcuno di voi sa qualcosa in più oppure siamo ancora tutti qui ad aspettare queste date??

Posted by elpampero on 01-03-2005 08:32:

Verso le 11 chiamo Fiorentini e faccio sapere...Ho anch'io qualche dubbio!

Posted by elpampero on 01-03-2005 08:33:

Scusa mattcobain..tu come hai implementato alla fine la tortuosità?

Posted by p2p on 01-03-2005 08:49:

Il prof. l ho visto ieri e gli ho chiesto, ha detto che sta preparando il calendario anzi pensava di metterlo online ieri o al max oggi,quindi secondo me aspettiamo che oggi dovrebbe uscire,il problema è che doveva sentire il prof Torelli che aveva difficolta' a recuperare l aula per l 11 .....
mi ha detto che una ricorsione con tabella,quelle viste in programmazione dinamica,era il modo migliore per sviluppare il progetto ;)

Posted by mattcobain on 01-03-2005 10:25:

Originally posted by p2p
Il prof. l ho visto ieri e gli ho chiesto, ha detto che sta preparando il calendario anzi pensava di metterlo online ieri o al max oggi,quindi secondo me aspettiamo che oggi dovrebbe uscire,il problema è che doveva sentire il prof Torelli che aveva difficolta' a recuperare l aula per l 11 .....
mi ha detto che una ricorsione con tabella,quelle viste in programmazione dinamica,era il modo migliore per sviluppare il progetto ;)



si, finalmente sono usciti!!!! era ora!!!!
http://homes.dsi.unimi.it/~fiorenti/labalg04/orali.txt

esatto, la ricorsione con memorizzazione era la scelta migliore...peccato che le abbiamo viste solo in teoria ed in pratica non avevo la minima idea di come implemetare la cosa...anche se so si tratta di una stupidaggine, ma non sapevo da dove partire!!!

Originally posted by elpampero
Scusa mattcobain..tu come hai implementato alla fine la tortuosità?


la tortuosità la calcolavo di pari passo con la ricerca di un percorso libero da un automa alla sorgente del segnale...in poche parole non ho fatto 2 funzioni a loro stanti (cioè una per vedere se esiste un percorso libero e uno per la tortuosità minima) ma ho fatto di pari passo....anche se penso che fare le cose separate sarebbe stato sicuramente più efficiente....
cmq per l'implementazione, se sei proprio curioso, abbi pazienza fino a quando verbalizzerò e dopodiché posterò il progetto in filez... ;)

Posted by elpampero on 01-03-2005 10:38:

Io ho fatto tutto con funzioni ricorsive. Spingevo l'automa verticalmente il più possibile e poi orizzontalemte il più possibile..così ricorsivamente..sembrava andare tutto bene ma il prof ha fatto altri test.
Risultava su 26 richieste di toruosità 24 giuste e 2 sballate di 1...
Sicuramente all'esame mi chiederà..cmq risponderò col metodo della prog dinamica

Posted by mattcobain on 01-03-2005 10:52:

Originally posted by elpampero
Io ho fatto tutto con funzioni ricorsive. Spingevo l'automa verticalmente il più possibile e poi orizzontalemte il più possibile..così ricorsivamente..sembrava andare tutto bene ma il prof ha fatto altri test.
Risultava su 26 richieste di toruosità 24 giuste e 2 sballate di 1...
Sicuramente all'esame mi chiederà..cmq risponderò col metodo della prog dinamica


anchio vado avanti ricorsivamente di "passo" in "passo" (ma il mio concetto di passo non è unitario, piuttosto un insieme di passi tutti nella stessa direzione fino ad un "eventuale" ostacolo)....però a differenza tua non ho il vincolo che prima vado tutto in verticale e poi tutto in orizzontale....

Posted by elpampero on 01-03-2005 10:59:

Bhè allora diciamo che il mio dovrebbe essere un bug non esagerato. Non penso me lo valuti male il progetto..

Posted by mattcobain on 01-03-2005 11:04:

Originally posted by elpampero
Bhè allora diciamo che il mio dovrebbe essere un bug non esagerato. Non penso me lo valuti male il progetto..


e boh, come possiamo sapere quello che pensa il prof?
una cosa è certa, che tuo progetto non funziona sempre correttamente...
e che io non ho usato l'algoritmo migliore (cioè ricorsione con memorizzazione)
il tuo con gli input del prof funzionava bene?
bisogna vedere cosa valuta...se magari hai utilizzato algoritmi molto efficienti e magari su qualche caso hai dimenticato qualche controllo che ti portano come risultato a quegli errori magari non darà molto peso al tuo "bug", se però oltre a questo problema magari l'algoritmo risolutivo non è fra i più efficienti allora la cosa è ancora più penalizzante...
ormai pochi giorni e tutti sapremo come siamo andati!!!
All times are GMT. The time now is 09:18. Pages (4): « 1 2 [3] 4 »
Show all 482 posts from this thread on one page

Powered by: vBulletin Version 2.3.1
Copyright © Jelsoft Enterprises Limited 2000 - 2002.