Tik-79.161 Kombinatoriset algoritmit

Kevät 2000

Yllä oleva rakenne on niin sanottu kombinatorinen sommitelma, jota voidaan käyttää esimerkiksi kokeiden suunnittelussa tai vaikkapa lottojärjestelmänä. Esimerkin sommitelma on sellainen, että jos valitset mitkä tahansa kaksi riviä niin löytyy täsmälleen yksi sarake jolla on 1 näissä rivissä. Tällaisia sommitelmia voidaan etsiä tietokoneella niin sanottujen kombinatoristen algoritmien avulla.

Käsitteellä kombinatorinen algoritmi voidaan tarkoittaa kahta asiaa: joko 1) algoritmia jolla käsitellään kombinatorisia rakenteita (permutaatioita, osajoukkoja, graafeja, koodeja, sommitelmia), tai 2) algoritmia joka on luonteeltaan kombinatorinen=diskreetti (esim. erilaiset hakualgoritmit). Tällä opintojaksolla käsitellään kombinatorisia algoritmeja kummassakin merkityksessä.

Maailman digitalisoituessa kombinatoristen algoritmien merkitys kasvaa voimakkaasti. Jokainen joka työssään kirjoittaa tietokoneohjelmia tai suunnittelee algoritmeja törmää ongelmiin joissa näitä 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.

Suoritettu kurssi 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 osaaminen, mukaan lukien näiden soveltaminen 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.

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

• Luennot: Patric Östergård, tiistaisin 10-12 (sali TB353).
• Laskuharjoitukset: Harri Haanpää, torstaisin 13-14 (sali TB353)
  • Vuoden 2000 tehtävät ja mallivastaukset.
  • Vanhat laskuharjoitukset: 1997, 1998, 1999.
• Oppikirja: D. L. Kreher & D. R. Stinson, Combinatorial Algorithms; Generation, Enumeration & Search, CRC Press, 1998. Kirjan myyvät ainakin Bokus ja Springer.
• Suoritus: Tentti ja kolme kotitehtävää. 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.
• Tentin ajankohta: ma 9.10.00, 16-19, salit T1 ja T2. Tenttivaatimukset.
• Jos on kysyttävää, ota yhteys luennoitsijaan tai assistenttiin.

Työpaikka

Last update: October 10, 2000.