 | |
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] Problemi vari
Clicca QUI per vedere il messaggio nel forum |
| drakend |
Dato che nel corso di algoritmi è iniziato e di problemi di certo non mancheranno direi che è il caso di aprire un thread apposito in cui raccogliere tutti i problemi che si potrebbero presentare. Comincio subito io: mi sono installato il cs1300 ma non mi va. L'ho installato nella root come indicato nelle istruzioni ed ho provato a compilare il seguente codice di prova:
/* prog1.c */
#include <stdio.h>
int main(void)
{
printf("Salve mondo\n");
return 0;
}
Bene il file lo metto nella subdirectory bin per far sì che il sistema veda gcc.exe (non ho impostato il path, lo farò :D) ma, quando provo ad eseguire questo comando:
gcc -o prog1 prog1.c
Ottengo questo risultato:
C:\cs1300\bin>gcc -o prog1 prog1.c
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: unrecognized option `-remap'
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
cpp: -lang-c: linker input file unused since linking not done
gcc: installation problem, cannot exec `cc1': No such file or directory
C:\cs1300\bin>
Da cosa può dipendere? Eppure le istruzioni di installazioni dicono semplicemente di decomprimere il file zip contenente il compilatore nella root del disco... |
| mixmax |
Originally posted by drakend
Dato che nel corso di algoritmi è iniziato e di problemi di certo non mancheranno direi che è il caso di aprire un thread apposito in cui raccogliere tutti i problemi che si potrebbero presentare. Comincio subito io: mi sono installato il cs1300 ma non mi va. L'ho installato nella root come indicato nelle istruzioni ed ho provato a compilare il seguente codice di prova:
Bene il file lo metto nella subdirectory bin per far sì che il sistema veda gcc.exe (non ho impostato il path, lo farò :D) ma, quando provo ad eseguire questo comando:
gcc -o prog1 prog1.c
Ottengo questo risultato:
Da cosa può dipendere? Eppure le istruzioni di installazioni dicono semplicemente di decomprimere il file zip contenente il compilatore nella root del disco...
E' capitato anche a me (su win 2000 Adv Srv), l'ho risolto riscaricando e riscoppattando lo zip.
PS: ricordati il gocs.bat per settare l'enviroment. |
| maynard80 |
| scusa l'ignoranza, : cos'è gocs.bat? |
| mixmax |
Originally posted by maynard80
scusa l'ignoranza, : cos'è gocs.bat?
hai ragione, traduco in modo piu' comprensibile:
Per poter funzionare, il gcc necessita del settaggio di determinate variabili di ambiente, questo settaggio viene fatto lanciando il file gocs.bat che si trova sotto c:\cs1300 o comunque nella directory "root" dell'installazione del compilatore.
Naturalmente, per evitare di lanciarlo ogni volta che si apre una shell (cmd o command) e' possibile settare le variabili direttamente nell'enviroment di Nt/2000 oppure nell'AUTOEXEC.BAT di win9x. |
| drakend |
| Ecco cos'è che non andava... grazie mixmax :) |
| mixmax |
Originally posted by drakend
Ecco cos'è che non andava... grazie mixmax :)
Prego!
:ciao: |
| drakend |
| Altro problema, questa volta più teorico: Aguzzoli afferma nelle sue dispense che linker e loader sono la stessa cosa (me lo ha confermato pure via email): io ho sempre saputo però che il linker serve a collegare fra loro i vari file oggetto fra loro e con le librerie, insomma serve a risolvere tutti i riferimenti esterni che ci sono in un file oggetto. Il loader invece serve ad allocare in memoria il programma, trasformando gli indirizzi relativi contenuti nell'eseguibile in assoluti per poter essere allocato effettivamente in memoria. Quindi linker e loader NON dovrebbero essere la stessa cosa... |
| Skilotto83 |
| NN ho seguito la lez di vene 3...di laboratorio...ma gli appunti che ci sonop on -line sul sito di Aguzzoli li ha fatti tutti??...36 pagine in tre ore??? |
| drakend |
| Esiste un buon debug passo-passo da associare al compilatore gcc? |
| drakend |
Originally posted by Skilotto83
NN ho seguito la lez di vene 3...di laboratorio...ma gli appunti che ci sonop on -line sul sito di Aguzzoli li ha fatti tutti??...36 pagine in tre ore???
Affermativo, le ha fatte tutte, dalla prima all'ultima. Si tratta comunque di argomenti di base molto semplici, infatti sono molto discorsive. :) |
| mixmax |
Originally posted by drakend
Altro problema, questa volta più teorico: Aguzzoli afferma nelle sue dispense che linker e loader sono la stessa cosa (me lo ha confermato pure via email): io ho sempre saputo però che il linker serve a collegare fra loro i vari file oggetto fra loro e con le librerie, insomma serve a risolvere tutti i riferimenti esterni che ci sono in un file oggetto. Il loader invece serve ad allocare in memoria il programma, trasformando gli indirizzi relativi contenuti nell'eseguibile in assoluti per poter essere allocato effettivamente in memoria. Quindi linker e loader NON dovrebbero essere la stessa cosa...
Hai ragione tu: il linker e il loader sono 2 cose differenti anche perche' il linker "appartiene al package del compilatore", il loader e' parte dell'OS. |
| mixmax |
Originally posted by drakend
Esiste un buon debug passo-passo da associare al compilatore gcc?
Sul sito di Fiorentini e' indicato il ddd. Pero' non so se sia un buon debugger... |
| jccc |
Il ddd è un ottimo debugger purtroppo a linea di comando. esistono, tuttavia, diverse gui che ne integrano le funzionalità in un Window-World.
Se utilizzate Linux, installate allora KDevelop, una IDE Developer Studio Oriented che contiene di già un debugger integrato, nonché un editor molto sofisticato anche se quest'ultimo plus non è richiesto affatto per il corso in questione, anzi, meglio dispensarne (consiglio mio modesto)
ciao |
| drakend |
Originally posted by jccc
Il ddd è un ottimo debugger purtroppo a linea di comando. esistono, tuttavia, diverse gui che ne integrano le funzionalità in un Window-World.
Se utilizzate Linux, installate allora KDevelop, una IDE Developer Studio Oriented che contiene di già un debugger integrato, nonché un editor molto sofisticato anche se quest'ultimo plus non è richiesto affatto per il corso in questione, anzi, meglio dispensarne (consiglio mio modesto)
ciao
Conosci un ide equivalente per Windows? |
| Fonzie |
| Scusate qualcuno può postare l'indirizzo del sito di Trubian, (quella per scaricare i lucidi), perchè haimè non ricordo più dove me l'ero segnato :cry: . Ciao. |
| drakend |
Originally posted by Fonzie
Scusate qualcuno può postare l'indirizzo del sito di Trubian, (quella per scaricare i lucidi), perchè haimè non ricordo più dove me l'ero segnato :cry: . Ciao.
Questo è il sito del professor Trubian:
http://homes.dsi.unimi.it/~trubian/studenti.htm |
| Fonzie |
| Graziaaaaaaaaaa :pazzo: |
| sonica |
Ciao volevo chiedervi alcune cose riguardo agli esercizi tipo compitino che ci ha dato Mr. T giovedì... sto cercando rimettermi in pari col programma e mi stanno saltando fuori grosse lacune...
1) Non mi è chiaro cosa volesse davvero trubian... trovare gli omega piccolo più stretti per quelle 4 funzioni? ma se è solo 4 a che serve una tabella 4x4 che ci ha disegnato? se ho 4 funzioni e devo trovare 4 soluzioni? boh, illuminatemi
3) come si calcola la 5 riga del codice? non ne ho idea, illuminatemi anche qui please
4) la verifica della condizione affinchè sussista il 3 caso: af(n/b) < cf(n) non è troppo difficile? io non la ho verificata, o magari c'è uno stratagemma sparando una c altissima e maggiorandola la prima funzione?
5) abbiamo visto 3 modi per risolvere le ricorrenze: Principale, Iterazione e Sostituzione. a cosa corrisponde il metodo di induzione richiesto da Trubian? Iterazione? io ho usato iterazione ed a lla fine la serie mi diverge, ho sbagliato qualcosa io?
il resto non lo ho ancora guardato, se avrò ltri dubbi le esprimerò...
grazie per le eventuali risposte
sonica |
| sonica |
ci riprovo, nella speranza che qualcuno abbia iniziato a studiare..
il problema 3
alla riga 5 credo che sia diverso dall'esempio sul Cormen in quanto nel while del libro Tj è indeterminato e dipende dall'input mentre nell'esercizio di Trubian io credo che sia determinato e credo che sia questo il calcolo della 5 linea di codice:
sommatoria, per i che va da 0 a n, di (n-i)
e d conseguenza la 6 mi viene
sommatoria, per i che va da 0 a n, di (n-i-1)
qualcun altro lo ha provato a risolvere? |
| Bloody |
allora se ho capito bene.....
1) ogni funzione va confrontata con le altre 3 e poi la tabella riempita completamente secondo l'esempio che ha fatto (i=righe, j=colonne, se xesempio c'è una omega piccolo in quella casella significa che a(i)=omega piccolo di a(j)
4) se stai parlando del metodo principale, secondo me c conta relativamente, nel senso che impostandola a1 e poi semplificando, per un esempio fatto in aula mi sono uscite 9righe di disequazione quando l'ho risolta con calma,lui si era limitato a dire che la condizione valeva.....poi tutti i termini noti nello svolgimento ti basta sapere se sono positivi o negativi.
5)il metodo di induzione è quello di sostituzione,causa il passaggio nella verifica dell'ipotesi induttiva....... |
| Bloody |
ops.... ho dimenticato metà della prima, limite stretto significa secondo me che dobbiamo distinguere tra o piccolo e O grande (analogo x omega), visto che se
f(n)=o(g(n)) allora per forza f(n)=O(g(n)),
(ma non il contrario)
visto che o piccolo significa che f che tende a zero + velocemente di g, allora f è sempre minore di g, per qualunque costante
Indi bisogna specificare o piccolo, non basta dire O grande |
| lucamjj |
Ciao ragazzi,
non e' che qualcuno riesce a mettere in rete gli esercizi che ha fatto in classe Trubian (quelli tipo compitino intendo)??
e magari anche le soluzioni !!!
ciao |
| pincopallino |
| avercele le soluzioni......=PP |
| chris83 |
Originally posted by lucamjj
non e' che qualcuno riesce a mettere in rete gli esercizi che ha fatto in classe Trubian (quelli tipo compitino intendo)??
mi associo..sarebbe davvero utile, anche perchè adesso come adesso non ho proprio idea di come possa essere il compitino!
:?
Un'altra cosa: ma come cavolo avete fatto a studiare il capitolo 4 :? :? :? :? :? :? |
| drakend |
Originally posted by chris83
mi associo..sarebbe davvero utile, anche perchè adesso come adesso non ho proprio idea di come possa essere il compitino!
:?
Un'altra cosa: ma come cavolo avete fatto a studiare il capitolo 4 :? :? :? :? :? :?
Le ricorrenze sono un po' un casino in effetti, però se hai capito gli ordini di grandezza le ricorrenze non dovrebbero essere impossibili... tu che problemi hai precisamente?
Per quanto riguarda gli esercizi io posso mettere online gli appunti che ho preso io, anche se sono delle ultime lezioni, ho potuto frequentare poco ad ottobre purtroppo :( |
| chris83 |
gli ordini di grandezza li ho capiti, quello che mi sfugge sono i 3 metodi per risolvere le ricorrenze...mi sembrano uno più complicato dell'altro...
Il dubbio principale è: pag. 52 del libro di Algoritmi-Metodo di soluzione.
Riporto il punto che non capisco: "Il metodo consiste nel provare che T(n)>=cn lg n........." " Assumendo che questo limite valga per n/2, cioè che t(n/2)<=c(n/2)log(n/2)....perchè prima il segno maggiore-uguale e poi il minore uguale ??? |
| drakend |
Originally posted by chris83
gli ordini di grandezza li ho capiti, quello che mi sfugge sono i 3 metodi per risolvere le ricorrenze...mi sembrano uno più complicato dell'altro...
Il dubbio principale è: pag. 52 del libro di Algoritmi-Metodo di soluzione.
Riporto il punto che non capisco: "Il metodo consiste nel provare che T(n)>=cn lg n........." " Assumendo che questo limite valga per n/2, cioè che t(n/2)<=c(n/2)log(n/2)....perchè prima il segno maggiore-uguale e poi il minore uguale ???
Errore di stampa :) |
| chris83 |
ci avevo pensato..ma sempre alla fine di quella pagina, ultima riga: "T(1)>c1lg 1 = 0 " ancora una volta il segno maggiore...
Ora, secondo me è giusto il minore perchè in pratica applico la definizione di O grande... però non vorrei che centri qualcosa la condizione al contorno...magari vuole dire che per n piccolo può succedere una cosa, per n molto grande ne succede un'altra (è come nella definizione di O grande: per N>No cg(n)<f(n) )....boh |
| drakend |
Originally posted by chris83
ci avevo pensato..ma sempre alla fine di quella pagina, ultima riga: "T(1)>c1lg 1 = 0 " ancora una volta il segno maggiore...
Ora, secondo me è giusto il minore perchè in pratica applico la definizione di O grande... però non vorrei che centri qualcosa la condizione al contorno...magari vuole dire che per n piccolo può succedere una cosa, per n molto grande ne succede un'altra (è come nella definizione di O grande: per N>No cg(n)<f(n) )....boh
Se noti poco dopo, sempre nella stessa pagina, mette il segno minore :) |
| chris83 |
| mi sa che hai ragione...grazie! |
| drakend |
| Io non ho capito cosa intende Trubian con T'(n) nella pagina 64 del file lez07.pdf (quello che parla dell'HeapSort). |
| chris83 |
| boh...non sono ancora arrivato lì a studiare...cmq guarda p. 66 di quella lezione, magari ci capisci qualcosa |
| drakend |
Originally posted by chris83
boh...non sono ancora arrivato lì a studiare...cmq guarda p. 66 di quella lezione, magari ci capisci qualcosa
Studiare è una parola grossa, io direi tentare di capire, che è più verosimile :D
Guardati pagina 92... che roba è? come ha fatto a fare quell'uguaglianza? |
| chris83 |
beh dai, difficile è difficile, però penso che se riusciamo a capire i concetti principali non dovremmo avere problemi...
basati sull'equazione fondamentale degli algoritmi:
2[cO(log n) + 2i] = 2cOglioni [effetto collaterale esame] |
|
|
|
|
