in English
 
 
Millaista on moderni matematiikka ja miten sitä tutkitaan?
Salainen viesti paljastuu, kun osuudet ovat päällekkäin.

Oleellisia tietotekniikkaan liittyviä ongelmia ovat muun muassa: Miten määritellään täsmällisesti käsite algoritmi (ohjelmallinen menetelmä), miten voidaan jollekin tietylle tehtävälle löytää paras mahdollinen ratkaisualgoritmi, miten voidaan osoittaa, että jokin tietty algoritmi on optimaalinen, onko olemassa täsmällisesti määriteltyjä ongelmia, joita ei voida algoritmisesti ratkaista ja mitkä mahdollisesti ovat tällaisia ongelmia? Listaa voidaan jatkaa kysymällä miten korjata heikkolaatuisen tiedonsiirtokanavan aiheuttamat virheet ja mikä on paras menetelmä tämän tekemiseen, miten turvata informaation salassapito salakuuntelulle alttiilla tiedonsiirtokanavalla, olisiko mahdollista laajentaa tietokoneen, algoritmin tai informaation käsitettä käyttämällä biologisia, molekulaarisia tai kvanttimekaanisia laskentakoneistoja?

Osaan edellä listatuista kysymyksistä on jo olemassa vastaus, mutta suurin osa on avoinna.  Listaa voitaisiin jatkaa edelleen hyvinkin pitkälle ja yhteistä kaikille listan ongelmille on, että niitä tutkitaan Turun yliopiston matematiikan laitoksella diskreetin matematiikan tutkimusryhmissä.

Moderni matematiikan tutkimus ei kuitenkaan liity vain diskreettiin matematiikkaan. Erityisesti 1900-luvun alkupuoliskolla aloitettu kvanttimekaniikan kehitys loi tarpeen perinteisesti jatkuvaan matematiikkaan kuuluneen matemaattisen analyysin kehittämiseksi edelleen. Muita motivaatioita jatkuvan matematiikan nykyaikaiselle tutkimukselle ovat tuoneet kaoottisten dynaamisten ilmiöiden kuvaaminen, biomatematiikka ja lääketieteellinen matematiikka.

Sekä diskreetin että jatkuvan matematiikan kehitys 1900-luvulla on osoittanut hyvin tärkeän seikan: jaolle jatkuvaan ja diskreettiin matematiikkaan ei ole kovinkaan kestäviä perusteita, vaan matematiikan rakenteellinen ykseys alkaa näyttäytyä kehityksen myötä yhä selvempänä. Nykyaikaisen matematiikan tutkimuksen kannalta mainittu ykseys tarjoaa mahdollisuuden molemminpuoliseen tutkimukseen käytettävien menetelmien vaihtoon: perinteisesti jatkuvassa matematiikassa käytettäviä menetelmiä voidaan soveltaa diskreettiin matematiikkaan ja päinvastoin. On kuitenkin mainittava, että jo 1800-luvulla lukuteorian tutkimuksessa havaittiin, että kokonaislukujen ominaisuuksien tutkimiseen sopivat sekä diskreetin että jatkuvan matematiikan työkalut.

Useiden matemaattisten ongelmien kuvailu, ratkaisemista puhumattakaan on varsin hankalaa käyttämättä pitkälle kehittynyttä matemaattista terminologiaa. On kuitenkin mahdollista esittää joidenkin tärkeiden tietotekniseen matematiikkaan liittyvien oivallusten perusidea ilman erityisen syvällistä matemaattista taustaa. 

Esimerkki 1: Virheitä korjaavat koodit

Virheitä korjaavien koodien sovellukset ovat lukuisat. Niiden ansiosta voidaan naarmuisiakin dvd-levyjä katsella, vähentää oleellisesti häiriöitä digitelevisiolähetyksissä tai vaikka saada kuva Saturnuksen kuusta maapallolle hyvin vähin häiriöin, vaikka lähetettävä viesti saattaakin vääristyä matkan varrella.

Perusajatus virheitä korjaavien koodien takana on helppo ymmärtää ja sitä valaisee seuraava esimerkki: välitettäessä puhelimitse henkilötunnuksia, rekisterinumeroita tai salasanoja joudutaan toisinaan tilanteeseen, jossa ääntämyksen epäselvyyden vuoksi on mahdollista sekoittaa "B" ja "P", "I" ja "J", "K" ja "H", tai muut vastaavat samankaltaisesti ääntyvät kirjaimet keskenään. Tällöin voidaan käyttää vanhaa hyväksi havaittua konstia: "B":n sijaan sanotaan "Bertta", "P":n sijaan "Pekka", "I":n sijaan "Ilkka", "J":n sijaan "Jaakko", jne. Koska nimiä "Iaakko" tai "Jlkka" ei esiinny suomen kielessä eivätkä nimet helposti sekoitu muihin olemassa oleviin nimiin, eivät "I" ja "J" sekoitu toisiinsa.

