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

Posts: 385



« Reply #45 on: 23-04-2010, 15:30:23 »

Siano T(n)=2aT(n/a)+n e T(n)=aT(n/a)+n due equazioni di ricorrenza con parametro a>1. Siano S1(a) e S2(a) le soluzioni di tali equazioni al variare del parametro a. Quali delle seguenti affermazioni è falsa.

a. E' possibile trovare un valore di a, tale che S1(a)=\Theta(S2(a))

b. E' possibile trovare un valore di a, tale che S1(a) \not = \Theta(S2(a))

c. E' possibile trovare un valore di a, tale che S1(a)=\omega(S2(a))

d. Non è possibile trovare un valore di a, tale che S1(a)=o(S2(a))

Non capisco come rispondere a questa domanda, qualcuno può darmi un suggerimento su come procedere?  pray
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #46 on: 23-04-2010, 16:05: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.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Yaroth
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 445



« Reply #47 on: 23-04-2010, 18:18:57 »

Sia T un albero binario di ricerca che contiene tutti e soli i numeri compresi tra 1 e 100. Supponete di volere
cercare il numero 50. Quanti numeri minori di 50 potete incontrare nella ricerca?

a. Tutti i numeri minori di 50
b. AI più la metà di tali numeri
c. Al.più log 50, numeri minori di 50
d. Nessuno dei precedenti

Se questa è la A.

a questa come rispondereste? :

Sia T un albero binario di ricerca che contiene tutti e soli i numeri compresi tra 1 e 100. Si suppone di dover cercare il numero 50. Quanti numeri maggiori di 50 potete incontrare nella ricerca?
a.   Tutti i numeri maggiori di 50
 b.   Al più la metà di tali numeri
c.   Al più log 50, numero maggiori di 50
d.   Nessuno dei precedenti
Logged
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #48 on: 23-04-2010, 18:34:21 »

credo che sia la d sempre per lo stesso ragionamento fatto per la domanda precedente; almeno questo è quello che penso io
Logged
Yaroth
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 445



« Reply #49 on: 23-04-2010, 18:44:54 »

credo che sia la d sempre per lo stesso ragionamento fatto per la domanda precedente; almeno questo è quello che penso io

si anche secondo me...
e questa?

Sia T un albero binario di ricerca con n nodi. Supponiamo di voler colorare i nodi di nero e rosso senza modificare la struttura dell’albero per ottenere un albero RB. Allora
a.   La colorazione è sempre possibile
b.   La colorazione è possibile solo se le foglie sono tutte allo stesso livello
c.   La colorazione è possibile solo se l’altezza dell’albero è O(log n)
d.   Nessuna delle precedenti affermazioni è vera
Logged
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #50 on: 23-04-2010, 18:47:03 »

secondo me è nuovamente la d
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #51 on: 23-04-2010, 20:12:41 »

Quote
Sia T un albero binario di ricerca che contiene tutti e soli i numeri compresi tra 1 e 100. Si suppone di dover cercare il numero 50. Quanti numeri maggiori di 50 potete incontrare nella ricerca?
a.   Tutti i numeri maggiori di 50
 b.   Al più la metà di tali numeri
c.   Al più log 50, numero maggiori di 50
d.   Nessuno dei precedenti
vi do un indizio:
se l'albero binario tendesse ad una lista a causa di un input scomodo??
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #52 on: 23-04-2010, 20:16:32 »

non vorrei sembrare un bastian contrario ma....
in questa:
Quote
Sia T un albero binario di ricerca con n nodi. Supponiamo di voler colorare i nodi di nero e rosso senza modificare la struttura dell’albero per ottenere un albero RB. Allora
a.   La colorazione è sempre possibile
b.   La colorazione è possibile solo se le foglie sono tutte allo stesso livello
c.   La colorazione è possibile solo se l’altezza dell’albero è O(log n)
d.   Nessuna delle precedenti affermazioni è vera
vi do un altro indizio:
un albero tutto nero, rispetta banalmente le pr 1-2-3-4, e la pr 5 se e solo se l'albero è bilanciato!
che vuol dire bilanciato?

