[Suluissa olevat n-lausekkeet pitäisivät olla t:n alaviitteitä.]
2. On annettu n työtä, joista kukin vaativat yhden aikayksikön prosessointiaikaa. Tietyllä hetkellä voidaan suorittaa enintään yhtä työtä. Työn i suorittamisesta saadaan "hyöty" g(i) ja ko. työn määräaika on d(i).
Esim.
i
1
2
3
4
5
g(i)
10
20
15
30
5
d(i)
1
2
2
1
1
Halutaan valita ko. töiden alijoukko siten, että töille on määräaikaehdot täyttävä suoritusaikataulu ja hyötyjen summa on maksimaalinen.
Anna ko. ongelmalle optimaalinen ahnas ratkaisualgoritmi, osoita optimaalisuus ja sovella esimerkkitapaukseen.
[Suluissa olevat i-merkinnät pitäisivät olla alaviitteitä.]
3. Selvitä miten hajoita-ja-hallitse -tekniikkaa voidaan soveltaa kahden matriisin kertolaskun tehostamiseksi. (Aikavaatimus?)
4. Osoita, että SAT-3-CNF on NP-täydellinen.
5. Osoita, että HAMD <=
P
ß-rel-TSP kaikille positiivivakioille ß.
T
HAMD = Hamiltonin sykli -päätösongelma
TSP = Kauppamatkustajan ongelma