Nashin tasapainon löytämisen laskennallinen vaativuus

Tässä tutkielmassa käsitellään approksimatiivisen Nashin tasapainon löytämisongelmaa laskennallisen vaativuuden kannalta. Vaikka Nashin tasapainon tiedetään olevan aina olemassa, on tasapainon löytäminen osoittautunut vaikeaksi ongelmaksi. Approksimatiivisen Nashin tasapainon löytämisongelma on PPAD-ongelmaluokan täydellinen ongelma. PPAD-luokkaan kuuluvat sellaiset etsintäongelmat, joissa etsittävän ratkaisun olemassaolo seuraa suunnattujen graafien pariteettiargumentista. Suunnattujen graafien pariteettiargumentti toteaa, että jos graafin jokaisen solmun lähtö- ja tuloasteet ovat korkeintaan yksi ja graafissa on tunnettu lähdesolmu, niin graafissa on myös nielusolmu tai toinen lähdesolmu. PPAD-täydellisyyden takia on luultavaa, ettei approksimatiivista Nashin tasapainoa voi löytää polynomisessa ajassa. Tässä kirjoituksessa esitetään uudelleenmuotoiltu ja tarkennettu versio approksimatiivisen Nashin tasapainon löytämisongelman PPAD-vaikeustodistuksesta. Lisäksi esitetään todistus ongelman kuulumiselle luokkaan PPAD. Vastaavaa todistusta ei löydy kirjallisuudesta, vaikka approksimatiivisen Nashin tasapainon löytämisongelman kuuluminen luokkaan PPAD mainitaan.

Sairaanhoitajaopiskelijoiden lääkelaskentataidot

Tutkimuksen tarkoituksena oli selvittää ja kuvailla sairaanhoitajaopiskelijoiden matemaattisia taitoja ennen ja jälkeen lääkelaskennan opetuksen. Tutkimuksessa selvitettiin, johtuvatko sairaanhoitajaopiskelijoiden lääkelaskennan kokeessa tapahtuvat virheet opiskelijoiden puutteellisista matemaattisista taidoista vai matematiikasta lääkelaskennan yhteydessä, ilmenikö ammattikoulu- ja ylioppilastutkinnon suorittaneiden opiskelijoiden välillä eroa tehtävissä suoriutumisen ja kokeesta läpipääsyn suhteen. Tutkimus suoritettiin kahdessa vaiheessa. Ennen lääkelaskennan opetusta opiskelijat täyttivät laskutaitojen kartoitus lähtö-tasotestin ja lääkelaskennan opetuksen päätteeksi arvioitiin opiskelijoiden koevastauspapereita. Tutkimuksessa oli mukana sekä ammattikoulun että lukion suorittaneita sairaanhoitajaopiskelijoita. Analysoidessa käytettiin keskiarvoja, hajontaa, frekvenssejä ja graafisia kuvioita kuvaamaan aineistoa. Tutkimuksen mukaan sairaanhoitajaopiskelijoilla on puutteelliset peruslaskutaidot. Lähtötasotestin vastauksista keskimäärin kaksi kolmasosaa oli oikein, muihin opiskelijat olivat jättäneet vastaamatta tai olivat laskeneet väärin. Eniten vastaamatta jätettiin desimaali- ja murtolukujen jakolaskuihin sekä prosentin, desimaaliluvun ja murtoluvun yhteyttä käsittelevään tehtävään. Ratkaistuista tehtävistä viidennes oli väärin. Vain yksi opiskelija laski kaikki lähtötasotestin tehtävät oikein. Paras neljännes sai vähintään 78 prosenttia vastauksistaan oikein. Ongelmia tuottivat desimaali- ja murtolukulaskut sekä yksikönmuunnoksista mikrogramman muuttaminen grammoiksi. Peruslaskutoimituksista yhteenlaskut sujuivat opiskelijoilta parhaiten, jakolaskut tuottivat opiskelijoille eniten vaikeuksia. Sanallisiin tehtävissä neljännes teki virheen. Virheistä yli puolet johtui siitä, ettei yhtälöä oltu osattu muodostaa lainkaan tai se oli muodostettu väärin. Kaksi viidesosaa käytti sanallisten tehtävien ratkaisutapanaan verrantoa ja kaksi viidesosaa annoskaava- tai prosenttikerroinajattelua. Päättelemällä tehtävät ratkaisi vajaa viidennes opiskelijoista. Lääkelaskennan kokeet läpäisi neljännes opiskelijoista. Kolmannes virheistä johtui siitä, ettei tehtävää oltu aloitettu oikein. Neljännes niistä, ettei opiskelijat osanneet antaa vastausta halutussa muodossa, tai jokin tehtävän oleellinen tieto oli jäänyt huomioimatta ja siten vastaus jäänyt vaillinaiseksi. Viidennes virheistä johtui kerto- tai jakolaskuvirheestä. Kaksi kolmasosaa virheistä oli käsitteellisiä, neljännes laskuvirheitä ja joka kymmenes liittyi yksikönmuunnoksiin. Lääkelaskennan kokeissa puolet käytti ratkaisutapanaan verrantoa. Koulutustaustalla ei ilmennyt vaikutusta tehtävissä suoriutumiseen ja kokeiden läpipääsyyn. Opettajia suositellaan käyttämään lääkelaskennan opetuksessa matematiikan apuvälineitä tehtävien havainnollistamiseksi.

