Forum Panda Pirate
Forum Grenier xIF  
Panda Pirate, forum rôliste
Lisez d'abord la FAQ, svp =>[ FAQ ] [ Thread Index ] [ Search ] [ Archives ] [ Pandapirate ]

Topic: la solution pour ceux que ça interesse (attention, c chiant)
Posted by: Tandyys at mar. 11 oct. 2005 18:17:41 CEST

Keywords: squiiiiik!!

Message:

solution ENS, meilleure que la mienne, mais moins intuitive.

1: on montre que dans l'arbre d'un code optimal, les 2 lettres les moins fréquentes seront automatiquement "tout en bas" et dépendantes du même noeud.
preuve assez facile, si c'est pas le cas, on fait l'échange de position et on montre qu'il y a un gain net en taille

2: on montre que si un arbre correspond à un code optimal pour un alphabet à n lettres, alors en changeant les 2 lettres les moins courantes (en bas, donc) en une seule, de fréquence somme (x de fréquence fx, y de fréquence fy, devient "x ou y" de fréquence fx+fy), on obtient un arbre (pour l'alphabet de (n-1) lettres) correspondant à un code optimal. bref, on passe de opt(n) à opt(n-1) en coupant 2 feuilles**

concernant la fameuse somme "fréquence*taille de lettre", la différence entre les 2 arbres (ou code, c pareil) est fx+fy

3:on montre le résultat par recurrence sur la taille de l'alphabet
---alphabet de taille 1: évident

---si c'est vrai pour la taille n-1
on prend l'arbre de huffman et un arbre optimal pour n
on remonte d'une lettre par le procédé ci dessus
on voit que la différence dans notre super somme est à chaque fois fx+fy

or, pour un alphabet n-1, hufman est optimal, donc les sommes sont égales à n-1. comme la différence entre n et n-1 est la même pour Huffman et l'arbre optimal, donc au rang n, les sommes sont aussi les memes
Huff (n) = Huff (n-1) + fx + fy
Huff(n-1) = opt(n-1)
Opt(n) = opt(n-1) + fx + fy

donc Huff (n) = Opt (n), CQFD

**
dans l'arbre, ça revient à changer ce noeud à 2 fils-feuilles par une feuille:

|--x
-|
|--y

devient

-(x ou y)




Warning: mysqli_query() expects parameter 1 to be mysqli, null given in /home/clients/13eaf4559a54d78787520f07cab62616/web/panda/archreply.php on line 98

Warning: mysqli_fetch_array() expects parameter 1 to be mysqli_result, null given in /home/clients/13eaf4559a54d78787520f07cab62616/web/panda/archreply.php on line 101
<< Previous topic:  Site Down - Marneus, lun. 17 oct. 2005 15:43:10 CEST
>> Next topic:  La PIF du Monde du jeu - Brunal, dim. 09 oct. 2005 11:12:20 CEST

Top


Les sites autour du Panda
Pandapirate.net   CasusNO

Le GROG c'est bon, buvez-en!

Powered by Pandapirate, based on Zforum © XGRA 2001.