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, valmistunee 2003) sarjassa The Art of Computer Programming on Combinatorial Algorithms.

Kurssilla tutustaan tärkeimpiin kombinatorisiin rakenteisiin (graafit, osajoukot, jne.) 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 hakujen rajoittamisessa.

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ä vaikeimpien (esim. NP-täydellisten) kombinatoristen ongelmien kimppuun stokastisia menetelmiä (tabuhaku, simuloitu jäähdytys) käyttäen.

Kurssin sisältö vastaa hyvin tietojenkäsittelyteorian laboratorion koodausteoria- ja optimointiryhmän tutkimusaiheita ja antaa valmiuden erikoistyön (Tik-79.189) tekoon. Kurssi sopii erittäin hyvin myös jatko-opiskelijoille.

• Ilmoittautuminen: TOPI:ssa tai luennoilla.
• Luennot: Harri Haanpää, keskiviikkoisin 12-14 (sali TB353) 17.1.2000 alkaen.
  • Luentokalvoja vuodelta 2001
• Laskuharjoitukset: Petteri Kaski, torstaisin 14-15 (sali TB353) 18.1.2000 alkaen.
  • Kevään 2001 laskuharjoitukset
  • Vanhat laskuharjoitukset: 1997, 1998, 1999, 2000.
• Suoritus: Tentti ja kolme kotitehtävää. Kotitehtävät on suoritettava ennen tenttiä ja ne ovat voimassa viimeisen kerran seuraavassa lokakuun tentissä.
• Tentti: ma 14.5.2001, 9-12, salit T1 ja T2.
  ma 1.10.2001, 12-15, sali A
  
  • Vanhat tentit: 10.5.97, 18.11.97, 20.5.98, 9.11.98, 17.5.99, 8.11.99, 9.5.00, 9.10.00.
• Tenttivaatimukset
  • Luennoilla ja laskuharjoituksissa käsitellyt asiat
  • Kirjasta luvut 1-7, paitsi:
    • 3.2., 4.3.1., 5.4.1. 5.4.2., 7.3.3.
• Kotitehtävät: Kurssilla annetaan kolme kotitehtävää, jotka voivat olla esim. pienimuotoisia ohjelmointitehtäviä, joissa voi soveltaa kurssilla opittuja tekniikoita. Erityisen ansiokkaista ratkaisuista voi saada bonuspisteen tenttiin (yhteensä siis max +3p).
• Kurssikirja:
  • D. L. Kreher & D. R. Stinson:
    Combinatorial Algorithms; Generation, Enumeration & Search, CRC Press, 1998.
    Kirjaa myyvät ainakin Bokus ja Springer.
• Oheismateriaalia ja linkkejä (ehdotuksia vastaanotetaan)
  • Sloane's Online Encyclopedia of Integer Sequences
  • Ranking and Unranking Permutations in Linear Time
  • Exercises on Catalan and Related Numbers

Työpaikka