Tietokoneavusteinen arviointi kurssilla Diskreetin matematiikan perusteet

Matematiikan opetuksen kehittämiseen korkeakoulutasolla on monia tapoja. Tavoitteena on parantaa opiskelijoiden opiskelukokemuksia, jotta he oppisivat paremmin. Oppimisen arvioinnin on todettu vaikuttavan oppimiseen merkittävästi. Arviointi tapahtuu yleensä sen perusteella, kuinka hyvin opiskelija menestyy kokeissa. Näihin kokeisiin liittyy kuitenkin useita ongelmia; ne koostuvat usein muutamasta tehtävästä, eivätkä siten kata koko koealuetta. Lisäksi perinteinen koetilanne on kaukana siitä ympäristöstä, jossa opittuja taitoja on tarkoitus käyttää. Tässä työssä tutkittiin Aalto-yliopiston Teknillisen korkeakoulun kurssin Diskreetin matematiikan perusteet (DMP) arviointikäytännön uudistamista. Kurssi toteutettiin sulautuvan oppimisen mallin mukaisesti osin verkossa. Arvioinnissa painotettiin jatkuvaa harjoitustehtävien tekemistä ja suurin osa näistä tehtävistä toteutetiin tietokoneavusteisina verkkotehtävinä. Käytössä oli automaattisen tarkistamisen mahdollistava STACK-järjestelmä. Työ jakaantui kahteen osaan: arvioinnissa käytettävien STACK-tehtävien laatimiseen ja empiiriseen osuuteen, jossa tutkittiin kurssin onnistumista. Tutkimuksessa keskityttiin toisaalta siihen, miten käytetty arviointimenetelmä toimi ja toisaalta siihen, millaiseksi opiskelijat menetelmän kokivat. Kurssia varten toteutettiin yhteensä 67 STACK-tehtävää, joista 46 oli käytössä kurssilla. Lisäksi kurssilla oli 26 perinteistä kirjallista tehtävää. Käytetyn arviointimenetelmän toimivuutta tutkittiin vertaamalla kurssin tuloksia vuosien 2008 ja 2009 DMP-kurssien tuloksiin. Vertailun perusteella huomattiin, että opiskelijat olivat vuonna 2010 ratkaisseet selvästi enemmän harjoitustehtäviä kuin edellisinä vuosina. Myös arvosanan 0 prosentuaalinen osuus suhteessa kaikkiin annettuihin arvosanoihin pieneni. Opiskelijoiden kokemuksien tutkimista varten laadittiin kurssikokemuskysely. Kyselyssä esitettiin väittämiä liittyen STACK-tehtävien laatuun, tavoitteiden ja vaatimusten selkeyteen, arvioinnin asianmukaisuuteen, työmäärän asianmukaisuuteen, opiskelijoiden sitoutuneisuuteen, käytännön järjestelyihin ja sulautuvaan oppimiseen liittyen. Tulokset olivat erittäin positiivisia. Kaikenkaikkiaan kokeilukurssi sujui hyvin; arvointimenetelmä toimi ja opiskelijat olivat tyytyväisiä. Vertailun ja kyselyn perusteella tärkeimmiksi kehityksen kohteiksi nousivat STACK-tehtävien automaattinen palaute, perinteisten tehtävien pisteyttäminen ja jako perinteisten tehtävien ja STACK-tehtävien välillä.

