T-79.161 Kombinatoriset algoritmit (2 ov) L

Kevät 2005

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-2010) 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 sopii erittäin hyvin myös jatko-opiskelijoille.

Kurssi T-79.165 Graafiteoria liittyy läheisesti aihepiiriin.

Järjestelyt

• Luennot: TkT Harri Haanpää, yksi luento viikossa (torstaisin 13.1. alkaen klo 12-14 salissa TB353)
• Harjoitukset: DI Emilia Oikarinen, yksi harjoitus viikossa (torstaisin klo 14-15 salissa TB353)
• Suoritus: Tentti ja kaksi kotitehtävää. Kurssista järjestetään tentti toukokuussa ja lokakuussa. Kurssilla annetaan kaksi pakollista kotitehtävää, jotka ovat tyypiltään ohjelmointitehtäviä, joissa voi soveltaa kurssilla opittuja tekniikoita, ja joista kirjoitetaan selostus. Kotitehtävät on suoritettava ennen tenttiä ja ne ovat voimassa viimeisen kerran suorituskevättä seuraavassa lokakuun tentissä.
• Seuraavat tentit: 6.5.2005 ja lokakuussa 2005.

Aineistoa

• Kirjallisuutta: D. L. Kreher & D. R. Stinson: Combinatorial Algorithms; Generation, Enumeration & Search, CRC Press, 1998.
• Luentokalvot, joita kyllä saatetaan päivittää tai järjestellä kurssin edetessä
• Harjoitus- ja kotitehtävät
• Oheismateriaalia ja linkkejä (ehdotuksia vastaanotetaan)
  • Brian Alspach analysoi korttien sekoittamista (kevyttä luettavaa)
  • Valmisteilla olevia katkelmia The Art of Computer Programming -kirjan osasta 4 (tiukkaa asiaa)
  • Sloane's Online Encyclopedia of Integer Sequences
  • Exercises on Catalan and Related Numbers

Arkistoja

• Vanhoja tenttejä
• Aiemmat kurssit

TKT - Opinnot - T-79.161 Kombinatoriset algoritmit