Tik-76.147 Tietämystekniikan peruskurssi

Merkitse jokaiseen vastauspaperiisi

- Tik-76.147 Tietämystekniikan peruskurssi

- 19.05.1995

- sukunimi, etunimet

- osasto

- opintokirjan numero

1. Kuvaile lyhyesti eteenpäin ja taaksepäin ketjuttavaa päättelyä. Voit käyttää apuna esimerkkiä, jossa meillä on säännöt:

A&B->D,

C & D -> E

E -> F

sekä tosiasiat A, B ja C ja halutaan päätellä F.

Miten päättelyä voitaisiin ohjata?

2. Esitä hakuproseduuri BACKTRACK, joka suorittaa peräytyvän haun. Milloin proseduurin ohjaama haku etenee syvyyssuuntaisesti ja milloin rintamahakuna? Proseduurin tulee palauttaa sekä polku lähtösolmusta maalisolmuun että ao. polun kustannukset.

3. Tarkastellaan seuraavia lauseita:

. Jussi pitää kaikesta ruoasta.

. Omenat ovat ruokaa.

. Nakit ovat ruokaa.

. Kaikki mitä joku syö ja mikä ei ole tappavaa (1. myrkkyä), on ruokaa.

. Ville syö perunoita ja on edelleen hengissä.

. Sari syö kaikkea, mitä Ville(kin syö).

a) Muunna lauseet predikaattilogiikan lausekkeiksi. (1 p)

b) Osoita, että Jussi pitää perunoista, käyttäen taaksepäin ketjuttavaa päättelyä. (1p)

c Muunna a-kohdan lausekkeet klausuulimuotoon. (1 p)

d) Todista resoluutiolla, että Jussi pitää perunoista. (1 p)

e) Etsi resoluutiolla vastaus kysymykseen: "Mitä (ruokaa) Sari syö?"(1 p)

+ 1 p, jos kaikki kohdat a - e ovat oikein.

4. a) Selosta A* -hakuproseduurin toimintaperiaate.

b) Sovella A* -hakuproseduuria ongelmaan, jossa seuraavat tilasiirtymät ovat

mahdollisia:

Siirtymä Sen kustannus

S ->A 2

S -> B 1

S ->C 2

A -> D 2

B ->E 1

C -> F 1

D->H 2

E -> H 8

E -> I 7

F -> I 2

H -> G 1

I -> G 2

Ongelmana on löytää polku tilasta S tilaan G, kun funktion h* arvot eri solmuissa ovat seuraavat: h*(A)=3, h*(B)=3, h*(C)=3, h*(D)=2, h*(E)=2, h*(F)=2, h*(H)=1 ja h*(I)=1. Kumman kahdesta minimikustannuspolusta algoritmisi löytää ja miksi?

(arvostelu: a-kohta max. 3 pistettä, b-kohta max. 3 pistettä)

5. Määrittele seuraavat rajoitteiden tyydyttämisongelmiin liittyvät käsitteet:

1) Solmukonsistenssi

2) Kaarikonsistenssi

3) Polkukonsistenssi

4) k-konsistenssi

5) Sunnattu konsistenssi

6) Rajoiteverkon leveys

(arvostelu: 1 piste/käsite, riittää kun kerrot miten käsitteet on määritelty, sinun ei siis tarvitse esim. kirjoittaa algoritmeja tms.)