Tehtävä:
Pinon muistinkäyttö

Lyhyt MathCheck-ohje (uuteen välilehteen)

Pino on tietorakenne, johon voi lisätä alkion ylimmäksi, ottaa ylimmän alkion pois, kysyä ylimmän alkion arvoa, ja kysyä onko pino tyhjä. (Joissakin pinoissa ylimmän alkion poistaminen ja arvon kysely on yhdistetty yhdeksi toiminnoksi.) Jos etukäteen ei tiedetä, kuinka monta alkiota pinossa voi enintään olla kerrallaan, niin pino voidaan toteuttaa tehokkaasti joustavan taulukon tai linkitetyn listan avulla. Tässä tehtävässä verrataan niiden muistin kulutusta. Tavoitteena on oppia analysoimaan muistin kulutusta.

Oletamme, että osoitin vie 8 tavua, koska nykyaikaisissa tietokoneissa on yleensä niin. Laskujen yksin­kertais­tamiseksi oletamme, että pinoon talletettava alkio (eli hyöty­kuorma) vie `8h` tavua, missä `h in NN`.

MathCheckin antamat bonuslupaukset eivät suoraan tarkoita lisäpisteitä, mutta voivat olla myötä­vaikut­tamassa lisä­pisteisiin yhdessä toistensa tai muiden ansioiden kanssa.

Taulukko­toteutuksessa on dynaamisesti varattu `2^k` alkion kokoinen muisti­alue (missä `k in NN`) sekä kantatietue, jossa on kolme 8-tavuista tietoa: missä muistialue sijaitsee, kuinka iso se on, ja kuinka paljon siitä on käytössä. Taulukon alkiossa on hyöty­kuorma eli pinon alkio, eikä muuta. Ilmaise muistin tarve `k`:n ja `h`:n funktiona.
tai

Merkitsemme pinossa olevien alkioiden määrää `n`:llä. Kun pino on suurimmillaan, `k` on pienin kokonais­luku, jolle `2^k` taulukon alkiota riittää. Ilmaise muistin tarve `n`:n ja `h`:n funktiona.

tai

Tuli niin hirveä lauseke, että sen kanssa laskelmia on vaikea jatkaa. Yritämme toista keinoa: tarkastelemme vain äärimmäiset tapaukset. Ilmaise muistin tarve `n`:n ja `h`:n funktiona silloin, kun dynaamisesti varattu muisti­alue on täsmälleen sopivan kokoinen.
(1) tai

Kuinka suuri `n` on silloin, kun `2^k` alkion kokoinen muisti­alue riittää mutta `2^(k-1)` alkion kokoinen juuri ja juuri ei riitä? Ilmaise `k`:n funktiona.
tai
Kuinka monta alkiota silloin on varattu, ilmaistuna `n`:n funktiona?
tai

Ilmaise muistin tarve `n`:n ja `h`:n funktiona silloin, kun dynaamisesti varatusta muisti­alueesta jää mahdol­lisimman paljon tilaa käyttämättä. Koska tilaa ei jää käyttämättä kun `n <= 2`, riittää, että lausekkeesi antaa oikean tuloksen kun `n >= 3`. Vastaus­tilaa on kaksi riviä siksi, että ensin voit antaa moni­mutkaisen lausekkeen, ja kun olet saanut sen oikein, voit kirjoittaa seuraavalle riville =-merkin ja vastauksen sievennettynä yksin­kertai­sempaan muotoon.
(2) tai

Listatoteutuksessa on listan alkuosoitin sekä `n` tietuetta, joista jokaisessa on hyöty­kuorma eli pinon alkio sekä osoitin seuraavaan tietueeseen listassa. Ilmaise muistin tarve `n`:n ja `h`:n funktiona.
(3) tai

Merkitsemällä (1) ja (3) yhtäsuuriksi saadaan yhtälö, jonka ratkaisu kertoo, millä `n`:n ja `h`:n arvoilla lista kuluttaa yhtä paljon muistia kuin taulukko parhaim­millaan. Valitettavasti MathCheck ei osaa käsitellä yhtälöitä, joissa on useita tuntemattomia. Mutta meillä kävi tuuri: edellä saadun yhtälön ratkaisu ei riipu `h`:sta. (Jos osaat ratkaista yhtälöitä ja olet saanut (1):n ja (3):n oikein, niin huomaat helpolla laskulla, että näin on.) Siksi voimme ratkaista yhtälön antamalla `h`:lle ihan minkä tahansa arvon (vaikka 1 tai 0).

