Uvod v teorijo informacij

delo diplomskega seminarja

Primož Durcik (Avtor), Tomaž Košir (Mentor), Gregor Šega (Komentor)

Povzetek

V delu diplomskega seminarja sem se ukvarjal z iskanjem kodiranja, ki ima najmanjšo pričakovano dolžino. Takšnemu kodiranju pravimo optimalno kodiranje. Najprej sem določil omejitve dolžin optimalnega kodiranja in dokazal Kraftovo neenakost za predponska kodiranja in kodiranja, ki se jih da enolično odkodirati (enolična kodiranja). Kraftova neenakost nam namreč daje potreben in zadosten pogoj za obstoj predponskega kodiranja ali enoličnega kodiranja za dano množico dolžin. V zaključku dela pa sem se osredotočil na Huffmanovo kodiranje. Na primerih sem predstavil idejo Huffmanovega algoritma ter povezave z nekaterimi drugimi matematičnimi problemi. Nato sem podal teoretično ozadje algoritma in dokazal, da je kodiranje, ki ga dobimo s Huffmanovim algoritmom, optimalno.

Ključne besede

matematika;entropija;Huffmanove kode;informacija;kode;kodiranje;Kraftova neenakost;optimalno kodiranje;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2018
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
Založnik:	[P. Durcik]
UDK:	519.8
COBISS:	18429529
Št. ogledov:	623
Št. prenosov:	242
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Introduction to information theory
Sekundarni povzetek:	In the course of the diploma seminar I was looking for code with the smallest expected length. Such code is called optimal code. First I defined the limits of lengths of optimal code and presented Kraft inequality for prefix code and uniquely decodable code. Kraft inequality gives us a necessary and sufficient condition for the existence of a prefix code or a uniquely decodable code for a given set of codeword lengths. At the end of my work I focused on Huffman codes. Using examples I presented the idea of Huffman algorithm and the connection with some other mathematical problems. Then I gave the theoretical background to the algorithm and concluded that the code obtained with the Huffman algorithm is optimal.
Sekundarne ključne besede:	mathematics;entropy;Huffman codes;information;codeword;codes;coding;Kraft inequality;optimal coding;Shannon information;
Vrsta dela (COBISS):	Delo diplomskega seminarja/zaključno seminarsko delo/naloga
Študijski program:	0
Komentar na gradivo:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Finančna matematika - 1. stopnja
Strani:	27 str.
ID:	10958730