Un pò di dubbi sulle Heap
Ho una serie di problemi nello studio delle heap.
Per esempio l' equazione di ricorrenza per Max-heapify è:
[tex]T(k)=T(2k/3)+\theta(1)[/tex]
Questo perchè se prendo un sottoalbero di dimensione n, e poi considero i sottoalberi radicati nei figli ognuno di essi non può avere dimensione maggiore di 2n/3, ma come si dimostra?
Non ricordo più le proprietà degli alberi, leggo che il numero massimo di nodi ad altezza h è [tex]2^{h+1}-1[/tex] ma non mi quadra...se disegno un albero binario completo con 7 nodi, e quindi di altezza due avrei [tex]2^{3}-1[/tex] che fa 7, ma io ho solo 4 nodi ad altezza h.......
E poi da qui come si arriva al fatto che il numero di nodi ad altezza h si può indicare come [tex]\frac{n}{2^{h+1}}[/tex] ?
Nel calcolo della complessità della costruzione di una maxheap ho questi calcoli:
[tex]\sum \left \lceil \frac{n}{2^{h+1}} \right \rceil O(h)[/tex] che diventa:
[tex]O(n\sum\frac{h}{2^h})[/tex]
L' unica cosa che non mi spiego è perchè dopo avere tolto il ceiling al denominatore non ho più [tex]2^{h+1}[/tex] ?
Per esempio l' equazione di ricorrenza per Max-heapify è:
[tex]T(k)=T(2k/3)+\theta(1)[/tex]
Questo perchè se prendo un sottoalbero di dimensione n, e poi considero i sottoalberi radicati nei figli ognuno di essi non può avere dimensione maggiore di 2n/3, ma come si dimostra?
Non ricordo più le proprietà degli alberi, leggo che il numero massimo di nodi ad altezza h è [tex]2^{h+1}-1[/tex] ma non mi quadra...se disegno un albero binario completo con 7 nodi, e quindi di altezza due avrei [tex]2^{3}-1[/tex] che fa 7, ma io ho solo 4 nodi ad altezza h.......
E poi da qui come si arriva al fatto che il numero di nodi ad altezza h si può indicare come [tex]\frac{n}{2^{h+1}}[/tex] ?
Nel calcolo della complessità della costruzione di una maxheap ho questi calcoli:
[tex]\sum \left \lceil \frac{n}{2^{h+1}} \right \rceil O(h)[/tex] che diventa:
[tex]O(n\sum\frac{h}{2^h})[/tex]
L' unica cosa che non mi spiego è perchè dopo avere tolto il ceiling al denominatore non ho più [tex]2^{h+1}[/tex] ?
Risposte
mi ricordo di aver già risposto alla tua domanda su questa particolarità degli Heap: vedi qua
l'altra parte sugli alberi, l'altezza ecc... ti rispondo in un altro momento o se passa qualcun'altro
l'altra parte sugli alberi, l'altezza ecc... ti rispondo in un altro momento o se passa qualcun'altro
"Darèios89":
Non ricordo più le proprietà degli alberi, leggo che il numero massimo di nodi ad altezza h è [tex]2^{h+1}-1[/tex] ma non mi quadra...se disegno un albero binario completo con 7 nodi, e quindi di altezza due avrei [tex]2^{3}-1[/tex] che fa 7, ma io ho solo 4 nodi ad altezza h.......
vediamo di fare ordine sugli alberi binari completi:
- altezza $h$ ha due possibili definizioni:
* definendo con $f$ il numero di foglie, $h=log_2(f)$
* definendo $n$ con il numero di nodi totali: $h = \lfloor log_{2}(n)\rfloor$
- profondità $i = h-k$ con $k=0,1,...,h$
- numero di nodi INTERNI: $2^i - 1$ (1)
NOTA: valido solo fino al livello $h-1$, vedi definizione "nodi interni". Da calcolare considerando il livello successivo.
Se si calcolano i nodi interni totali, si considera il livello attuale come $h-1$ ma si considera il livello successivo come le foglie, cioè si aggiunge $1$. Perciò $h-1=i rArr 2^(i+1)-1 = 2^(h-1+1) -1 = 2^h-1$. Tutto questo per generalizzare la formula.
- numero di foglie: $2^h$ (2)
- numero di nodi totali (nodi interni + foglie) = $2^{h+1} - 1 = (2^h - 1) + 2^h = 2*(2^h) - 1 = 2^{h+1} - 1$
Veniamo agli heap binari, classificati come alberi binari quasi completi.
Ti devo prima ringraziare, perchè ho scoperto una curiosità che non avevo compreso quando studiai questi argomenti, ci ho passato un buon quarto d'ora questa sera a capirla
un heap essendo un albero binario quasi completo prende quasi tutte le particolarità di quello completo, ma può variare il suo numero di nodi totali (altezza calcolabile solo come $h = \lfloor log_{2}(n)\rfloor$ essendo non completo...)
- se è completo (massimo): $2^{h+1} - 1$ (come sopra)
- se è quasi completo, nodi interni + 1 foglia (minimo): $2^h = (2^h - 1) + 1$ (questa è la curiosità che non avevo capito, pensavo fosse riferito alle foglie il valore $2^h$)
Nel calcolo della complessità della costruzione di una maxheap ho questi calcoli:
[tex]\sum \left \lceil \frac{n}{2^{h+1}} \right \rceil O(h)[/tex] che diventa:
[tex]O(n\sum\frac{h}{2^h})[/tex]
L' unica cosa che non mi spiego è perchè dopo avere tolto il ceiling al denominatore non ho più [tex]2^{h+1}[/tex] ?
mmm non vedo il problema. Ah scrivimi come è scritto dove lo hai trovato, secondo me è così:
[tex]\sum \left \lceil \frac{n}{2^{h+1}} \right \rceil O(h) = O(n\sum\frac{h}{2^h})[/tex]
se sì, quell'uguale è unidirezionale, e significa "appartiene" (v. https://www.matematicamente.it/forum/pos ... ml#p544370)
è semplicitmente l'appartenza ad una classe di complessità:
[tex]\sum \left \lceil \frac{n}{2^{h+1}} \right \rceil O(h) \in O(n\sum\frac{h}{2^h})[/tex]
non ho sotto mano un libro per vedere la correttezza di questa appartenenza, ma ricordando la teoria mi sembra di si
per stasera basta, gli altri post li guardo un altro giorno se nessuno ti risponderà. Se hai dubbio chiedi pure
PS: su che libro stai studiando mi sembra molto strano che non ci siano questi argomenti...
EDIT:
corretto le proprietà degli alberi.
Mh ho capito molte cose. Grazie della spiegazione 
Però ancora mi rimane qualche dubbio su quel discorso del numero massimo di nodi, visto che la dimostrazione è complicata basta anche capirla più o meno, io ho:
il ceiling di [tex]\frac{n}{2^{h+1}}[/tex]
Cioè divido il numero totale di nodi per quelli di altezza h.
Però se io ho una heap completa, con 7 nodi, in questo caso per determinare il numero di nodi ad altezza h mi basterebbe dire che sono [tex]2^h[/tex], invece con quella forumla per calcolare il numero all' altezza 2 avrei [tex]\frac{7}{8}[/tex] giusto? Che arrotondato da 1, che media è scusami, non capisco sono proprio cocciuto
Per quanto riguarda la complessità dell' algoritmo avevi ragione tu, si tratta di un' uguaglianza che rappresenta la classe di appartenenza.
Il mio libro è il Cormen: Introduzione agli algoritmi e strutture dati 2° edizione. Il problema è che questo discorso sul numero di nodi massimo non è spiegato ma solo proposto come esercizio da dimostrare.
P.S ti ringrazio come sempre, se puoi dare un' occhiata a delle ricorrenze che ho postato recentemente sugli alberi di ricorsione mi farai un favore, ho dimenticato alcune cose....grazie:
altra-equazione-di-ricorrenza-come-si-continua-t79962.html
Però ancora mi rimane qualche dubbio su quel discorso del numero massimo di nodi, visto che la dimostrazione è complicata basta anche capirla più o meno, io ho:
il ceiling di [tex]\frac{n}{2^{h+1}}[/tex]
Cioè divido il numero totale di nodi per quelli di altezza h.
Però se io ho una heap completa, con 7 nodi, in questo caso per determinare il numero di nodi ad altezza h mi basterebbe dire che sono [tex]2^h[/tex], invece con quella forumla per calcolare il numero all' altezza 2 avrei [tex]\frac{7}{8}[/tex] giusto? Che arrotondato da 1, che media è scusami, non capisco sono proprio cocciuto
Per quanto riguarda la complessità dell' algoritmo avevi ragione tu, si tratta di un' uguaglianza che rappresenta la classe di appartenenza.
Il mio libro è il Cormen: Introduzione agli algoritmi e strutture dati 2° edizione. Il problema è che questo discorso sul numero di nodi massimo non è spiegato ma solo proposto come esercizio da dimostrare.
P.S ti ringrazio come sempre, se puoi dare un' occhiata a delle ricorrenze che ho postato recentemente sugli alberi di ricorsione mi farai un favore, ho dimenticato alcune cose....grazie:
altra-equazione-di-ricorrenza-come-si-continua-t79962.html
Il mio libro è il Cormen: Introduzione agli algoritmi e strutture dati 2° edizione. Il problema è che questo discorso sul numero di nodi massimo non è spiegato ma solo proposto come esercizio da dimostrare
se possiedi il cormen tutto ciò divrebbe essere spiegato in qualche modo (non direttamente, conoscendo il libro), se lo avessi sotto mano ti direi dove guardare...
Se non riesci a seguire la metodologia Pro del Cormen, ti consiglio di valutare di utilizzare un altro libro.
Io utilizzai: "Algoritmi e strutture dati - 2° ed." di Bertossi e Montresor, più discorsivo ma altrettanto rigoroso (il cormen lo utilizzato come complemento)
Se hai dubbi chiedi pure
Bò semmai mi toccherà improvvisare qualcosa, non capisco perchè il libro al posto di dire dimostrare questa cosa per esercizio non fa come in tutti i libri la dimostrazione lui, odio che debba dimostrare per esercizio da solo una cosa che mi possa essere chiesta all'orale.
Non saprei, quello che dici mi torna, cioè che i nodi interni sono a [tex]\left \lfloor \frac{n}{2} \right \rfloor[/tex] mentre le foglie siano a [tex]\left \lfloor \frac{n}{2} \right \rfloor+1[/tex]
Quindi io posso calcolare il numero di nodi ad altezza h dividendo n per il numero [tex]2^h[/tex] e ho [tex]\frac{n}{2^h}[/tex], siccome le foglie si ottengono da [tex]\left \lfloor \frac{n}{2} \right \rfloor+1[/tex] allora aggiungo a quella potenza un altro termine e diventa: [tex]\left \lceil \frac{n}{2^{h+1}} \right \rceil[/tex].
Bò.....ho provato a ragionaci, ma l' intuito non è mai stato il mio forte, finisce che invento....
Poi.....tra l' altro questo discorso sui nodi interni e le foglie lo so perchè ho provato a rappresentare le heap e mi quadra alla perfezione, però sempre in un esercizio chiede di dimostrare che le foglie in una heap sono a partire da [tex]\left \lfloor \frac{n}{2} \right \rfloor+1[/tex]. A me quadra, però mica saprei dimostrarlo....
Grazie comunque della pazienza, purtroppo sono tanto lento che finisce che sul forum le persone diventino tutor personali
Non saprei, quello che dici mi torna, cioè che i nodi interni sono a [tex]\left \lfloor \frac{n}{2} \right \rfloor[/tex] mentre le foglie siano a [tex]\left \lfloor \frac{n}{2} \right \rfloor+1[/tex]
Quindi io posso calcolare il numero di nodi ad altezza h dividendo n per il numero [tex]2^h[/tex] e ho [tex]\frac{n}{2^h}[/tex], siccome le foglie si ottengono da [tex]\left \lfloor \frac{n}{2} \right \rfloor+1[/tex] allora aggiungo a quella potenza un altro termine e diventa: [tex]\left \lceil \frac{n}{2^{h+1}} \right \rceil[/tex].
Bò.....ho provato a ragionaci, ma l' intuito non è mai stato il mio forte, finisce che invento....
Poi.....tra l' altro questo discorso sui nodi interni e le foglie lo so perchè ho provato a rappresentare le heap e mi quadra alla perfezione, però sempre in un esercizio chiede di dimostrare che le foglie in una heap sono a partire da [tex]\left \lfloor \frac{n}{2} \right \rfloor+1[/tex]. A me quadra, però mica saprei dimostrarlo....
Grazie comunque della pazienza, purtroppo sono tanto lento che finisce che sul forum le persone diventino tutor personali
Grazie comunque della pazienza, purtroppo sono tanto lento che finisce che sul forum le persone diventino tutor personali
non preoccuparti, un forum serve a scambiarsi idee, opinioni e spiegazioni. Se no, non ne vedo l'utilità, esistono i libri.
Bò semmai mi toccherà improvvisare qualcosa, non capisco perchè il libro al posto di dire dimostrare questa cosa per esercizio non fa come in tutti i libri la dimostrazione lui, odio che debba dimostrare per esercizio da solo una cosa che mi possa essere chiesta all'orale.
La metodologia del Cormen si dice "Pro".
"Pro" sta per Professional, cioè ti da tutto il necessario direttamente o, la maggior parte, indirettamente per capire un argomento, una materia e risolvere gli esercizi proposti. Il libro è chiuso rispetto agli argomenti proposti. Se sai risolvere gli esercizi puoi darti il nome di Pro. Cioè possiedi la materia che studi (poi Pro ha anche altri significati).
Molte volte gli esercizi sono dati come homework nei corsi universitari americani.
Pure io la ho detestata questa metodologia (ci fai il callo e via). Ma è come sbattere contro un muro, se sai che nel libro c'è il necessario per risolvere gli esercizi, cerchi di svolgerli o almeno capirli. Se no cambi libro, non c'è altro da fare.
___________________________________________________________________________________________________________
Si dai ci sei su un passaggio, ma ti riscrivo il tutto in maniera più semplice e diretta, senza fare giri che ti creano confusione.
Rileggendo ciò che ho scritto, se non hai compreso un passaggio chiave che collega tutto, non penso tu possa capire il perchè di sta limitazione (è un piccolo problema rispetto ad altri).
Molti libri avanzati, almeno per quanto riguarda la matematica, sono scritti in questo modo lasciando tante cose per esercizio. Ha il vantaggio di permettere diversi livelli di lettura e di adattarsi a più tipi corsi (quelli meno avanzati ignorano più o meno gli esercizi mentre gli altri li devono fare). In molti corsi che ho fatto, gli esercizi che venivano chiesti come teoria venivano però spiegati a lezione. Per i libri più diffusi è comunque abbastanza facile trovare le soluzioni degli esercizi su internet o nei programmi p2p.. Nel caso del libro di Cormen sono pubblicati su sito del MIT come spiegato nella FAQ sul sito istituzionale di Cormen. Fa sicuramente bene cercare di risolverli da solo o con l'aiuto di altri, ma se hai dubbi di aver "inventato qualcosa", dai pure un'occhiata lì.
Riproviamo
Allora:
ciò che bisogna dimostrare è che in un heap di $n$ elementi ci sono al più $\lceil n/(2^{i+1}) \rceil$ nodi di altezza $i$. (*)
Un heap binario può essere rappresentato come un albero quasi completo e un vettore.
Le proprietà degli alberi te le ho già elencate.
Il vettore di $n$ elementi ha questa proprietà (oltre quelle che trovi sul libro):
- da $1$ a $\lfloor n/2 \rfloor$ sono rappresentati i nodi interni.
- da $\lfloor n/2 \rfloor +1$ ad $n$ sono le foglie.
I nodi interni sono $\lfloor n/2 \rfloor$ perchè se noti in un albero, dalla proprietà sopra, i nodi interni sono al massimo $2^{h} - 1\ ,h=\lfloor log_(2)(n) \rfloor$ e togliendo il floor: $\lfloor log_(2)(n) \rfloor > log_2(n) - 1 rArr h=log_2(n) - 1$ (**)
Se semplifichiamo e ci riduciamo a solo alberi completi e ti ricordi la proprietà dell'esponziale in base qualunque: $a^{log_{b}(n)} = n^{log_{b}(a)}$
Per (**)
$2^{h} - 1 = 2^{log_{2}(n)-1} -1 < 2^{log_{2}(n)-1} = 2^{log_{2}(n)}/2 = n^{log_{2}(2)}/2 = n/2$ ed ecco il valore cercato (ricorda la semplificazione) cioè il numero massimo di nodi interni a livello $h-1$.
Ora la parte importante, se noti l'algoritmo heapCreate() (il costruttore da zero dell'Heap, ogni libro usa la sua notazione) va in ricorsione inversa dall'elemento $\lfloor n/2 \rfloor$ fino ad $1$, cioè in ricorsione sui nodi interni, escludendo le foglie, questo perchè per definizione sono già (max-min)heap.
heapCreate() chiama una funzione (o lo fa in loco) che ristruttura l'heap, cioè controlla che il vettore sia veramente (max-min)heap, facendo uno swap tra un nodo e le foglie. Cioè il vettore tra $\lfloor n/2 \rfloor +1$ ad $n$ sono possibili heap da cui far iniziare una ricorsione della ristrutturazione dell'heap (guarda il libro se non ti è chiaro come funziona l'algoritmo).
Premesso questo, l'altezza che la proprietà (*) si riferisce è rovesciata.
l'altezza $0$ (caso base) non è riferita alla radice, ma alle foglie, cioè il numero massimo di nodi che si hanno a profondità $h$ sono $\lceil n/(2^{0+1}) \rceil = \lceil n/2 \rceil = n - \lfloor n/2 \rfloor$
dopo tutto questo, riusciresti a continuare la dimostrazione per induzione che ho indirittamente inziato?
Il caso base è altezza $0$ pari al livello $h$ delle foglie.
Il passo successivo sarà su livello $h-1$ ed altezza $1$, prova su altezza $i$ e livello $h-k$ con il passo induttivo.
Se hai problemi ti do una piccola mano, ma vorrei che lo dimostri te.
@apatriarca:
ma da quando sono disponibili le soluzioni per tutti, questa è una novità...penso sia solo dalla terza edizione. Troppo facile così
EDIT:
ho messo una pezza con (**) da prendere come idea, non come dimostrazione formale.
Allora:
ciò che bisogna dimostrare è che in un heap di $n$ elementi ci sono al più $\lceil n/(2^{i+1}) \rceil$ nodi di altezza $i$. (*)
Un heap binario può essere rappresentato come un albero quasi completo e un vettore.
Le proprietà degli alberi te le ho già elencate.
Il vettore di $n$ elementi ha questa proprietà (oltre quelle che trovi sul libro):
- da $1$ a $\lfloor n/2 \rfloor$ sono rappresentati i nodi interni.
- da $\lfloor n/2 \rfloor +1$ ad $n$ sono le foglie.
I nodi interni sono $\lfloor n/2 \rfloor$ perchè se noti in un albero, dalla proprietà sopra, i nodi interni sono al massimo $2^{h} - 1\ ,h=\lfloor log_(2)(n) \rfloor$ e togliendo il floor: $\lfloor log_(2)(n) \rfloor > log_2(n) - 1 rArr h=log_2(n) - 1$ (**)
Se semplifichiamo e ci riduciamo a solo alberi completi e ti ricordi la proprietà dell'esponziale in base qualunque: $a^{log_{b}(n)} = n^{log_{b}(a)}$
Per (**)
$2^{h} - 1 = 2^{log_{2}(n)-1} -1 < 2^{log_{2}(n)-1} = 2^{log_{2}(n)}/2 = n^{log_{2}(2)}/2 = n/2$ ed ecco il valore cercato (ricorda la semplificazione) cioè il numero massimo di nodi interni a livello $h-1$.
Ora la parte importante, se noti l'algoritmo heapCreate() (il costruttore da zero dell'Heap, ogni libro usa la sua notazione) va in ricorsione inversa dall'elemento $\lfloor n/2 \rfloor$ fino ad $1$, cioè in ricorsione sui nodi interni, escludendo le foglie, questo perchè per definizione sono già (max-min)heap.
heapCreate() chiama una funzione (o lo fa in loco) che ristruttura l'heap, cioè controlla che il vettore sia veramente (max-min)heap, facendo uno swap tra un nodo e le foglie. Cioè il vettore tra $\lfloor n/2 \rfloor +1$ ad $n$ sono possibili heap da cui far iniziare una ricorsione della ristrutturazione dell'heap (guarda il libro se non ti è chiaro come funziona l'algoritmo).
Premesso questo, l'altezza che la proprietà (*) si riferisce è rovesciata.
l'altezza $0$ (caso base) non è riferita alla radice, ma alle foglie, cioè il numero massimo di nodi che si hanno a profondità $h$ sono $\lceil n/(2^{0+1}) \rceil = \lceil n/2 \rceil = n - \lfloor n/2 \rfloor$
dopo tutto questo, riusciresti a continuare la dimostrazione per induzione che ho indirittamente inziato?
Il caso base è altezza $0$ pari al livello $h$ delle foglie.
Il passo successivo sarà su livello $h-1$ ed altezza $1$, prova su altezza $i$ e livello $h-k$ con il passo induttivo.
Se hai problemi ti do una piccola mano, ma vorrei che lo dimostri te.
@apatriarca:
ma da quando sono disponibili le soluzioni per tutti, questa è una novità...penso sia solo dalla terza edizione. Troppo facile così
EDIT:
ho messo una pezza con (**) da prendere come idea, non come dimostrazione formale.
Non lo so se c'era anche per le edizioni precedenti, però non è l'unico libro che inserisce molta teoria negli esercizi ed è spesso abbastanza facile trovare le soluzioni su internet. Non sono sempre ufficiali però e a volte non contengono tutti gli esercizi. Per cui ho fatto semplicemente una ricerca su google ed è uscito quello..
Scusa, non ti seguo e mi sono dovuto fermare subito, non abbiamo mai detto che il numero di nodi interni è al massimo [tex]2^{h-1}-1[/tex], ma è [tex]2^h-1[/tex].
"Darèios89":
Scusa, non ti seguo e mi sono dovuto fermare subito, non abbiamo mai detto che il numero di nodi interni è al massimo [tex]2^{h-1}-1[/tex], ma è [tex]2^h-1[/tex].
è la stessa cosa, ma indicati in modi diversi.
[tex]2^h-1[/tex] è il livello $h$ generico.
[tex]2^{h-1}-1[/tex] è la massima profondità che è valida la terminologia di "nodo interno".
se vuoi metterla così:
[tex]2^h-1[/tex] = [tex]2^i-1[/tex]
[tex]2^{h}-1[/tex] è $i=h-1$ con $h= log_2(n)$
foglie: $2^(log_2(n))$
nodi interni: $2^{log_2(n)-1}-1$
ok?
EDIT:
sbagliato vedi: post554952.html#p554952
ma corretto nel dire livello $h$ generico, intendo che questa formula è valida per qualunque livello dell'albero fino ad $h-1$.
Si benissimo, ho preso anche il libro e ripassato un secondo due definizioni, mi quadra tutto, ora provando a continuare quella dimostrazione, non so se è corretto:
Siamo a:
[tex]\left \lceil \frac{n}{2^{0+1}} \right \rceil=\left \lceil \frac{n}{2} \right \rceil=n-\left \lfloor \frac{n}{2} \right \rfloor[/tex]
Quindi verifico per h=i:
[tex]\left \lceil \frac{n}{2^{i+1}} \right \rceil=\left \lceil \frac{n}{2^i2} \right \rceil=\left \lceil \frac{n}{2^i} \right \rceil\left \lceil \frac{n}{2} \right \rceil=(n-\left \lfloor \frac{n}{2} \right \rfloor)(n-\left \lfloor \frac{n}{2^i} \right \rfloor)[/tex]
Non so se va bene, poi....rimango fermo...
Siamo a:
[tex]\left \lceil \frac{n}{2^{0+1}} \right \rceil=\left \lceil \frac{n}{2} \right \rceil=n-\left \lfloor \frac{n}{2} \right \rfloor[/tex]
Quindi verifico per h=i:
[tex]\left \lceil \frac{n}{2^{i+1}} \right \rceil=\left \lceil \frac{n}{2^i2} \right \rceil=\left \lceil \frac{n}{2^i} \right \rceil\left \lceil \frac{n}{2} \right \rceil=(n-\left \lfloor \frac{n}{2} \right \rfloor)(n-\left \lfloor \frac{n}{2^i} \right \rfloor)[/tex]
Non so se va bene, poi....rimango fermo...
"Darèios89":
Si benissimo, ho preso anche il libro e ripassato un secondo due definizioni, mi quadra tutto, ora provando a continuare quella dimostrazione, non so se è corretto:
Siamo a:
[tex]\left \lceil \frac{n}{2^{0+1}} \right \rceil=\left \lceil \frac{n}{2} \right \rceil=n-\left \lfloor \frac{n}{2} \right \rfloor[/tex]
Quindi verifico per h=i:
[tex]\left \lceil \frac{n}{2^{i+1}} \right \rceil=\left \lceil \frac{n}{2^i2} \right \rceil=\left \lceil \frac{n}{2^i} \right \rceil\left \lceil \frac{n}{2} \right \rceil=(n-\left \lfloor \frac{n}{2} \right \rfloor)(n-\left \lfloor \frac{n}{2^i} \right \rfloor)[/tex]
Non so se va bene, poi....rimango fermo...
Ma \( \left \lceil \frac{n}{2^i2} \right \rceil \neq \left \lceil \frac{n}{2^i} \right \rceil\left \lceil \frac{n}{2} \right \rceil \). Basta prendere il caso particolare in cui \( 2^{i+1} \, | \, n \) (\(2^{i+1}\) divide \(n\) - non sono sicuro che questa notazione venga insegnata anche ad informatica) per cui posso togliere il floor ottenendo \( \frac{n}{2^i 2} = \frac{n}{2^i} \frac{n}{2} = \frac{n^2}{2^i 2} \) che è evidentemente falso. Non sono certo di capire dove vuoi arrivare con questi calcoli.
Quello che si vuole dimostrare è la proprietà:
"In un heap di $n$ elementi ci sono al più \(\lceil \frac n {2^{i+1}} \rceil\) nodi di altezza $i$"
Io ho fatto il giro largo con tutta la spiegazione, per non far cadere una proprità dal nulla. Se si dimostra per induzione la proprietà è di facile risoluzione, ma se non si comprende da dove viene non serve a nulla, a mio parere.
Comunque dimostriamo definitivamente sta proprietà, andiamo con induzione sull'altezza $i$.
abbiamo un heap H con $n$ elementi.
Caso base:
$i=0$ stiamo calcolando il numero di foglie.
\(n - \lceil \frac n {2^{0+1}} \rceil = \lfloor \frac n 2 \rfloor\) per le proprietà dell'heap, il caso base è provato.
ipotesi: la proprietà è vera per $i-1$
passo induttivo, provo per $i$.
se abbiamo ipotizzato che per altezza $i-1$ è vera, possiamo avere un nuovo heap $H_1$ ricavato da $H$ (senza le foglie di $H$)
Perciò $H_1$ ha $n/2 =$ \(n_{H_{1}^{i}}\) ($i$ rispetto all'altezza$ H^{i-1}$) nodi per le proprietà dell'heap (qua ho un dubbio se è ceil o floor, controllerò o se mi chiarite il dubbio penso comunque sia $\lfloor n/2 \rfloor$ # ).
Se pensiamo che $H_1$ è rivato da $H$, i nodi interni di $H$ (di altezza $i-1$) sono gli elementi di $H_1$ ad altezza $i$
Perciò per ipotesi induttiva:
\(n_{H^{i-1}} = n_{H_{1}^{i}} = \lceil \frac {n_{H_{1}^{i}}}{2^i} \rceil =\) (con dubbio #) \( \lceil \frac{\lfloor n/2 \rfloor} {2^i} \rceil < \frac n {2^{i+1}}\)
la proprietà è dimostrata.
se non c'è qualche errore di calcolo o svarioni colossali (probabile) questo è tutto.
@apatriarca:
se vuoi controllare i passaggi, mi faresti un favore
"In un heap di $n$ elementi ci sono al più \(\lceil \frac n {2^{i+1}} \rceil\) nodi di altezza $i$"
Io ho fatto il giro largo con tutta la spiegazione, per non far cadere una proprità dal nulla. Se si dimostra per induzione la proprietà è di facile risoluzione, ma se non si comprende da dove viene non serve a nulla, a mio parere.
Comunque dimostriamo definitivamente sta proprietà, andiamo con induzione sull'altezza $i$.
abbiamo un heap H con $n$ elementi.
Caso base:
$i=0$ stiamo calcolando il numero di foglie.
\(n - \lceil \frac n {2^{0+1}} \rceil = \lfloor \frac n 2 \rfloor\) per le proprietà dell'heap, il caso base è provato.
ipotesi: la proprietà è vera per $i-1$
passo induttivo, provo per $i$.
se abbiamo ipotizzato che per altezza $i-1$ è vera, possiamo avere un nuovo heap $H_1$ ricavato da $H$ (senza le foglie di $H$)
Perciò $H_1$ ha $n/2 =$ \(n_{H_{1}^{i}}\) ($i$ rispetto all'altezza$ H^{i-1}$) nodi per le proprietà dell'heap (qua ho un dubbio se è ceil o floor, controllerò o se mi chiarite il dubbio
penso comunque sia $\lfloor n/2 \rfloor$ # ).Se pensiamo che $H_1$ è rivato da $H$, i nodi interni di $H$ (di altezza $i-1$) sono gli elementi di $H_1$ ad altezza $i$
Perciò per ipotesi induttiva:
\(n_{H^{i-1}} = n_{H_{1}^{i}} = \lceil \frac {n_{H_{1}^{i}}}{2^i} \rceil =\) (con dubbio #) \( \lceil \frac{\lfloor n/2 \rfloor} {2^i} \rceil < \frac n {2^{i+1}}\)
la proprietà è dimostrata.
se non c'è qualche errore di calcolo o svarioni colossali (probabile) questo è tutto.
@apatriarca:
se vuoi controllare i passaggi, mi faresti un favore
Eh ci sono sul ragionamento, l' unica cosa non capisco quando dici [tex]nH_1^{i}[/tex] quella uguaglianza, [tex]\left \lfloor \frac{n}{2} \right \rfloor=nH_1^{i}[/tex] cioè cosa moltiplichi ad n con [tex]H_1^{i}[/tex]? Cosa significa i rispetto all' altezza [tex]H^{i-1}[/tex]?
"Darèios89":
Eh ci sono sul ragionamento, l' unica cosa non capisco quando dici [tex]nH_1^{i}[/tex] quella uguaglianza, [tex]\left \lfloor \frac{n}{2} \right \rfloor=nH_1^{i}[/tex] cioè cosa moltiplichi ad n con [tex]H_1^{i}[/tex]?
non è una moltiplicazione è un pedice per diversificare il numero di elementi di $H$ con quelli di $H_1$, puoi chiamarli come vuoi.
\(n = \text{pippo}\)
\(\frac{n}2 = \text{pluto} = \frac{\text{pippo}}2 \)
Cosa significa i rispetto all' altezza [tex]H^{i-1}[/tex]?
intendo dire che se $H$ è un albero
$H_1$ è un sottoalbero di $H$.
perciò se $H$ ad altezza $i-1$, $H_1$ avrà altezza $h$ cioè profondità radice-foglia massima che è equivalente alla posizione $i$ di H.
in parole becere: le foglie di $H_1$ stanno al livello $i-1$ di $H$ (sottoalbero radicato).
ok?
Aaaaaah, perfetto, si un modo per diversificare le cose, si adesso mi quadra completamente, aggiungo questa pagina tra i preferiti così me la posso scrivere sul quaderno e ripassare la dimostrazione di volta in volta. Grazie mille come al solito 
Ci si becca in qualche ricorrenza....forse...XD
Ci si becca in qualche ricorrenza....forse...XD
Ottimo. Di nulla, alla prossima
Ciao, riprendo questo post per una cosa, ho riletto e tra le proprietà che avevi elencato sugli alberi binari c' è che la profondità i è data da [tex]i=h-i[/tex]. Ho trovato strana come definizione, che significa? Se io dovessi considerare una fogli di un albero con 7 nodi avrei che ogni foglia ha profondità 2, ma non risulta che 2=h-i cioè 2=2-2.....
Del resto non mi pare che [tex]2^h-1=2^{h-1}-1[/tex], come possiamo dirlo?
Del resto non mi pare che [tex]2^h-1=2^{h-1}-1[/tex], come possiamo dirlo?
"Darèios89":
Ciao, riprendo questo post per una cosa, ho riletto e tra le proprietà che avevi elencato sugli alberi binari c' è che la profondità i è data da [tex]i=h-i[/tex]. Ho trovato strana come definizione, che significa? Se io dovessi considerare una fogli di un albero con 7 nodi avrei che ogni foglia ha profondità 2, ma non risulta che 2=h-i cioè 2=2-2.....
ovviamente è un assurdo
ho corretto il post.
se hai una profondità $i=h-k$ con $k=0,1,....,h$
come riferimento l'altezza $h$ andrai in ordine inverso a partire dal fondo dell'albero a calcolarlo perciò con $k=0$ corrisponde all'altezza $h$.
Del resto non mi pare che [tex]2^h-1=2^{h-1}-1[/tex], come possiamo dirlo?
se ti riferisci a questo: post549476.html#p549476
forse è questione di terminlogia, ma dipende dal contesto, rileggerò i vari post chissà cosa intentedevo. Secondo me deriva dal fatto che utilizzo le stesse lettere per dire cose diverse.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo