TKT / Opinnot / T-79.161 Kombinatoriset algoritmit
Teknillinen korkeakoulu, Tietojenkäsittelyteorian laboratorio

  • Tenttivaatimukset:Luennoilla, laskuharjoituksissa ja kotitehtävissä käsitellyt asiat. Lisäksi Kreher & Stinsonin kappaleet 1-7 niiltä osin kuin ne käsittelevät kurssilla käsiteltyjä asioita. Kreher & Stinsonin seuraavat kappaleet eivät kuitenkaan käsittele kurssilla käsiteltyjä asioita: 3.2, 4.3.1. Kappaleissa 5.3-5.7 esitettyjen algoritmien yksityiskohdat eivät myöskään ole olennaisia.

T-79.161 Kombinatoriset algoritmit (2 ov) L

Kevät 2003

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:

  1. Kyky ymmärtää keskeisiä kombinatorisia objekteja (graafeja, jne.).
  2. Tärkeimpien kombinatoristen perusobjektien, kuten osajoukkojen ja permutaatioiden, tehokkaiden käsittelyalgoritmien hallitseminen.
  3. Yleisimpien hakumenetelmien tunteminen ja kyky soveltaa niitä käytännön ongelmiin.
  4. Symmetriakäsitteen ja symmetria/ryhmä -yhteyden ymmärtäminen. Kyky käyttää symmetrioita hyväksi hakujen rajoittamiseksi.
  5. 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

  • Luennot: TkL Harri Haanpää, yksi luento viikossa (maanantaisin 13.1. alkaen klo 12-14 salissa TB353)
  • Laskuharjoitukset: tekn. yo. Emilia Oikarinen, yksi laskuharjoitus viikossa (keskiviikkoisin 15.1. alkaen klo 13-14 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 2003 ja lokakuussa 2003.

Aineistoa

[TKT pääsivu] [Yhteystiedot] [Henkilöstö] [Tutkimus] [Julkaisut] [Ohjelmistot] [Opinnot] [Uutisarkisto] [Linkkejä]
Päivitetty viimeksi 08.05.2003. Harri Haanpää (Harri.Haanpaa@hut.fi)