Gio 22 Agosto, 11:21:47 - 2019

Autore Topic: costi computazionali  (Letto 2401 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline giozh

  • Author
  • Direttore di Dipartimento
  • **
  • Post: 2146
  • FeedBack: +148/-108
  • antagonista e me ne compiaccio
    • Mostra profilo
    • sites
costi computazionali
« il: Mar 02 Febbraio, 10:43:25 - 2010 »
apro un topic specifico per questa "branca" del compito che per me è un pò ostica. inizio con l'appello del 15/7

Codice: [Seleziona]
static int somma1(int v1, int v2) {
    return somma1(v1, v2, 0);
}
static int somma2(int v1, int v2) {
    return somma2(v1, v2, 1);
}
static int somma1(int v1, int v2, int i) {
    if (v1 == 0 && v2 == 0) return 0;
    int c1 = v1 % 2;
    int c2 = v2 % 2;
    int pow = power(i);
    return (c1 + c2) * pow + somma1(v1 / 2, v2 / 2, i + 1);
}
static int somma2(int v1, int v2, int pow) {
    if (v1 == 0 && v2 == 0) return 0;
    int c1 = v1 % 2;
    int c2 = v2 % 2;
    return (c1 + c2) * pow + somma2(v1 / 2, v2 / 2, pow * 2);
}
private static int power(int i) {
    int pow = 1;
    for (int j = 0; j < i; j++)
        pow = pow * 2;
    return pow;
}

(a) Determinare il costo computazionale di somma1 in funzione di v1 e v2.
(b) Determinare il costo computazionale di somma2 in funzione di v1 e v2.
(c) Esprimere i costi individuati ai punti (a) e (b) in funzione della dimensione dell'input.


allora facciamo un pezzo alla volta. punto a:
allora se non erro, quel pezzo di codice ha come costo massimo la metà del massimo di v1 e v2 (visto che dimezza ad ogni chiamata  v1 e v2). però c'è anche quell'indice i che mi da alquanto fastidio. siccome chiede il costo in funzione di v1 e v2, posso trascurare quell'i??
(intanto fatemi capire questo poi andiamo avanti col resto)
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/CM/E/IT d- s: a-- C++ UL>++++ P L++ !E W++>+++ !N !o K-? !w--- !O- !M- !V PS+ !PE !Y PGP !t 5? !X !R tv+ b++ DI !D G e h r+++ y+++*
------END GEEK CODE BLOCK------

http://inviaggionelpiatto.blogspot.com

Offline Crabro

  • Direttore di Dipartimento
  • ***
  • Post: 1044
  • FeedBack: +118/-61
    • Mostra profilo
Re: costi computazionali
« Risposta #1 il: Mar 02 Febbraio, 11:21:57 - 2010 »
(b) penso sia O(log(max{v1,v2})) in quanto ogni volta si dimezza l'input e si ferma quando il più grande arriva a 0(tuttavia non so se è corretto scrivere così).

(a) si ripete sempre O(log(max{v1,v2})) ma ogni volta chiama power(i) che ha costo O(i) con i che andrà da 0 a log(max{v1,v2}) ??? ??? ??? Potrebbe venire tipo O( (log(max{v1,v2}))^2 )?

(c) Ancora non capisco cosa intende quando dice in relazione alla dimesione dell'input... ???
« Sono convinto che l'informatica abbia molto in comune con la fisica. Entrambe si occupano di come funziona il mondo a un livello abbastanza fondamentale. La differenza, naturalmente, è che mentre in fisica devi capire come è fatto il mondo, in informatica sei tu a crearlo. Dentro i confini del computer, sei tu il creatore. Controlli – almeno potenzialmente – tutto ciò che vi succede. Se sei abbastanza bravo, puoi essere un dio. Su piccola scala. »
   
(Linus Torvalds)

Offline giozh

  • Author
  • Direttore di Dipartimento
  • **
  • Post: 2146
  • FeedBack: +148/-108
  • antagonista e me ne compiaccio
    • Mostra profilo
    • sites
Re: costi computazionali
« Risposta #2 il: Mar 02 Febbraio, 11:38:07 - 2010 »
Citazione
(a) si ripete sempre O(log(max{v1,v2})) ma ogni volta chiama power(i) che ha costo O(i) con i che andrà da 0 a log(max{v1,v2}) Huh? Huh? Huh? Potrebbe venire tipo O( (log(max{v1,v2}))^2 )?

mo che c'entra il logaritmo??? se ad esempio v1 è 1 e v2 è 4, al piu ci saranno 2 chiamate (che ora che ci penso è il log di 4 :D, ma perche proprio il logaritmo? che è per quella storia che dimezzo l'input ad ogni chiamata? ) poi per il fatto della i, il numero di passi di power aumenta di uno ogni volta che dimezzo l'input... però chiede di esprimersi in funzione di v1 e v2... quindi sta i non so quanto possa risultare utile...
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/CM/E/IT d- s: a-- C++ UL>++++ P L++ !E W++>+++ !N !o K-? !w--- !O- !M- !V PS+ !PE !Y PGP !t 5? !X !R tv+ b++ DI !D G e h r+++ y+++*
------END GEEK CODE BLOCK------