Kohti uudistuvaa Verkkokoulua : Käyttäjätutkimus osana Tilastokeskuksen oppimateriaalin kehittämistä

Tutkimuksen lähtökohtana on tilastojen luku- ja käyttötaitojen kehittäminen verkko-oppimisympäristöissä. Tutkimus käynnistyi Tilastokeskuksen Verkkokoulun kehittämisen tarpeesta. Päätavoitteena on muodostaa toimenpide-ehdotuksia Verkkokoulun kehittämiselle käyttäjälähtöisestä näkökulmasta. Tutkimuksessa selvitetään, miten matematiikan aineenopettajat käyttävät Tilastokeskuksen Verkkokoulua opetuksessaan ja opetuksensa suunnittelussa, ja millaisia toiveita heillä ja Verkkokoulun parissa työskentelevillä tilastokeskuslaisilla on Verkkokoulun kehittämiseksi. Tämän lisäksi selvitetään Verkkokoulun käyttöä kävijäseurantapalvelun avulla. Tutkimuksella etsitään vastauksia siihen, miten Verkkokoulua voidaan kehittää käyttäjän kannalta paremmaksi palveluksi. Tutkimusongelmiin vastataan verkkokyselyllä, sähköpostihaastattelulla, teemahaastatteluilla ja kävijäseurantapalvelulla kerättyjen aineistojen kvalitatiivisella analyysillä. Matematiikan aineenopettajille tehty kyselylomake toteutettiin maaliskuussa 2009 ja haastattelut syksyn 2009 aikana. Kävijäseurantapalvelun tarkasteluajankohta on 1.9.2008–31.8.2009. Tutkimuksen tulosten mukaan Verkkokoulu tunnetaan huonosti matematiikan aineenopettajien keskuudessa. Verkkokoulun oppimateriaaleja käytetään enemmän opetuksen suunnitteluun kuin opetukseen. Opettajat toivovat etenkin arkielämälähtöisiä ja helposti käytettäviä opetuksen suunnitteluun soveltuvia palveluja, jotka soveltuvat myös perinteiseen luokkahuoneopetukseen. Tilastokeskuslaiset näkevät Verkkokoulun kehittämisen tarpeelliseksi, vaikkakin haastavaksi kehittämiseen tarvittavien resurssien vähyyden vuoksi. Heidän mukaansa Verkkokoulua tulisi päivittää ja laajentaa monipuolisilla oppimateriaalikokonaisuuksilla. Myös teknisen toteutuksen toivotaan uudistuvan. Kävijäseurantapalvelun aineiston mukaan Verkkokoulu on keskimääräistä käytetympi kuin Tilastokeskuksen verkkosivut kokonaisuudes- saan. Verkkokoulua käytetään enemmän yksittäisten asioiden tietojen tarkistamiseen kuin kokonaisuuksien opiskeluun. Johtopäätöksenä voidaan todeta, että Tilastokeskuksen Verkkokoulu on palvelu, joka käyttäjälähtöisen kehittämisen ja markkinoinnin myötä voi nousta merkittävään rooliin tilastoalan kouluttajana. Jotta tähän päästään, kehittämiseen on löydettävä riittävästi resursseja.

Komplexa tal - vad är det?

