MATA2500 Information Theory (2–6 cr)

Study level:
Intermediate studies
Grading scale:
0-5
Language:
Finnish
Responsible organisation:
Department of Mathematics and Statistics
Curriculum periods:
2020-2021, 2021-2022, 2022-2023

Tweet text

Informaatioteoria

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

Perusosa: Calculus 1-2, Lineaarinen algebra ja geometria, eli harjaantuneisuutta todistamiseen. Todennäköisyyslaskennan ja diskreetin matematiikan perustiedoista on hyötyä.

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.

Study materials

The courses own lecture notes or, almost comparatively; David MacKay: Information Theory, Inference and Learning Algorithms, Sections 1-5 jand 8-10.

Completion methods

Method 1

Description:
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.
Evaluation criteria:
Arviointi perustuu kurssikokeeseen, harjoitustehtäviin sekä mahdollisen harjoitustyön arvosanaan.
Select all marked parts
Parts of the completion methods
x

Teaching (2–6 cr)

Type:
Participation in teaching
Grading scale:
0-5
Language:
Finnish
No published teaching