Curs Algoritmul Huffman si procedura Merge

Incarcat la data: 18 Decembrie 2009

Autor: Maria Mihaela

Pret: 50 credite

Numar pagini: 7

Tip fisier: rar

Marime fisier: 7782 kb

Algoritmul lui Huffman construieste un arbore binar de codificare optim. Demonstratie: Prin inductie dupa n = |E|. Pentru n  2 avem un singur arbore posibil si teorema e evident adevarata. Sa presupunem ca n  3. Notam cu TH arborele construit cu algoritmul lui Huffman pentru ponderile w1  w2  · · ·  wn. Algoritmul leaga intre ele frunzele e1 si e2 corespunzatoare ponderilor w1 si w2 si creeaza un arbore cu ponderea w1 + w2. Fie T0 H arborele construit de algoritmul lu Huffman din ponderile w1 + w2,w3, · · · ,wn. Avem relatia Cost(TH) = Cost(T0 H) + w1 + w2.

Conform ipotezei de inductie, T0Heste arbore optim pentru n - 1 frunze cu ponderile w1 + w2,w3, · · · ,wn. Fie Topt un arbore de codificare optim ce satisface Lema 2, adica frunzele e1 si e2 sunt frati in Topt. Fie T0 arborele obtinut din Topt inlocuind frunzele e1 si e2 si pe tatal lor cu o singura frunza de pondere w1 + w2. Apicand ipoteze de inductie Cost(T0 H ) Cost(T0)

Textul de mai sus reprezinta un extras din "Curs Algoritmul Huffman si procedura Merge". Pentru versiunea completa a documentului apasa butonul Download si descarca fisierul pe calculatorul tau. Prin descarcarea prezentei lucrari stiintifice, orice utilizator al site-ului www.studentie.ro declara si garanteaza ca este de acord cu utilizarile permise ale acesteia, in conformitate cu prevederile legale ablicabile in domeniul proprietatii intelectuale si in domeniul educatiei din legislatia in vigoare.

In cazul in care intampini probleme la descarcarea fisierului sau documentul nu este nici pe departe ceea ce se doreste a fi te rugam sa ne anunti. Raporteaza o eroare

Important!

Referatele si lucrarile oferite de Studentie.ro au scop educativ si orientativ pentru cercetare academica.

Iti recomandam ca referatele pe care le downloadezi de pe site sa le utilizezi doar ca sursa de inspiratie sau ca resurse educationale pentru conceperea unui referat nou, propriu si original.

Alti utilizatori au mai cautat: MERGEAlgoritmihuffmandate statisticecurs formator
Jacheta usoara verde oliv inchis Jacheta usoara verde oliv inchis Descriere produs:Tip: jachetaCuloare: verde oliv inchisMaterial: usorDetalii: margini...
Jacheta usoara violet inchis Jacheta usoara violet inchis Descriere produs:Tip: jachetaCuloare: violet inchisMaterial: usorDetalii: margini...
Camasa alba in dungi Camasa alba in dungi Descriere produs:- camasa alba cu dungi albastre- imprimeu text pe partea din spate- guler...