Tentti

Kirjoita jokaiseen paperiin

- nimi, osasto, vsk

- opintokirjan numero

- Tik-79.153 Alg. ja lasket. tentti

(Tentissä ei saa olla mukana kirjallisuutta)

1. Osoita, että funktio f(x,y) on laskettava.

f(x,y) = {0, jos x = 0

{x + y, muulloin

(x ja y ei-negatiivisia kokonaislukuja)

2. Mitkä seuraavista ovat kompleksisuus- eli vaativuusmittoja:

a) Ci(x) = 0, kaikilla i, x

b) Ci(x) = Mi(x), jos i on parillinen, muuten fi(x):n laskemiseen vaadittavien askelien määrä

Perustele!

3. Z-väritettävyysongelmassa (2-COLORABILITY) on määritettävä voidaudco annettu verkko "växittää" käyttäen vain kahta "väriä". Osoita, että 2-väritettävyysongelma on luokassa P.

4. Selitä tai määrittele seuraavat käsitteet:

a) "Jump" operaatio

b) Speedup-teorecma

c) Turing-redusoituvuus (<=T)

5. Miten ratkeamattomia ongelmia voidaan luokitella.