MATA2500 Informaatioteoria (2–6 cr)
Tweet text
Description
Kurssin tarkoituksena on johdatella informaation käsitteen ja sen matemaattisen analysoinnin perusideoihin. Kurssin sisältö saattaa varioida hieman luentokertojen välillä, mutta suuntaa-antava sisältö on seuraava. (Ohjeistuksellisesti syventävän osion kohdat merkitty "(S)".)
1) Informaatio paikallaan:
- Informaatiosisältö
- Shannonin entropia
- Endollinen entropia
- Yhteisentropia
- Kullback-Leibler -divergenssi (S)
- Kolmogorov-kompleksisuus ja pakkauksen rajoista
- Gödelin epätäydellisyyslauseen idea (S)
- Kolmogorov-kompleksisuus ja Halting problem (S)
- Maksimientropian periaate (S)
- Martin-löf -satunnaisuus
- Chaitinin Omega-vakio (S)
2) Informaatio liikkeessä
- Koodausteoria
- Huffmanin koodi
- Shannonin lähdekoodauslause
- Shannonin lähdekoodauslauseen todistus (S)
- Shannonin kanavakoodauslause
- Shannonin kanavakoodauslauseen todistus(S)
3) Muita aiheita:
- Coxin lause (S)
- Bayesiläinen päättely
- Yhteyksiä kryptografiaan, Unicity distance
- Alkulkukujen äärettömyystodistus informaatioteorian avulla
Sisältöä vastaa karkeasti David MacKay: Information Theory, Inference and Learning Algorithms, Luvut 1-5 ja 8-10, mutta kyseisessä kirjassa on tuolla alueella käsitteitä mitä ei ehditä kurssilla käsittelemään, ja toisaalta kyseisessä kirjassa ei puhuta Kolmogorov-kompleksisuudesta. Jälkimmäiseen löytyy materiaalia esimerkiksi lähteestä Sipser: Introduction to the Theory of Computation sekä Chaitin: From Philosophy to Program Size.
Kurssin perusosa (2 op) suoritetaan harjoitustehtävien perustehtävillä sekä kurssitentillä.
Kurssin matemaattinen laajennusosa (2 op) suoritetaan perusosan päälle tekemällä osaan liittyviä harjoitustehtäviä ja suorittamalla laajennusosan kurssitentti.
Kurssin soveltava lisätyö (2 op) suoritetaan harjoitustyöllä (essee tai ohjelmistoprojekti), joka käsittelee ja syventää jotakin kurssilla käydyistä tai siihen liittyvistä aiheista.
Learning outcomes
- Perusosa: Opiskelilja osaa todistaa informaation matemaattisia perusominaisuuksia ja käyttää informaation käsitettä ongelmien ratkaisussa.
- Laajennusosa: Opiskelija hallitsee informaation matemaattisen käytön ja osaa soveltaa sitä eri tilanteissa.
- Harjoitustyö: Opiskelija perehtyy omatoimisesti johonkin informaatioteorian haastavahkoon ominaisuuteen, johon kurssilla ei ole ehditty syventyä.
Additional information
Kurssin on tarkoitus toimia johdantona informaation perusominaisuuksiin matemaattisena käsitteenä. Kurssin voi suorittaa kolmessa eri laajuudessa; joko 2, 4 tai 6 op. Mahdollisuuksina ovat Perusosa 2op, Perus- ja Syventävä osa 4op tai Perus- ja syventävä osa sekä harjoitustyö/essee 6op.
Description of prerequisites
Matemaattinen laajennos: Perehtyneisyys todistamiseen ja matemaattiseen päättelyyn (esim. Todistamisen perusteet). Kursseista JMA 1-2, Todennäköisyyslaskenta 1 ja Johdatus diskreettiin matematiikkaan on hyötyä.
Harjoitustyö: Aihe sovitetaan omaan osaamiseen.
Compulsory prerequisites
Recommended prerequisites
Study materials
The courses own lecture notes or, almost comparatively; David MacKay: Information Theory, Inference and Learning Algorithms, Sections 1-5 jand 8-10.