Kurssiviikko 3

Luentokysymykset¶

Kysymys 1

hajota ja hallitse -suunnittelustrategiassa ..

alkuperäisen ongelma jaetaan pienempiin osaongelmiin, sitten yksi osaongelma ratkaistaan ja lopetetaan

alkuperäisen ongelma hajoitetaan osaongelmiin, jotka ovat pienempiä versioita alkuperäisestä ongelmasta

jaamme aina alkuperäisen ongelman tasan kahteen osaongelmaan

jaamme alkuperäisen ongelman joukoksi osaongelmia, joiden ratkaisut ovat kaikki helppoja laskea, ja sitten lopetamme

Kysymys 2

Mikä seuraavista kuvaa parhaiten hajota ja hallitse -strategian ja rekursiivisten algoritmien välistä suhdetta?

Koska hajota ja hallitse -strategiassa muodostetut osaongelmat ovat kaikki erilaisia, rekursiivisen algoritmin käyttö on lähes mahdotonta.

Rekursiivinen algoritmi on aina hajota ja hallitse -strategian toteutus.

Jaa ja hallitse (divide-and-conquer) -strategiat toteutetaan usein käyttämällä rekursiivisia algoritmeja, koska osaongelmat ovat pienempiä versioita alkuperäisestä ongelmasta.

hajota ja hallitse -strategiaa ei voida koskaan toteuttaa käyttämällä rekursiivista algoritmia.

Kysymys 3

Mikä seuraavista kuvaa parhaiten tietorakennetta, jossa hajota ja hallitse -strategiat voisivat olla tehokkaita?

Tietorakenne, jota ei voi jakaa osiin.

Tietorakenne, joka voidaan hajottaa osiin ja jokaisella osalla on samat ominaisuudet/ominaisuudet kuin alkuperäisellä tietorakenteella.

Tietorakenne, joka voidaan hajottaa osiin ja jokaisessa osassa on jokin uusi ominaisuus tai ominaisuus, jota alkuperäisessä ei ollut.

Kysymys 1

Sanotaan, että pikalajittelu käyttää hajota ja hallitse -strategiaa käsitellessään taulukkoa \(A\). Mikä pikalajittelun osa vastaa “hajoittamista”?

\(A\):n elementit jaetaan toistuvasti jollain vakiolla, kunnes kaikkien elementtien absoluuttinen arvo on pienempi kuin 1.

Osiointia käytetään \(A\):n jakamiseen kahdeksi aliryhmäksi, ja näitä kahta aliryhmää käytetään sitten itse syötteinä Quicksortille.

Binäärihakua käytetään \(A\):n elementtien jakamiseen alkioihin, jotka ovat pienempiä tai yhtäsuuria kuin pivot, ja niihin, jotka ovat pivotia suurempia.

Kysymys 2

Pikalajittelu-algoritmin tarkoitus on

löytää taulukon suurin elementti

tuottaa taulukko, jossa elementit ovat järjestyksessä

jakaa taulukon elementit suuriin ja pieniin elementteihin

Kysymys 3

Pikalajittelussa käytetään osiointimenettelyä. Olkoon osioinnin syöte array \(A\) ja \(A\):sta meidän tulee osioida vähintään kolme elementtiä. Mikä seuraavista on totta?

On mahdollista, että osioinnin for-silmukka ei tarvitse suorittaa.

On mahdollista, että pivot-elementin sijainti ei muutu osioinnin aikana.

On mahdollista, että toinen kahdesta osioinnin aikana muodostuneesta aliryhmästä on tyhjä.

Olettaen, että \(A[1]\) on ensimmäinen elementti, on mahdollista, että osioinnin palauttama pivot on pienempi kuin 1.

Kysymys 4

Pikalajittelussa osiointia käytetään

jakamaan taulukko kahdeksi aliryhmäksi, joista toisessa on elementit vähintään yhtä suuria kuin pivot ja toisessa enintään yhtä suuret elementit kuin pivot

jakamaan taulukko kahdeksi aliryhmäksi, joista toisessa on elementit, jotka ovat yhtä suuret kuin pivot ja toisessa elementit, jotka eivät ole yhtä suuret kuin pivot

jakamaan taulukon elementit kahdeksi aliryhmäksi sen perusteella, onko pivot parillinen vai pariton luku

Kysymys 5

Mikä seuraavista väittämistä pitää paikkansa pikalajittelun suhteen?

