BeBrA
19-06-2004, 14:19
Salve!
Sto preparando l'esame di calcolatori II e mi sono abbattuto in questo esercizio:
(Se c'e' qualcuno dell'università di padova che sta seguendo il corso, l'esercizio è a pagina 7 della dispensa.)
Ecco il testo.
PREFIX COMPUTATION:
Sia N2^n e sia x=(x0,...xN-1) una sequenza di elementi di un semigruppo. Sia P2^d, con P<=N.
a) Si descriva un algoritmo per calcolare i prefissi y=(y0,..yN-1) delal sequenza x su linear array di P nodi, assumendo che (per j=0,1,...P-1) il nodo j contenga inizialmente gli elementi xjN/P+k con k0,1,....,N/P-1.
b) Si analizzi il tempo T(N,P) dell'algoritmo proposto e si determini il valore di P che minimizza tale tmpo pr un dato valore di N.
c) Si dimostri che, comunque si scelga P, T=Omega(radice(N)) per qualsiasi algoritmo. (Considerare le distanze tra i dati ed il numero di operazioni da svolgere).
Grazie!
Sto preparando l'esame di calcolatori II e mi sono abbattuto in questo esercizio:
(Se c'e' qualcuno dell'università di padova che sta seguendo il corso, l'esercizio è a pagina 7 della dispensa.)
Ecco il testo.
PREFIX COMPUTATION:
Sia N2^n e sia x=(x0,...xN-1) una sequenza di elementi di un semigruppo. Sia P2^d, con P<=N.
a) Si descriva un algoritmo per calcolare i prefissi y=(y0,..yN-1) delal sequenza x su linear array di P nodi, assumendo che (per j=0,1,...P-1) il nodo j contenga inizialmente gli elementi xjN/P+k con k0,1,....,N/P-1.
b) Si analizzi il tempo T(N,P) dell'algoritmo proposto e si determini il valore di P che minimizza tale tmpo pr un dato valore di N.
c) Si dimostri che, comunque si scelga P, T=Omega(radice(N)) per qualsiasi algoritmo. (Considerare le distanze tra i dati ed il numero di operazioni da svolgere).
Grazie!