http://inviaggionelpiatto.blogspot.com

Agilulfo

  • Visitatore
Re: costi computazionali
« Risposta #3 il: Mar 02 Febbraio, 13:07:15 - 2010 »
il logaritmo c'è perché ad ogni passo dimezzi, breve dimostrazione:
al primo passo lavori sull'input intero \frac{n}{1}
al secondo sull'input dimezzato \frac{n}{2}
al terzo sull'input del secondo dimezzato (quindi dimezzato 2 volte) \frac{n}{2*2}
...
al passo k-esimo l'input sarà, rispetto a quello originale, \frac{n}{2^{k-1}}
quindi alla fine l'input sarà diventato tanto piccolo che sarà considerato nel passo base, non ci sta più la ricorsione, ed assumiamo per semplicità che ad n=1 ci sia il passo base (va bene qualsiasi valore costante, visto che ragioniamo in termini asintotici)
Per vedere "quanti" passi si son fatti si considera la seguente uguaglianza:
1=\frac{n}{2^{k-1}}
e passando ai logaritmi, dopo aver moltiplicato per 2^(k-1) entrambe le parti:
\log_2 (2^{k-1}) = \log_2 n
semplificando:
k = \log_2 n +1
k = O(\log_2 n)


volendo per esprimere O(max(v1,v2)) si può usare quest'altra dicitura: O(v1 + v2)
vince semplicemente il valore più alto, ovvero sarà sempre, denotando v = "quello + grosso", O(a*v) = O(v), dove a è una costante (ed in caso di 2 valori, il caso limite sarebbe a=2, quando i due valori sono uguali).


per il punto (c) basta mettere
x = \log_2 v1 \rightarrow v1 = 2^x
y = \log_2 v2 \rightarrow v2 = 2^y
e quindi sostituire v1 e v2 con i costi trovati nei punti precedenti.
P.S. questo procedimento l'ha fatto il prof 1 volta a lezione e nei compiti passati con soluzioni. Questo vale SOLO per input numerici e quando la ricorsione dipende dal valore di tali numeri.


il punto (a) anche io l'avrei fatto col logaritmo quadro, ma non saprei dirti se è sicuramente giusto :P
più che altro mi ricondurrei alla somma dei primi numeri interi, per dimostrare che fare 1+2+3+4+...+n passi equivale ad avere O(n^2), e quindi mettendo logn invece di n, dovrebbe venire log^2(n) :D

Offline Feanoer

  • Ricercatore
  • ****
  • Post: 313
  • FeedBack: +9/-6
    • Mostra profilo
Re: costi computazionali
« Risposta #4 il: Mar 02 Febbraio, 13:09:19 - 2010 »
guarda...se ti può essere d'aiuto se ne è parlato anche qui
http://solo.dis.uniroma1.it/index.php?option=com_smf&Itemid=6&topic=5403.0

Offline Crabro

  • Direttore di Dipartimento
  • ***
  • Post: 1044
  • FeedBack: +118/-61
    • Mostra profilo
Re: costi computazionali
« Risposta #5 il: Mar 02 Febbraio, 15:18:03 - 2010 »
Non ho capito molto il discorso della dimensione...cioè, sarebbe il costo in relazione al numero di bit? e se l'input è un vettore?
« Sono convinto che l'informatica abbia molto in comune con la fisica. Entrambe si occupano di come funziona il mondo a un livello abbastanza fondamentale. La differenza, naturalmente, è che mentre in fisica devi capire come è fatto il mondo, in informatica sei tu a crearlo. Dentro i confini del computer, sei tu il creatore. Controlli – almeno potenzialmente – tutto ciò che vi succede. Se sei abbastanza bravo, puoi essere un dio. Su piccola scala. »
   
