Kurssiviikko 2

Luentokysymykset¶

Kysymys 1

Mitä oikeastaan mitataan, kun mitataan algoritmin tehokkuutta?

Suoritettujen toimintojen määrää

Millisekunteja

Algoritmissa käytettyjen muuttujien määrää

Koodirivien määrää algoritmin pseudokoodissa

Kysymys 2

Miksi algoritmin asymptoottinen suorituskyky on kiinnostava?

Sen avulla voidaan arvioida toteutuksen koodirivien lukumäärä

Sen avulla tiedämme, miten algoritmin tehokkuus muuttuu syötetietojen koon kasvaessa.

Se mahdollistaa toteutetun algoritmin todellisen suoritusajan tarkan mittauksen

Kysymys 3

Valitse oikeat väittämät

Algoritmin asymptoottinen suorituskyky antaa aina tarkat arvot algoritmin suorituskyvylle.

Asymptoottisen suorituskyvyn avulla voimme verrata kahta vaihtoehtoista algoritmia saman tehtävän suorittamiseen.

Asymptoottinen suorituskyky ilmaisee nopeuden, jolla algoritmi hidastuu tiedon määrän kasvaessa.

Tehokas algoritmi hidastuu aina hyvin nopeasti tiedon määrän kasvaessa.

Kysymys 4

Miksi algoritmin ratkaisun laskemiseen kuluvan ajan mittaaminen ei ole toteuttamiskelpoinen tapa mitata algoritmin tehokkuutta?

Koskaan ei voi tietää, milloin algoritmi on lopettanut laskennan.

Ei ole olemassa kelloa, joka olisi tarpeeksi tarkka mittaamaan minkä tahansa algoritmin laskenta-aikaa millään tietokoneella.

Aika riippuu liian monesta tekijästä.

Jos on olemassa parempi algoritmi, niin heikomman algoritmin laskenta-ajan mittaaminen on turhaa.

Kysymys 5

Oletetaan, että meillä on pseudokoodi jollekin algoritmille A ja meille annetaan tehokkuusanalyysi tälle pseudokoodille. Mitä voimme tehdä tällä tehokkuusanalyysillä?

Voimme laskea tarkalleen algoritmin A laskenta-ajan jollekin tietylle syötteelle tietyllä tietokoneella.

Voimme tarkalleen määrittää sellaiset tilanteet, joissa algoritmi A laskee oikein ja tilanteet, joissa se epäonnistuu.

Jos algoritmi B on olemassa saman ongelman ratkaisemiseksi kuin algoritmi A ja meillä on myös algoritmin B tehokkuusanalyysi, niin voimme verrata A:n ja B:n tehokkuuksia.

Voimme kertoa kuinka monta muuttujaa algoritmi A tarkalleen käyttää.

Kysymys 1

Missä ohjelmoinnin osa-alueissa järkevä tiedon jakaminen tehostaa algoritmia?

tietojen ylläpidossa

koodin luettavuudessa ja ymmärrettävyydessä

turhan tiedon varastoinnin vähentämisessä

koodin suoritusajassa

koodin kirjoittamisessa

Kysymys 2

Oletetaan, että tietokonekieli X käyttää arvosemantiikkaa ja tietokonekieli Y viitesemantiikkaa. Oletetaan, että on olemassa suuri objekti A ja meillä on seuraava koodirivi: B=A. Mikä seuraavista on väärin?

Y:ssä sekä A että B viittaavat samaan kohteeseen.

Kun koodirivi B = A on suoritettu, sekä X että Y käyttävät saman määrän muistia.

X:ssä A ja B varaavat erilliset muistialueet.

Kysymys 3

Oletetaan, että C++:ssa jokainen taulukon A elementti sisältää suuren objektin. Useita tekniikoita voidaan käyttää A:n elementtien jakamiseen: osoittimet, älykkäät osoittimet, indeksit ja niin edelleen. Mitkä seuraavista ovat totta?

Kaikilla erilaisilla jakamistavoilla on automaattinen roskien kerääminen, jos jokin A:n elementti tuhoutuu.

Jokainen tekniikka edellyttää jonkin aputietorakenteen (tai tietorakenteiden) muodostamista A:n elementteihin viittaamista varten.

