1., 2. ja 3. kotitehtävän tulostilanne

Kolmas kotitehtävä julkaistu

Luennot päättyneet, ei laskuharjoituksia 11.4. tai 18.4.

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 haun 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ä 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 koodausteoria- ja optimointiryhmän tutkimusaiheita ja antaa valmiuden erikoistyön (T-79.189) tekoon. Kurssi sopii erittäin hyvin myös jatko-opiskelijoille.

• Ilmoittautuminen: TOPI:ssa tai luennoilla.
• Luennot: Harri Haanpää, maanantaisin 12-14 (sali TB353) 14.1.2002 alkaen.
  
  • Kevään 2002 luentokalvoja
• Laskuharjoitukset: Petteri Kaski, torstaisin 13-14 (sali TB353) 17.1.2002 alkaen.
  • Kevään 2002 laskuharjoitukset
• Suoritus: Tentti ja kolme kotitehtävää. Kurssista järjestetään tentti toukokuussa ja lokakuussa. Kotitehtävät on suoritettava ennen tenttiä ja ne ovat voimassa viimeisen kerran lokakuun 2002 tentissä.
• Tentti:
  ma 13.5.2002, 16-19
  xx ??.10.2002, ??-??
  • 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, 14.5.2001 , 1.10.2001.
• 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.
• 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