Komplexa tal har traditionellt undervisats i de finländska gymnasierna som en valbar kurs. Denna situation har förändrats i och med de nya läroplanerna som tagits i bruk senast hösten 2005. Den nya, striktare läroplanen ger inte lika stora valmöjligheter för skolorna att bestämma undervisningsstoffet, inte ens för de valbara kurserna, och därför har många gymnasier varit tvungna att sluta undervisa om komplexa tal. För att fortsättningsvis ge en möjlighet för gymnasieelever att studera komplexa tal finns detta kompendium. Kompendiet fyller två syften. I de gymnasier där komplexa tal fortfarande finns med i läroplanen kan kompendiet användas som läromedel på ifrågavarande kurs. Kompendiet torde vara önskat eftersom det inte existerar något modernt, finlandssvenskt läromedel där de komplexa talen tas upp. Kompendiets andra, huvudsakliga syfte är att finnas till att ge en möjlighet för de elever, som inte går ett gymnasium där komplexa tal undervisas, att på egen hand lära sig grunder om komplexa tal. Kunskap om utvidgandet av talområdet från reella talen till komplexa hör till matematisk allmänbildning, och är till stor nytta om man är intresserad av att fortsätta studera matematik eller naturvetenskaper efter gymnasiet. Kompendiet kommer att läggas ut på nätet för att få det lättillgängligt. I det första kapitlet behandlas matematikens uppkomst. Det andra kapitlet är en introduktion till varför man behöver komplexa tal, där gås tal- och mängdlära igenom samtidigt som de i kompendiet använda beteckningarna introduceras. I det tredje kapitlet behandlas de komplexa talen; grundläggande räkneregler, absolutbelopp och argument, komplexa tal i polär form och lösning till högregradsekvationer är centrala begrepp. de Moivers formel är ett av de viktigare målen, även Eulers formel behandlas kort. Problematik med negativa kvadratrötter tas också upp. Det fjärde kapitlet handlar om de komplexa talens intressanta historia. I kompendiet finns rikligt med exempel och övningsuppgifter. Kapitel fem innehåller extra övningsuppgifter och i kapitel sex finns lösningarna till samtliga uppgifter. Trots att kompendiets omfång avsevärt ökas i och med dessa lösningar är det av värde att de finns med för att kompendiets huvudsakliga syfte skall uppfyllas: att eleverna på egen hand skall kunna lära sig stoffet.

Luokan P loogisesta karakterisoinnista

Deskriptiivisessä vaativuusteoriassa tutkitaan laskennan vaativuuteen liittyviä kysymyksiä logiikan työkalujen avulla. Tällöin käsitellään tilannetta, jossa laskennan syötteenä toimivat äärelliset mallit. Tässä kehyksessä erinäisiä vaativuusluokkia voidaan karakterisoida etsimällä logiikoita, joilla on kyseistä vaativuusluokkaa vastaava ilmaisuvoima. Klassiset esimerkit tällaisista tuloksista ovat Faginin esittämä epädeterministisen polynomiaalisen ajan karakterisaatio logiikan Σ_1^1 avulla ja Immermanin, Livchakin ja Vardin esittämä deterministisen polynomiaalisen ajan karakterisaatio ensimmäisen kertaluvun inflatorisen kiintopistelogiikan avulla. Tässä opinnäytetyössä tarkastellaan Gurevichin esittämää kysymystä polynomiaalisessa ajassa ratkeavien kielten luokan P vahvasta loogisesta karakterisaatiosta. Kyseinen kysymys on yksi äärellisen malliteorian haastavimpia ongelmia. Kysymyksen esittelyyn tarvittavan peruskoneiston läpikäynnin lisäksi tässä käsi- tellään myös sen yhteyksiä laskennan vaativuusteoriassa keskeiseen P-NP-ongelmaan. Gurevichin kysymyksestä voidaan esittää myös rajoitetumpia versioita, mikäli käsitellään tilannetta, jossa laskennan syötteenä voi olla vain kiinnitetyn malliluokan K malleja. Tällöin luokan P karakterisointi helpottuu, ainakin jos luokka K on riittävän suppea. Tässä opinnäytetyössä käydään läpi Grohen esittämä tulos siitä, että mikäli luokaksi K valitaan 3-yhtenäisten tasoverkkojen luokka, niin ensimmäisen kertaluvun inflatorinen kiintopistelogiikka karakterisoi polynomiaalisessa ajassa laskettavat kielet.

