Eräs tärkeä hilarakenteiden erityistapaus on ns. osajoukkojärjestelmä (engl. subset system). Se on rakenne S = (E,T), missä E on jokin äärellinen joukko ja T on osajoukon suhteen suljettu kokoelma E:n osajoukkoja. Tämä tarkoittaa sitä, että jos A on joukossa T ja A' on A:n osajoukko, niin myös A' on joukossa T. T:n alkioita kutsutaan riippumattomiksi joukoiksi.
Esimerkki osajoukkojärjestelmästä voisi olla vaikka sellainen, jossa E = {0,1,2} ja T = {{}, {0}, {1}, {0,1}, {2}, {0,2}}.
Osajoukkojärjestelmään liitetään usein kombinatorinen optimointitehtävä, jossa jokaiseen E:n alkioon e liitettän jokin (yleensä ei-negatiivinen) paino, w(e), ja tehtävänä on etsiä sellainen riippumaton joukko, jonka painojen summa on mahdollisimman suuri. Esimerkiksi ns. repunpakkaus-ongelma on tällainen kombinatorinen ongelma.
Osajoukkojärjestelmää ei tietenkään yleisessä tapauksessa voi esittää eksplisiittisesti, siis siten, että luetellaan koko T, koska osajoukkojen määrä räjähtää täysin E:n kasvaessa; osajoukkoja on 2|E|, joten vaikka näistä pieni murto-osa kuuluisi T:hen, niiden luetteleminen isommilla joukoilla olisi mahdotonta. Esimerkiksi, jos E:ssä on vaikkapa noin sata alkiota ja vaikkapa miljardisosa (1/109) osajoukoista tarvitsisi luetella, niin luettelossa olisi luokkaa 1021 joukkoa. Tämän vuoksi osajoukot ilmaistaan yleensä implisiittisesti eli antamalla jokin keino joko tunnistaa tai generoida T:n alkioita.
Optimointitehtäviä ei pidä sekoittaa päätöstehtäviin; Osajoukkojärjestelmän formulointiin liittyy usein päätöstehtävä tietynlaisten riippumattomien joukkojen tunnistamiseksi. Esimerkiksi 3-SAT ongelmassa meillä on annettuna propositiologiikan kaava, joka on ns. 3-CNF- muodossa ja pitää selvittää, löytyykö propositioille sellaisia totuusarvoja, jotka tekevät kaavan todeksi. Tämä voidaan ajatella osajoukkojärjestelmänä, jossa E on propositioiden joukko ja T on koostuu sellaisista osajoukoista propositioita, jotka valitsemalla "todeksi" tekevät jonkin konjunktion klausuulin todeksi, eivätkä pakota mitään klausuulia epätodeksi. Tällöin päätöstehtävänä on, onko olemassa sellaista maksimaalista riippumatonta joukkoa, joka tekee koko kaavan todeksi.
(Optimointitehtävälla ja päätöstehtävällä on kylläkin vastaavuus, koska optimointitehtävä voidaan aina muuttaa päätöstehtäväksi niin, että esitettään kysymys "onko olemassa ratkaisua, jonka paino on x".)
Eräs tärkeä osajoukkojärjestlmien luokka on ns. matroidi. Matroidi on osajoukkojärjestelmä, jolla on sellainen säännönmukainen rakenne, että jokainen siihen liitetty kombinatorinen optimointitehtävä ratkeaa ns. ahneella algoritmilla, eli valitsemalla ensin "paras" alkio ja sitten laajentamalla saatua osajoukkoa parhaalla sen kanssa yhteensopivalla jne, kunnes päädytään maksimaaliseen riippumattomaan joukkoon.
Matroideille on monia vaihtoehtoisia karakterisointeja. Esimerkiksi ns. vaihdettavuus, joka sanoo että osajoukkojärjestelmä on matroidi, jos mielivaltaisille riippumattomille joukoille A ja B, siten että A:ssa on yksi alkio enemmän kuin B:ssä, voidaan aina löytää jokin alkio, joka voidaan siirtää A:sta B:hen ja saada jokin riippumaton joukko. Vaihdettavuus takaa sen, että jos jokin suurempi riippumaton joukko löytyy, nykyistä voidaan aina kasvattaa hieman suuremmaksi "lainaamalla" yksi alkio tästä isommasta joukosta.
Vaihdettavuus on yhtäpitävä myös sen kanssa, että maksimaaliset riippumattomat joukot ovat kaikki saman suuruisia, nimitän tätä maksimaalisuusehdoksi.
Matroidi on tärkeä rakenne myös lineaarialgebrassa, sillä jos E on vektoriavaruus ja T sen lineaarisesti riippumattomien alkioiden joukko, (E,T) on matroidi. Vaihdettavuuden ja maksimaalisuusehdon paikkansapitävyys on ilmeinen, mutta se, että mielivaltainen kombinatorinen optimointitehtävä ratkeaa vektoriavaruusessa, ei ehkä ole yhtä triviaalia. Tosin; vektoriavaruus ei lopulta ole ihan niin rikas ja ilmaisuvoimainen abstraktio, kuin voisi ajatella; sen puitteissa voi tietysti määritellä rajoitteita, joilla voi ilmaista paljonkin, mutta itse vektoriavaruus on rakenteena melko yksinkertainen.
Matroidi on myös vaarallinen abstraktio. Tarkoitan tällä sitä, että ihmiset abstrahoivat usein ilmiöt matroideiksi ajattelematta lainkaan mitä tekevät. Jos abstraktio on virheellinen (tai siis, se on liian epätarkka; abstraktiohan on aina "väärä"), ilmiön kohteleminen matroidina johtaa pahoihin virheisiin. Ehkä näkyvin näistä on komposition virhepäätelmä. Matroidit ovat luonteeltaan kompositionaalisia abstraktioita. Ihmisen mieli ja kieli nojaa paljolti (tosin ei kokonaan) juuri kompositionaalisuuteen ja siksi matroidi on hyvin houkutteleva.
Nyt varoituksen sananen kaikille makkaratukille ja "yhteiskuntakriitikoille". Tällaisten abstraktioiden tunnistaminen puheesta on tarkkaa puuhaa, eikä riitä yksinään validiksi kritiikiksi. Pelkän tunnistamisen lisäksi täytyy pystyä osoittamaan kohta, josta abstraktio vuotaa.
10 kommenttia:
Tämä on taas niitä kirjoituksia, joihin vuodatan sieluni, ja joita kukaan ei ikinä kommentoi.
Komea on, mutta ohjaamoon taitaa mahtua vain koulutettu henkilökunta.
*Vilkuttaa*
Luin perustutkintooni paljon diskreettiä matematiikkaa, etenkin ryhmäteoriaa ja muuta kryptaukseen liittyvää, joten käsitteet ovat tuttuja. Mutta into näiden asioiden pyörittelyyn puuttuu jostain syystä täysin.
Nykyisissä hommissani tarvitsen lähinnä analyysiä.
Esimerkki matroidin väärinkäytöstä vaikka jossain konkreettisessa verkkokeskustelussa auttaisi ehkä ymmärtämään mitä ajat takaa.
Ihmiset eivät jaksa lukea teknisiä juttuja, heillä ei ole niiden ymmärtämiseen riittävää pohjaa ja lisäksi jos he ovat tajunneet jotain väärin, heidät nolataan kommenttiketjussa.
Tosin ymmärrän kyllä hyvin, että aina haluaisi verrata asioita mieluummin puhtaisiin abstraktioihin kuin loputtomasti vääriin tulkintoihin ja sivuseikkoihin vieviin konkreettisiin analogioihin.
Itse tajusin tuon tekstin lähinnä niin, että aina paras ratkaisu ei löydy ikäänkuin hajua seuraamalla, enkä osaa sanoa siitä mitään pidempää. Varsinkin kun viimeisessä kappaleessa kielletään sanomasta mitään jos ei tajunnut kaikkea kokonaan ja oikein.
Algoritmien suunnittelun ja analyysin kurssilla tosiaan mainittiin ohimennen matroidit, nimenomaan keinona todistaa, että joskus sikayksinketainen ahne algoritmi oikeasti tuottaa globaalisti optimaalisen lopputuloksen, eikä jää junnaamaan paikalliseen huippuun kuten yleensä. Tosin ne mainittiin vain
parilla lauseella.
Viesti tosiaan hieman vaimenee "kombinatoriseen räjähdykseen" jos alkaa varmistelemaan Wikipedista, että miten ne määritelmät nyt oikeasti menivätkään ja että onko ymmärtänyt käsitteet oikein. Sinänsä opettavaista, mutta ei kauheasti kirvoita keskustelua.
Yksi esimerkki matroidin käytöstä on argumentti "nostamalla veroja valtio saa lisää tuloja ja laskemalla niitä valtion tulot pienenevät", joskin tämän argumentin rakenteen esittäminen matroidina ei ole suorviivaista.
Suoraviivaisempi esimerkki on esimerkiksi ajatus, että kokoamalla urheilujoukkue/projektitiimi/whatever lisäämällä joukkoon aina se, jolla on paras pistesaldo/pisin CV/whatever, saadaan paras mahdollinen joukko ihmisiä annettuun tehtävään.
Itse tajusin tuon tekstin lähinnä niin, että aina paras ratkaisu ei löydy ikäänkuin hajua seuraamalla, enkä osaa sanoa siitä mitään pidempää. Varsinkin kun viimeisessä kappaleessa kielletään sanomasta mitään jos ei tajunnut kaikkea kokonaan ja oikein.
Tekstin lähtökohta oli tuo, siis tarkoituksena oli tutkia tuollaisen ajatuksen taustalla olevaa abstraktiota. On hyödyllistä kyetä tunnistamaan abstraktio, joka houkuttelee ajattelemaan että "hajua seuraamalla" voisi löytää parhaan tuloksen. Jos joku väittää, että näin on, hänen pitäisi kyetä jotenkin perustelemaan, että olemme tekemisissä matroidin tms. kanssa.
Kun ei ole opiskellut noita juttuja ja matikkaakin viimeksi lukiossa, on vähän vaikea kommentoida juuri mitään... Sori. :/
Ensimmäinen kommenttini oli kyllä jossain määrin sarkastinen. Olisin voinut laittaa hymiön, mutta fiilis olisi ehkä vähän mennyt.
Fffiiiiuuuuu... ja kone ohjaamoineen lentää kaaressa yli hilseen. Ei sillä, että mitenkään voisin muutenkaan taata ymmärtäväni tämän blogin teksteistä kummoistakaan osaa niin kuin kirjoittaja tarkoittaa... Itseasiassa jos viitataan perinteisesti määrittelemättömään keskiarvoon, niin jo tämän blogin lukeminen on elitististä toimintaa o_=
Lähetä kommentti