57024
Äärellisten mallien teoria
Kurssikoodi
57024
Tyyppi
Syventävä opinto.
Kurssisivut
Laajuus
10 op.
Kurssikuvaus
Malliteoriassa tietyntyyppisiä matemaattisia struktuureja, malleja, tutkitaan matemaattisen logiikan välinein. Malleja ovat niin algebralliset struktuurit, kuten ryhmät, kunnat ja renkaat, kuin diskreetissä matematiikassa tutut verkot, puut ja lineaariset järjestykset. Äärelliset mallit ovat kiinnostavia diskreetin matematiikan ja tietojenkäsittelyn kannalta, minkä vuoksi äärellisten mallien teoriaa voi luonnehtia nimenomaan diskreetin matematiikan malliteoriaksi, kun taas klassinen, äärettömiä malleja tutkiva malliteoriaa on algebrallisesti suuntautuneempi.
Kurssilla tutustutaan ensin mallin käsitteeseen ja siihen, miten kahden mallin samanlaisuutta voi mitata eri tavoilla: homomorfisuudella, isomorfisuudella ja kombinatorisilla peleillä. Loogisiin käsitteisiin paneuduttaessa huomataan, että kombinatoriset pelit ovat suorassa yhteydessä logiikkaan. Malleja voi ajatella myös tietokoneohjelmien syötteinä eli relationaalisina tietokantoina; tämän idean kehittäminen johtaa deskriptiiviseen vaativuusteoriaan. Kurssin lopuksi käsitellään lyhyesti ensimmäisen kertaluvun logiikan 0-1-lakia ja yleistettyjä kvanttoreita.
Esitietovaatimukset
Kurssi vaatii ennen kaikkea tietyn määrän matemaattista kypsyyttä. Olisi suotavaa, että ainakin yksi kursseista Logiikka I, Algebra I tai Tietorakenteet (tkt) olisi suoritettuna.