Diskreetti matematiikka II

Asema opetuksessa

Kurssi on tarkoitettu etupäässä matematiikan ja tietojenkäsittelyn opiskelijoille, mutta siitä saattaa olla hyötyä myös esim. kemian lukijoille. Monen matematiikan linjan pääaineopiskelijat voivat suorittaa kurssin valinnaisena laudatur-kurssina, mutta kurssi on vaikeustasoltaan lähinnä cum laude -kurssi.

Laajuus

5 ov

Luennoija

Syyslukukaudella 2004 kurssin luennoi dos. Kerkko Luosto.

Info

Kurssin infosivu sisältää kurssin hallinnolliset tiedot, ts. tiedot luentoajoista ja -paikoista, laskuharjoituksista ja välikokeista.

Laskuharjoitukset

Harjoitustehtävät ovat omalla sivullaan, tiedot harjoitusryhmistä infosivulla.

Esitiedot

Kurssi ei vaadi sanottavia esitietoja, jonkin verran kylläkin matemaattista kypsyyttä. Kurssilla käsitellään varsinaista diskreettiä matematiikkaa, joten sillä on vain vähän yhteistä matematiikan laitoksella muutaman vuoden ajan luennoidun kurssin Diskreetti matematiikka I kanssa (tuolla kurssilla lähinnä esitellään matematiikan peruskäsitteistöä). Erityisesti, Diskreetti matematiikka II:n suoritus ei edellytä Diskreetti matematiikka I:n suorittamista.

Kurssikuvaus

Kurssilla käsitellään etupäässä kahteen diskreetin matematiikan tärkeimpään haaraan, kombinatoriikkaan ja verkkoteoriaan, kuuluvia peruskäsitteitä ja -tuloksia. Kombinatoriikasta käydään läpi mm. laatikkoperiaate sekä summa- ja erotusperiaate sovelluksineen, valinta- ja sijoitteluongelmia sekä sovituksien (engl. matching) teorian perustulos, Hallin Lause. Verkkoteoriasta käsittellään mm. yhtenäisyyttä, renkaita, Eulerin ja Hamiltonin kulkuja, verkkojen suuntaamista sekä puita.

Sisällys

• LUKU I: JOUKOT JA RELAATIOT
  • 0. Merkinnöistä
  • 1. Relaatiot ja kuvaukset
  • 2. Luonnolliset luvut. Induktio
  • 3. Äärelliset joukot
  • 4. Joukon ositukset. Ekvivalenssirelaatiot
  • 5. Joukkojen symmetrinen erotus
  • 6. Relaation sisältämät kuvaukset
• LUKU II: JOUKKOJEN KOKO
  • 1. Koon vertailu. Laatikkoperiaate
  • 2. Summan ja erotuksen periaate
  • 3. Jonojen, kuvausten ja osajoukkojen lukumäärät
  • 4. Ositusten lukumäärät
  • 5. Valinnat ja sijoittelut
• LUKU III: SUHTEIKOT JA VERKOT
  • 1. Johdanto
  • 2. Pisteiden asteet
  • 3. Yhtenäisyys
  • 4. Kulku suhteikossa
  • 5. Hamiltonin kulut
• LUKU IV: VERKON RENKAAT
  • 1. Renkaiden olemassaolo
  • 2. Renkaistot
  • 3. Eulerin kulut
  • 4. Verkon yksisuuntaistukset
• LUKU V: PUUT
  • 1. Puiden perusominaisuudet
  • 2. Virittävät puut
  • 3. Suunnatut puut

Luentomateriaali

Kurssi seurailee Heikki Junnilan monistetta Diskreettiä matematiikkaa.

Kirjallisuutta

Diskreetistä matematiikasta on julkaistu valtavasti kirjallisuutta, jonka laatu ja vaikeustaso vaihtelee. Alla on näistä mainittu muutamia hyvätasoisia.

• Peter Cameron: Combinatorics. Tunnetun kombinatorikon kirjoittama, aiheiden valinnaltaan hyvin tasapainoinen diskreetin matematiikan perusteos. Kirja lähtee perusasioista liikkeelle, mutta tekijä tunnustaa itsekin kirjassa olevan materiaalia ainakin kahdelle kurssille, joista ensimmäinen olisi perusopiskelijoille, toinen jatko-opiskelijoille. Itse asiassa alkupuolisko sisältää paljon enemmän asiaa, kuin mitä meidän kurssillamme käydään läpi.
• Béla Bollobás: Combinatorics. Tämä on edellistä pidemmälle menevä, mutta ohuempi kirja. Kirjalla onkin aivan eri päämäärät kuin edellisellä; tekijä ei ole pyrkinyt aiheen käsittelyn kattavuuteen, vaan on valinnut edustavan otoksen kombinatorisia tuloksia, joista monet liittyvät geometrisiin ongelmiin. Tenhoava kirja, joka on erittäin suositeltava erityisesti funktioanalyysistä kiinnostuneille. Kirja on pikemminkin lisä-, kuin oheismateriaalia.
• Konrad Jacobs: Einführung in die Kombinatorik. Kahta edellistä selkeästi helpompi saksankielinen diskreetin matematiikan kirja, joka kattaa hiukan kurssia laajemman alueen.
• Rheinhard Diestel: Graph theory. Erinomaisesti uusimman tutkimuksen tasalla oleva verkkoteorian kirja.
• Frank Harary: Graph theory. Vanha, mutta edelleen kiinnostava verkkoteorian kirja.