Quote
ovviamente se volete vi do entrambe le risposte ma forse se ci ragionate un pochino è meglio
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Yaroth
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 445



« Reply #53 on: 24-04-2010, 08:30:54 »

non vorrei sembrare un bastian contrario ma....
in questa:
Quote
Sia T un albero binario di ricerca con n nodi. Supponiamo di voler colorare i nodi di nero e rosso senza modificare la struttura dell’albero per ottenere un albero RB. Allora
a.   La colorazione è sempre possibile
b.   La colorazione è possibile solo se le foglie sono tutte allo stesso livello
c.   La colorazione è possibile solo se l’altezza dell’albero è O(log n)
d.   Nessuna delle precedenti affermazioni è vera
vi do un altro indizio:
un albero tutto nero, rispetta banalmente le pr 1-2-3-4, e la pr 5 se e solo se l'albero è bilanciato!
che vuol dire bilanciato?

Quote
ovviamente se volete vi do entrambe le risposte ma forse se ci ragionate un pochino è meglio

Secondo me è la b...
Logged
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #54 on: 24-04-2010, 08:52:44 »

Quote
Sia T un albero binario di ricerca che contiene tutti e soli i numeri compresi tra 1 e 100. Si suppone di dover cercare il numero 50. Quanti numeri maggiori di 50 potete incontrare nella ricerca?
a.   Tutti i numeri maggiori di 50
 b.   Al più la metà di tali numeri
c.   Al più log 50, numero maggiori di 50
d.   Nessuno dei precedenti
vi do un indizio:
se l'albero binario tendesse ad una lista a causa di un input scomodo??


ho detto appunto la d perchè si potrebbe verificare una cosa simile:
 
           1
             \
              2
                \
                  .                                          quindi se si dovesse rientrare in questo caso, arriveremmo al numero 50
                   .                                         senza aver trovato alcun numero maggiore di 50. Mi sto sbagliando
                    .                                        secondo voi?
                     \
                     50
                        \
                        51
                          \
                            .
                             .
                              .
                               \
                              100

                        
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #55 on: 24-04-2010, 14:07:41 »

e se l'inserimento fosse da 100 a 1???che albero verrebbe fuori??
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #56 on: 24-04-2010, 14:11:08 »

Quote
Secondo me è la b...
eh già!
perchè se le foglie fossero tutte allo stesso livello potremmo colorare un albero tutto di nero, e rispettare quindi la proprietà della bh.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #57 on: 24-04-2010, 14:15:15 »

e se l'inserimento fosse da 100 a 1???che albero verrebbe fuori??

...e allora come si fa in questi casi, così non diventa ambigua la domanda?
Logged
8leoncina7
Apprendista Forumista
**
Offline Offline

Posts: 266



« Reply #58 on: 24-04-2010, 14:23:56 »

e se l'inserimento fosse da 100 a 1???che albero verrebbe fuori??

...e allora come si fa in questi casi, così non diventa ambigua la domanda?

no perchè la domanda dice -->  Quanti numeri minori di 50 potete incontrare nella ricerca? ciò implica quanti ne puoi incontrare al massimo.. quindi è la A..
Logged

meglio fare e pentirsi che non fare e pentirsi lo stesso..
                                                                Machiavelli
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #59 on: 24-04-2010, 14:29:36 »

no no! perchè devi sempre pensare le condizioni limite. Una domanda come questa:
Quote
Quanti numeri maggiori di 50 potete incontrare nella ricerca?
quanti ne puoi incontrare vuol dire al massimo, cioè nella condizione peggiore, e la condizione peggiore è quella di un inserimento inverso cosicchè la lista sarà da 100 ad 1 e per arrivare a 50 scorriamo tutti i maggiori.
Bisogna analizzare bene il testo. Prima di gettarsi a leggere le 4 possibilità, che come in questo o in molti altri casi potrebbero fuorviarti. Non se stai attento e hai studiato.
Comunque per qualunque dubbio io posso aiutarti a provare a dare una buona interpretazione (prima che darti la risposta).
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Pages: 1 2 3 [4] 5   Go Up
Print
Jump to: