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

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

__________________
Ci vuole scienza, ci vuol costanza ad invecchiare senza maturità

Guccini

Visti My Fotolog

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

Graziaaaaaaaaaa

__________________
Ci vuole scienza, ci vuol costanza ad invecchiare senza maturità

Guccini

Visti My Fotolog

Esercizi tipo compitino

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

__________________
I really love your peaches,
wanna shake your tree...

The Joker - Steve Miller Band

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?

__________________
I really love your peaches,
wanna shake your tree...

The Joker - Steve Miller Band

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

__________________
I don't care if you're black, white, straight, bisexual, gay, lesbian, short, tall, fat, skinny, rich or poor. If you're nice to me, I'll be nice to you. Simple as that.

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

__________________
I don't care if you're black, white, straight, bisexual, gay, lesbian, short, tall, fat, skinny, rich or poor. If you're nice to me, I'll be nice to you. Simple as that.

esercizi tipo compitino

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

avercele le soluzioni......=PP

__________________
"Che ne sai di un ragazzo che ti amava
che parlava e niente sapeva
eppur quel che diceva chissà perchè‚ chissà adesso è verità."

Re: esercizi tipo compitino

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

Re: Re: esercizi tipo compitino

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

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

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

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

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