Informaatioteorian peruskäsitteet, koodaaminen |
todennäköisyyslaskennan perusasiat (TN johdantokurssi) |
- määrittelee entropian (marginaali-, ehdollisen, yhteis-), keskinäisinformaation.
- annettuna yhteisjakauma, laskee em. suureet
- ratkaisee yhden em. suureista annettuna muiden arvot (esim. keskinäisinformaation annettuna marginaali- ja yhteisentropiat)
- määrittelee prefix-koodin ja dekoodattavan koodin
|
- annettuna koodi, laskee odotusarvoisen koodinpituuden
- soveltaa Kraft-McMillan -epäyhtälöä koodin olemassaolon päättelemiseen
- selvittää onko koodi optimaalinen soveltaen Shannonin kohinatonta lähdekoodauslausetta
|
- määrittelee entropian ei i.i.d.-tapauksessa
- soveltaa edellä mainittuja käsitteitä jatkuva-arvoisiin muuttujiin (differentiaalientropia)
- käyttää tyypillisia jonoja kohinattoman lähdekoodausteoreeman todistamiseen
|
Kompressiomenetelmät |
- tietorakenteiden perusteet (TiRa)
|
- toteuttaa Shannon-Fano -koodin.
|
- toteuttaa Huffman-koodin, mahdollisesti laskennallisesti ei-optimaalisella tavalla
|
- toteuttaa aritmeettisen koodin tai adaptiivisen Huffman-koodin
|
MDL-periaate |
- suositeltu: tilastotieteen esitietoja (suurimman uskottavuuden estimaattori)
|
- selittää Okkamin partaveitsen ja esittää esimerkkejä siitä
- perustelee sanallisesti miksi ylisovittaminen on ongelma
|
- yhdistää Okkamin partaveitsen ja MDL-periaatteen toisiinsa
- määrittelee kaksiosaiseen koodiin ja sekajakaumaan perustuvat universaalikoodit
- soveltaa MDL-periaatetta mallinvalintaan
|
- soveltaa NML-universaalikoodia mallinvalintatehtävään
- soveltaa MDL-periaatetta realistisessa mallinvalintaongelmassa (esim. Hutter prize
|
Kolmogorov-kompleksisuus |
- Turingin kone ja algoritmin käsite (Laskennan mallit)
|
- selittää sanallisesti Kolmogorov-kompleksisuuden
- todistaa yksinkertaisia ylärajoja Kolmogorov-kompleksisuudelle K(x) esittämällä x:n tuottavan ohjelman
|
- selittää Kolmogorov-kompleksisuuden laskettavuuteen liittyvän paradoksin
- todistaa tasaisesti jakautuneen merkkijonon Kolmogorov-kompleksisuuden odotusarvon alarajaksi merkkijonon pituuden
|
- tuntee Kolmogorov-kompleksisuuden variantit (prefix, resurssirajoitettu, jne)
- soveltaa normalisoitua kompressioetäisyyttä (NCD) ryvästykseen
|