Valitse `h`:lle jokin arvo ja kirjoita ruutuun yhtälö, jossa `h`:n sijalla on se arvo. Tarkasta nappia klikkaamalla, että kirjoittamasi on oikein. Sitten lisää perään <=> ja yhtälön ratkaisu. Jos tarvitset välivaiheita, kirjoita lisää <=>-symboleita.

tai

Sanomme, että `n` on pieni, kun se on pienempi kuin edellä johtamasi raja, ja suuri kun se on rajaa suurempi. Valitse vaihtoehdot, jotka vastaavat lausekkeita (1) ja (3).
Kun `n` on pieni, taulukko kuluttaa vähemmän muistia.
Kun `n` on pieni, lista kuluttaa vähemmän muistia.
Kun `n` on suuri, taulukko kuluttaa vähemmän muistia.
Kun `n` on suuri, lista kuluttaa vähemmän muistia.
tai

Valitse vaihtoehto, joka vastaa lausekkeita (1) ja (3).
Kun `n` on pieni, niin molempien toteutusten muistin kulutus on niin pieni, että sillä ei ole merkitystä juuri koskaan. Siksi se rakenne on parempi, joka kuluttaa vähemmän muistia, kun `n` on suuri.
Kun `n` on pieni, niin molempien toteutusten muistin kulutus on niin pieni, että sillä ei ole merkitystä juuri koskaan. Emme kuitenkaan voi päätellä tästä kumpi rakenne on parempi, sillä olemme analysoineet vasta tapauksen, joka on taulukolle erityisen edullinen.
Kun `n` on pieni, niin molempien toteutusten muistin kulutus on niin pieni, että sillä ei ole merkitystä juuri koskaan. Emme kuitenkaan voi päätellä tästä kumpi rakenne on parempi, sillä olemme analysoineet vasta tapauksen, joka on taulukolle erityisen epäedullinen.
Muistin määrän vähentäminen on tärkeää myös kun `n` on pieni.
tai

Lausekkeiden (2) ja (3) vertaaminen edellä käytetyllä keinolla ei onnistu. Siksi kirjoita ruutuun (2) − (3), missä (2) ja (3) ovat em. lausekkeet. Kun olet tarkastanut että se on oikein (vaikkakin liian moni­mutkainen), lisää perään =-merkki ja sievennetty muoto. Voit halutessasi kirjoittaa useita väli­vaiheita. Lopuksi pitää päästä muotoon, jossa lauseke koostuu kertolaskuista, jossa kerrottavat ovat lukuja, muotoa `(n - `luku`)` tai muotoa `(h - `luku`)`.

tai

Tästä muodosta näkyy, että muistin kulutukset ovat yhtä­suuret, kun `h=` tai `n=`.
tai

Kun `n` ja `h` ovat näitä rajoja isommat, kumpi kuluttaa vähemmän muistia?
taulukko
lista
tai

Valitse oikeat vaihtoehdot olettaen, että `n >= 3` ja taulukon koko voi olla tapauksen (1) tai tapauksen (2) mukainen tai siltä väliltä.
Oletamme, että `n >= 3`, koska edellä olevan analyysin mukaan (2) antaa väärän tuloksen kun `n=2` tai vähemmän.
Oletamme, että `n >= 3`, koska edellä oleva analyysi jättää avoimeksi, antaako (2) oikean tuloksen kun `n=2` tai vähemmän.
Kun `h` on edellä johdetun rajan suuruinen, kuluttaa taulukko aina saman määrän muistia kuin lista.
Kun `h` on edellä johdettua rajaa suurempi, joillakin `n`:n arvoilla taulukko ja joillakin lista kuluttaa vähemmän muistia.
tai

Olemme edellä laskeneet vain taulukolle varatun muistin kulutusta. Kun taulukolle varattu tila kasvaa, aikaisemmin käytössä ollut tila palautetaan käyttö­järjes­telmälle, joka ei välttämättä pysty hyödyntämään sitä, koska se saattaa olla hankalan kokoinen erillinen pätkä. Kun tämä otetaan huomioon,
Taulukon asema vertailussa paranee.
Listan asema vertailussa paranee.
Kummankaan asema vertailussa ei muutu.
tai

Lopetamme analyysimme tähän. Vaikka analyysimme ei sitä kerrokaan, sekä taulukko että lista ovat yleensä hyviä toteutuksia pinolle.