Osiointi (partition) osittaa taulukon aina kahteen samankokoiseen alitaulukkoon.

Pikalajittelu lakkaa kutsumasta itseään rekursiivisesti, kun sen syöte sisältää enintään yhden elementin.

Pikalajittelu ei koskaan tarvitse enempää kuin kolme rekursiotasoa.

Joka kerta kun osiointia kutsutaan, pivotin vasemmalla puolella olevat elementit lajitellaan pienimmästä suurimpaan suorituksen lopuksi.

Kysymys 1

Sanotaan, että lomituslajittelu käyttää jaa ja hallitse -strategiaa käsitellessään taulukkoa \(A\). Mikä lomituslajittelun osa vastaa “jakamista”?

Lomituslajittelun aikana taulukko \(A\) jaetaan kahteen alitaulukkoon, joiden koot ovat mahdollisimman lähellä toisiaan.

Kun yhdistetään kaksi aliryhmää, yksi vaihtoehto on jakaa toinen aliryhmistä kahteen osaan. Näistä kahdesta osasta vain toista käytetään yhdistämisessä.

Lomituslajittelun aikana tietyt taulukon \(A\) elementit jaetaan kahdella niiden pienentämiseksi.

Lomituslajittelun aikana aloitetaan \(A\) vasemmasta päästä ja etsitään ensimmäinen indeksi \(i\), jolle \(A[i] > A[i+1]\). Taulukko A jaetaan aliryhmiin tämän indeksin kohdalta.

Kysymys 2

Kun kaksi lajiteltua taulukkoa yhdistetään,

saamme yhden taulukon, jossa suurin elementti sijaitsee keskellä

saamme yhden taulukon, joka on lajiteltu

saamme yhden taulukon, jonka kokoa ei voi tietää etukäteen

saamme kaksi taulukkoa, joista toinen on lajiteltu nousevaan ja toinen laskevaan järjestykseen

Kysymys 3

Kun kaksi aliryhmää yhdistetään Mergesortissa,

yhden alitaulukon kaikkien elementtien on oltava suurempia kuin toisen alitaulukon suurin elementti

viimeinen taulukko ei koskaan sisällä kahta peräkkäistä elementtiä samasta aliryhmästä

lopullisessa yhdistetyssä taulukossa voivat kaikki elementit yhdestä alitaulukosta esiintyä peräkkäin

molemmissa aliryhmissä on oltava täsmälleen sama määrä elementtejä

Kysymys 4

Olkoon taulukon (tai alitaulukon) koko sen sisältämien elementtien lukumäärä. Lomituslajittelu..

lisää syöttötaulukon kokoa yhdellä

ei kutsu itseään rekursiivisesti, kun syötetaulukon koko on pienempi kuin 8

ei toimi, kun syöttötaulukon koko on pariton

jakaa syöttötaulukon kahteen alitaulukkoon, joiden koot ovat mahdollisimman lähellä toisiaan

Kysymys 5

Mitkä seuraavista väittämistä pätevät lomituslajitteluun?

Kun kaksi aliryhmää yhdistetään, taulukko lajitellaan.

Lomituslajittelu ei koskaan kutsu itseään syötetaulukolla (tai alitaulukolla), joka sisältää täsmälleen yhden elementin.

Keskipiste (tai keski-indeksi) lasketaan vain, jos syöttötaulukko (tai alitaulukko) sisältää vähintään kaksi elementtiä.

Lomituslajittelu ei lajittele oikein syötetaulukkoa, jossa kahdella tai useammalla elementillä on sama arvo.

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?

hajota ja hallitse

pikalajittelu

osiointi

lomituslajittelu

lomittaminen

Kysymys 3

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

Linkkejä viikon aiheisiin:

An Introduction to Recursion, Part 1
Efficient recursion
Wikipedia’s pages on quicksort
Wikipedia’s pages on mergesort

Week03 - Glossary

Viikko03 - Sanasto

Kurssiviikko 3¶

Itseopiskelu (videot ja kalvot suomeksi)¶

hajota ja hallitse¶

Pikajärjestäminen (Quicksort)¶

Pikajärjestäminen: ositus (Partition)¶

Lomitusjärjestäminen (Mergesort)¶

Lomitusjärjestäminen: Lomitus (Merge)¶

Luentokysymykset¶

Palauta viikkotehtävät¶