 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
[algoritmi] Progetto di Febbraio "Itinerari"
Clicca QUI per vedere il messaggio nel forum |
| crime |
Ragazzi, avete visto il progetto?
Sono sbigottito!
Avete suggerimenti sulla struttura?
Credo che durante le lezioni di Torelli, bisognava approfondire maggiormente il capitolo 25 sui cammini minimi.
:shock: |
| Lunik |
PLEASE: se dovete parlare di algoritmi scrivere in informatica e non nel Forum FileZ..lì ci vanno solo i file....e nient'altro...
cià!
e grazie! |
| Antrox |
Concordo con Crime!
Chi di Voi sa veramente come svilupparlo? |
| gallu10 |
nn è difficile da svillupare
è difficile implementare una struttura dati con complessità che nn sia lineare.... |
| crime |
| Visto che non hai difficolta', hai qualche consiglio sulla strategia? |
| lord2y |
| un grafo??sviluppato con liste concatenate?Voi che dite? |
| gallu10 |
con una lista di liste nn sembra impossibile da realizzare...
il problema che ha complessità lineare e al prof nn andrà sicuramente bene...o sbaglio?
in un altro post ho sentito parlare di grafi ma nn saprei proprio da dove iniziare |
| lord2y |
Originally posted by gallu10
con una lista di liste nn sembra impossibile da realizzare...
il problema che ha complessità lineare e al prof nn andrà sicuramente bene...o sbaglio?
in un altro post ho sentito parlare di grafi ma nn saprei proprio da dove iniziare
con liste concatenate...il problema sta nella ricerca all'interno nella lista |
| crime |
| Liste concatenate? Leggendo sul progetto sembrerebbe che non si possa utilizzare Matrici e strutture similari. Interpreto questa affermazione come una chiara dichiarazione di non usare Liste Concatenate. Provo a inviare un E-Mail a Fiorentini. Vi informo. Comunque al di la' della struttura ci interessa l'algoritmo. Le idee, opinioni, strategie etc.... |
| gallu10 |
Originally posted by lord2y
con liste concatenate...il problema sta nella ricerca all'interno nella lista
con il grafo nn saprei proprio da dove partire...nn riesco a visualizzarlo:? :? |
| Skanky |
anche io non riesco bene a capire...ero partito con lista di liste , ora sono propenso per lista dei ollegamenti e grafo di nodi....
Altro che algoritmo, forse non ci arrivero' mai alla fase dell' ottimizzazione, quello di gennaio mi sembrava 10 volte piu' facile
arghhhhh impazziro' a breve :shock: |
| nicoursi |
Originally posted by crime
Liste concatenate? Leggendo sul progetto sembrerebbe che non si possa utilizzare Matrici e strutture similari. Interpreto questa affermazione come una chiara dichiarazione di non usare Liste Concatenate. Provo a inviare un E-Mail a Fiorentini. Vi informo. Comunque al di la' della struttura ci interessa l'algoritmo. Le idee, opinioni, strategie etc....
Hey! guarda che le matrici con le liste non hanno niente a che fare! Le matrici non sono dinamiche e di conseguenza si rischia di occupare spazio inutilmente.... con le liste invece no! LA lista è dinamica e la dimensione può variare durante l'esecuzione. L'aspetto negativo delle liste sta nelle scansioni.....
Corregetemi se sbaglio.. |
| gallu10 |
Originally posted by nicoursi
Hey! guarda che le matrici con le liste non hanno niente a che fare! Le matrici non sono dinamiche e di conseguenza si rischia di occupare spazio inutilmente.... con le liste invece no! LA lista è dinamica e la dimensione può variare durante l'esecuzione. L'aspetto negativo delle liste sta nelle scansioni.....
Corregetemi se sbaglio..
Non sbagli:) |
| lord2y |
Originally posted by gallu10
Non sbagli:)
ti consglio di dare un occhi ad algoritmi in C |
| nicoursi |
Originally posted by lord2y
ti consglio di dare un occhi ad algoritmi in C
Spiega xkè non dovrebbe essere così... l'array non è altro che 1 o + locazioni di memoria consecutive... la lista concatenata invece no. Spiega e dimostra il contrario così se c'è da imparare impariamo tutti :) |
| lord2y |
Originally posted by nicoursi
Spiega xkè non dovrebbe essere così... l'array non è altro che 1 o + locazioni di memoria consecutive... la lista concatenata invece no. Spiega e dimostra il contrario così se c'è da imparare impariamo tutti :)
veramente ti stavo dando ragione...e se guardi indietro sono stato io il primo a suggerire le liste concatenate...
vedi tu...sembrava solo che ci fossero un po' di idee confuse..un occhio alla teoria nn fa male...:D
:ciao: |
| AlphaGamma |
Ma siamo in tantissimi!!!!!!
Non credo che l'uso di grafi sia la strada migliore.
E nemmeno il solo uso di liste (un delirio poi nella gestione, oltre alla complessita' lineare).
Gli alberi sono e restano l'unica vera strada percorribile (non veniamo dalle scimmie? :lol: ok basta battute).
Il cammino minimo puo' essere implementato attraverso un albero, mentre resta centrale la rappresentazione dei punti nel piano. Io sto facendo un albero binario. Secondo me questo dovrebbe semplificare moltissimo l'implementazione perche' diventa facile e veloce fare una funzione di ricerca su un albero binario. |
| Skanky |
scusa ma un labero binario implica che da un nodo partano al massimo 2 lati per collegarsi ad altri 2 nodi .....ma nel progetto potrebbero benissimo essere 3 i lati......non capisco proprio perhè albero binario....
Ale |
| crime |
Ragazzi, state fraintendendo. La differenza tra dinamico e statico e' ben consolidata nella testa di tutti.
Siccome nei precedenti progetti (Minlife,Life) veniva espressamente recitato di utilizzare strutture dinamiche invece di quelle statiche, mentre in questo parla di non utilizzare una rappresentazione del piano con matrici o strutture analoghe, mi viene in mente: e se uso una struttura dinamica che mi mappa il piano come una matrice? Ossia una matrice di NxM con N liste contenenti ogni nodo una lista di M nodi? Avete capito il senso? Credo che non ci siano problemi.
Comunque ieri sera ho scoperto tante belle cose sul capitolo 25 e 26. Vi consiglio di guardarli. |
| Skanky |
Grazie del consiglio...in effetti il libro ci viene proprio in aiuto .....
liste di adiacenza o matrice di adiacenza dovrebbero fare al caso nostro.
Cap 22 edizione in inglese Second edition...in italiano magari campia il numero del cap ma non di molto |
| dario |
QUALCUNO SA CHE ALGORITMO SI USA PER SAPERE TUTTI I CAMMINI POSSIBILI DA UN VERTICE A UN ALTRO DI UN GRAFO ?
GRAZIE. |
| dan |
Scusate ma di che libro state parlando ... della dispensa di Goldwurm per caso??
D. |
| Skanky |
Il libro è appunto il Cormen (nome autore) vera bibbia degli algoritmi (con la dispensa di goldwurm ...ehm ...ehm :uhmehehe: non ci fai molto)
autore: cormen
titolo: introduction to algorithms
c' è anche in italiano e anche se si chiama introduction sembra l' lelenco telefonico
cià |
| Wolf |
| Secondo me il tempo lineare va bene (vedi nuovo thread) |
| Wolf |
Una semplice matrice (non di liste) secondo me è inadeguata
perchè richiederebbe di effettuare una ricerca in tutta la matrice
anche quando i punti sono veramente pochi, allungando i tempi
di esecuzione! |
| Skanky |
Il problema è che non sai quanto è grossa la matrice.
Non c' è limite di input ...per questo devi programmare dinamicamente , se ti avesse detto in un piano grosso "tot" avresti potuto usare una bella matriciona...ma purtroppo cosi' non è
ciao ciao |
| Wolf |
| Ma Skanky parli con me? Senza offesa ma... sai leggere? Ho detto che è inadeguata! |
| Wolf |
| Credo che sul libro di algoritmi lo trovi (verso il cap 22 o giù di lì) |
| filuferro |
Originally posted by Wolf
Ma Skanky parli con me? Senza offesa ma... sai leggere? Ho detto che è inadeguata!
conosco skanky.
non sa leggere.
soprattutto in questo periodo.
(ola skanky)
f. |
| lord2y |
Originally posted by Wolf
Una semplice matrice (non di liste) secondo me è inadeguata
perchè richiederebbe di effettuare una ricerca in tutta la matrice
anche quando i punti sono veramente pochi, allungando i tempi
di esecuzione!
a parte che nn la puoi usare perchè è esplicitamente vietato dalle specifiche |
| AlphaGamma |
Originally posted by Skanky
scusa ma un labero binario implica che da un nodo partano al massimo 2 lati per collegarsi ad altri 2 nodi .....ma nel progetto potrebbero benissimo essere 3 i lati......non capisco proprio perhè albero binario....
Ale
Attenzione. Io memorizzo su un albero binario i punti, NON il percorso. In questo modo inserimento, cancellazione e ricerca diventano operazioni semplici ed efficienti.
Cmq secondo me c'e' un po' troppa confusione.
NON si possono usare matrici, NE' e' conveniente farlo.
Si possono usare liste, ma sono difficili da mantenere e lente come efficienza.
Si possono usare alberi e sono decisamente piu' efficienti e comodi.
Si possono usare grafi (per liste di adiacenza) tuttavia se i grafi NON sono in programma vuol dire che ESISTONO metodi alternativi per memorizzare dati in memoria.
Infine, esistono anche le tabelle hash. Inserimento e cancellazione O(1), uso di array, indirizzamento aperto.
Infine, scaricatevi il codice dei progetti che sono stati fatti e che sono qui sul dsy (area filez, esame di algoritmi). In particolare e' utile quello di Mino (non a caso e' admin). |
| rafnet |
| Qualcuno ha iniziato a metterlo giù con qualche struttura?? io sono in mare aperto e sto andando alla deriva con una tempesta in arrivo e un uragano dietro al chapet! |
| piuma82 |
| Ma come cavolo si può attraversare un grafo se in tutti i libri scrivono la procedura in pseudocodice ?!?! |
| crime |
| Come tieni memorizzato il percorso? Mettendo una flag che indichi la strada. E per calcolare il percorso minimo presente tra due punti interni della strada, che algoritmo usi? Ogni idea e' benvenuta! |
| dankan |
You wrote:
Infine, scaricatevi il codice dei progetti che sono stati fatti e che sono qui sul dsy (area filez, esame di algoritmi). In particolare e' utile quello di Mino (non a caso e' admin).
Scusami ma qual'è il progetto di Mino ?
Grazie Mille
Dankan |
| Lunik |
| Progetto "MiniLife" è quello di Mino ...credo.....o "Life"??? |
| lord2y |
Originally posted by piuma82
Ma come cavolo si può attraversare un grafo se in tutti i libri scrivono la procedura in pseudocodice ?!?!
On line trovi tutti gli algoritmi di cui hai bisogno (e cmq esiste algoritmi in c)
Io credo che si debba usare un grafo non orientato aciciclico.
La struttura da utilizzare credo sia quella a liste concatenate...l'unica perplessità che nasce è l'attraversamento del grafo che non è del tutto performante...
non siete gli unici nei c****i...questo progetto non è proprio semplice anzi :( :( |
| AlphaGamma |
Il grafo e' ciclico.
Sono le strade che devono essere prive di cicli.
Mi sembra che lo stesso esempio mostrato nel progetto contenga un ciclo. |
| lord2y |
| si mi sono epresso male..il grafo può essere ciclico, però le strade devono essere prive di cicli... |
| piuma82 |
scusate, sarò stupida, ma davvero non trovo come si faccia a visitare un grafo in ampiezza in linguaggio c...
Qualcuno mi può aiutare? |
| M3lkor |
Scusa ma se l'algoritmo è scritto in pseudo codice un motivo c'è... ed è che SEI tu ad adattare il codice ad un algoritmo non il contrario.
Comunque dando un occhiata al progetto (molto di sfuggita ad essere sincero) non mi è sembrato un eccessivo casino. Si ok sulla difficoltà di implementazione di alcuni passaggi ma in linea di massima il vero problema è la scelta di una struttura dati adeguata.
Una matrice è poco adeguata perchè non dinamica e inoltre è un metodo poco elegante a mio parere: va bene per Programmazione ma non per un esame più avanzato.
Una liste di liste è parecchio lenta ma forse a livello logico più semplice da implementare anche se poi potrebbe essere un mezzo casino da gestire.
Un albero è una soluzione interessante ma forse non un semplice bi-albero... forse è meglio un rb... Non so sinceramente su due piedi...
Forse una tabella HASH sarebbe interessante da utilizzare...
Per il resto non so che dirvi dato che in questo appello non posso partecipare del vostro dolore ;)
Melkor |
| Wolf |
| Problema: come cavolo faccio a prendere in ingresso una maledetta stringa di dimensioni qualsiasi?? |
| lord2y |
...
main(){
char *stringa;
scanf("%s", stringa);
}
problema risolto...però poi devi tokenizzare l'input |
| Cancer |
Originally posted by lord2y
...
main(){
char *stringa;
scanf("%s", stringa);
}
problema risolto...però poi devi tokenizzare l'input
Ehm...Io non farei proprio cosi... Insomma, il tuo puntatore char stringa punta ad un area di memoria non riservata...Insomma, con quella scanf vai a scrivere in un'area di memoria che non hai allocato... Cosi non funza proprio...O meglio: potrebbe X CASO funzionare se l'area di memoria puntata da stringa (che e' random) fosse libera. Il chè non è per niente detto...
Ciao! |
| lord2y |
vers. 1.2
#define DIM 1000
main(){
char stringa[DIM];
/*dimensiono una stringa di 1000*/
scanf("%s", stringa);
}
... |
| AlphaGamma |
In questo caso violi le specifiche del progetto che NON DEVE porre limiti alla lunghezza delle strade.
Molto piu' semplicemente, ho deciso di leggere da stdin carattere per carattere, poi col carattere devo ancora decidere cosa fare.
PS: ho messo on line nell'area filez->esame di algoritmi->progetto itinerari un piccolo programmino che genera strade casuali generando un output compatibile con l'input richiesto dal progetto. Potrebbe essere utile quando fate debugging nella costruzione delle strade.
Il link e' questo:
http://www.dsy.it/forum/showthread....44432#post44432 |
| AlphaGamma |
Originally posted by M3lkor
Scusa ma se l'algoritmo è scritto in pseudo codice un motivo c'è... ed è che SEI tu ad adattare il codice ad un algoritmo non il contrario.
Non sono del tutto d'accordo. ;)
Il codice in C in un corso di algoritmi e' direttamente implementabile, modificabile e quindi piu' facilmente comprensibile (perche' e' empiricamente verificabile).
Inoltre il tuo lavoro non deve consistere nel TRADURRE ma nell'ADATTARE il codice esistente.
In altre parole non dobbiamo reinventare la ruota. Tantopiu' che 16 giorni sono pochi.
Comunque dando un occhiata al progetto (molto di sfuggita ad essere sincero) non mi è sembrato un eccessivo casino.
L'implementazione del cammino piu' breve e la cancellazione di tutti i cammini sono algoritmi complessi che richiedono attenzione sia nella scelta della struttura dati che nella implementazione.
Ok, non sono molto esperto di C e di programmazione, so qualcosina della teoria, pero' a me sembra un progetto assolutamente non banale per il poco tempo a disposizione. |
| Cancer |
Originally posted by lord2y
vers. 1.2
#define DIM 1000
main(){
char stringa[DIM];
/*dimensiono una stringa di 1000*/
scanf("%s", stringa);
}
cmq la scanf mi inizializza a null il puntatore azzerando l'area di memoria...
Cosa intendi per "scanf inizializza a null il puntatore azzerando l'area di memoria"? Guarda ti assicuro che scanf il puntatore non lo tocca proprio...
Comunque se vuoi ti do un consiglio su come leggere una stringa di lunghezza arbitraria (almeno,come farei io,poi ci sono 1000 modi!):
Allochi un area di memoria di N bytes, leggi un carattere alla volta da stdin, se arrivi a leggere N caratteri, reallochi ulteriori N bytes (quindi 2N in tutto) e cosi via...
Ciao! |
| dan |
Cosa ne dite di un albero costituito da nodi con 4 figli a testa (denominati magari N S W E), i cui puntatori possano essere NULL o puntare al nodo che seguono il nodo nelle varie direzioni.
Non so però come implementare il numero di strade passanti per quel nodo!! :(
D. |
| lord2y |
Originally posted by Cancer
Cosa intendi per "scanf inizializza a null il puntatore azzerando l'area di memoria"? Guarda ti assicuro che scanf il puntatore non lo tocca proprio...
Comunque se vuoi ti do un consiglio su come leggere una stringa di lunghezza arbitraria (almeno,come farei io,poi ci sono 1000 modi!):
Allochi un area di memoria di N bytes, leggi un carattere alla volta da stdin, se arrivi a leggere N caratteri, reallochi ulteriori N bytes (quindi 2N in tutto) e cosi via...
Ciao!
infatti ho detto che questa nn era la soluzione giusta..
Per evitare di incorrere in seg fault, problemi di lunghezza di stringa uso un getchar per prendere il singolo carattere ponendo la condizione ... != '\n' .
La scanf la uso solo per prendere in input le coordinate del punto.
:ciao:
Ps s vuoi saperne di più sulla scanf --> da prompt man scanf |
| lord2y |
Originally posted by AlphaGamma
Non sono del tutto d'accordo. ;)
Il codice in C in un corso di algoritmi e' direttamente implementabile, modificabile e quindi piu' facilmente comprensibile (perche' e' empiricamente verificabile).
Inoltre il tuo lavoro non deve consistere nel TRADURRE ma nell'ADATTARE il codice esistente.
In altre parole non dobbiamo reinventare la ruota. Tantopiu' che 16 giorni sono pochi.
L'implementazione del cammino piu' breve e la cancellazione di tutti i cammini sono algoritmi complessi che richiedono attenzione sia nella scelta della struttura dati che nella implementazione.
Ok, non sono molto esperto di C e di programmazione, so qualcosina della teoria, pero' a me sembra un progetto assolutamente non banale per il poco tempo a disposizione.
apro una parentesi polemica:
il progetto è complesso. Il tempo è poco e il laboratorio di C che accompagnava le lezioni di algoritmi è stato del tutto inutile. Certi aspetti della programmazione in C nn sono stati minimamente visti..E certo esempi di strutture dati simili a quella che dovremo usare per implementare questo progetto non sono neanche stati accenati...
Quindi...........
chiudo la parentesi polemica |
| Cancer |
Originally posted by lord2y
infatti ho detto che questa nn era la soluzione giusta..
Per evitare di incorrere in seg fault, problemi di lunghezza di stringa uso un getchar per prendere il singolo carattere ponendo la condizione ... != '\n' .
La scanf la uso solo per prendere in input le coordinate del punto.
:ciao:
Ps s vuoi saperne di più sulla scanf --> da prompt man scanf
Mah,dal tuo primo messaggio a riguardo mi sembra che tu volessi rispondere a chi aveva chiesto come leggere una stringa di lunghezza arbitraria...
Comunque se sappiamo tutti come farlo non c'è più nessun problema!:-D
L'unica cosa (e man scanf te lo potra' confermare) e' che scanf non ci pensa proprio a inizializzarti a null il puntatore... (bho, forse ho interpretato ancora male io quello che hai scritto, ma hai proprio detto "cmq la scanf mi inizializza a null il puntatore azzerando l'area di memoria... ").
Ri-Ciao! |
| nous |
Originally posted by M3lkor
Forse una tabella HASH sarebbe interessante da utilizzare...
Melkor
Secondo me sarebbe divertente usare la heap ;) |
| nous |
Originally posted by Wolf
Problema: come cavolo faccio a prendere in ingresso una maledetta stringa di dimensioni qualsiasi??
Copio e incollo dal mio progetto,adattatevelo al vostro caso :
int readline(FILE *stream, char **buffer) {
#define TBSIZE 10
int in_buffers=0;
char tmpbuf[TBSIZE+1]={0};
char *newline;
do {
in_buffers++;
*buffer=realloc(*buffer, in_buffers*TBSIZE*sizeof(char)+1);
if (!(*buffer)) return ERROR_CANT_MALLOC;
if (fgets(tmpbuf,TBSIZE+1,stream)==NULL) {
if(in_buffers==1) return ERROR_EOF;
else return 0;
}
newline=strchr(tmpbuf,'\n');
if(newline) *newline='\0';
strcpy((*buffer)+(in_buffers-1)*TBSIZE, tmpbuf);
} while (!newline);
return 0; |
| rafnet |
Originally posted by Cancer
...
Comunque se sappiamo tutti come farlo non c'è più nessun problema!.....
Calma, calma io no ci ho capito un h, ho usato una normale stringa per prendere in input il percorso che per quanto lungo sia non potrà mai colmare la dimensione di una stringa no?
:ban: |
| M3lkor |
Originally posted by AlphaGamma
Non sono del tutto d'accordo. ;)
Il codice in C in un corso di algoritmi e' direttamente implementabile, modificabile e quindi piu' facilmente comprensibile (perche' e' empiricamente verificabile).
Inoltre il tuo lavoro non deve consistere nel TRADURRE ma nell'ADATTARE il codice esistente.
In altre parole non dobbiamo reinventare la ruota. Tantopiu' che 16 giorni sono pochi.
L'implementazione del cammino piu' breve e la cancellazione di tutti i cammini sono algoritmi complessi che richiedono attenzione sia nella scelta della struttura dati che nella implementazione.
Ok, non sono molto esperto di C e di programmazione, so qualcosina della teoria, pero' a me sembra un progetto assolutamente non banale per il poco tempo a disposizione.
Ok sono d'accordo su alcuni punti... Diciamo che il tempo a disposizione non è sufficentemente lungo perchè tutti riescano a farlo. Ma rimane comunque una cosa non eccessivamente complessa escludendo il fattore tempo.
Non sono d'accordo sugli algoritmi. Un algoritmo deve essere utilizzabile con goni tipo di linguaggio e quindi non deve essere scritto in un linguaggio specifico proprio perchè noi dovremmo, in teoria, estrapolare dall'algoritmo il codice nel linguaggio che ci interessa. D'altro canto un algoritmo di per sè è un insieme di "istruzioni" che permettono il compimento di un compito in un tempo "x". Che poi tu lo scriva in Java, in C, in C++, in Perl, in CGI, in Algol o in Fortran la cosa cambia relativamente poco...
Questo presumo fosse lo scopo del corso... che poi sia più comodo che gli algoritmi vengano presentati nel linguaggio che poi sarà quello del progetto finale.... beh questo è ovvio che renderebbe le cose più semplici ;)
Melkor |
| nous |
| Trasudi saggezza,concordo su te in tutto e ti stringo virtualmente la mano ;) |
| Lestat de lioncourt |
Alphagamma, mi spieghi un po' meglio la tua idea per utilizzare gli alberi in questo prog.?
Sul pdf dell'ultima lezione di Fiorentini a pag.5 c'è un esempio in cui usa un albero di ricerca per rappresentare i punti del piano.
Se ogni nodo rappresenta i punti, dove memorizzi l'informazione relativa al reale percorso esistente fra questi punti?
Se tale info è rappresentata dai legami di parentela fra i nodi, l'albero rappresentato non degenera quasi in una lista nel caso del nostro progetto?
A parte che una volta che le strade iniziano ad incrociarsi non ci si trova più davanti ad un albero, ma ad un grafo, perchè si creano dei cicli.
:help:
Io sto usando un grafo non orientato rapp. con liste d'adiacenza |
| AlphaGamma |
Originally posted by M3lkor
Non sono d'accordo sugli algoritmi. Un algoritmo deve essere utilizzabile con goni tipo di linguaggio e quindi non deve essere scritto in un linguaggio specifico proprio perchè noi dovremmo, in teoria, estrapolare dall'algoritmo il codice nel linguaggio che ci interessa. D'altro canto un algoritmo di per sè è un insieme di "istruzioni" che permettono il compimento di un compito in un tempo "x". Che poi tu lo scriva in Java, in C, in C++, in Perl, in CGI, in Algol o in Fortran la cosa cambia relativamente poco...
Melkor
Credo che esistano almeno due modi per approcciarsi a questa materia, uno piu' marcatamente teorico, ed uno piu' orientato ad applicazioni pratiche.
Se l'approccio e' teorico allora va bene una rappresentazione degli algoritmi indipendente dall'architettura dell'elaboratore. Questo e' utile per studi matematici sugli algoritmi, per mostrare il "nudo" algoritmo senza perdersi in "noiose" questioni di contorno.
Se tuttavia la finalita' principale dello studio e' alla fin fine una applicazione pratica, diventa assolutamente prioritario riferirsi ad un reale linguaggio di programmazione, che sappia implementare tutte le caratteristiche degli algoritmi.
In altre parole se sei interessato all'informatica piu' teorica, allo studio della complessita', la struttura degli algoritmi o problemi simili, vale il primo approccio. Se invece vuoi imparare a programmare, ed imparare a farlo bene, segui necessariamente una strada concretamente praticabile e sperimentale.
Questo tipo di scelta e' indipendente dall'esistenza o meno di un progetto finale in C. Si tratta infatti dell'ennesima riproposizione di una questione esistente in moltissimi esami.
Personalmente ho scelto per la seconda, perche' l'informatica mi appassiona per le sue applicazioni e perche' un domani dovrebbe darmi da mangiare.
Pertanto ben vengano delle soluzioni pratiche a quelli annosi problemi che parlano di implementazione pratica, di definizione di variabili, e tutto il resto.
Quindi credo che il lavoro di uno studente di algoritmi debba essere prima di tutto non quello di tradurre in C cose scritte in pseudolinguaggio, ma di adattarle alle proprie esigenze.
Anche Nous che contesta questa mia idea alla fin fine quando ha postato il codice per inserire strighe di dimensione a piacere mica ha usato un pseudolinguaggio. Li ha postati in maniera direttamente utilizzabile ed adattabile. Cioe' in C. |
| AlphaGamma |
Originally posted by Lestat de lioncourt
Alphagamma, mi spieghi un po' meglio la tua idea per utilizzare gli alberi in questo prog.?
Sul pdf dell'ultima lezione di Fiorentini a pag.5 c'è un esempio in cui usa un albero di ricerca per rappresentare i punti del piano.
Io ho usato un albero binario per memorizzare i punti, ed uno 4-ario per memorizzare gli itinerari.
Devo ancora vedere se funziona. :D |
| M3lkor |
Beh il codice che ha postato era direttamente riferito al progetto in questione se non erro...
Il corso di Algoritmi e Strutture DAti è invece di applicazione teorica con un esame di Laboratorio che richiede un applicazione pratica, con un linguaggio, di ciò che si è imparato nelle lezioni di Algoritmi.
In altre parole. Io credo che un corso di Algoritmi in C (ad esempio) sarebbe forse più dannoso in quanto non darebbe la capacità di astrare (corretto?) dallo pseudo codice un programma in un linguaggio diverso dal C... In altre parole il rischio sarebbe quello di avere dei Tecnici Informatici non dei Laureati in Informatica. La cosa è ben diversa anche se magari l'applicazione i risultati possono (notare: possono) essere uguali.
Nel senso. Se io specializzo una persona a livelli estremi questa difficilmente riuscirà ad uscire dagli schemi della specializzazione con risultati accettabili. Es. Se io ti insegno solo C, con tutte le librerie, tutti gli exploit utilizzabili per rendere i programmi C migliori etc etc se tu non hai la capacità di adattare la tua conoscenza in altri campi sei fregato. Ma se io ti dò una conoscenza di Algoritmi in maniera più generale e poi ti dò le basi di un pò di linguaggi, magari con più tempo, tu riesci a sfruttare tutti gli algoritmi con tutti i linguaggi e non tutti gli algoritmi con un solo linguaggio.
Penso che alla fine sia il problema del dare il pesce o la canna da pesca. Tu preferisci il pesce da quanto ho capito mentre secondo me è meglio la canna da pesca (magari con un corso su come usarla bene ;) ).
Ciauz
Melkor |
| Lunik |
non ho capito una cippa dei vostri discorsi,ma volevo solo essere sicura di una cosa: sapete che il progetto E' da fare in C? e non con altri linguaggi?
solo x curiosità.... ;) |
| nous |
Originally posted by AlphaGamma
Anche Nous che contesta questa mia idea alla fin fine quando ha postato il codice per inserire strighe di dimensione a piacere mica ha usato un pseudolinguaggio. Li ha postati in maniera direttamente utilizzabile ed adattabile. Cioe' in C.
Accidenti,mi sono fregato...quasi quasi cancello il post :D:D
Peccato che questo modo di postare renda l'algoritmo meno leggibile che se lo avessi fatto in pseudocodice.
In più,la mia era una risposta a una domanda schietta (come faccio in C a fare questa cosa?) , non a una del tipo "Quale algoritmo useresti per farlo?" |
| nous |
Originally posted by AlphaGamma
Credo che esistano almeno due modi per approcciarsi a questa materia, uno piu' marcatamente teorico, ed uno piu' orientato ad applicazioni pratiche.
E le due cose sono disgiunte totalmente,secondo te?
Personalmente ho scelto per la seconda, perche' l'informatica mi appassiona per le sue applicazioni e perche' un domani dovrebbe darmi da mangiare.
Ma scusa,dopodomani esce il linguaggio di programmazione C### e tu che fai,visto che gli algoritmi li sai fare solo in C??
Secondo me bisogna capire la logica dell'algoritmo,e per questo lo psudo codice è ottimo.Secondo me la materia per essere capita deve essere disgiunta da ogni implementazione.
Poi il progetto serve a vedere se si sa applicare quello che si studia. |
| lord2y |
Io credo che una volta che hai imparato a programmare lo puoi fare in qualunqe linguaggio...basta solo capire la sintassi e imparare i trucchi con un po' di esercizio.
Per quanto riguarda algoritmi credo che vedere un algoritmo in un contesto pratic aiuta..Teorizzare troppo fa male. Il pseudo codice è spesso troppo astratto...mentre nn ci impiego niente a fare il porting da C a java a C#### a php etc...
Come giustamente diceva qualcuno è la logica quella da seguire.
Per quanto rigarda il discorso dell'"essere tecnico"...bhe credo che noi dovremmo essere dei tecnici proffessionisti...non credete?
:ciao: |
| M3lkor |
Originally posted by lord2y
Io credo che una volta che hai imparato a programmare lo puoi fare in qualunqe linguaggio...basta solo capire la sintassi e imparare i trucchi con un po' di esercizio.
Per quanto riguarda algoritmi credo che vedere un algoritmo in un contesto pratic aiuta..Teorizzare troppo fa male. Il pseudo codice è spesso troppo astratto...mentre nn ci impiego niente a fare il porting da C a java a C#### a php etc...
Come giustamente diceva qualcuno è la logica quella da seguire.
Per quanto rigarda il discorso dell'"essere tecnico"...bhe credo che noi dovremmo essere dei tecnici proffessionisti...non credete?
:ciao:
Azz allora ho sbaglio corso di Laurea... sinceramente il porting lo fai seguendo una logica che ti è data dall'esperienza... Ma se vai a controllare la tua logica può essere ridotta ad algoritmi... che sono esplicitati in pseudo codice... Cioè il tuo programma lo riduci astrattamente in pseudocodice quando fai un porting... non te ne rendi conto ma lo fai...
E comunque non credo che tu faccia un porting ma una rielaborazione del programma in altro linguaggio...
Melkor |
| AlphaGamma |
Originally posted by M3lkor
[B]In altre parole. Io credo che un corso di Algoritmi in C (ad esempio) sarebbe forse più dannoso in quanto non darebbe la capacità di astrare (corretto?) dallo pseudo codice un programma in un linguaggio diverso dal C... In altre parole il rischio sarebbe quello di avere dei Tecnici Informatici non dei Laureati in Informatica. La cosa è ben diversa anche se magari l'applicazione i risultati possono (notare: possono) essere uguali.
Sarebbe da capire qual'e' la differenza secondo te tra un tecnico informatico ed un laureato informatico.
Sulla dannosita' proprio non capisco. Se vai a lavorare in una azienda ti chiedono se sai programmare in C++ o Java (discendenti del C), non se sai fare il quicksort in pseudocodice.
Se invece vuoi approfondire lo studio, allora lo pseudocodice e' un utile strumento ed in quel caso il C e' del tutto inutile.
Ma in entrambi i casi non c'e' nulla di dannoso.
Se poi parli di portare un sorgente in un altro linguaggio, vedo meno difficolta' a portare codice dal C al Visual Basic che dal pseudolinguaggio al Visual Basic.
Nel senso. Se io specializzo una persona a livelli estremi questa difficilmente riuscirà ad uscire dagli schemi della specializzazione con risultati accettabili. Es. Se io ti insegno solo C, con tutte le librerie, tutti gli exploit utilizzabili per rendere i programmi C migliori etc etc se tu non hai la capacità di adattare la tua conoscenza in altri campi sei fregato. M
Il C e' un linguaggio di alto livello, non e' assembler.
E' molto potente, e puo' essere utilizzato sia per fare programmi ultra ottimizzati, sia per scrivere programmi strutturati classici come si studiano all'uni.
Ripeto, vedo meno difficolta' a portare codice da C ad altri linguaggi che dallo pseudocodice a qualsiasi linguaggio.
Penso che alla fine sia il problema del dare il pesce o la canna da pesca. Tu preferisci il pesce da quanto ho capito mentre secondo me è meglio la canna da pesca (magari con un corso su come usarla bene ;) ).
Penso che la distinzione sia piu' che io preferisco andare a pescare trote anche se devo mettere i vermetti sull'amo, mentre a te non piacciono i vermetti e lanci solo la lenza. Tu sostieni che cosi' pero' peschero' solo trote, io ritengo che i pesci sono tutti uguali e tutti vogliono i vermetti. :D |
| AlphaGamma |
Originally posted by nous
(1)Peccato che questo modo di postare renda l'algoritmo meno leggibile che se lo avessi fatto in pseudocodice.
(2)In più,la mia era una risposta a una domanda schietta (come faccio in C a fare questa cosa?) , non a una del tipo "Quale algoritmo useresti per farlo?"
(1) La leggibilita' e' molto opinabile. Finora ho capito di piu' leggendo codice C che pseudolinguaggio. ;)
(2) Come in tutti i problemi pratici, occorre dare una soluzione pratica. ;) Appunto quel che sostengo. |
| AlphaGamma |
Originally posted by nous
E le due cose sono disgiunte totalmente,secondo te?
Leggi con attenzione quel che ho scritto.
Ma scusa,dopodomani esce il linguaggio di programmazione C### e tu che fai,visto che gli algoritmi li sai fare solo in C??
Secondo me bisogna capire la logica dell'algoritmo,e per questo lo psudo codice è ottimo.Secondo me la materia per essere capita deve essere disgiunta da ogni implementazione.
Poi il progetto serve a vedere se si sa applicare quello che si studia. [/B]
Scrivere ad esempio quicksort in C e passarlo in Pascal o Basic e' meno difficile IMHO che farlo da pseudocodice. Prima di tutto perche' i costrutti utilizzati esistenti sono simili (while, if, for), in secondo luogo perche' ci sono le condizioni di contorno (se uso la variabile X allora devo dichiararla), terzo perche' le strutture dati dinamiche fanno uso di puntatori, che nello pseudolinguaggio sono molto semplificati, quarto perche' una riga in pseudocodice spesso puo' significare diverse righe di codice reale.
Se un domani esce Java# ed e' cosi' diverso dai predecessori, allora nemmeno il nostro pseudocodice sara' utile. Ma non credo che sara' cosi'. Infatti sia lo pseudocodice che i linguaggi attuali non differiscono in maniera sostanziale, perche' derivano dalla comune necessita' di fare eseguire o assegnazioni o cicli o confronti o salti. Non si scappa da qui. :D
Lord2y :approved: |
| Nonsaprei |
Originally posted by Lestat de lioncourt
Alphagamma, mi spieghi un po' meglio la tua idea per utilizzare gli alberi in questo prog.?
Sul pdf dell'ultima lezione di Fiorentini a pag.5 c'è un esempio in cui usa un albero di ricerca per rappresentare i punti del piano.
Se ogni nodo rappresenta i punti, dove memorizzi l'informazione relativa al reale percorso esistente fra questi punti?
Se tale info è rappresentata dai legami di parentela fra i nodi, l'albero rappresentato non degenera quasi in una lista nel caso del nostro progetto?
A parte che una volta che le strade iniziano ad incrociarsi non ci si trova più davanti ad un albero, ma ad un grafo, perchè si creano dei cicli.
:help:
Io sto usando un grafo non orientato rapp. con liste d'adiacenza
Penso che la scelta del grafo non orientato sia giusta, mi lascia un po' perplessa quella delle liste d'adiacenza, non sarebbe meglio utilizzare degli alberi liberi....:cool: |
| rafnet |
Ragazzi sono il primo ad aver rinunciato???
Ci vediamo all'appello di aprile |
| Lestat de lioncourt |
Originally posted by Nonsaprei
Penso che la scelta del grafo non orientato sia giusta, mi lascia un po' perplessa quella delle liste d'adiacenza, non sarebbe meglio utilizzare degli alberi liberi....:cool:
con le liste d'adiacenza abbiamo già qualke algoritmo semi-pronto
e visto ke già così sono sull'orlo dell'esaurimento preferisco semplificarmi la vita. :( |
| Nonsaprei |
| Sì, in effetti, è meglio semplificarsi la vita!! :approved: :approved: |
| lord2y |
Originally posted by Lestat de lioncourt
con le liste d'adiacenza abbiamo già qualke algoritmo semi-pronto
e visto ke già così sono sull'orlo dell'esaurimento preferisco semplificarmi la vita. :(
non sei l'unico :cry: |
| rafnet |
Originally posted by Lestat de lioncourt
con le liste d'adiacenza abbiamo già qualke algoritmo semi-pronto
e visto ke già così sono sull'orlo dell'esaurimento preferisco semplificarmi la vita. :(
Potreste indicarmi dove si trovano questi esempi?? che non li trovo |
| lord2y |
Originally posted by rafnet
Potreste indicarmi dove si trovano questi esempi?? che non li trovo
su algoritmi in c oppure sul cormen |
| Lestat de lioncourt |
Originally posted by rafnet
Potreste indicarmi dove si trovano questi esempi?? che non li trovo
bè, costruendo il grafo con delle liste, le operazioni base sono quelle negli ultimi 3 pdf di Fiorentini.
In più per le funzioni distanza e separa credo risultino utili
alcuni algoritmi sul cormen CAP. 23 edizione italiana...
...in particolare la visita in ampiezza potrebbe essere utile per la funz. distanza.
Cmq sono solo idee, non sono ancora riuscito a rendere funzionante la crea(). :evil:
bye |
| gallu10 |
| ragazzi qualcuno di voi è riuscito a implementare la funzione separa?mi sembra impossibile!!!!!!!! |
| AlphaGamma |
Implementare e' un parolone! :D
Se per implementare intendi fare codice che compila e fa quel che dicono le specifiche. :D
PS: l'unica cosa che sono riuscito a implementare (al momento) e' che adesso inserisco n strade da prompt e le inserisce, e se voglio eliminare un qualsiasi tratto unitario, lo elimina eventualmente spezzando la strada in due. |
| Giz |
Che strippoooooooo!
Chi mi passa il codice che và è un grande!
GiZ |
| nous |
| Fortuna che ho fatto l'appello prima...che culo ;) |
| Lunik |
Originally posted by Giz
Che strippoooooooo!
Chi mi passa il codice che và è un grande!
GiZ
:nono:
non puoi fare richieste simili nel forum..... |
| livio_82 |
ma non era una richiesta.
Stava solo dicendo che se qualcono ipoteticamente glielo passasse, sarebbe un GRANDE. |
| Lunik |
"Chi mi manda il codice.."
non mi sembra ipotetico...
e poi non :climb: ... siamo tutti studenti...
;) |
| M3lkor |
Originally posted by Lunik
"Chi mi manda il codice.."
non mi sembra ipotetico...
e poi non :climb: ... siamo tutti studenti...
;)
Se un qualcuno CASUALMENTE mi facesse trovare nel tavolo un sorgente FUNZIONANTE io potrei altrettanto CASUALMENTE raccoglierlo e farlo mio lasciando al posto dei fogli una somma per risarcire le spese... un 100 EURO!
:D :D :D :D |
| livio_82 |
hehe, si dai... non era serio il mio post...
Cmq io son ancora + disperato di Giz, ma mi contengo... |
| AlphaGamma |
Originally posted by livio_82
ma non era una richiesta.
Stava solo dicendo che se qualcono ipoteticamente glielo passasse, sarebbe un GRANDE.
Sei un GRANDE. :D :lol: :wall: |
| AlphaGamma |
Originally posted by M3lkor
Se un qualcuno CASUALMENTE mi facesse trovare nel tavolo un sorgente FUNZIONANTE io potrei altrettanto CASUALMENTE raccoglierlo e farlo mio lasciando al posto dei fogli una somma per risarcire le spese... un 100 EURO!
:D :D :D :D
Un mio amico dello staff mi ha detto che circolano i prof qua dentro. Non credo che avrebbero problemi a risalire dal nick al nome reale, in caso di infrazione delle specifiche del loro progetto.
Quindi, occhio. |
| M3lkor |
| LoL a parte il fatto che non sto dando l'esame... Bè che i prof girino mi sembra naturale... e comunque era una cosa scherzosa Alpha! ;) |
| AlphaGamma |
| Io non sono un prof. :D |
| holylaw |
Ma in definitiva quanti di voi sono riusciti a fare qualcosa di serio e soprattutto funzionante (e magari con un albero)??
Vi prego ditemi che non sono l'unico a non aver fatto assolutamente nulla: il mio ego ne risenterebbe troppo... |
| Giz |
Porcazza la miseria....
LUNIKKKKKK... Sii un pò meno seria!! Ti pregoo!!
Cmq la proposta di scavallamento Codice C x progetto Itinerari è + che mai VALIDA!!!!
GIZ |
| Giz |
Cmq, raga, sono veramente in MERDA (si può dire, LunikArompip..?) con gli Itinerari!
Stavo pensando di fare un RB-albero in cui mettere tutti i punti attraversati da tutte le strade (i punti del piano interessati dai possibili percorsi) ed in ogni nodo, oltre alla x e y, mettere il nome delle strade (es. S1, S3) che passando x quel punto. X ciò quando devo cercare se esiste un itinerario, vedo se esiste il nodo (tempo di ricerca log(N) x' RB-albero ordinato) e scansiono i punti vicini x vedere se ci sono punti della stessa strada (se ho (3,5) cercherò (3,6), (3,4),(2,5),(4,5)) e su questi che esistono creo un albero NON binario che ha nella radice (3,5) e da questo si diramano tanti rami quanto i possibili itinerari che ci possono essere. A questo punto mi sono perso anch'io nel mio stesso discorso, è meglio che vado a farmi 2 o 3 mila birre x riordinarmi le idee (e x dimenticarmi dell'esistenza del C) e poi domani posto qualcosa di forse interesante.
Xcusate la lunghezza del sopra
Buona Notte & Justice For All
GIZ |
| Buffone |
Mi è venuta in mente un idea geniale mentre lavoravo sul progetto. Forse potrà essere utile aa alcuni di voi. Forse sono io che sono arrivato in ritardo.
Comunque mi sono appena accorto che una funzione che trovi tutti gli itinerari tra due punti è assolutamente inutile. Basta dirgli di cercare il tratto minimo, cancellarlo ed iterare finchè non ci sono più tratti minimi. Trovare il tratto minimo è una semplice variante dell'algoritmo per trovare la distanza minimia.
Spero sia un idea giusta.
Ciao. |
| AlphaGamma |
Questo algoritmo non e' corretto.
Se tu cancelli il percorso piu' breve, e questo conteneva tratti comuni a percorsi piu' lunghi, avrai che alla seconda chiamata di ricerca ti dirà che i due punti non sono collegati, mentre invece lo erano prima della cancellazione del tratto piu' breve.
Ad esempio nel testo del progetto ti fa come esempio due percorsi possibili per andare dal punto di partenza a quello di arrivo, e ti dice che risultato deve avere una separazione. Se tu cancelli l'itinerario breve, quello lungo rimarrà scollegato, e quindi non sarà mai possibile cancellarlo.
Quindi e' meglio registrarli tutti i percorsi. |
| Lunik |
Originally posted by Giz
Porcazza la miseria....
LUNIKKKKKK... Sii un pò meno seria!! Ti pregoo!!
scusa? I prof girano nel forum..poi se leggono qualcosa che non è "legale" (tipo chiedere il codice) vengono da noi e ci fanno la capa tanta... |
| Cr34t|v3 |
vedo che qualcuno che si impegna c'è davvero. Avrei voluto collaborare anch'io al Progetto Itinerari ma al momento ho altri esami a cui pensare.. In bocca Al LuPo
#include <sys/porcozio.h>
#include <linux/Itinerari.h> |
| Buffone |
Originally posted by AlphaGamma
Questo algoritmo non e' corretto.
Grazie. Me ne sono accorto.
Comunque credo di aver raggiunto quasi la fine. Devo solo vedere perchè ogni tanto mi si blocca ed ogni tanto mi da un segmentation fault. Ed implementare ancora una qualche funzioncina.
Devo però ammettere che il progettino era molto complicato. Ho dovuto scrivere oltre 800 righe di codice !!! |
|
|
|
|