Jos käytämme jotakin tekniikoista, emme voi enää tehdä kopiota A:sta.

Käyttämällä jotakin aputietorakennetta voimme tehokkaasti käsitellä A:n elementtejä tietyssä järjestyksessä ilman, että A:ta tarvitsee muuttaa ollenkaan.

Yhdessä C++-funktiossa ei voi käyttää useampaa kuin yhtä jakotekniikkaa.

Kysymys 1

Rekursio on hyödyllinen, koska

rekursiivisella funktiolla on aina parempi suorituskyky kuin vastaavalla iteratiivisella funktiolla

rekursiossa ei koskaan tarvitse käyttää for-silmukoita, while-silmukoita tai if-lauseita

suuret ongelmat voidaan jakaa pienempiin versioihin samasta ongelmasta

rekursiivinen funktio sisältää vain triviaaleja (perus)tapauksia

Kysymys 2

Mitkä seuraavista kutsupinoa koskevista väittämistä ovat tosia rekursiolle?

Proseduurin parametrit (tai argumentit) ovat erilaisia pinon eri tasoilla.

Ohjelmoijan on nimenomaisesti sisällytettävä koodi sellaiseen prosessiin, joka pitää kirjaa kutsupinon koosta.

Kutsupinoa voidaan pitää sellaisten kutsujen järjestettynä pinona, joita ei ole vielä suoritettu kokonaan.

Kun kutsu on kerran lisätty kutsupinoon, sitä ei voi koskaan poistaa.

Kutsupino tyhjennetään aina kun rekursiivinen proseduuri suorittaa triviaalin (tai perus/pohjatapauksen).

Kysymys 3

Oletetaan, että taulukko A sisältää lukuja, jotka on järjestetty pienimmästä suurimpaan ja käytämme rekursiivista binäärihakua elementin etsimiseen. Mitkä seuraavista väitteistä ovat totta?

Suoritamme triviaalisen (tai perus)tapauksen vain silloin, kun A:n pienin elementti on suurempi kuin se elementti, jota etsimme.

Joka kerta kun binäärihakualgoritmia kutsutaan, sekä vasen että oikea sijainti muuttuvat.

Jos jollakin rekursiotasolla etsitään alitaulukosta, jonka koko on m ja m >= 2, niin seuraavalla rekursiotasolla etsitään alitaulukosta, jonka koko on enintään (m+1)/2.

Rekursiivisessa (tai ei-triviaalissa) tapauksessa lasketaan sijainti, joka on vasemman ja oikean sijainnin puolivälissä.

Kysymys 4

Oletetaan, että X on rekursiivinen funktio. Mikä seuraavista väitteistä on totta?

Perustapauksessa (tai triviaalissa) X kutsuu itseään kerran ja rekursiivisessa tapauksessa X kutsuu itseään vähintään kahdesti.

Sekä perus- (tai triviaali-) että rekursiivisessa tapauksessa X voi kutsua itseään.

Perustapauksessa (tai triviaalissa) X voi kutsua vain itseään, mutta ei mitään muuta proseduuria, ja rekursiivisessa tapauksessa X voi kutsua mitä tahansa muuta proseduuria paitsi itseään.

Perustapauksessa (tai triviaalissa) X ei kutsu itseään ja rekursiivisessa tapauksessa X kutsuu itseään ainakin kerran.

Kysymys 1

Muotoile kurssin kannalta keskeinen kysymys, johon tämän viikon videot antavat vastauksen.

Kysymys 2

Minkä videon aiheesta pitäisi erityisesti keskustella keskustelutilaisuudessa?

algoritmin tehokkuus

tietojen jakaminen

rekursio

Kysymys 3

Oliko videoiden sisällössä jotain erityisen vaikeaa? Entä mielenkiintoista? Jotain josta haluaisit oppia lisää?

Kurssiviikko 2¶

Itseopiskelu (videot ja kalvot suomeksi)¶

Tehokkuuden mittaaminen ja sen rajat¶

Asymptoottisen tehokkuuden idea¶

Datan jakaminen¶

Rekursio¶

Luentokysymykset¶

Palauta viikkotehtävät¶