Lamén lause
375.7 KB
avoin
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
Lataukset6
Pysyvä osoite
Verkkojulkaisu
DOI
Tiivistelmä
Tässä LuK-tutkielmassa esitetään ja todistetaan Lamén lause. Lause arvioi, kuinka nopeasti Eukleideen algoritmi löytää suurimman yhteisen tekijän kahdelle kokonaisluvulle. Algoritmin nopeus riippuu tutkittavien kokonaislukujen logaritmisesta suuruudesta eli numeroiden lukumäärästä luvuissa. Tutkielmassa esitellään lyhyesti jaollisuuden perusteita ja Eukleideen algoritmi. Lisäksi käsitellään Fibonaccin lukuja ja todistetaan niihin liittyviä aputuloksia. Tutkitaan, miten Fibonaccin lukujono liittyy Eukleideen algoritmin analysointiin.