Algoritmy komprese dat - NSWI072

• Anglický název: Data Compression Algorithms
• Zajišťuje: Katedra softwaru a výuky informatiky (32-KSVI)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Další informace: http://ksvi.mff.cuni.cz/~dvorak/vyuka/NSWI072/
• Garant: doc. RNDr. Tomáš Dvořák, CSc.
• Vyučující: doc. RNDr. Tomáš Dvořák, CSc.
• Třída: Informatika Mgr. - volitelný
• Kategorizace předmětu: Informatika > Softwarové inženýrství, Teoretická informatika

Anotace

čeština

Přednáška podává přehled algoritmů používaných pro bezztrátovou i ztrátovou kompresi dat. Bezztrátová komprese dat • Statistické metody: Huffmanův kód, aritmetické kódování, adaptivní algoritmy, metody s konečným kontextem • Teorie informace a teoretické meze bezztrátové komprese • Slovníkové metody tříd LZ77 a LZ78, aplikace gzip, formáty GIF a PNG • Burrowsova-Wheelerova transformace, aplikace bzip2 Ztrátová komprese dat • skalární kvantizace • diferenční kódování, metody DPCM a ADPCM • transformační metody, standard JPEG • subpásmové kódování, standard MP3 • komprese videa,

Poslední úprava: T_KSVI (04.05.2015)

angličtina

This course surveys techniques used for both lossless and lossy data compression.

Poslední úprava: DVORAK (19.05.2004)

Podmínky zakončení předmětu

čeština

Předmět je zakončen ústní zkouškou. Otázky, které jsou u zkoušky pokládány, čerpají z témat, uvedených v sylabu předmětu, a to v rozsahu, v němž jsou tato témata probírána na přednášce.

Poslední úprava: Dvořák Tomáš, doc. RNDr., CSc. (13.10.2017)

angličtina

The course is concluded with an oral exam. Questions posed in the exam explore the topics included in the syllabus to the extent that these topics are covered in lectures.

Poslední úprava: Dvořák Tomáš, doc. RNDr., CSc. (13.10.2017)

Literatura

čeština

G. A. Harris, P. D. Johnson, D. R. Hankerson, Introduction to Information Theory and Data Compression, 2nd ed., Chapman & Hall/CRC, New York, 2019.

A. Moffat, A. Turpin, Compression and Coding Algorithms, Kluwer Academic Publishers, Boston, 2002.

D. Salomon, G. Motta, D. Bryant, Handbook of Data Compression, 5th edition, Springer-Verlag, 2010.

K. Sayood, Introduction to Data Compression, 5th ed., Morgan Kauffmann Publishers, San Francisco, 2017.

J. Čapek, P. Fabián, Komprimace dat: Principy a praxe, Computer Press, 2000.

Poslední úprava: Dvořák Tomáš, doc. RNDr., CSc. (24.09.2023)

angličtina

G. A. Harris, P. D. Johnson, D. R. Hankerson, Introduction to Information Theory and Data Compression, 2nd ed., Chapman & Hall/CRC, New York, 2019.

A. Moffat, A. Turpin, Compression and Coding Algorithms, Kluwer Academic Publishers, Boston, 2002.

D. Salomon, G. Motta, D. Bryant, Handbook of Data Compression, 5th edition, Springer-Verlag, 2010.

K. Sayood, Introduction to Data Compression, 5th ed., Morgan Kauffmann Publishers, San Francisco, 2017.

Poslední úprava: Dvořák Tomáš, doc. RNDr., CSc. (24.09.2023)

Sylabus

čeština

Bezztrátová komprese dat

• statistické metody: Huffmanův kód, aritmetické kódování, adaptivní algoritmy, metody s konečným kontextem

• teorie informace a teoretické meze bezztrátové komprese

• slovníkové metody tříd LZ77 a LZ78, aplikace gzip, formáty GIF a PNG

• Burrowsova-Wheelerova transformace, aplikace bzip2

Ztrátová komprese dat

• skalární kvantizace

• diferenční kódování, metody DPCM a ADPCM

• transformační metody, standard JPEG

• subpásmové kódování, standard MP3

• komprese videa, standard MPEG

Poslední úprava: Dvořák Tomáš, doc. RNDr., CSc. (01.05.2015)

angličtina

Lossless data compression

• statistical methods: Huffman coding, arithmetic coding, adaptive algorithms, finite context methods

• information theory and theoretical limits of lossless compression

• dictionary methods of classes LZ77 and LZ78, application gzip, GIF and PNG standards

• Burrows-Wheeler transform, application bzip2

Lossy data compression

• scalar quiantization

• differential coding, methods DPCM and ADPCM

• transform conding, JPEG standard

• subband coding, MP3 standard

• video compression, MPEG standard

Poslední úprava: Dvořák Tomáš, doc. RNDr., CSc. (01.05.2015)

Vstupní požadavky

čeština

Znalosti na úrovni předmětu Pravděpodobnost a statistika.

Poslední úprava: T_KSVI (04.05.2015)

angličtina

Knowledge at the level of the subject Probability and Statistics.

Poslední úprava: T_KSVI (04.05.2015)