| |
T-79.161 Kombinatoriset algoritmit (2 ov) L
Kevät 2004
Maailman digitalisoituessa kombinatoristen algoritmien merkitys
kasvaa voimakkaasti. Jokainen työssään algoritmeja suunnitteleva
törmää
ongelmiin, joissa niitä tarvitaan.
Ei liene mikään sattuma, että
Donald Knuthin seuraava kirja (Vol. 4A-4C,
arvioitu valmistumisaika 2007) sarjassa
The Art of Computer Programming on Combinatorial
Algorithms.
Kombinatoriset algoritmit -kurssilla tarkastellaan tärkeimpiä kombinatorisia rakenteita,
kuten graafeja ja osajoukkoja, ja tutustutaan algoritmeihin, joilla niitä
voidaan käsitellä tehokkaasti. Lisäksi tutustutaan menetelmiin
(peräytymishaku, tabuhaku, simuloitu jäähdytys), joilla voidaan
tehokkaasti etsiä halutunlaista kombinatorista rakennetta, ja opitaan
käyttämään ongelman symmetrioita hyväksi haun rajoittamisessa.
Kurssin tavoitteena on antaa opiskelijalle muun muuassa
seuraavat valmiudet:
- Kyky ymmärtää keskeisiä kombinatorisia objekteja
(graafeja, jne.).
- Tärkeimpien kombinatoristen perusobjektien,
kuten osajoukkojen ja permutaatioiden, tehokkaiden
käsittelyalgoritmien hallitseminen.
- Yleisimpien hakumenetelmien tunteminen ja kyky
soveltaa niitä käytännön ongelmiin.
- Symmetriakäsitteen ja symmetria/ryhmä -yhteyden
ymmärtäminen. Kyky käyttää symmetrioita
hyväksi hakujen rajoittamiseksi.
- Taito hyökätä vaikeiden (esim. NP-täydellisten)
kombinatoristen ongelmien kimppuun stokastisia menetelmiä
(tabuhaku, simuloitu jäähdytys) käyttäen.
Kurssin sisältö vastaa hyvin Tietojenkäsittelyteorian laboratorion
Laskennallisen vaativuuden ja kombinatoriikan tutkimusryhmän
tutkimusaiheita ja antaa valmiuden erikoistyön
(T-79.189)
tekoon. Kurssi sopii erittäin hyvin
myös jatko-opiskelijoille.
Järjestelyt
Laskuharjoitukset: DI Emilia Oikarinen,
yksi laskuharjoitus viikossa (maanantaisin 26.1. alkaen klo 14-15 salissa TB353)
Suoritus:
Tentti ja kolme kotitehtävää.
Kurssista järjestetään tentti
toukokuussa ja lokakuussa. Kurssilla annetaan kolme pakollista
kotitehtävää,
jotka ovat tyypillisesti pienimuotoisia ohjelmointitehtäviä, joissa voi
soveltaa kurssilla opittuja tekniikoita. Erityisen ansiokkaista
ratkaisuista voi saada bonuspisteen tenttiin (yhteensä siis max +3p).
Kotitehtävät on suoritettava ennen tenttiä
ja ne ovat voimassa viimeisen kerran suorituskevättä seuraavassa
lokakuun tentissä.
Seuraavat tentit: Toukokuussa 2004 ja lokakuussa 2004.
Aineistoa
- Kirjallisuutta:
D. L. Kreher &
D. R. Stinson:
Combinatorial Algorithms; Generation, Enumeration &
Search, CRC Press, 1998.
- Luentokalvot Kevään 2004 luentokalvoja
- Laskuharjoitukset erillisellä sivulla
- Kotitehtävät erillisellä sivulla
- Oheismateriaalia ja linkkejä (ehdotuksia vastaanotetaan)
- Aiempien vuosien kurssien sivuja:
[kl 2003]
[kl 2002]
[kl 2001]
- Vanhoja tenttejä:
10.5.1997,
18.11.1997,
20.5.1998,
9.11.1998,
17.5.1999,
8.11.1999,
9.5.2000,
9.10.2000,
14.5.2001,
1.10.2001,
13.5.2002,
14.10.2002,
5.5.2003,
20.10.2003.
[TKT pääsivu]
[Ajankohtaista]
[Yhteystiedot]
[Henkilöstö]
[Tutkimus]
[Julkaisut]
[Ohjelmistot]
[Opinnot]
[Linkkejä]
Päivitetty viimeksi 20.02.2004.
Harri Haanpää (Harri.Haanpaa©hut.fi)
|
