Uhm, mi sfugge qualcosa... ^^'
Convincetemi che, come dice il Cormen, in qualunque heap di n elementi vi sono al più
nodi di altezza h.
MindFlyer
Questo esercizio mi ha spiazzato un po', finché sono andato a vedere la definizione che dà di altezza. E' una definizione a cui non ero abituato: l'altezza di un nodo è la lunghezza del cammino discendente più lungo che parte dal nodo stesso. Insomma è la distanza della foglia più lontana del sottoalbero pendente da quel nodo. Ergo tutte le foglie hanno altezza 0, tutti i genitori di una foglia hanno altezza 1, etc.
Data questa definizione, è facile contare esattamente i nodi ad altezza 0, ovvero le foglie: sono [math]. Questo è sostanzialmente ciò che dice l'esercizio 6.1-7, che avrai fatto (altrimenti cazzo! cioè, volevo dire: altrimenti fallo!). Quindi vedi già che la formula è vera per h=0. Il resto segue per induzione e qualche conticino...
Ymir
Nella seconda edizione che ho non c'è l'esercizio che nella terza è 6.1-7... ma ora ho pure la terza!
Comunque graziee!
MindFlyer
Come grazie? Lasci a me il privilegio di scrivere la gaia soluzione? Che gentile!! -.-
Facciamo vedere prima che le foglie sono davvero [math]. Questo è vero non solo per gli alberi binari bilanciati, ma per tutti gli alberi binari in cui c'è al più un nodo con un solo figlio! Supponiamo prima che tutti i nodi abbiano 0 o 2 figli. Quelli con 0 figli li chiamiamo foglie, e diciamo che sono [math]. Quelli con 2 figli li chiamiamo interni, e diciamo che sono [math]. Dunque [math]. Notiamo che in questo caso [math] dev'essere dispari.
Adesso contiamo il numero di archi dell'albero in due modi diversi. Sia questo numero [math]. Abbiamo che [math], perché si tratta di un albero. Infatti, immaginiamo di togliere una foglia alla volta, col suo rametto attaccato, come se l'albero fosse una margherita. Insieme ad ogni foglia si toglie un rametto, finché resta solo la radice. A quel punto abbiamo tolto [math] nodi e [math] archi (e abbiamo scoperto che non ci ama, tanto per cambiare). Quindi i nodi totali devono essere [math].
Un altro modo di contare gli archi è questo: le foglie hanno un arco incidente, mentre i nodi interni hanno 3 archi incidenti, tranne la radice che ne ha 2. La somma delle incidenze nodo-arco è quindi [math]. In questo modo abbiamo contato ogni arco esattamente due volte (perché ogni arco è incidente a esattamente due nodi), e quindi abbiamo [math]. Uguagliando le due espressioni di [math], abbiamo [math].
Ricordando che [math] e sostituendo, viene fuori che [math]. Siccome [math] è dispari, abbiamo equivalentemente [math].
Supponiamo adesso che ci sia esattamente un nodo con un figlio, e che quindi [math] sia pari. Togliendo questo unico figlio si rimane con un albero che ha lo stesso numero di foglie (una foglia va via, ma il suo genitore diventa foglia!), e [math] nodi, i quali hanno tutti 0 o 2 figli. Per quanto detto sopra, sappiamo che qui le foglie sono [math]. Poiché [math] è pari, questo è uguale a [math].
Forti di questo lemma, passiamo al problema principale. Lo facciamo per induzione sull'altezza dell'albero. Per altezza 0, ovvero per l'albero che consiste della sola radice-foglia, la verifica è banale. Supponiamo adesso che l'albero sia alto un po' più di Leonardo DiCaprio, e vediamo che, grazie al lemma, i nodi di altezza [math], ovvero le foglie, sono esattamente [math]. Quindi ok. Adesso togliamo tutte le foglie, restando così con un albero bilanciato di [math] nodi. Per ipotesi induttiva, i nodi ad altezza [math] in questo albero sono al più [math]. Ora osserviamo che nell'albero originario questi nodi hanno altezza [math], perché qui c'è un livello di foglie in più. Sostituendo, abbiamo che i nodi a livello [math] sono al più (per via di quel [math]) [math], come volevamo.
Ymir
Uhm non intendevo che dovessi scrivere la dimostrazione... ho scritto grazie ringraziandoti di avermi fatto capire come aveva contato per arrivare a quella congettura ^^'
Beh, ormai che l'hai scritta, posso guardarla dopo averla fatta. Grazie anche di questo ahaha
... poverino, guarda quanto hai scritto °-°
Heap, numero nodi di altezza h
Torna a “[ALL] Algoritmica e Laboratorio”
Vai a
- Generale
- ↳ Discussioni
- ↳ Discussions (in english)
- ↳ I rappresentanti rispondono
- ↳ Parliamone
- ↳ Mercatino
- ↳ Tirocini
- ↳ Annunci
- ↳ Announcements (in english)
- ↳ Eventi
- I anno
- ↳ Algebra Lineare
- ↳ Analisi Matematica
- ↳ Fondamenti dell'Informatica
- ↳ Laboratorio I
- ↳ Programmazione e Algoritmica
- II anno
- ↳ Architetture e Sistemi Operativi
- ↳ Calcolo Numerico
- ↳ Calcolo Numerico - Vecchio Ordinamento
- ↳ Laboratorio II
- ↳ Paradigmi di Programmazione
- ↳ Ricerca Operativa
- ↳ Ricerca Operativa - Vecchio Ordinamento
- ↳ Statistica
- ↳ Statistica - Vecchio Ordinamento
- III anno
- ↳ Basi di Dati
- ↳ Basi di Dati - Vecchio Ordinamento
- ↳ Introduzione all'Intelligenza Artificiale
- ↳ Introduzione all'Intelligenza Artificiale - Vecchio Ordinamento
- ↳ Ingegneria del Software
- ↳ Ingegneria del Software - Vecchio Ordinamento
- ↳ Reti e Laboratorio III
- Complementari
- ↳ Algebra
- ↳ Cloud Computing
- ↳ Cloud e Green Computing
- ↳ Computer Grafica
- ↳ Crittografia
- ↳ Elementi di Calcolabilità e Complessità
- ↳ Elementi di Calcolabilità e Complessità - Vecchio Ordinamento
- ↳ Esperienze di programmazione
- ↳ Fisica
- ↳ Fisica - Vecchio Ordinamento
- ↳ Gestione di Reti
- ↳ Green Computing
- ↳ Interazione Uomo-Macchina
- ↳ Laboratorio di Basi di Dati
- ↳ Laboratorio di Web Scraping
- ↳ Sicurezza di Sistemi ICT
- ↳ Sviluppo di Applicazioni Mobili
- ↳ Sviluppo di Applicazioni Web
- ↳ Teoria dell'Informazione
- Vecchio Ordinamento
- ↳ I anno
- ↳ [ALL] Algoritmica e Laboratorio
- ↳ [AM] Analisi matematica
- ↳ [FIS] Fisica
- ↳ [LPP] Logica per la programmazione
- ↳ [MDAL] Matematica discreta e algebra lineare
- ↳ [PRL] Programmazione I e laboratorio
- ↳ II anno
- ↳ [AE] Architettura degli elaboratori
- ↳ [BD] Basi di dati
- ↳ [CPS] Calcolo delle probabilità e statistica
- ↳ [CN] Calcolo numerico
- ↳ [IS] Ingegneria del software
- ↳ [PR2] Programmazione II
- ↳ [RO] Ricerca Operativa
- ↳ [SOL] Sistemi operativi e laboratorio
- ↳ III anno
- ↳ [ECC] Elementi di calcolabili e complessità
- ↳ [PI] Programmazione di interfacce
- ↳ [IIA] Introduzione all'intelligenza artificiale
- ↳ [RCL] Reti di calcolatori e laboratorio
- ↳ Advanced databases
- ↳ Advanced programming
- ↳ Advanced software engineering
- ↳ Algorithm design
- ↳ Algorithm engineering
- ↳ Artificial intelligence fundamentals
- ↳ Bioinformatics
- ↳ Competitive programming and contests
- ↳ Computational mathematics for learning and data analysis
- ↳ Data mining
- ↳ Human language technologies
- ↳ ICT infrastructures
- ↳ ICT risk assessment
- ↳ Information Retrieval
- ↳ Intelligent Systems for pattern recognition
- ↳ Laboratory for innovative software
- ↳ Languages, compilers and interpreters
- ↳ Machine learning
- ↳ Mobile and cyber-physical systems
- ↳ Parallel and distributed systems: paradigms and models
- ↳ Peer to peer systems and blockchains
- ↳ Principles for software composition
- ↳ Smart applications
- ↳ Software validation and verification
- Links
- ↳ HomePage Dipartimento
- ↳ Portale Esami