Pages: 1 ... 3 4 [5]   Go Down
Print
Author Topic: Domanda compito  (Read 9290 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
alex180788
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 422


« Reply #60 on: 20-01-2011, 21:56:55 »

dato che ho trovato questo vecchio post con tanti esercizi discussi aggiungo pure io un esercizio di un compito cosi ne possiamo discutere insieme

Sia OT un ordinamento topologico di un grafo orientato aciclico G con |V|=n vertici ed |E|=n archi. Sia Gt il grafo trasposto di G.
Qual'è la compessità del migliore algoritmo possibile per calcolare un ordinamento topologico per Gt?

a) O(1)
b) O(V)
c) O(V+E)
d) O(OT)

non ne sono sicuro ma posso ottenere l'ordinamento topologico di Gt semplicemente invertendo l'ordinamento topologico di G?... OT è un ordinamento dei vertici di G lungo una linea orizzontale in modo che tutti gli archi orientati siano diretti da sinistra a destra..... se leggo OT al "contrario" non ottengo un ordinamento topologico di Gt ?

secondo voi come si deve rispondere a questa domanda?
Logged

Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
alex180788
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 422


« Reply #61 on: 20-01-2011, 22:48:49 »

come non detto.... posto questo esercizio a parte
Logged

Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
Dhavamba
Apprendista Forumista
**
Offline Offline

Posts: 286


« Reply #62 on: 25-01-2011, 19:33:14 »

questa ricorrenza... 2T(n-1) + n...

Il problema è quel 2!!!
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #63 on: 25-01-2011, 19:58:42 »

Albero di ricorsione....del resto tieni conto che:

2T(n-1)+n=T(n-1)+T(n-1)+n
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Dhavamba
Apprendista Forumista
**
Offline Offline

Posts: 286


« Reply #64 on: 25-01-2011, 20:05:29 »

si e la devo fare...

n-1 + n-1...       2n-4

n-2 + n-2 + n-2 + n-2...    4n - 8

.....................................    8n - 16

giusto? E poi faccio la sommatoria del valore esterno che è?
« Last Edit: 25-01-2011, 20:33:43 by Dhavamba » Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #65 on: 25-01-2011, 22:52:10 »

Non mi ricordo benissimo, non le faccio da tempo, il lavoro esterno a me sembra n.
Cioè avresti se ci fai caso:

2n-4
4n-8
8n-16
.
.
.
(2)^in-.....

Ora il secondo termine non mi ricordo come si scrive, più o meno la sommatoria del lavoro esterno dovrebeb essere quella, ti manca il secondo fattore da generalizzare. Ad ogni modo dovrebbe essere di ordine lineare.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
alex180788
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 422


« Reply #66 on: 25-01-2011, 23:25:42 »

dividi per 2^n..... ma nessuno ha provato a rispondere alla mia domanda??
Logged

Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
alex180788
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 422


« Reply #67 on: 26-01-2011, 10:47:52 »

T(n)=4T(n/b)+n   e   T(n)=4T(n/b)+nlog(n). Siano S1(b) e S2(b) le soluzioni di tali equazioni al variare di b. Quale delle seguenti affermazioni è falsa?

a. è possibile trovare un valore di b tale che S1(b)=theta(S2(b))
b. è possibile trovare un valore di b tale che S1(b)!=theta(S2(b))
c. è possibile trovare un valore di b tale che S1(b)="o piccolo"(S2(b))
d. è possibile trovare un valore di b tale che S1(b)="omega piccolo"theta(S2(b))


secondo me è la d. perchè studiando i vari casi in cui b=4 b<4 e b>4 S1 è al più uguale a S2. che ne pensate?
Logged

Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
alex180788
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 422


« Reply #68 on: 31-01-2011, 10:34:40 »

hai le 4 opzioni?
dovrebbero essere rispettivamente:
O(n^2)
O(n^3)
O(1)
O(n)
se non mi abaglio.
quindi la prima e l'ultima in ordine asintotico crescente, dovrebbero essere:
n^3/(n+logn)^2,2^(n+2)/2^n.
Se non sbaglio eh?


scusa mi potresti spiegare come hai ottenuto questi limiti superiori?
nella prima c'è una frazione tra un termine n di secondo grado e un termine n di primo ed io direi O(n)
lo stesso ragionamento farei per il secondo ed il quarto ma credo che tu abbia ragione è solo che vorrei sapere il perchè 
Logged

Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
alex180788
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 422


« Reply #69 on: 31-01-2011, 10:53:44 »

Sia T(i,n) una funzione che indica la complessità computazionale di Heapify quando chiamata a partire dall'elemento i-esimo, in una heap di n elementi. Allora, per 2i <=n e costante c
non saprei però possiamo raggionarci...

il fatto che 2i<=n vuol dire solo che siamo nella prima metà del heap, e quindi almeno una chiamata possiamo farla.
L'heapify fa risalire da i ad n , quindi in n/2 perchè ci troviamo nella prima metà del heap, allora potrebbe essere la d.
Tu come sei arrivato alla A?!

secondo me è la a) perché heapfy va a scendere e non a salire come dici tu... infatti se A<A[2i] li scambia (costo c) ed effettua una chiamata ricorsiva sull'elemento di indice 2i quindi (secondo il mio ragionamento) sarebbe T(i,n)=T(2i,n) + c .... secondo te è corretto il mio ragionamento???
Logged

Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
alex180788
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 422


« Reply #70 on: 31-01-2011, 11:17:34 »

non so se darti la soluzione, io la scrivo caso mai fermati a consiglio.

CONSIGLIO
Quote
Prova ad applicare Master, e ricorda che alfa è maggiore di uno, è importante.

SVOLGIMENTO
Quote
Applicando Master, la prima sarà teta(nlgn) poichè per qualunque alfa ci troviamo nel secondo caso (lg in base alfa di alfa = 1 per ogni alfa);
mentre nella seconda, l'esponente (che moltiplica per un numero maggiore di uno il termine del logaritmo) sarà sempre maggiore di uno, quindi n elevato ad un numero maggiore di uno è asintoticamente maggiore di n ci conduce al primo caso e la soluzione sarà teta(n^lg_alpha(2*alpha)) per ogni alpha;

SOLUZIONE
Quote
confrontando polinomialmente e asintoticamente le due equazioni, la seconda è più grande, quindi la a dovrebbe essere falsa.


scusa ma nella tua risposta hai sostituito la prima con la seconda per errore?!?!
inoltre dato che la seconda è sempre maggiore della prima la risposta falsa non potrebbe essere la c)?
« Last Edit: 31-01-2011, 11:26:07 by alex180788 » Logged

Codice etico e di pratica professionale dello sviluppo software:
..
..
7. Colleghi. Gli sviluppatori software devono essere leali e di supporto nei confronti dei loro colleghi.
...
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #71 on: 01-02-2011, 18:38:53 »

Non mi ricordo benissimo, non le faccio da tempo, il lavoro esterno a me sembra n.
Cioè avresti se ci fai caso:

2n-4
4n-8
8n-16
.
.
.
(2)^in-.....

Ora il secondo termine non mi ricordo come si scrive, più o meno la sommatoria del lavoro esterno dovrebeb essere quella, ti manca il secondo fattore da generalizzare. Ad ogni modo dovrebbe essere di ordine lineare.
Scusa ma quello che hai scritto e' un eresia... come puo' essere quell'equazione lineare se gia' l'equazione di ricorrenza dei numeri di fibonacci ( T(n)=T(n-1)+T(n-2)+\Theta(1) ) e' esponenziale? testate

T(n)\ =\ 2T(n-1)\ +\ n

Sfruttando l'albero abbiamo che

0:\ n

1:\ 2n - 2

2:\ 4n - 8

3:\ 8n - 24

4:\ 16n - 64

...

T(n)\ =\ \sum_{i=0}^n {n2^i\ - i2^{i}}

T(n)\ =\ n\ \sum_{i=0}^n\ {2^i} - \sum_{i=1}^n\ {i2^{i}}

T(n)\ \leq\ (n\ (2^{n+1} - 1) - (\frac{n-1}{\ln 2}2^n - \frac{1}{\ln 2}) \ =\ O(n2^n)

Ovvero super-esponenziale...

P.S. \sum_{i=0}^n\ {i2^{i}}\ =\ \sum_{i=1}^n\ {i2^{i}} in quanto il primo termine vale 0
P.S.2 \sum_{i=1}^n\ {i2^{i}} l'ho approssimata con gli integrali in quanto monotona crescente.
« Last Edit: 01-02-2011, 22:58:33 by shiny » Logged
Pages: 1 ... 3 4 [5]   Go Up
Print
Jump to: