Corsi di Laurea

[danilo_sica]

ragazzi vorrei sapere come comportarmi davanti ad una formula di ricorrenza!!!in giro per il forum ho visto che chiedono lo svolgimento ma non riesco a capire come farlo..... cioe' come faccio a calcolare la formula di ricorrenza di una specifica funzione???e il prof cosa mi potrebbe chiedere per capire se l'ho capita o l'ho imparata a memoria??? spero sia stato chiaro

[Luigo]

per la parte della complessità computazionale io mi trovai molto bene a studiarla del libro del prof. Vento ...prova da lì

[danilo_sica]

da li sto studiando...li c'è una specie di procedimento ma non riesco a capire il prof come fa a vedere se l'ho imparato a memoria o l'ho capito...una volta imparato il caso generale è fatta...ma non penso sia cosi' semplice...

[Luigo]

il modo più semplice per esercitarti è prendere funzioni che hai usato per esercitarti per lo scritto e trovarti la complessità computazionale....

se le riesci a fare senza problemi vai tranquillo....il prof per vedere se sai a memoria o hai imparato ti chiede di trovarla per brani di codici non " frequenti" (cioè non ti chiederà la CC di selection sort o funzioni comunque usate spesso, ma di brani di codice che ti chiederà anche di scrivere...semplici di solito)

[danilo_sica]

a ok grazie mille!!!!!

[danilo_sica]

cioè io per calcolare la complessita' basta che vedo in quante parti divido la struttura, su quale applico la ricorsione,e il tempo di combinazione...poi una volta individuato la formula giusta la scrivo cosi' come sta sul libro di vento???senza modificare niente all'interno della formula???

[antoniosim]

cioè io per calcolare la complessita' basta che vedo in quante parti divido la struttura, su quale applico la ricorsione,e il tempo di combinazione...poi una volta individuato la formula giusta la scrivo cosi' come sta sul libro di vento???senza modificare niente all'interno della formula???

L'importante è scrivere tutto lo sviluppo della formula di ricorrenza. Non solo la formula finale.
Quindi il consiglio che sento di darvi è imparare quanto meno possibile a memoria, e cercare piuttosto di capire ogni passaggio (anche perchè sostanzialmente nulla di particolarmente complicato).
"Scrivere come sta sul libro" potrebbe far si che alla minima particolarità della funzione, magari un po più elaborata rispetto agli esempi, si vada in tilt.

[danilo_sica]

ecco è proprio questo che non riesco a capire!!!
come faccio a svolgere la ricorrenza se basta capire che dopo k sostituzioni si ha la formula generale???e di conseguenza l'appartenenza ad una delle notazioni???
mi spiego: dopo aver fatto una funzione e visto che quest'ulima per esempio divide la struttura in 1 e n-1!! e giusto che io scriva cosi'??:
c1 per n>1
t(n){
t(n-1)+c2 per n>1

considerando che n-1>1 (ovvero n>2) dalla precedente abbiamo che:
t(n)=t(n-2)+2c2 per n>2
osservando che dopo k sostituzioni si ha che:
t(n)=t(n-k)+kc2 per n>k
notiamo che la ricorrenza si chiude quando k=n,e in tal caso t(n)=c1 si ha che:
t(n)=c1+nc2
ovvero:+t(n)€O(n)
adesso cosa potrebbe cambiare all'orale da come sta scritto sul libro!!!
scusatemi ma non riesco proprio a capire!!!

[antoniosim]

Rispetto a quello che hai scritto, all'orale non dovrebbe cambiare niente. L'importante è non imparare nulla a memoria.
Durante l'appello in cui superai l'esame, il professore fu, giustamente, molto esigente da questo punto di vista.

[danilo_sica]

in che senso???come fa a vedere se hai imoarato a memoria o no???semplicemente chiedendomi la spiegazione di ogni passo???

[antoniosim]

in che senso???come fa a vedere se hai imoarato a memoria o no???semplicemente chiedendomi la spiegazione di ogni passo???

ti dico solo che sentii chiedere "Cos'è $n$ ?"

[danilo_sica]

scusami ma n non è il numero di elementi???

[|system88|]

scusami ma n non è il numero di elementi???

Si, ma c'è gente che non lo sa XD

[simply me]

Ragazzi ma oltre a farcela calcolare cosa può kiedere + il prof sulla complessità computazionale a livello teorico?

[Blackjack]

beh il significato delle varie notazioni: omega, theta, o.

[simply me]

L'avevo immaginato. Ho visto ke il prof tiene anche a qst. Però avendo assisito a degli esami vidi il prof Pergen arrabbiarsi molto cn 1 ragazzo xkè evidentemente nn gli rispose bene alla domanda sulle notazioni. Ke tipo di domande potrebbe fare? nel senso + di kiederti cs sono? sl cn qst domanda nn può sgamare se 1 le ha imparate a memoria

[Corrado]

Io penso che potrebbe tipo diegnare un grafico sul foglio con varie funzioni e farti domande sulle notazioni nel caso di quelle funzioni...

Comunque scusate, vorrei anche approfitatre del thread già aperto e postare un altro dubbio che mi è sorto...

Nella quinta ricorenza notevole, quella che divide la struttura dati in 1 ed (n-1)...

La formula di ricorrenza è questa giusto?

c1 per n=1
T(n-1)+c2 pern>1

Ok...

...ora iterando fino a k si ha:

T(n)=T(n-k)+kc2

...e fin qui ci siamo...

Quello che vi chiedo è: la ricorrenza si ferma quando "n=k+1" o quando "n=k"???

Sul libro del prof. Vento e sulle slide c'è scritto che si ferma quando "n=k"...
Ma se n=k, la formula alla iterazione k-esima sarà:

T(n)=T(0)+kc2... e c1 dove lo mettiamo? c1 lo prendiamo quando n=1, ma qui è uguale 0...

[simply me]

Hai ragione anche io avevo notato la stessa cosa xò ho pensato considerando che n è il numero di elementi della struttura dati considerata non avrebbe senso n=0. Quindi la sostituzione n=k è sbagliata xkè poi avremmo cm hai dtt tu T(0). Sostituendo invece n=k+1 avremmo T(1) che per la V formula di ricorrenza è = a c1. Almeno io così ho ragionato.
Spero di aver risolto i tuoi dubbi

[Corrado]

Ancora una volta grazie! Almeno ho la conferma che non sono l'unico allora a cui era venuto questo dubbio!
Poi magari in seduta d'esame facciamo presente al prof l'errore! O forse meglio di no...

PS: ma siamo gli unici due in questa sezione in questo periodo?! XD

[simply me]

Non penso che il giorno dell'orale avrò il pensiero di segnalare l'errore al prof talmente sarà agitata . Cmq non so xkè siamo sl noi 2 a stare qui in qst periodo sarà il freddo