Matemaattisesti ilmaistuna tämä merkitsee, että viestiin lisätään redundanttia (ylimääräistä) informaatiota, jonka avulla alkuperäinen viesti voidaan selvittää viestinnän aikana tapahtuneista virheistä huolimatta. Digitaalisessa viestinnässä idea on aivan sama, lähetettäessä bittijonoja (nollien ja ykkösten jonoja) lisätään jonoihin hieman pituutta niin, että lähetettäviksi sovitut jonot eroavat toisistaan mahdollisimman paljon. Mikäli lähetyksen aikana tapahtuu virheitä, voidaan niiden määrän ollessa vähäinen tavoittaa alkuperäinen viesti etsimällä sovittu jono, joka muistuttaa eniten perille tullutta.

Hamming.jpgYksinkertaisena mutta konkreettisena esimerkkinä voidaan sopia, että bittijonojen 00, 01, 10 ja 11 sijaan lähetetäänkin koodisanat 00000, 11100, 00111 ja 11011 (tässä järjestyksessä). Uusista 5-pituisista koodisanoista voidaan helposti havaita, että ne kaikki eroavat toisistaan vähintään kolmessa kohdassa, joten yhden bitin virheen jälkeen saatu merkkijono muistuttaa kuitenkin vielä eniten alkuperäistä koodisanaa. Jos siis esimerkiksi halutaan lähettää 01, lähetetäänkin sen sijaan 01:n koodisana 11100, mikä saattaa muuntua lähetyskanavan virheen vuoksi esim. muotoon 10100. Näin saatu virheellinen muoto muistuttaa kuitenkin eniten vielä koodisanaa 11100, mikä vuoksi alkuperäinen informaatio 01 saadaan virheestä huolimatta talteen. Mikäli virheitä sattuu enemmän kuin yksi, voi olla että alkuperäistä informaatiota ei enää saada talteen: jos koodisana 11100 muuntuukin muotoon 11111, muistuttaa se eniten koodisanaa 11011, joka onkin 2-pituisen jono 11 koodisana.

Tässä esimerkissä 2-pituiset bittijonot korvattiin 5-pituisilla jonoilla, jolloin lähetysaika 2,5-kertaistuu. Lisäksi voidaan ajatella, että koska lähetettävä viesti koodataan 2,5 kertaa pidemmäksi lähetystä varten, on myös virheelle alttiita bittejä 2,5 kertaa enemmän ja että siksi yhden virheen korjaamisen etu menetettäisiin. Tarkempi analyysi kuitenkin paljastaa, että tämä yksinkertainen koodaus pienentää virhetodennäköisyyttä merkittävästä, jos alkuperäinen virhetodennäköisyys on pienehkö. Jos esimerkiksi alkuperäinen virhetodennäköisyys on yhden miljoonasosan suuruusluokkaa, niin koodaamatta siirretty informaatio sisältää 200000 kertaisesti enemmän virheitä kuin koodisanojen avulla siirretty sama informaatio. Tämän hintana on kuitenkin 2,5-kertainen siirtoaika.

Jos 2-pituisten bittijonojen sijaan koodataan alunperinkin pidempiä jonoja, saadaan parempi hyötysuhde: siirtoajan pidentyminen suhteessa virhetodennäköisyyden pienenemiseen saadaan yhä pienemmäksi. Toisaalta taas hyvin pitkiä bittijonoja käytettäessä törmätään ainakin kahteen ongelmaan: ensinnäkin bittijonojen määrä tulee niin suureksi, että koodisanojen taulukointi ei ole mahdollista ja toiseksi "lähimmän" koodisanan etsiminen muuntuneelle sanalle tulee erittäin hankalaksi. Näiden ongelmien ratkaisemiseksi käytetään koodisanajoukkoja, joiden algebrallinen rakenne sallii tehokkaan menetelmän kumpaankin tehtävään.

Tarvittavan algebrallisen rakenteen löytämiseksi sovelletaan modernia matematiikkaa muun muuassa käyttämällä äärellisten kuntien teoriaa, algebrallista geometriaa ja algebrallisen lukuteorian menetelmiä.

Esimerkki 2: Kommunikaatioprotokollat

Monissa järjestelmissä tarvitaan tarkoin kuvattuja menetelmiä tietokoneiden väliseen "keskusteluun"; tyypillisenä esimerkkinä voidaan mainita vaikkapa nosto pankkiautomaatilla. Automaatin tulee varmistua, että syötetty pankkikortti kuuluu sen oikealle haltijalle, sen jälkeen tarkistaa, että tilillä on katetta ja vasta sitten luovuttaa pyydetty käteissumma.

Jokainen mainituista vaiheista sisältää ongelmia, joihin voidaan pureutua matemaattisin keinoin. Muun muuassa katteen varmistamisessa tulee huolehtia, että tiedonkulku pankkiautomaatin ja pankin tietokoneen välillä pysyy salassa. Sama ongelma on myös kotoa käsin tapahtuvassa verkkopankin käytössä.

Mainittujen ongelmien käsittelemiseksi voidaan tarkastella ns. kommunikaatioprotokollia, jotka ovat menetelmiä yksinkertaisten perustehtävien ratkaisemiseksi. Niitä voidaan pitää eräänlaisina rakennuspalikoina, joita yhdistämällä voidaan muodostaa monimutkaisia menetelmiä.

Tarkastellaan esimerkkinä arvontaa, jossa kommunikoivat osapuolet tahtovat määrittää satunnaisen bitin (arvo 0 tai 1). Poistutaan vielä hetkeksi automaattisen tietojenkäsittelyn kuvioista ja siirretään arvonta seuraavanlaiseen ympäristöön: ajatellaan, että Alice ja Bob ovat sopineet yhteisestä iltapäivän ohjelmasta joko klassisen konsertin tai jääkiekko-ottelun muodossa. Alice tahtoo konserttiin ja Bob jääkiekko-otteluun. Heidän tulisi puhelimitse arpoa kumpaan tapahtumaan osallistutaan. Lisävaatimuksena on, että sekä Alicen että Bobin tulisi kummankin vakuuttua arvonnan puolueettomuudesta. Tällöin ei tietenkään riitä, että esimerkiksi Alice heittäisi kolikkoa ja kertoisi tuloksen Bobille, koska tällöin Bob ei voi vakuuttua siitä, että Alice kertoo hänelle tuloksen rehellisesti. 

Ennen kuin luet pidemmälle, mieti hetken miten arvonta voitaisiin suorittaa kumpaakin osapuolta tyydyttävällä tavalla. Mainittakoon vinkkinä, että kumpaisellakin on käytössään kaupungin puhelinluettelo, joka nyt otaksutaan varsin paksuksi opukseksi.

Arvonnan suorittamiseksi Alice ja Bob voivat menetellä näin: Alice valitsee puhelinluettelosta umpimähkään jonkin nimen ja kertoo Bobille valitun henkilön puhelinnumeron, mutta ei nimeä. Bobin tulee nyt välittömästi arvata, onko äskenmainittua henkilöä seuraavan henkilön numero parillinen vai pariton. Alice voi nyt välittömästi tarkistaa, oliko Bobin arvaus oikein. Jos Bob arvasi oikein, pariskunta viettää illan jääkiekon parissa, muutoin konsertissa. Arvauksen jälkeen Alice kertoo Bobille myös ensiksi valitun henkilön nimen, jotta Bob voi puolestaan omasta puhelinluettelostaan varmistua puhuiko Alice totta Bobin arvauksesta. Alicehan kertoi hänelle alkuperäisen henkilön puhelinnumeron, joten Alice ei voi enää muuttaa ensimmäiseksi valittua henkilöä ja tällöin siis Bob yksinkertaisesti etsii alkuperäisen henkilön nimen perusteella, tarkistaa, vastasiko hänelle kerrottu numero nimeä ja lopuksi oliko hänen arvauksensa koskien seuraavan henkilön numeroa oikein.

Menetelmän toimivuus perustuu siihen, että tunnettaessa nimi on paksustakin puhelinluettelosta helppoa etsiä numero, kun taas toisinpäin (numerosta nimi) tehtävä on lyhyessä ajassa mahdoton. Mainitun tehtävän matemaattinen versio on ns. yksisuuntainen funktio f, jolle arvon f(x) laskeminen on helppoa, mutta x:n laskeminen arvosta f(x), siis f:n käänteisfunktion laskeminen on äärimmäisen työlästä.

Yksisuuntaiset funktiot ovat äärimmäisen tärkeitä monissa kommunikaatio- ja salausprotokollissa, mutta niistä tiedetään aivan liian vähän. Itse asiassa ei tiedetä, onko niitä laisinkaan olemassa! Toistaiseksi on tyydytty hyviin ehdokkaisiin, joille käänteisfunktion laskeminen vaikuttaa työläältä - ei vain ole voitu näyttää toteen, ettei käänteisfunktion laskemiseksi olisi olemassa (toistaiseksi tuntematonta) tehokasta menetelmää. Kysymys yksisuuntaisten funktioiden olemassaolosta kuuluukin teoreettisen tietojenkäsittelytieteen vaikeimpiin avoimiin ongelmiin.

Arvontaprotokolla on vain yksi sovellus yksisuuntaisista funktioista. Niiden avulla voidaan laatia lukuisia muita protokollia, mukaan lukien salausmenetelmiä, menetelmät sähköiseen allekirjoitukseen ja mainittakoon lopuksi ns. nollatietotodistukset, joiden avulla on mahdollista vakuuttaa toinen osapuoli informaation hallussapidosta paljastamatta tästä informaatiosta yhtäkään bittiä!

Asiasana:
Tagit:
 

 Matematiikan ja tilastotieteen laitos

 
Käyntiosoite: Quantum, toinen kerros
(Kartta)
Postiosoite: Matematiikan ja tilastotieteen laitos,  20014 Turun yliopisto