od muffined » 21. 1. 2023 13:08
Toto je skúška z 19.1.2023. Dostali sme nasledujúce otázky:
1. Huffmanové kódovanie
a) Ktorý z nasledujúcich kódov nemôže byť Huffmanov?
- {0, 10, 01}
- {01, 10}
- {00, 01, 10, 110}
b) Vysvetlite otpimálnosť Huffmanovho kódovania
c) Je najeké lepšie kódovanie pre lossless compression?
2. BWT transformation of banana
a) napísať výsledok tejto transformácie
b) napísať a vysvetliť dekódovanie
c) prečo je to dobré pre lossless compression?
3. Hlavné myšlienky video kompresie
Čiastočné riešenie/hinty:
1. a) ano, nie, nie - vysvetliť na tom, že v prvom vieme napisat input taký, že toto bude kód. V ostatných stačí argument, že ak postavíme stromy týchto kódov, bude tam vrchol, ktorý má iba jedného syna a tým pádom to nie je HC.
b) napísať lemmy s tým spojené, spomenúť Kraft-McMillan inequality a že HC je uniquely decodable.
c) artimetické kódovanie + argument s entropiou - toto je v nejakom predošlom príspevku.
2) a) napísať cykliské transformácie, ich abecedné zoradenie a výsledný vektor aj s číslom riadku, v ktorom je pôvodné slovo
b) popísať ten algoritmus, že máme pole F, T, L a ako sa používajú + že dekódovanie ide od konca
c) povedať, že chceme aby rovnaké písmená boli pri sebe a taktiež spomenút Move To Front a prečo je to dobré
3) toto som moc nevedela ale napísala som tam niečo o motion vectore. Potom sa ma pýtal na DCT a druhy rôznych framov (P, I, B) a trošku to spájal aj s JPEG ako sa tam využíva DCT.
Doplňujúca otázka: povedať niečo o lossless compression obrázkov (GIF, PNG), hlavne PNG a aký algoritmus sa tam používa (predikcia a LZ77)
Taktiež viem o zadaní z iného termínu:
1. Udělat huffmanuv kód z danejch pravděpodobností znaků. To mělo asi 5 poduloh, spocitat entropii, průměrnou délku slova, jakej je vztah mezi průměrnou délkou a tou entropii a pak ten priklad na maximální hloubku než dojde k přetečení u huffmanova stromu z predchádzajúcich príspevkov.
2. Elias codes a universality
3. Porovnejte z hlediska komprese png a jpeg
Toto je skúška z 19.1.2023. Dostali sme nasledujúce otázky:
1. Huffmanové kódovanie
a) Ktorý z nasledujúcich kódov nemôže byť Huffmanov?
- {0, 10, 01}
- {01, 10}
- {00, 01, 10, 110}
b) Vysvetlite otpimálnosť Huffmanovho kódovania
c) Je najeké lepšie kódovanie pre lossless compression?
2. BWT transformation of [b]banana[/b]
a) napísať výsledok tejto transformácie
b) napísať a vysvetliť dekódovanie
c) prečo je to dobré pre lossless compression?
3. Hlavné myšlienky video kompresie
Čiastočné riešenie/hinty:
1. a) ano, nie, nie - vysvetliť na tom, že v prvom vieme napisat input taký, že toto bude kód. V ostatných stačí argument, že ak postavíme stromy týchto kódov, bude tam vrchol, ktorý má iba jedného syna a tým pádom to nie je HC.
b) napísať lemmy s tým spojené, spomenúť Kraft-McMillan inequality a že HC je uniquely decodable.
c) artimetické kódovanie + argument s entropiou - toto je v nejakom predošlom príspevku.
2) a) napísať cykliské transformácie, ich abecedné zoradenie a výsledný vektor aj s číslom riadku, v ktorom je pôvodné slovo
b) popísať ten algoritmus, že máme pole F, T, L a ako sa používajú + že dekódovanie ide od konca
c) povedať, že chceme aby rovnaké písmená boli pri sebe a taktiež spomenút Move To Front a prečo je to dobré
3) toto som moc nevedela ale napísala som tam niečo o motion vectore. Potom sa ma pýtal na DCT a druhy rôznych framov (P, I, B) a trošku to spájal aj s JPEG ako sa tam využíva DCT.
Doplňujúca otázka: povedať niečo o lossless compression obrázkov (GIF, PNG), hlavne PNG a aký algoritmus sa tam používa (predikcia a LZ77)
Taktiež viem o zadaní z iného termínu:
1. Udělat huffmanuv kód z danejch pravděpodobností znaků. To mělo asi 5 poduloh, spocitat entropii, průměrnou délku slova, jakej je vztah mezi průměrnou délkou a tou entropii a pak ten priklad na maximální hloubku než dojde k přetečení u huffmanova stromu z predchádzajúcich príspevkov.
2. Elias codes a universality
3. Porovnejte z hlediska komprese png a jpeg