(Linus Torvalds)

Agilulfo

  • Visitatore
Re: costi computazionali
« Risposta #6 il: Mar 02 Febbraio, 16:16:54 - 2010 »
si, c'entra il numero di bit, guarda la soluzione dell'es. 1 (specialmente il terzo paragrafo):
http://www.dis.uniroma1.it/~damore/asd/esami/20061213/20061213.pdf

mentre se è un vettore non è necessario questo tipo di ragionamento
per esempio in questo compito l'input è un array:
http://www.dis.uniroma1.it/~damore/asd/esami/20060628/20060628.pdf


edit: nel secondo caso non serve perché, ai fini del calcolo del numero dei passi iterativi/ricorsivi, il valore degli elementi nelle singole celle è ininfluente: sempre considerando costanti le varie operazioni (per esempio di confronto) sui numeri, grandi o piccoli che siano :P
« Ultima modifica: Mar 02 Febbraio, 16:23:02 - 2010 da Agilulfo »

Offline Crabro

  • Direttore di Dipartimento
  • ***
  • Post: 1044
  • FeedBack: +118/-61
    • Mostra profilo
Re: costi computazionali
« Risposta #7 il: Mar 02 Febbraio, 17:17:13 - 2010 »
...resto comunque un pò confuso ???
Nel primo caso x è il numero di bit che servono a rappresentare n? se si, questo cosa cambia nel costo del problema?
Nel secondo caso, n è la lunghezza dell'array...e perchè non la riportiamo in bit?

Scusa ma veramente non riesco a capire...o meglio, ora so che se n è l'intero in considerazione, allora lo riporto in bit, altrimenti no, ma non riesco a capire il perchè...
« Sono convinto che l'informatica abbia molto in comune con la fisica. Entrambe si occupano di come funziona il mondo a un livello abbastanza fondamentale. La differenza, naturalmente, è che mentre in fisica devi capire come è fatto il mondo, in informatica sei tu a crearlo. Dentro i confini del computer, sei tu il creatore. Controlli – almeno potenzialmente – tutto ciò che vi succede. Se sei abbastanza bravo, puoi essere un dio. Su piccola scala. »
   
(Linus Torvalds)

Agilulfo

  • Visitatore
Re: costi computazionali
« Risposta #8 il: Mar 02 Febbraio, 19:25:13 - 2010 »
perché il numero NON è la dimensione dell'input, esempio:

ho in input l'intero 100 e quindi la sua dimensione in termini di bit usati per rappresentarlo è:
k = \log_2 100 + 1 = 7.64 = 7 (si prende l'intero più piccolo)

supponiamo che al passo ricorsivo l'input si dimezza (quindi diventa 50), ma vediamo cosa succede alla dimensione:
k = \log_2 50 + 1 = 6.64 = 6

ed ancora dimezzando:
k = \log_2 25 + 1 = 5.64 = 5

come si vede, l'input viene dimezzato, mentre la dimensione diminuisce di 1 ad ogni passo
(quindi tra l'altro è sensato dire che O(logn) convertito in bit è O(log(2^k)) = O(k))

inoltre se invece di dimezzare l'input, lo si decrementa di 1 ad ogni passo, la dimensione resterebbe costante per tot valori e poi varierebbe (ogni bit aggiunto permette di rappresentare sempre più numeri in modo esponenziale)

visto che il costo è in funzione della dimensione dell'input questa rappresentazione è più corretta, in quanto tiene conto dello spazio effettivo utilizzato dall'input

-

per quanto riguarda gli array, l'input è l'array stesso e la dimensione la dimensione dell'array. Cioé usando termini simili a quelli usati sopra, l'array visto come totalità si può paragonare al valore dell'intero discusso sopra, mentre la sua dimensione sono i bit che rappresentavano l'int

infatti il costo dipende da quant'è grande la dimensione dell'array e non dai valori all'interno di tale array


se non è chiaro chiedi pure  :)


edit:
per come la vedo io, nel secondo caso, se si prende ad esempio un array di int, questo è composto da celle grandi 2 byte e quindi se si volesse scrivere il costo tenendo conto dei byte usati, questo diventa O(2*n), e 2 è una costante moltiplicativa (non varia al crescere dell'input) e quindi trascurabile asintoticamente

inoltre i valori delle celle dell'array sono spesso sconosciuti (e non ci interessa neanche saperli), quindi non si possono convertire in modo preciso in numero di bit
« Ultima modifica: Mar 02 Febbraio, 19:42:57 - 2010 da Agilulfo »

Offline Crabro

  • Direttore di Dipartimento
  • ***
  • Post: 1044
  • FeedBack: +118/-61
    • Mostra profilo
Re: costi computazionali
« Risposta #9 il: Mer 03 Febbraio, 08:56:38 - 2010 »
Sei stato chiarissimo!
Quindi nel secondo caso la dimensione rimane n perchè sarebbe O((numero di bit per rappresentare il singolo elemento)*n)=O(n), giusto?
« Sono convinto che l'informatica abbia molto in comune con la fisica. Entrambe si occupano di come funziona il mondo a un livello abbastanza fondamentale. La differenza, naturalmente, è che mentre in fisica devi capire come è fatto il mondo, in informatica sei tu a crearlo. Dentro i confini del computer, sei tu il creatore. Controlli – almeno potenzialmente – tutto ciò che vi succede. Se sei abbastanza bravo, puoi essere un dio. Su piccola scala. »
   
(Linus Torvalds)

Offline mkl

  • Studente
  • *
  • Post: 11
  • FeedBack: +0/-0
    • Mostra profilo
Re: costi computazionali
« Risposta #10 il: Mer 03 Febbraio, 11:01:26 - 2010 »
grazie Agilulfo per la chiarezza, finalmente s'è capita sta cosa del valore dell'input e della sua dimensione.

Riguardo al punto (a) a quanto ho capito il logaritmo al quadrato deriva dal fatto che saranno necessarie al più log(max(v1, v2)) chiamate al metodo somma1(int v1, int v2, int i) perchè di fatto tale numero di chiamete è l'upper bound entro cui il termine più grande tra v1 e v2 va a zero e quindi si arriva al caso base della ricorsione. Tale valore va moltiplicato per il massimo numero di operazioni fatte nel metodo power(int i) che di fatto saranno al massimo O(log(max(v1, v2)) visto che al massimo il valore di i sarà quello. Quindi costo totale O(log(max(v1, v1))^2). Non ho capito la storia di O(max(v1, v2)) = O(v1 + v2) , potreste spiegarmela?

Riguardo al punto (b) di fatto questo è il punto (a) senza la chiamata a power quindi ha costo O(log(max(v1, v2)), giusto?

Riguardo al punto (c) si calcolano x = log v1 => v1 = 2^x e y = log v2 => 2^y e si sostituiscono ai valori di v1 e v2  in O(log(max(v1, v1))^2), per somma1, e O(log(max(v1, v1)) per somma2.

Mi sfugge qualcosa?

Offline Crabro

  • Direttore di Dipartimento
  • ***
  • Post: 1044
  • FeedBack: +118/-61
    • Mostra profilo
Re: costi computazionali
« Risposta #11 il: Mer 03 Febbraio, 11:29:07 - 2010 »
Allora, faccio un esempio per vedere se ho capito.
Se ho un algoritmo che richiama se stesso ricorsivamente decrementando di volta in volta di 1 l'input int n, il costo dell'algoritmo sarà O(n) che espresso nella sua dimensione è O(2^x) ove x=log(n)...giusto?????
« Sono convinto che l'informatica abbia molto in comune con la fisica. Entrambe si occupano di come funziona il mondo a un livello abbastanza fondamentale. La differenza, naturalmente, è che mentre in fisica devi capire come è fatto il mondo, in informatica sei tu a crearlo. Dentro i confini del computer, sei tu il creatore. Controlli – almeno potenzialmente – tutto ciò che vi succede. Se sei abbastanza bravo, puoi essere un dio. Su piccola scala. »
   
(Linus Torvalds)

Offline mkl

  • Studente
  • *
  • Post: 11
  • FeedBack: +0/-0
    • Mostra profilo
Re: costi computazionali
« Risposta #12 il: Mer 03 Febbraio, 11:41:43 - 2010 »
Allora, faccio un esempio per vedere se ho capito.
Se ho un algoritmo che richiama se stesso ricorsivamente decrementando di volta in volta di 1 l'input int n, il costo dell'algoritmo sarà O(n) che espresso nella sua dimensione è O(2^x) ove x=log(n)...giusto?????

Se l'input è un numero intero è così, ma nel calcolo della sua dimensione dovresti mettere x = log (n) +1 anche se poi in termini asintotici diventa x = O(log n + 1) => x= O(log n) e quindi n = 2^x .

Se invece hai un array e decrementi di volta in volta l'indice dell'array di uno (quindi analizzi tutte le celle una alla volta) hai un costo in termini di dimensione dell'input O(n), dove n è la dimensione dell'array. Tale costo corrisponde anche al costo in funsione del valore dell'input perchè se hai come input un array il costo in funzione del suo valore corrisponde al costo in funzione della sua dimensione.
Spero di non aver detto ca*****, correggetemi se sbaglio.

p.s. Crabro ti risulta il mio ragionamento sul problema di prima?

Offline mkl

  • Studente
  • *
  • Post: 11
  • FeedBack: +0/-0
    • Mostra profilo
Re: costi computazionali
« Risposta #13 il: Mer 03 Febbraio, 11:52:57 - 2010 »
Esame 14/09/2009 (20090914.pdf)

Codice: [Seleziona]
// il metodo esegue il quicksort sull’array
private static void quicksort(int[] array) {
Arrays.sort(array);
}
private static void merge (
int[] array1, int i1,
int[] array2, int i2,
int[] result, int i_ris) {
if (i1 < array1.length && i2 < array2.length)
if (array1[i1] <= array2[i2]) {
result[i_ris] = array1[i1];
merge(array1, i1 + 1, array2, i2, result, i_ris + 1);
} else {
result[i_ris] = array2[i2];
merge(array1, i1, array2, i2 + 1, result, i_ris + 1);
}
else
if (i1 < array1.length) {
result[i_ris] = array1[i1];
merge(array1, i1 + 1, array2, i2, result, i_ris + 1);
} else if (i2 < array2.length) {
result[i_ris] = array2[i2];
merge(array1, i1, array2, i2 + 1, result, i_ris + 1);
}
}
private static void merge(int[] array1, int[] array2, int[] result) {
merge(array1, 0, array2, 0, result, 0);
}
public static int[] mergeInOrder1(int[] array1, int[] array2) {
int[] ris = new int[array1.length + array2.length];
merge(array1, array2, ris);
quicksort(ris);
return ris;
}
public static int[] mergeInOrder2(int[] array1, int[] array2) {
quicksort(array1);
quicksort(array2);
int[] ris = new int[array1.length + array2.length];
merge(array1, array2, ris);
return ris;
}

(a) Determinare il costo computazionale di mergeInOrder1 in funzione della dimensione di array1 e array2.
(b) Determinare il costo computazionale di mergeInOrder2 in funzione della dimensione di array1 e array2.
(c) Immaginando di sostituire il quicksort con il mergesort, come varierebbero i costi determinati?

Dato che il quicksort richiede un costo nel caso peggiore O(n^2) e nel caso medio di O(n log n) e il merge sort ha un costo O(n log n):

punto (a): costo complessivo O(k log k), dove k = m + n. Tale costo è dato da fatto che occorrono O(n + m) confronti per fare il merge dei due vettori di dimensione n ed m (costo asintoticamente trascurabile) più il costo del quicksort nel caso medio O((n+m) log (n+m)). Se consideriamo il costo del quicksort nel caso peggiore invece risulta O(k^2)

punto (b): costo complessivo O(max(n log n, m log m)). Tale costo è dato da fatto che occorrono O(n log n) operazioni per il quicksort dell'array di dimensione n e O(m log m) operazioni per il quicksort dell'array di dimensione m quindi di fatto l'upperbound è dato dall'ordinamento dell'array di dimensione maggiore. A questo va aggiunto il costo del merge sort dell'array complessivo che ha costo O(n+m) che asintoticamente è trascurabile. Se consideriamo il costo del quicksort nel caso peggiore invece risulta O(max(n^2, m^2))

punto (c): i costi dovrebbero essere uguali a quelli del caso medio del quicksort

Vi trovate?