ALGORITMIEN SUUNNITTELU JA ANALYYSI

Kevät-2007

Harjoitus 2. (viikolla 5)

1. Kuvaa sanallisesti puun ja verkon läpikäyntialgoritmien periaatteet. Puun läpikäyntialgoritmit, syvyyssuuntainen- ja leveyssuuntainen läpikäynti, ovat monisteen sivulla 12 ja verkon vastaavat algoritmit ovat monisteen sivulla 13. (Vrt. Luennoissa oleva lause "vieraile sellaisen solmun lapsessa, jolla on vielä vierailemattomia lapsia ja jonka vierailusta on kulunut mahdollisimman paljon aikaa".)

2. Piirrä seuraavasta verkosta saatava (eräs) syvyyssuuntainen virittävä metsä, kun haku alkaa solmusta e. Merkitse kuvaan lisäksi erikseen etenevät kaaret, takautuvat kaaret ja poikittaiskaaret.

3. Piirrä edellisen tehtävän verkosta saatava (eräs) leveyssuuntainen virittävä metsä, kun haku alkaa solmusta a. Merkitse tähänkin kuvaan lisäksi erikseen etenevät kaaret, takautuvat kaaret ja poikittaiskaaret.

4. Eräs syklittömän suunnatun verkon (eli DAGin) visualisointialgoritmi jakaa aluksi verkon solmut päällekkäisiin kerroksiin niin, että kaikki verkon kaaret osoittavat alaspäin:

Kerros 1

Kerros 2

Kerros 3

Algoritmi siis valitsee jokaiselle verkon solmulle kerroksen sillä rajoituksella, että jokaisen kaaren alkupään kerros on pienempi kuin sen loppupään kerros.

Kirjoita algoritmi (pseudokoodi), joka tekee jaon kerroksiin. Yritä tehdä algoritmista sellainen, että kerroksia tulee mahdollisimman vähän. Vihje: Sellaiset solmut, joiden lähtöaste on 0, sopivat esimerkiksi alimpaan kerrokseen.

Toteuta tehtäväpaperin taustapuolen esiinkääntämissuorite.

5. Maksimaalisen osajoukon ongelmassa etsitään kokonaislukujonosta yhtenäistä osaa, joka antaa suurimman lukujen summan. Esimerkiksi jonosta [-1,2,3, -5, 7, -2, 5, 1, -1] suurin summa on 11, joka tulee jonon osasta [7, -2, 5, 1].

Seuraavassa on kaksi algoritmia suurimman summan etsimiseen:

procedure maxsummal (F: integer[n])

begin

maxsumma ← 0 ;

for vasen ← 1 to n do

for oikea ← vasen to n do

begin

summa ← 0 ;

for i ← vasen to oikea do

summa ← summa +F[i] ;

if summa> maxsumma then maxsumma ← summa

end ;

return maxsumma

end

procedure maxsumma2 (F: integer[n])

begin

scanmax 0; vanhamax ← 0;

for i ← 1 to n do

begin

if scanmax + F[i] > 0

then scanmax ← scanmax + F[i]

else scanmax ← 0 ;

if scanmax > vanhamax then vanhamax ← scanmax

end ;

return vanhamax

end

a) Selitä, miten kumpikin algoritmi toimii.

b) Mitkä ovat em. algoritmien aikavaatimukset?

6. Binäärihaku on toteutettu rekursiivisella proseduurilla. Kirjoita algoritmin aikavaatimusta T(n) kuvaava rekursioyhtälö ja ratkaise se.