On the Rademacher maximal function

Tools known as maximal functions are frequently used in harmonic analysis when studying local behaviour of functions. Typically they measure the suprema of local averages of non-negative functions. It is essential that the size (more precisely, the L^p-norm) of the maximal function is comparable to the size of the original function. When dealing with families of operators between Banach spaces we are often forced to replace the uniform bound with the larger R-bound. Hence such a replacement is also needed in the maximal function for functions taking values in spaces of operators. More specifically, the suprema of norms of local averages (i.e. their uniform bound in the operator norm) has to be replaced by their R-bound. This procedure gives us the Rademacher maximal function, which was introduced by Hytönen, McIntosh and Portal in order to prove a certain vector-valued Carleson's embedding theorem. They noticed that the sizes of an operator-valued function and its Rademacher maximal function are comparable for many common range spaces, but not for all. Certain requirements on the type and cotype of the spaces involved are necessary for this comparability, henceforth referred to as the “RMF-property”. It was shown, that other objects and parameters appearing in the definition, such as the domain of functions and the exponent p of the norm, make no difference to this. After a short introduction to randomized norms and geometry in Banach spaces we study the Rademacher maximal function on Euclidean spaces. The requirements on the type and cotype are considered, providing examples of spaces without RMF. L^p-spaces are shown to have RMF not only for p greater or equal to 2 (when it is trivial) but also for 1 < p < 2. A dyadic version of Carleson's embedding theorem is proven for scalar- and operator-valued functions. As the analysis with dyadic cubes can be generalized to filtrations on sigma-finite measure spaces, we consider the Rademacher maximal function in this case as well. It turns out that the RMF-property is independent of the filtration and the underlying measure space and that it is enough to consider very simple ones known as Haar filtrations. Scalar- and operator-valued analogues of Carleson's embedding theorem are also provided. With the RMF-property proven independent of the underlying measure space, we can use probabilistic notions and formulate it for martingales. Following a similar result for UMD-spaces, a weak type inequality is shown to be (necessary and) sufficient for the RMF-property. The RMF-property is also studied using concave functions giving yet another proof of its independence from various parameters.

Computational Methods for Reconstruction and Analysis of Genome-Scale Metabolic Networks

Metabolism is the cellular subsystem responsible for generation of energy from nutrients and production of building blocks for larger macromolecules. Computational and statistical modeling of metabolism is vital to many disciplines including bioengineering, the study of diseases, drug target identification, and understanding the evolution of metabolism. In this thesis, we propose efficient computational methods for metabolic modeling. The techniques presented are targeted particularly at the analysis of large metabolic models encompassing the whole metabolism of one or several organisms. We concentrate on three major themes of metabolic modeling: metabolic pathway analysis, metabolic reconstruction and the study of evolution of metabolism. In the first part of this thesis, we study metabolic pathway analysis. We propose a novel modeling framework called gapless modeling to study biochemically viable metabolic networks and pathways. In addition, we investigate the utilization of atom-level information on metabolism to improve the quality of pathway analyses. We describe efficient algorithms for discovering both gapless and atom-level metabolic pathways, and conduct experiments with large-scale metabolic networks. The presented gapless approach offers a compromise in terms of complexity and feasibility between the previous graph-theoretic and stoichiometric approaches to metabolic modeling. Gapless pathway analysis shows that microbial metabolic networks are not as robust to random damage as suggested by previous studies. Furthermore the amino acid biosynthesis pathways of the fungal species Trichoderma reesei discovered from atom-level data are shown to closely correspond to those of Saccharomyces cerevisiae. In the second part, we propose computational methods for metabolic reconstruction in the gapless modeling framework. We study the task of reconstructing a metabolic network that does not suffer from connectivity problems. Such problems often limit the usability of reconstructed models, and typically require a significant amount of manual postprocessing. We formulate gapless metabolic reconstruction as an optimization problem and propose an efficient divide-and-conquer strategy to solve it with real-world instances. We also describe computational techniques for solving problems stemming from ambiguities in metabolite naming. These techniques have been implemented in a web-based sofware ReMatch intended for reconstruction of models for 13C metabolic flux analysis. In the third part, we extend our scope from single to multiple metabolic networks and propose an algorithm for inferring gapless metabolic networks of ancestral species from phylogenetic data. Experimenting with 16 fungal species, we show that the method is able to generate results that are easily interpretable and that provide hypotheses about the evolution of metabolism.

