Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Programmazione 2, 9 CFU => Topic started by: AnGeL88 on 03-07-2010, 18:33:04



Title: Capitolo 4
Post by: AnGeL88 on 03-07-2010, 18:33:04
Salve ragazzi... stavo dando un'occhiata al programma del prof faro... Nello specifico, sapete per caso di cosa non ha parlato il prof all'interno del capitolo 4 riguardo la complessità asintotica? Ci sono le dimostrazioni? Grazie!


Title: Re:Capitolo 4
Post by: peppe89ct on 05-07-2010, 11:50:01
Fallo tutto tranne omega e theta.
Falla benissimo la notazione O..........


Title: Re:Capitolo 4
Post by: AnGeL88 on 06-07-2010, 11:35:51
Fallo tutto tranne omega e theta.
Falla benissimo la notazione O..........

ok grazie mille ^^
E invece per quanto riguarda l'implementazione degli alberi binari mediante struttura collegata (cioè da pag. 255 capitolo 7)? mi sembra alquanto complicata e francamente non so se ne ha parlato il prof a lezione.....


Title: Re:Capitolo 4
Post by: peppe89ct on 06-07-2010, 15:11:50
fai i pseudocidi del capitolo 7 quelli inziali tipo post pre e inorder...depth e height.
poi per quanto riguarda l'albero binario ha spiegato a lezione lui tutti metodi....
ti conviene  contattare quancuno che li ha.


Title: Re:Capitolo 4
Post by: AnGeL88 on 10-07-2010, 10:16:58
ok grazie mille! ^_^ infatti notavo che vengono implementati in maniera un pò... contorta  nella classe BST :-ciao


Title: Re:Capitolo 4
Post by: aryanna on 10-07-2010, 10:55:38
nel libro nel capitolo degli alberi binari di ricerca ci sono anche gli alberi AVL che a lezione abbiamo fatto teoricamente ora mi è venuto un dubbio... differenza tra alberi n-ari e binari in altre parole è che noi in un albero binario dobbiamo sempre garantire che sia anche bilanciato o nn c'entra nulla..?


Title: Re:Capitolo 4
Post by: XDnl on 10-07-2010, 11:03:07
nel libro nel capitolo degli alberi binari di ricerca ci sono anche gli alberi AVL che a lezione abbiamo fatto teoricamente a
Non ho seguito tutte le lezioni, ma non mi risulta che abbiamo fatto gli alberi AVL (non sono elencati nel diario delle lezioni).

Quote
ora mi è venuto un dubbio... differenza tra alberi n-ari e binari in altre parole è che noi in un albero binario dobbiamo sempre garantire che sia anche bilanciato o nn c'entra nulla..?
Gli alberi binari sono dei particolari alberi n-ari (con n = 2). In un albero n-ario ogni nodo puo' avere fino ad un massimo di n figli. Il bilanciamento non c'entra.


Title: Re:Capitolo 4
Post by: cock86 on 10-07-2010, 11:08:37
Quote
differenza tra alberi n-ari e binari
ti riferisci agli alberi avl?? non vorrei sbagliarmi ma mi sa che gli alberi avl n-ari non esistono. Sono solo binari e garantiscono il bilanciamento grazie ad un particolare coefficiente.
In generale la differenza tra n-ari e binari è che nagli alberi binari ogni nodo ha al più due figli, negli n-ari può avere al più n figli (con n € {3,4,5 ...}).
Quindi binario è un particolare albero n-ario con n=2. Entrambi possono essere sbilanciati.


Title: Re:Capitolo 4
Post by: XDnl on 10-07-2010, 11:10:16
Esattamente  .smile
Citando un esercizio del professore:
Code:
Un albero si dice autobilanciante se è in grado di modificare la propria struttura in modo tale da trasformarsi in un albero completo, a meno dell'ultimo livello che è riempito da sinistra verso destra.


Title: Re:Capitolo 4
Post by: peppe89ct on 11-07-2010, 11:58:41
nel libro nel capitolo degli alberi binari di ricerca ci sono anche gli alberi AVL che a lezione abbiamo fatto teoricamente a
Non ho seguito tutte le lezioni, ma non mi risulta che abbiamo fatto gli alberi AVL (non sono elencati nel diario delle lezioni).

Quote
ora mi è venuto un dubbio... differenza tra alberi n-ari e binari in altre parole è che noi in un albero binario dobbiamo sempre garantire che sia anche bilanciato o nn c'entra nulla..?
Gli alberi binari sono dei particolari alberi n-ari (con n = 2). In un albero n-ario ogni nodo puo' avere fino ad un massimo di n figli. Il bilanciamento non c'entra.

 .quoto  .quoto  .quoto  .quoto  .quoto  .quoto