Kombinatoriikka

Kevät 2011

Luennot ja harjoitukset

Luennot:

            ma   14-16  A2a  päätalo
            to     12-14  A2b  päätalo

Harjoitukset:

            ma   10-12  A2a  päätalo

Ensimmäinen luento on maanantaina  7.3. ja ensimmäiset harjoitukset maanantaina  14.3. 
Luennot päättyvät  maanantaina  2.5. ja viimeiset harjoitukset ovat myös maanantaina 2.5.

Luennoija:  Lauri Hella (lauri.hella[ät]uta.fi), tavattavissa luentojen yhteydessä sekä vastaanotolla  (to 15-16).
Harjoitusryhmää ohjaa  Raine Rönnholm (raine.ronnholm[ät]uta.fi).

Loppukoe

HUOM: Loppukoesali muutettu!

Loppukoeaika ja -paikka ovat:

            to  5.5.  12-14   K103  Linna

Kurssin suorittaminen

Kombinatoriikka on matematiikan syventävä erikoiskurssi, jonka laajuus on 5 op.  Kurssi suoritetaan loppukokeella, ja aktiivisella osallistumisella harjoituksiin. Loppukokeesta annetaan  0-24 pistettä. Harjoitustetävien suorittamisesta saa pisteitä seuraavan taulukon mukaan:

    0-9   0 p       10-15   1 p       16-21   2 p       22-27   3 p       28-33   4 p       34-39   5 p       40-49   6 p

Nämä pisteet eivät ole lisäpisteitä, vaan niillä voi korvata yhden loppukokeessa mahdollisesti epäonnistuneen tehtävän pisteet. Läpipääsyyn vaaditaan n. 12 pistettä.

Kurssin sisältö

Kurssilla käydään läpi kombinatoriikan perusasioita (laatikkoperiaate, summa- ja tuloperiaate, seulaperiaate, permutaatiot ja kombinaatiot) syventäen Diskreetin matematiikan kurssilla opittua. Lisäksi perehdytään Ramseyn teoriaan, latinalaisiin neliöihin sekä generoiviin funktioihin ja niiden sovelluksiin.

Kurssi ei edellytä erityisiä pohjatietoja; matematiikan perusopintokurssien sisältö riittää hyvin.

Luennoilla käytetään monistetta

Heikki Junnila (HY): Diskreettiä matematiikkaa,
josta käydään läpi luvun II sisältöä. Lisäksi käsitellään joitakin asioita Pentti Haukkasen monisteesta Kombinatorikkaa, sekä oppikirjasta

            Reinhard Diestel:  Graph Theory

Diestelin kirjasta on saatavilla verkkoversio, jonka voi vapaasti lukea ja ladata omalle koneelle (mutta ei tulostaa).

(HUOM: Junnilan monisteen versio on vaihdettu helpommin selaimella luettavaan.)

Viikkoharjoitustehtävät

Tehtävät annetaan harjoitusta edeltävän viikon maanantaina, jolloin ne löytyvät tältä kotisivulta.

       Harjoitus 1      Harjoitus 2      Harjoitus 3      Harjoitus 4      Harjoitus 5      Harjoitus 6      Harjoitus 7

Luentojen eteneminen

     Viikko          Luentoaihe                                                                                                      Monisteen sivut

     7. ja 10.3.      1. Koon vertailu, Laatikkoperiaate, 2. Summan ja erotuksen periaate               Junnila s.45-55  
     14. ja 17.3.    3. Jonojen, kuvausten ja osajoukkojen lukumäärät                                            Junnila s.55-65  
     21. ja 24.3.    4. Ositusten lukumäärät, 5. Valinnat ja sijoittelut (alku)                                     Junnila s.65-75  
     28. ja 31.3.    5. Valinnat ja sijoittelut (loppu)                                                                          Junnila s.75-77
                           9. Latinalaiset neliöt                                                                                           Haukkanen s.40-47
     4. ja 7.4.        6. Rekursiiviset jonot                                                                                         Haukkanen s.19-26
     11. ja 14.4.    2.1 Matching in bipartite graphs, 2.2 Matching in general graphs                     Diestel s.35-43
     18. ja 28.4.    9.1 Ramsey's original theorems, 9.2 Ramsey numbers                                      Diestel s.270-274