Computational Methods for Detecting Large-Scale Chromosome Rearrangements in SNP Data

Large-scale chromosome rearrangements such as copy number variants (CNVs) and inversions encompass a considerable proportion of the genetic variation between human individuals. In a number of cases, they have been closely linked with various inheritable diseases. Single-nucleotide polymorphisms (SNPs) are another large part of the genetic variance between individuals. They are also typically abundant and their measuring is straightforward and cheap. This thesis presents computational means of using SNPs to detect the presence of inversions and deletions, a particular variety of CNVs. Technically, the inversion-detection algorithm detects the suppressed recombination rate between inverted and non-inverted haplotype populations whereas the deletion-detection algorithm uses the EM-algorithm to estimate the haplotype frequencies of a window with and without a deletion haplotype. As a contribution to population biology, a coalescent simulator for simulating inversion polymorphisms has been developed. Coalescent simulation is a backward-in-time method of modelling population ancestry. Technically, the simulator also models multiple crossovers by using the Counting model as the chiasma interference model. Finally, this thesis includes an experimental section. The aforementioned methods were tested on synthetic data to evaluate their power and specificity. They were also applied to the HapMap Phase II and Phase III data sets, yielding a number of candidates for previously unknown inversions, deletions and also correctly detecting known such rearrangements.

Semantic Classes in Topic Detection and Tracking

Topic detection and tracking (TDT) is an area of information retrieval research the focus of which revolves around news events. The problems TDT deals with relate to segmenting news text into cohesive stories, detecting something new, previously unreported, tracking the development of a previously reported event, and grouping together news that discuss the same event. The performance of the traditional information retrieval techniques based on full-text similarity has remained inadequate for online production systems. It has been difficult to make the distinction between same and similar events. In this work, we explore ways of representing and comparing news documents in order to detect new events and track their development. First, however, we put forward a conceptual analysis of the notions of topic and event. The purpose is to clarify the terminology and align it with the process of news-making and the tradition of story-telling. Second, we present a framework for document similarity that is based on semantic classes, i.e., groups of words with similar meaning. We adopt people, organizations, and locations as semantic classes in addition to general terms. As each semantic class can be assigned its own similarity measure, document similarity can make use of ontologies, e.g., geographical taxonomies. The documents are compared class-wise, and the outcome is a weighted combination of class-wise similarities. Third, we incorporate temporal information into document similarity. We formalize the natural language temporal expressions occurring in the text, and use them to anchor the rest of the terms onto the time-line. Upon comparing documents for event-based similarity, we look not only at matching terms, but also how near their anchors are on the time-line. Fourth, we experiment with an adaptive variant of the semantic class similarity system. The news reflect changes in the real world, and in order to keep up, the system has to change its behavior based on the contents of the news stream. We put forward two strategies for rebuilding the topic representations and report experiment results. We run experiments with three annotated TDT corpora. The use of semantic classes increased the effectiveness of topic tracking by 10-30\% depending on the experimental setup. The gain in spotting new events remained lower, around 3-4\%. The anchoring the text to a time-line based on the temporal expressions gave a further 10\% increase the effectiveness of topic tracking. The gains in detecting new events, again, remained smaller. The adaptive systems did not improve the tracking results.