582487 Tiedon tiivistämisen tekniikat (4 op)
Taso
Kurssi on algoritmien ja koneoppimisen linjan valinnainen syventävä opintojakso.
Ennakkovaatimukset
Kurssilla sovelletaan Merkkijonomenetelmien tekniikoita tiedon tiivistämiseen. Tämän vuoksi etenkin indeksirakenteisiin (loppuosapuu / loppuosataulukko) liittyvät perusteet oletetaan tunnetuiksi edeltävältä kurssilta. Todennäköisyyslaskennan perusteista on myös hyötyä informaatioteorian alkeiden ymmärtämiseksi sekä algoritmien tiivistystulosten analysoinneissa.
Järjestäjät
Luennoija Veli Mäkinen,
Assistentti Niko Välimäki
Uutisia
Kurssin arvostelu on valmistunut. Palautetilaisuus 12.12 klo 11.15-12:00 B230. Pisteytyksen periaatteet löytyvät täältä.
Luennot: 28.10.-04.12. TI, TO 12-14 B222
Harjoitukset: 03.11.-05.12. TO 10-12 C221
Koe: TI 09.12. 9-12 A111
Poikkeukset: Ensimmäinen harjoitus on siirretty pidettäväksi 4.11 TI 10-12 C221. Francois Nicolas pitää torstain 30.10 luennon. Jarkko Toivonen pitää laskuharjoitukset 2 ja 3.
Englanninkielinen kurssimoniste on myytävänä Yliopistopainossa, Exactum 1. kerros (hinta 5 euroa). Moniste on päivitetty kevään 2006 kurssille. Kurssin sisältö noudattelee suurelta osalta monistetta, joskin materiaalia täydentää syksyn aikana päivittyvät Powerpoint-kalvot.
Kurssiin liittyvien tiivistysmenetelmien implementointeja löytyy (kurssin edetessä) kurssiwikistä.
Kuvaus
Ensimmäinen osa kurssia kattaa vakiintuneet tiedon tiivistyksen tekniikat kuten Huffman koodauksen aritmeettisen koodauksen, Lempel-Ziv jäsennyksen, PPM:n, Burrows-Wheeler muunnoksen, ja kokonaislukukoodit. Painotus on algoritmeissa: miten tiivistää/purkaa tietoa tehokkaasti. Tiivistystulosten analyysien ymmärtämiseen vaadittava matemaattinen tausta käydään myös läpi. Tämä johdattaa käsitteisiin tiivistyvyys, tiivistymättämyys, entropia, ja Kolmogorov kompleksisuus. Toinen osa kurssia keskittyy uuteen tiedon tiivistyksen osa-alueeseen - tietorakenteiden tiivistämiseen. Tämä uusi osa-alue on syntynyt erityisesti laajamittaisten sekvenssianalyysiongelmien tarpeisiin bioinformatiikassa: opimme kurssilla miten suosittu tietorakenne, loppuosataulukko, voidaan esittää samassa tilassa kuin tiivistetty sekvenssi. Tämä tulos rakentuu kurssin ensimmäisen osan tekniikoiden päälle, sekä muutamaan hyödylliseen erityisesti tietorakenteiden tiivistykseen kehitettyyn tekniikkaan, joita käytetään myös usean muun tietorakenteen tiivistämiseen. Kurssin lopuksi käsitellään myös opittujen tekniikoiden sovelluksia (häviämättömässä) kuvan tiivistyksessä.
Kurssin suoritus
Kurssikoe järjestetään tiistaina 9.12 klo 16-20 salissa A111 ((alustava tieto). Kokeesta saa maksimissaan 60 pistettä. Aktiivinen osallistuminen harjoitukseen tuo maksimissaan 6 ylimääräistä pistettä (25%->1p,37.5%->2p,50%->3p,62.5%->4p,75%->5p,87.5%->6p). Arvostelu perustuu kokonaispisteisiin.
Aikataulu (alustava)
| Viikko | Päivä | Moniste | Aihe | Lisätietoa |
|---|---|---|---|---|
| 44 | TI 28.10 | 1.1.1, 2.1.1, 2.1.2 | Esittelyluento, taustaa, yksinkertaiset koodaukset, entropia, kokonaislukukoodit, käänteisindeksi | |
| 44 | TO 30.10 | 1.1.2, 2.1.3, 2.1.4 | Alkuosakoodit, Kraftin epäyhtälö, häviöttömän koodauksen teoreema, Shannon-Fano koodaus, Huffman koodaus | Luennot 1-2 (.ppt) Pdf |
| 45 | TI 4.11 | Harjoitus 1 | Tehtävät Mallivastaukset | |
| 45 | TI 4.11 | 2.1.5-2.1.7 | Huffman koodauksen implementointi, Huffman koodauksen analyysi, Adaptiivinen Huffman | |
| 45 | T0 6.11 | 2.1.8 | Aritmeettinen koodaus | Luennot 3-4 (.ppt) Pdf |
| 46 | TI 11.11 | 1.1.3-1.1.5, 2.2 | Kolmogorov kompleksisuus, tiivistymättömyys: alaraja järjestämiselle. Lempel-Ziv menetelmä, LZ77 koodaus loppuosapuulla, LZ78 | Loppuosapuun online konstruktio |
| 46 | TO 13.11 | Harjoitus 2 | Tehtävät Mallivastaukset | |
| 46 | TO 13.11 | 2.2,1.1.1,2.3 | Lempel-Ziv menetelmien analyysi, k-nnen asteen entropia, staattinen PPM | Luennot 5-6 (.ppt)Pdf |
| 47 | TI 18.11 | 2.3,2.4, | Adaptiivinen PPM, Burrows-Wheeler muunnos | |
| 47 | TO 20.11 | Harjoitus 3 | Tehtävät Mallivastaukset | |
| 47 | TO 20.11 | 2.4 - 2.4.2 | Burrows-Wheeler muunnoksen implementointi ja tiivistyvyyden analyysi, tiivistyksen kiihdytys | Luennot 7-8 (.ppt) Pdf |
| 48 | TI 25.11 | 3.1, 3.2 | Johdatus tietorakenteiden tiivistykseen: bittivektorit ja binääripuut, wavelet puu | |
| 48 | TO 27.11 | Harjoitus 4 | Tehtävät Mallivastaukset | |
| 48 | TO 27.11 | 3.3, 3.4.1 | Tiivistetty loppuosataulukko, takaperinhaku, itseindeksit | Luennot 9-10 (.ppt) Pdf |
| 49 | TI 2.12 | - (uusi asia, vain kalvoilla) | Tunnistekoodaus, implisiittinen tiivistyksen kiihdytys | Luento 11 (.ppt) Pdf |
| 49 | TO 4.12 | Harjoitus 5 | Tehtävät
Mallivastaukset Koeaika väärin ilmoitettu tehtäväpaperissa, ks. oikea aika alla | |
| 49 | TO 4.12 | 1,2.1.3, 2.2.3,3.1-3.3,4.1.1, 4.1.2 | Johdatus kuvan tiivistykseen | Pasi Fräntin kuvan tiivistyksen luentomoniste |
| 50 | TI 9.12 | Koe 9-12 A111 | Huom:Koe onkin aamulla, eikä illalla kuten aiemmin ilmoitettiin. | |
| 3/09 | PE 16.1.2009 | Uusintakoe 16-20 A111 | Alustava tieto, tarkista täältä. Laskaripisteet otetaan huomioon tässäkin kokeessa. |
Veli Mäkinen