DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

229

DODATAK: PROGRAMIRANJE U

PROGRAMSKIM JEZICIMA UMJETNE

INTELIGENCIJE

Najpoznatiji programski jezici umjetne inteligencije su Lisp, Prolog i Python, no programiranje

metoda umjetne inteligencije nije ograničeno samo na njih. U praksi se metode umjetne inteligencije

mogu programirati u bilo kojem programskom jeziku, no u nekima od njih će, zbog dostupne ili

nedostupne podrške i dokumentacije, to biti jednostavnije ili složenije. Danas se za programiranje metoda

umjetne inteligencije najčešće koristi Python jer je jednostavan, ima izvrsnu dokumentaciju, besplatan

je, te je za njega dostupan velik broj biblioteka vezanih uz umjetnu inteligenciju.

Iako se Lisp i Prolog danas ne koriste toliko često kao prije, ipak ih je dobro naučiti jer zahtijevaju

potpuno drugačiji pristup razmišljanju i programiranju od programskih jezika na koje je većina

programera danas naviknuta, pa je savladavanje osnova ovih jezika sastavni dio svih uvodnih kolegija

umjetne inteligencije.

U nastavku su osnove Lispa, Prologa i primjena Pythona u programima umjetne inteligencije.

Kako su ovo ujedno i materijali laboratorijskih vježbi, organizirali smo ih u 10 vježbi. Sastavni dio vježbi

su i zadaci za samostalno vježbanje.

VJEŽBA 1 - UVOD U PROGRAMIRANJE U LISP-U

Lisp (engl. LISt Processor) je jedan od najstarijih programskih jezika i jedan od najpopularnijih

koji se tradicionalno koriste u umjetnoj inteligenciji. Osmišljen je 1958. g., i to samo dvije godine nakon

što je utemeljeno područje umjetne inteligencije, a osmislio ga je John McCarthy, istraživač koji je bio

dio skupine znanstvenika koji su utemeljili područje umjetne inteligencije 1956. g.

Po kategoriji, Lisp spada u skupinu funkcionalnih programskih jezika (podržava komponiranje

funkcija i rekurziju). Lisp je jezik opće namjene i drugi je po redu najstariji programski jezik visoke razine

Dodatak ovog udžbenika posveć en je programiranju u programskim jezicima umjetne

inteligencije. Neki od njih, kao što su Lisp i Prolog, razvili su se u okvirima umjetne

inteligencije, a bili su posebno značajni u razdobljima kada se umjetna inteligencija

intenzivno razvijala. Danas je njihovo mjesto u najvećoj mjeri zauzeo Python, možda ne

zato što je bolji, već zato što je univerzalni programski jezik koji se lako uči. U okviru

programerske zajednice Pythona mogu se pronaći programska rješenja većine postupaka

koje smo opisali u ovom udžbeniku. Dodatak je napisan u obliku vježbi koje se

posljednjih godina izvode na FESB-u u okviru kolegija Umjetna inteligencija.

“

„

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

230

(prvi je bio Fortran). Sjedinjuje svojstva strojnih jezika (potreba za poznavanjem detalja i sloboda

manipuliranja podacima i programima) i viših jezika (jednostavnost programiranja). Lisp je dostupan u

velikom broju tzv. dijalekata, tj. različitih verzija samoga sebe. Najpoznatiji dijalekti Lispa su Common

Lisp, Scheme i Emacs Lisp. Postoji puno Lisp interpretera

108

, a mi smo za primjere u tekstu ovog

udžbenika već koristili online Lisp kompajler

109

V1.1 Struktura Lispa

Lisp je programski jezik koji se temelji na listama. Svi izrazi (tj. forme) napisani u Lispu

predstavljeni su u obliku listi, a liste su omeđene zagradama. Zbog mnogobrojnih zagrada u programskom

kodu Lisp je zaradio status programskog jezika koji je složen za početnike jer se je lako „izgubiti” u svim

tim zagradama. Važno je napomenuti da Lisp koristi prefiks notaciju (ime funkcije zadaje se prije

argumenata). Na primjer, ako želimo obrađivati listu (a b c ... n), tada vrijedi sljedeće pravilo:

izraz a primjenjuje se na izraze b c ... d koji su njegovi argumenti. Na primjer, (PLUS 2 3)

primjenjuje funkciju na argumente 2 i 3. Iznimka se događa u slučaju kada ispred liste navedemo znak

', jer tada lista predstavlja podatak (npr. '(1 2 3 4) i 'string). Lisp nije osjetljiv na velika i mala

slova.

Nakon upisane naredbe u Lisp interpreter, Lisp vraća rezultat izvršavanja te naredbe ili poruku

o grešci.

Komentari u Lispu započinju znakom ;. Na primjer:

; ovo je komentar

Primjer ispisa znakovnog niza u Lispu:

(print "Pozdrav!")

Postavljanje vrijednosti varijabli u Lispu:

(setq a 6) ; a = 6

(setq b 'lubenica) ; b = "lubenica"

(setq c '(proljece ljeto jesen zima)) ; c = "proljece ljeto jesen zima"

Primijetite da se u gornjim primjerima jednostruki navodnik ' koristi za oznaku znakovnog niza.

Dakle, ako se jednostruki navodnik nalazi ispred neke riječi, ta se riječ u Lispu koristi kao znakovni niz.

Ako se jednostruki navodnik nalazi ispred zagrada, sve što se nalazi unutar tih zagrada koristi se kao

znakovni niz.

Dva osnovna tipa podataka u Lispu su atomi i liste. Atomi su objekti koji se ne sastoje od drugih

objekata i oni su za Lisp ono što su riječi u prirodnom jeziku. Oni s obje strane moraju biti ograđeni

graničnicima (delimiterima), a to su praznina , točka zarez ;, točka . i zagrade (). Atomi mogu biti simboli

ili brojevi.

Pomoću funkcije atom može se provjeriti je li neki objekt atom. Ova će funkcija vratiti T (istinito,

engl. True) ako je objekt atom, te NIL ako nije. Na primjer:

> (atom 1)

> (atom '(1 2 3 4))

NIL

> (atom 'a)

108

newLisp – http://www.newlisp.org, LispIDE – http://www.daansystems.com/lispide/, LispWorks –

http://www.lispworks.com/

109

https://rextester.com/l/common_lisp_online_compiler

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

231

Svaki atom ili lista može biti element liste. Bilo koji podskup liste također može biti lista. Atomi

i liste zovu se još i s-izrazi (simbolički izrazi).

Brojevi u Lispu mogu biti cjelobrojni ili realni brojevi. Cjelobrojni brojevi započinju s + ili -.

Realni brojevi imaju decimalnu točku i mogu biti napisani u eksponencijalnoj notaciji. Lisp podržava i

kompleksne brojeve koji se pišu u obliku #c(r i), gdje su r i i realni i imaginarni dijelovi kompleksnog

broja. Primjeri brojeva u Lispu su: 23, -54, +5, 6.1234, 1.335e-16 i \#c(1.123e-10

0.12).

Simboli u Lispu su nizovi znakova koji započinju sa slovom, a sastoje se od slova, brojeva i

povlaka (npr. i, a1, funkcija, funkcija-broj-jedan). U Lispu se funkcija za pridruživanje

vrijednosti simbolu naziva setq.

U Lispu su dostupne standardne aritmetičke funkcije: +, -, * i /, ali i floor,

ceiling, mod, sin, cos, tan, sqrt, exp, expt, itd. Sve funkcije primaju za argument

bilo koji tip broja, a vraćaju broj čiji tip ovisi o tipu argumenta. Jedino ograničenje za apsolutnu vrijednost

cijelog broja je količina memorije u računalu. Potrebno je voditi računa o tome da su kalkulacije s velikim

brojevima spore.

V1.2 Programiranje u Lispu

Lisp programi se interpretiraju. Kompajler je program koji uzima program napisan u skladu s

pravilima nekog programskog jezika i pretvara ga u skup binarnih naredbi koje računalo može obraditi.

Interpreter reagira izravno na naredbe i izvršava ih. Kada pokrenemo Lisp interpreter pojavljuje se

prompt: '>'. Lisp interpreter čeka da korisnik unese dobro formirani Lisp izraz (formu) i odmah ga

izvršava, ispisuje rezultat te se ponovo prikazuje prompt znak. Na primjer:

> (+ 1 2 1 2)

Kada interpreter pročita formu, izvršava tzv. čitaj-evaluiraj-ispiši (engl. Read-Eval-Print)

petlju ili proceduru, koja se još naziva i temeljna petlja Lisp-a. read označava čitanje naredbe,

evaluate označava izvršavanje naredbe, a print označava ispisivanje rezultata koji su se dobili nakon

izvršavanja naredbe. Ako se dogodi da neka forma uzrokuje grešku, Lisp će vas postaviti u debugger

mode. Većina debuggera odgovara na naredbu help ili :help. Za izlazak iz debugging moda dovoljno

je utipkati abort.

Lisp omogućava dohvaćanje rezultata prethodnih naredbi na sljedeći način:

* dohvaća rezultat posljednje naredbe

** dohvaća rezultat prve od posljednje dvije naredbe

*** dohvaća rezultat prve od posljednje tri naredbe

Primjeri dohvaćanja rezultata prethodnih naredbi:

> (setq a 6) ; ovo korisnik upisuje

> 6 ; ovo je rezultat gornje naredbe koju Lisp ispisuje

> * ; ovo korisnik upisuje

> 6 ; ovo Lisp ispisuje

> (setq b 4)

> 4

> (setq c 10)

> 10

> **

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

232

> 4

> ***

> 4

Linija iza ; je komentar u Lispu i interpreter će je ignorirati. Lisp nije osjetljiv na velika i mala

slova (engl. Case Sensitive).

V1.2.1 Setq

Lisp ima ugrađenu posebnu formu za pridruživanje vrijednosti simbolu koja se zove setq. Na

primjer, u C-u bi se pisalo x = 5 kada bismo željeli varijablu x postaviti na 5, a u Lispu bi se pisalo (setq

x 5). Primjeri korištenja naredbe setq u Lispu:

> (setq a 5) ; pohrana broja 5 u simbol a

> a ; dohvaćanje vrijednosti simbola

> (setq a 'hello) ; pohrana simbola

HELLO

> (setq lista1 '(1 2 3 4)) ; inicijalizacija liste

(1 2 3 4)

> b ; pokušaj korištenja nepostojećeg simbola

Error: Attempt to take the value of the unbound symbol B

V1.2.2 Cons

cons je zapis s dva polja. Polja se zovu car (engl. Contents of Address Register) i cdr (engl.

Contents of Decrement Register) iz povijesnih razloga, te odgovaraju prvom polju i ostatku (engl. first i

rest). Ova su polja shematski prikazana na slici V1-1.

Slika V1-1. Polja car i cdr

Primjeri korištenja naredbe cons u Lispu:

> (cons 4 5) ; alocira se cons polje, car se postavlja na 4 a cdr na 5

(4 . 5)

> (cons (cons 4 5) 6) ; car se sastoji od cons, koji se sastoji od car i cdr

((4 . 5) . 6)

> (car (cons 4 5)) ; dohvati car

> (cdr (cons 4 5)) ; dohvati cdr

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

233

V1.2.3 Liste

Od cons se mogu graditi razne strukture, kao na primjer liste ili stabla. Vezana lista može se

izgraditi na način da car jednog consa pokazuje na jedan element liste, a cdr pokazuje ili na drugi

element ili na nil. Takva vezana lista u Lispu je shematski prikazana na slici V1-2.

Slika V1-2. Vezana lista u Lispu

Vezane liste u Lispu mogu se kreirati na jednostavniji način pomoću funkcije list. Na primjer:

> (list 4 5 6)

(4 5 6)

Funkcija listp vraća T (istinito, engl. True) ako je argument funkcije lista, te NIL ako nije. Na

primjer:

> (setq a '(1 2 3 4 5))

(1 2 3 4 5)

> (listp a)

> (listp 'a)

NIL

Ako ispred liste nije quote (') onda se prvi element liste tretira kao ime funkcije.

Lisp ispisuje liste na poseban način (ne ispisuje neke točke i zagrade), po sljedećim pravilima:

•

ako je cdr nil ne ispisuju se točke

•

ako je cdr cons-a A cons B, ne ispisuju se točke za A ni zagrade za B.

Primjeri gore navedenih pravila:

> (cons 4 nil)

(4)

> (cons 4 (cons 5 6))

(4 5 . 6)

Car i cdr nil liste su nil. Nil označava listu bez elementa. Na primjer:

> (cons 4 (cons 5 (cons 6 nil)))

(4 5 6)

Gornja naredba je ekvivalentna naredbi (list 4 5 6).

V1.3 Zadaci

Zadatak 1.3.1. Napišite izraz u Lispu čiji će ispis odgovarati slici V1-3, te odredite što su car i

cdr te strukture.

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

234

Slika V1-3. Slika vezana uz zadatak 1

Zadatak 1.3.2. Izdvojite broj 5 iz strukture iz prvog zadatka.

Zadatak 1.3.3. Koristeći car i cdr izvucite riječ svemir iz sljedećih konstrukcija:

(svemir je pun zvijezda)

(svemir (((je) beskonacan)))

(((((svemir) je) inspirirao) brojne) poznate znanstvenike)

(mate (i ivana) vole promatrati svemir)

Zadatak 1.3.4. Koristeći cons napraviti sljedeću strukturu:

(ovo (je jedna) (struktura (sa zagradama))).

VJEŽBA 2 - NAPREDNO PROGRAMIRANJE U LISPU

V2.1 Napredan rad s listama

Funkcijom list u Lispu se kreira lista. Na primjer:

> (list a b c d)

> (list 'a 'b 'c 'd)

Lista se može ponašati i kao stog, pa se mogu koristiti funkcije push i pop. Na primjer:

> (setq a nil)

NIL

> (push 4 a)

(4)

> (push 5 a)

(5 4)

> (pop a)

> a

(4)

> (pop a)

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

235

> (pop a)

NIL

> a

NIL

Primjeri funkcije atom:

> (setq a '(l i s t a))

(L I S T A)

> (atom a)

NIL

> (atom 'l)

Primjeri funkcije listp:

> (listp a)

> (listp 'a)

NIL

Primjeri funkcije length:

> (length a)

> (length 'a)

*** - LENGTH: A is not a sequence

Primjeri funkcije append:

> (append a a)

(L I S T A L I S T A)

> (length (append a a))

> (length '(append a a))

Primjeri:

> (cons 'a '(b c d))

(a b c d)

> (list 2 3 4)

(2 3 4)

> (cons 1 *)

(1 2 3 4)

> (list 'a '(a s d f))

(a (a s d f))

> (setq a *)

(A (A S D F))

> (cons 'a a)

(A A (A S D F))

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

236

V2.2 Booleovi izrazi

Lisp koristi simbol nil za označavanje neistine. Sve drugo osim nil znači istinu, osim ako imamo

poseban razlog za korištenje simbola T za označavanje istine.

Korisno:

•

nil - prazna lista ili logička neistina

•

T - eksplicitna oznaka logičke istine

•

null - funkcija koja provjerava je li argument nil

•

not - negacija, ako je argument nil vraća T, u protivnom vraća nil.

Primjeri:

> (null nil)

> (not nil)

> (null ())

> (not ())

> (null '(a s))

NIL

> (not '(a s))

NIL

Lisp ima standardne logičke funkcije (and, or i not). and i or djeluju kao kratki spoj. and

izvršava sve argumente dok se ne pojavi jedan koji se izvršava u nil, a or izvršava sve argumente dok

se ne pojavi jedan koji se izvršava u T.

Primjer:

> (and 1 2 3 4)

> (and 1 (cons 'a '(b)) (rest '(a)) (setf y 'hello))

NIL

> (or nil nil 2 (setf y 'goodbye))

> (or (rest '(a)) (equal 3 4))

NIL

V2.3 Uvjetni izrazi

Lisp ima ugrađene predikate <, >, <= i >=. Brojčana jednakost označava se s =. Funkcija

equal daje istinu za dvije cons strukture ako i samo ako su njihovi car dijelovi jednaki i njihovi cdr

dijelovi jednaki. Daje istinu za dvije strukture ako i samo ako su one istog tipa i ako su njihova

odgovarajuća polja jednaka.

Pravila:

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

237

•

(= x y) - istina ako su x i y numerički jednaki

•

(equal x y) - istina ako su ispisi vrijednosti x i y varijabli jednaki, tj. imaju jednaku

vrijednost i strukturalno su jednaki

•

(eq x y) - istina ako su x i y isti objekt u memoriji

•

(eql x y) - koristi se kao eq ako su x i y simboli, ili kao = ako su x i y brojevi.

Općenito, funkcije = i equal se koriste češće nego eq i eql.

Primjeri:

> (setq a '(1 2 3))

(1 2 3)

> (eq a '(1 2 3))

NIL

> (setq b a)

(1 2 3)

> (eq a b)

> (= 3 3.0)

> (= 3/1 6/2)

> (eq 3 3.0)

NIL

> (eq 3 6/2)

> (eq 3.0 6/2)

NIL

> (eql 3.0 3/1)

NIL

> (eql 3 6/2)

> (equal 3 3)

> (equal 3 3.0)

Lisp ima nekoliko posebnih formi za uvjetno izvršavanje. Najjednostavnija je if forma. Prvi

argument uzrokuje hoće li se izvršiti drugi ili treći argument. If forma ima sljedeći oblik:

(if (uvjet) (then dio) (else dio))

Primjeri:

> (if t 5 6)

> (if nil 5 6)

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

238

> (if 4 5 6)

> (setq a 7)

> (setq b 0)

> (setq c 5)

> (if (> a 5)(progn (setq a (+ b 7)) (setq b (+ c 8))) (setq b 4) )

Ako je potrebno staviti više od jednog izraza u then ili else dio može se koristiti progn posebna

forma. Progn izvršava svaku naredbu u svom tijelu i vraća vrijednost posljednje.

If naredba kojoj nedostaje ili then ili else dio može se napisati koristeći when ili unless

posebne forme, koje imaju sljedeće oblike:

(when (uvjet) (then dio))

(unless (uvjet) (else dio))

Primjeri:

> (when t 3)

> (when nil 3)

NIL

> (unless t 3)

NIL

> (unless nil 3)

Za razliku od if naredbe when i unless naredbe dopuštaju veći broj naredbi u svom tijelu. Na

primjer, (when x a b c) je identičan s (if x (progn a b c)).

Za složenije uvjetne izraze koristimo cond posebnu formu koje je ekvivalentna s if ... else

if ... else konstrukcijom. Sintaksa: nakon ključne riječi cond piše se niz cond izraza. Cond izraz

je lista koje se sastoji od uvjeta na prvom mjestu i liste akcija koja se izvršavaju ako je uvjet istinit.

Izvršavaju se samo akcije iz prvog cond izraza koji se razvije u istinu, sve ostale se preskaču.

(cond(uvjet1 akcije...)(uvjet2 akcije2 ...)...(t else-dio ...) )

Primjeri:

> (setq a 3)

> (cond

((evenp a) a) ; ako je a paran - vratiti a

((> a 7) (/ a 2)) ; ako je a neparan i veći od 7 - vratiti $\frac{a}{2}$

((< a 5) (- a 1)) ; ako je a manji od 5 - vratiti $a-1$

(t 17) ; ništa od ponuđenog - vratiti 17

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

239

)

Ako u cond izrazu nedostaje akcija, cond vraća ono u što se razvije uvjet. Na primjer:

> (cond ((+ 3 4)))

Case naredba u Lispu je kao switch naredba u C-u, te ima sljedeći oblik:

(case simbol((lista vrijednosti1) akcija 1)((lista vrijednost2) akcija

2) ... (otherwise default akcija) )

Primjer:

> (setq x 'b)

> (case x

(a 5)

((d e) 7)

((b f) 3)

(otherwise 9)

)

otherwise izraz na kraju znači da x nije neka od ponuđenih vrijednosti.

V2.4 Funkcije

Kod definiranja funkcija u Lispu vrijedi sljedeće pravilo:

(DEFUN ime funkcije(lista argumenata)(implementacija funkcije))

Primjer definiranja funkcije:

> (defun bar(x) (setq x (* x 3)) (setq x (/ x 2)) (+ x 4) )

BAR

> (bar 6)

Ako funkcija ima više izraza unutar sebe, onda će vratiti rezultat posljednjeg izraza.

Primjeri funkcija:

> (+ 3 4 5 6) ;ova funkcija uzima bilo koji broj argumenata

> (+ (+ 3 4) (+ (+ 4 5) 6))

> (defun foo(x y)(+ x y 5)) ; definiranje funkcije

FOO

> (foo 5 0) ; poziv funkcije

Kada pozivamo funkciju moramo joj dati onoliko argumenata koliko smo specificirali prilikom

definicije funkcije. Na primjer:

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

240

> (defun moj-zbroj (x y) (+ x y))

MOJ-ZBROJ

> (moj-zbroj 2 3)

> (moj-zbroj 2)

error: too few arguments

U Lispu je moguće specificirati i neobavezne argumente funkcije. Svaki argument nakon simbola

&optional je neobavezan. Neobaveznim argumentima mogu se pridijeliti predefinirane vrijednosti

(engl. Default). Primjeri:

> (defun bar (x &optional y) (if y x 0))

BAR

> (defun baaz (&optional (x 3) (z 10)) (+ x z))

BAAZ

> (bar 5)

> (bar 5 t)

> (baaz 5)

> (baaz 5 6)

> (baaz)

Funkcija može primati neodređeni broj argumenata. Ako listu argumenata završimo s

parametrom &rest, Lisp će pokupiti sve argumente koji nisu već vezani u listu i vezati parametar

&rest za listu.

Primjeri:

> (defun foo (x &rest y) y)

FOO

> (foo 3)

NIL

> (foo 4 5 6)

(5 6)

Kada se poziva funkcija argumenti se mogu davati bilo kojim redom jer su označeni ključnom riječi &key.

Primjeri:

> (defun foo (&key x y) (cons x y))

FOO

> (foo:x 5:y 3)

(5 . 3)

> (foo:y 3:x 5)

(5 . 3)

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

241

> (foo:y 3)

(NIL . 3)

> (foo)

(NIL)

Parametar &key može imati default vrijednost:

> (defun foo (&key (x 5)) x)

FOO

> (foo:x 7)

> (foo)

V2.5 Lokalne i globalne varijable

Primjeri:

> (defun y-plus (x) (+ x y))

Y-PLUS

> (setq y 2)

> (y-plus 4)

> (setq x 5)

> (y-plus 23)

> x

> (setq y 27)

> (y-plus 43)

V2.6 Naredbe ponavljanja (iteracije)

Najjednostavnija naredba ponavljanja u Lispu je loop. Loop izraz izvršava se iznova i iznova

dok ne naiđe na posebnu formu return. Loop mora doći u kombinaciji s return inače će se razviti u

beskonačnu petlju. Forma return vraća vrijednost izraza unutar return forme ili nil, te ima sljedeći

oblik: (return izraz).

Primjer 1:

> (setq a 4)

> (loop (setq a (+ a 1)) (when (> a 7) (return a)) )

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

242

Primjer 2:

> (loop (setq a (- a 1)) (when (< a 3) (return)) )

NIL

Forma dolist redom veže varijablu za elemente liste i završava izvršavanje kada dođe do kraja

liste. Ima sljedeći oblik:

(dolist (simbol lista) akcije koje se izvršavaju za svaki član liste)

Primjer:

> (dolist (x '(a b c)) (print x))

NIL

Forma dolist uvijek vraća nil. U gornjem primjeru X nikada nije bio nil, no nil je ipak

vrijednost koju je gornji izraz vratio nakon izvršavanja.

Forma do je najsloženija naredba ponavljanja. Do izraz izgleda ovako:

(do (

( varijabla1 poč-vrij-var1 (izraz-za-promjenu-var1) )

( varijabla2 poč-vrij-var2 (izraz-za-promjenu-var2) )

...)

((uvjet-prekida petlje) (povratna-vrijednost))

...

Tijelo-petlje

... )

Prvi dio do forme specificira koje varijable vezati, njihove početne uvjete, te kako ih mijenjati.

Drugi dio do forme specificira uvjet prekida i konačnu vrijednost. Posljednji dio do forme je tijelo izraza.

Do forma veže varijable na početne vrijednosti, kao i forma let, te tada provjerava uvjet prekida. Kad

se uvjet prekida razvija se u nil, te se iznova izvršava tijelo, a kada uvjet postane istina, vraća se

vrijednost forme povratne vrijednosti.

Primjer:

> (do ((x 1 (+ x 1)) (y 1 (* y 2))) ((> x 5) y) (print y) (print 'working) )

WORKING

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

243

V2.7 Rekurzivna funkcija

Primjer 1:

> (defun factorial (n) (if (<= n 1) 1 (* n (factorial (- n 1)))) )

FACTORIAL

> (factorial 5)

120

> (defun a (x) (if (= x 0) t (b (- x)))) ; mutually recursive functions

> (defun b (x) (if (> x 0) (a (- x 1)) (a (+ x 1))))

> (a 5)

Primjer 2:

> (defun listanaopako (l1) (setq a nil) (dolist (x l1) (if (atom x) (push x a) (push

(listanaopako x) a) ) ) a)

(trace listanaopako)

(listanaopako '( 1 2 3 (3 4) 5 ))

1. Trace: (LISTANAOPAKO '(1 2 3 (3 4) 5))

2. Trace: (LISTANAOPAKO '(3 4))

2. Trace: LISTANAOPAKO $\implies$ (4 3)

1. Trace: LISTANAOPAKO $\implies$ (5 (4 3) 4 3)

(5 (4 3) 4 3) ...

V2.8 Ispis

Neke funkcije zahtijevaju izlaz, a za to je najjednostavnije korištenje forme print koja ispisuje

argument i vraća argument.

> (print 3)

U gornjem primjeru prvi 3 je ispisan, a drugi je vraćen.

Za složenije ispise koristi se forma format:

> (format t "An atom: ~S~\%and a list: ~S~\%and an integer: ~D~\%" nil (list 5) 6)

An atom: NIL

and a list: (5)

and an integer: 6

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

244

V2.9 Zadaci

Zadatak 2.9.1. Definirati funkciju koja računa hipotenuzu pravokutnog trokuta.

Zadatak 2.9.2. Napisati funkciju koja koristeći car i cdr vraća četvrti element liste.

Zadatak 2.9.3. Definirati funkciju koja prima 1, 2 ili više argumenata:

ako ima 1 argument vraća taj argument pomnožen s 1,

ako ima 2 argumenta vraća umnožak ta 2 broja,

ako ima više argumenata vraća listu kojoj je na prvom mjestu umnožak prva 2 argumenta a ostatak

liste su preostali argumenti.

Zadatak 2.9.4. Definirati funkciju koja prima 1 ili više argumenata:

ako ima 1 argument vraća taj argument,

ako ima više argumenata vraća listu kojoj je na prvom mjestu umnožak prva 2 argumenta a ostatak

liste su preostali argumenti.

Zadatak 2.9.5. Napisati funkciju koja koristeći do petlju vraća listu prvih 15 kubnih vrijednosti

(1 8 27 64 ... 3375).

Zadatak 2.9.6. Napisati funkciju moj-kalkulator koja prima dva broja i opcionalno operaciju (*

/ \%). Funkcija vraća rezultat izvršavanja operacije na dva broja. Ako korisnik ne navede

operaciju koristi se zbrajanje.

Primjeri izvršavanja funkcije:

> (moj-kalkulator 2 3 '*)

> (moj-kalkulator 2 3)

> (moj-kalkulator 10 50 \%) ; 10 posto od 50

Zadatak 2.9.7. Definirati funkciju add12 koja svakom članu liste dodaje broj 12.

Primjer izvršavanja funkcije:

> (add12 '(1 2 3 4))

(13 14 15 16)

Zadatak 2.9.8. Napisati rekurzivnu funkciju postoji koja vraća T ako se dati atom pojavljuje

bilo gdje u nekom izrazu, a NIL inače.

Primjer provjere postoji li varijabla x u nekom izrazu:

> (postoji 'x '(sqrt (/ (+ (exp x 2) (exp y 2)) 2)))

VJEŽBA 3 - PROLOG

Predikatna logika je matematički formalni jezik koji koristimo za predstavljanje znanja, te

predstavlja logički sustav u kojemu se mogu izraziti i matematički izrazi i rečenice iz prirodnog jezika.

Predikatna logika sadrži i pravila zaključivanja pomoću kojih se izvode nove rečenice iz skupa postojećih.

Korištenje formalnog jezika je bitno zbog njegove nedvosmislenosti i zbog lakšeg zapisivanja pravila.

Prolog je programski jezik kojim je moguće opisati i riješiti određen problem na način opisan predikatnom

logikom.

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

245

Programski jezik Prolog

110

(fran. PROgrammation en LOGique, engl. PROgramming in LOGic)

osmislio je Alain Colmerauer (1941.-2017.) 1973. g. Programi napisani u Prologu sastoje se od liste

činjenica i pravila (tj. od baze znanja), te od upita vezanih uz te informacije. Zbog ovih činjenica Prolog se

najčešće koristi za izgradnju stručnih (ekspertnih) sustava.

Pisanje Prolog programa ssastoji se od:

•

deklariranja tvrdnji (činjenica) o objektima i njihovim međusobnim odnosima

•

deklariranja pravila o objektima i njihovim međusobnim odnosima i

•

postavljanja upita tj. ciljeva o objektima i njihovim međusobnim odnosima.

Prolog program je lista činjenica i pravila, i to je sve što program sadrži. Zatim postavljamo upite.

Prolog sadrži stroj za zaključivanje (engl. Inference Engine) koji je procedura koja prolazi kroz listu

pravila i činjenica i pokušava odgovoriti na upit koristeći dedukcijsku logiku.

Za vježbanje Prologa najbolje je koristiti on – line verziju SWI-Prologa (https://swish.swi-

prolog.org/) koji ima izvrsnu podršku. S njim smo se već susretali u primjerima koje smo u okviru ovog

udžbenika davali u Prologu.

Programi u Prologu mogu se pisati u Python shell-u (koji započinje znakovima ?-) ili u datotekama

s ekstenzijom .pl. Ako se programi pišu u datoteci s ekstenzijom .pl, onda se ta datoteka u Python shell

učitava sa consult(imeDatoteke) ili [imeDatoteke].

Prolog podržava dva načina unosa komentara. U prvome načinu komentari započinju znakom %,

a u drugom načinu komentari su omeđeni znakovima /* i */ (tj. jednaki su komentarima u programskom

jeziku C). Drugi način zapisa komentara koristi se u slučajevima kada je potrebno brzo komentirati više

linija koda.

Primjeri komentara u Prologu:

% ovo je prvi komentar

/* ovo je drugi komentar */

/* ovo je početak trećeg komentara

* ovo je sredina trećeg komentara

* ovo je kraj trećeg komentara */

Primjer ispisa znakovnog niza u Prologu:

writeln(‘Pozdrav!’).

V3.1 Predikati

Predikati se koriste za opisivanje pravila, činjenica i upita. Primjeri:

Cold.

likes(dora,dancing).

difficult(physics).

5 < 12.

Svi predikati imaju sljedeći oblik:

functor(arg1, arg2, arg3, ...).

gdje je:

110

Prolog – Computer Language. URL: https://www.britannica.com/technology/PROLOG

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

246

•

functor - ime predikata koje sami zadajemo - može biti relacija ili predikat,

•

argX - argumenti mogu biti:

o konstante - brojevi ili atomi (obično započinju malim slovom, za razliku od varijabli)

o varijable - započinju velikim slovom

o strukture

o liste - posebni oblik strukture.

Napomena: između functora i lijeve zagrade ne smije doći razmak.

Sami pridajemo značenje predikatu i moramo ga koristiti konzistentno - uvijek s istim brojem i

značenjem argumenata. Na primjer:

likes(nina,jabuke)

Gornji primjer znači da Nina voli jabuke. Functor 'like' ima 2 argumenta od kojih je prvi volitelj

a drugi voljenik. Da bismo održali jednoznačnost pomažu nam komentari. Trebali bismo datoteci koja

sadrži pravila dodati:

/* likes(liker,likee). */

Ako neku činjenicu baza podataka ne sadrži automatski se smatra neistinom. Postoji i eksplicitan

način za izražavanje neistine:

likes(nina,jabuke):- fail,!.

Predikati se koriste za izražavanje nekoliko općih jezičnih smislenosti:

•

odnos između dvaju entiteta - prijedlog, imenica ili glagol

•

opis entiteta - pridjev, često ima samo jedan argument

•

označavanje radnje - glagol

•

predikati bez argumenta koriste se za označavanje općenitog stanja „svijeta”.

Primjeri:

/* odnos između dva entiteta */

boss(ivana,matea). /* Ivana je šefica Matei. */

on(olovka,stol). /* Olovka je na stolu. */

rules(elizabeth,engleska). /* Elizabeth vlada Engleskom. */

/* opis entiteta */

alkoholan(viski). /* Viski po sastavu sadrži alkohol. */

tezak(ui). /* Umjetna inteligencija je težak kolegij. */

/* označavanje radnje */

eat(dječak,sladoled). /* Dječak jede sladoled. */

/* predikati bez argumenta */

game\_running. /* Igra traje, nije zaustavljena. */

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

247

V3.2 Rad sa Prologom

Nakon pokretanja Prologa pojavi se:

Učitavanje baze:

?- consult(prvi) /* 1. način */

?- [prvi] /* 2. način */

Ispis svih činjenica iz učitane baze:

?- listing

Izlazak iz programa:

?- halt

V3.2.1 Upiti

Upiti se u Prologu koriste za pretraživanje baze znanja. Činjenica koja nam je nepoznata i na koju

želimo saznati odgovor u Prologu se označava sa velikim slovom. Činjenicu koja nam je nevažna

označavamo znakom _.

Primjer baze znanja:

roditelj(marko, šime). % Marko je roditelj Šime.

roditelj(ana, petra). % Ana je roditelj Petre.

sestra(marija, anđela). % Marija je sestra Anđele.

brat(stipe, matija). % Stipe je brat Matije.

brat(stipe, dominik). % Stipe je brat Dominika.

roditelji(branimir, mia, ivana). % Branimir i Mia su roditelji Ivane.

roditelji(domagoj, mia, mirta). % Domagoj i Mia su roditelji Mirte.

Primjeri upita:

?- roditelj(X, šime). % X označava činjenicu koju želimo saznati.

X = marko % Odgovor koji dobijemo u Prologu.

?- brat(stipe,X).

X = matija

X = dominik

?- roditelj(X, petra).

X = ana

?- roditelji(X,Y,ivana).

X = branimir,

Y = mia

?- roditelji(_, mia, X). % Tražimo djecu Mije bez obzira na oca.

X = ivana

X = mirta

?- brat(stipe, matija). % Pitamo Prolog je li ova činjenica istinita.

true % Prolog odgovara pozitivno.

?- brat(stipe, luka). % Ova činjenica ne postoji u bazi znanja.

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

248

false % Prolog odgovara negativno.

V3.2.2 Pravila – relacije između predikata

Pravila izražavaju povezanost predikata. Na primjer:

like(X,Y):- love(X,Y).

Gornji primjer znači da ako nešto volimo onda nam se to sviđa. Odnosno:

if love(X,Y) then like (X,Y).

Oznaka ':-' znači 'if', ali imamo obrnutu notaciju.

Ponekad nam je potrebno više uvjeta. Ako uvjete razdvojimo s ',' zarez se ponaša kao logičko 'i'.

Na primjer:

zaključak:- uvjet1,uvjet2,uvjet3.

U gornjem primjeru Zaključak je istinit ako su istiniti uvjeti uvjet1, uvjet2 i uvjet3.

Primjer:

can_enter(X):- high_school_grad(X),gpa >=2.0,has_money(X).

Zaključak i uvjet su predikati. Uvjeta može biti 0 ili više.

Logičko 'ili' se formira na način da više pravila ima iste posljedice. Na primjer:

roditelj(X,Y):-otac(X,Y).

roditelj(X,Y):-majka(X,Y).

Također možemo definirati i iznimke:

ptica(X):- leti(X), ima(X,perje).

Ali postoje ptice (pingvin i noj) koje ne lete, pa moramo uključiti i iznimke:

ptica(pingvin).

ptica(noj).

Pravila u Prologu dopuštaju i rekurziju. Dopušteno je imati isti predikat s lijeve i desne strane

implikacije. Na primjer:

predak(X,Y):- roditelj(X,Z), predak(Z,Y).

Gornji primjer kaže da ako je Y predak od Z i ako je Z roditelj od X, onda je Y predak od X. Pogledajmo

sada jedan jednostavni primjer definiranja pravila i zaključivanja s njima:

otac(marko, julija). % Marko je otac Julije.

majka(viktorija, julija). % Viktorija je majka Julije.

roditelj(X,Y):- otac(X,Y). % Ako je X otac od Y, onda je X roditelj od Y.

roditelj(X,Y):- majka(X,Y). % Ako je X majka od Y, onda je X roditelj od Y.

?- roditelj(X,julija). % Primjer upita.

X = marko % Prologov odgovor.

X = viktorija % Prologov odgovor.

djed(filip,marija). % Filip je djed Marije.

baka(lucija,marija). % Lucija je baka Marije.

majka(marijeta,marija). % Marijeta je majka Marije.

otac(luka, marija). % Luka je otac Marije.

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

249

predak(X,Y):- djed(X,Y). % Ako je X djed od Y, onda je X predak od Y.

predak(X,Y):- baka(X,Y). % Ako je X baka od Y, onda je X predak od Y.

predak(X,Y):- majka(X,Y). % Ako je X majka od Y, onda je X predak od Y.

predak(X,Y):- otac(X,Y). % Ako je X otac od Y, onda je X predak od Y.

?- predak(X,marija). % Primjer upita.

X = filip % Prologov odgovor.

X = lucija % Prologov odgovor.

X = marijeta % Prologov odgovor.

X = luka % Prologov odgovor.

djed(ivan, mia).

baka(jelena, mia).

% Ako je Y baka od X, i ako je Z djed od X, onda je X unuka od Y i Z.

unuka(X, Y, Z):- baka(Y, X), djed(Z, X).

?- unuka(mia, jelena, ivan). % Je li Mija unuka Jelene i Ivana?

true % Prolog odgovara pozitivno.

?- unuka(mia, X, Y). % Tko su baka i djed Mije?

X = jelena,

Y = ivan

V3.3 Logičke operacije u Prologu

Pravila u Prologu su implementacija logičkog operatora implikacije:

\begin{equation}

A \implies B \iff (\neg A) \lor B

\end{equation}

U tablici V-1 dana je tablica istine za logičke operacije, među kojima i za implikaciju.

Tablica V-1. Tablica istine za logičke operacije

ILI

IMPLIKACIJA

NEGACIJA

Primjeri implikacije:

• Ako konji imaju krila tada slonovi lete.

• Ako pada kiša vrata fakulteta su otvorena.

• Ako je 3 paran broj tada je 3 djeljiv s 2.

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

250

• Ako smo živi tada dišemo.

Pravila u Prologu su implicitno univerzalno kvantificirana. Sve varijable koje se pojavljuju u

drugim predikatima osim u predikatu lijeve strane su egzistencijalno kvantificirane. Na primjer:

ptica(X):-imaperje(X).

Gornji primjer kaže da za svaki X, ako je istina da X ima perje, onda je istina da je X ptica. Sve

što ima perje mora biti ptica. Nadalje, lijeva strana gornjeg primjera označava se s LHS (engl. Left Hand

Side), a desna s RHS (engl. Right Hand Side).

Pravila u Prologu moraju biti općenita (moraju uvijek vrijediti) te zbog toga varijable moraju biti

univerzalno kvantificirane.

Poredak implikacije je RHS → LHS, što znači da desna strana implicira lijevu stranu. To ne znači

da vrijedi i obrnuto, tj. ne vrijedi LHS → RHS. Na primjer, '(pada kiša) → (ne sja sunce)' je uglavnom

istinito, ali '(ne sija sunce) → (pada kiša)' nije.

U Prologu postoje i pravila koja imaju više izraza na RHS, npr. 'Moji prijatelji su tvoji prijatelji',

tj. ako smo ja i ti prijatelji svi tvoji prijatelji su i moji prijatelji. U Prologu bi ovo zapisali kao:

prijatelj(ja,netko):- prijatelj(ja,ti), prijatelj(ti,netko).

U gornjem primjeru varijable 'ja' i 'netko' su univerzalno kvantificirane. To znači da za

sve 'ja' i za sve 'netko' vrijedi sljedeće: ako smo 'ja' i 'ti' prijatelji i 'ti' i 'netko' ste

prijatelji onda smo 'ja' i 'netko' prijatelji. Varijabla 'ti' je egzistencijalno kvantificirana što

znači sljedeće: ako postoji 'ti' koji je prijatelj od 'ja', a ako je 'ti' prijatelj s nekim 'netko', tada

su 'ja' i 'netko' također prijatelji. Ovo pravilo vrijedi bez obzira tko je 'ja' i tko je 'netko', dok

god postoji neki 'ti' na koji se ovo može primijeniti.

V3.4 Trace mehanizam

Prolog ima ugrađen mehanizam praćenja pretraživanja baze koji se pokreće na sljedeći način:

?-trace

Postavljanjem upita ispisuju se svi koraci prilikom pretraživanja baze. Trace mehanizam se

zaustavlja na sljedeći način:

?-notrace

V3.5 Primjer složenijeg zaključivanja u Prologu

Pogledajmo jedan složeniji primjer zaključivanja u Prologu. Radi se o Einsteinovoj zagonetki

(engl. Einstein' Riddle) koju smo već spominjali u poglavlju 3. Legenda kaže da ju je osmislio Albert

Einstein (1879.-1955.) kao dijete, ali to nikada nije dokazano. Varijacijua ove zagonetke poznata kao

zebra zagonetka (engl. Zebra Puzzle) pripisuje se Lewisu Carrollu (1832.-1898.), engleskom piscu i

matematičaru, autoru „Alise u zemlji čudesa”, ali ni to nije potpuno potvrđeno. Ovdje ćemo prikazati malo

izmijenjenu varijantu zagonetke koju smo prilagodili današnjem vremenu u kojem je velik broj nepušača.

Evo zagonetke:

Postoji pet kuća različitih boja u redu. U svakoj živi jedna osoba drugačije nacionalnosti. Pet

vlasnika ovih kuća pije posebno piće, jede posebno voće i ima ljubimca. Ni jedan od njih ne jede isto voće,

pije isto piće i ima istog ljubimca. Poznate činjenice su:

1. Britanac živi u crvenoj kući.

2. Šveđanin ima psa za ljubimca.

3. Danac pije čaj.

4. Zelena kuća nalazi se s lijeve strane bijele kuće.

5. Vlasnik zelene kuće pije kavu.

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

251

6. Vlasnik koji jede jabuke ima ptice za ljubimce.

7. Stanovnik žute kuće jede kruške.

8. Osoba koja živi u kući u sredini pije mlijeko.

9. Norvežanin živi u prvoj kući.

10. Vlasnik koji jede šljive živi pokraj kuće čiji vlasnik ima mačku.

11. Osoba koja ima konja živi pokraj osobe koja jede kruške.

12. Osoba koja jede lubenice pije pivo.

13. Nijemac jede trešnje.

14. Norvežanin živi pokraj plave kuće.

15. Osoba koja jede šljive živi pokraj čovjeka koji pije vodu.

Pitanje je: Tko ima ribicu za ljubimca?

Neke od ovih tvrdnji su jednostavne izjave, a neke su malo složenije. Postoji puno načina za

rješavanje zagonetke

111

. Ovdje ćemo prikazati jednu varijantu rješenja u Prologu

112

koja je možda najbliže

standardnim notacijama predikatne logike.

% Einsteinova zagonetka

% definiranje procedura

postoji(A, list(A, _, _, _, _)).

postoji(A, list(_, A, _, _, _)).

postoji(A, list(_, _, A, _, _)).

postoji(A, list(_, _, _, A, _)).

postoji(A, list(_, _, _, _, A)).

desnoOd(R, L, list(L, R, _, _, _)).

desnoOd(R, L, list(_, L, R, _, _)).

desnoOd(R, L, list(_, _, L, R, _)).

desnoOd(R, L, list(_, _, _, L, R)).

sredina(A, list(_, _, A, _, _)).

prva(A, list(A, _, _, _, _)).

nextTo(A, B, list(B, A, _, _, _)).

nextTo(A, B, list(_, B, A, _, _)).

nextTo(A, B, list(_, _, B, A, _)).

nextTo(A, B, list(_, _, _, B, A)).

nextTo(A, B, list(A, B, _, _, _)).

nextTo(A, B, list(_, A, B, _, _)).

nextTo(A, B, list(_, _, A, B, _)).

nextTo(A, B, list(_, _, _, A, B)).

111

https://rosettacode.org/wiki/Zebra_puzzle

112

Prolog verzija je inspirana rješenjem s https://curiosity-driven.org/prolog-interpreter .

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

252

% kodiranje tvrdnji

zagonetka(Kuce):-

postoji(kuca(crvena, britanac, _, _, _), Kuce),

postoji(kuca(_, svedjanin, _, _, pas), Kuce),

postoji(kuca(zelena, _, kava, _, _), Kuce),

postoji(kuca(_, danac, caj, _, _), Kuce),

desnoOd(kuca(bijela, _, _, _, _), kuca(zelena, _, _, _, _), Kuce),

postoji(kuca(_, _, _, jabuka, ptica), Kuce),

postoji(kuca(zuta, _, _, kruska, _), Kuce),

sredina(kuca(_, _, mlijeko, _, _), Kuce),

prva(kuca(_, norvezanin, _, _, _), Kuce),

nextTo(kuca(_, _, _, sljiva, _), kuca(_, _, _, _, macka), Kuce),

nextTo(kuca(_, _, _, kruska, _),kuca(_, _, _, _, konj), Kuce),

postoji(kuca(_, _, pivo, lubenica, _), Kuce),

postoji(kuca(_, nijemac, _, tresnja, _), Kuce),

nextTo(kuca(_, norvezanin, _, _, _), kuca(plava, _, _, _, _), Kuce),

nextTo(kuca(_, _, _, sljiva, _), kuca(_, _, voda, _, _), Kuce),

postoji(kuca(_, _, _, _, ribica), Kuce).

rjesenje(VlasnikRibice):-

zagonetka(Kuce),

postoji(kuca(_, VlasnikRibice, _, _, ribica), Kuce).

Na primjer prvu tvrdnju „Britanac živi u crvenoj kući.” smo definirali izrazom:

postoji(kuca(crvena, britanac, _, _, _), Kuce)

gdje je postoji(.,.) unaprijed definirana procedura, a kuca(_, _, _, _, _) predikat kojim

povezujemo boju, vlasnika, piće, voće i ljubimca.

Postavimo li upit:

? – rjesenje(VlasnikRibice)

dobit ćemo odgovor

VlasnikRibice = nijemac

Cijelu listu tko u kakvoj kući živi daje:

? – zagonetka(Kuce)

a odgovor glasi:

list(kuca(zuta, norvezanin, voda, kruska, macka), kuca(plava, danac, caj,

sljiva, konj), kuca(crvena, britanac, mlijeko, jabuka, ptica),

kuca(zelena, nijemac, kava, tresnja, ribica), kuca(bijela, svedjanin,

pivo, lubenica, pas))

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

253

V3.6 Zadaci

Zadatak 3.6.1. Koristeći predikat spojen prikazati graf dan na slici V3-1, te postaviti upit kojim

će se ispisati s kojim je sve čvorovima povezan čvor e.

Slika V3-1. Graf vezan uz zadatak 1

Primjer označavanja povezanosti čvora a s čvorom b (ali ne i čvora b s čvorom a): spojen(a,b).

Zadatak 3.6.2. Napisati pravilo za predikat povezan kojim kažemo da nam nije bitan smjer u

kojemu su povezani čvorovi grafa na slici V3-1: a je spojen s b ako je b spojen s a. Postaviti upit

kojim će se ispisati s kojim je sve čvorovima povezan čvor e.

Zadatak 3.6.3. Definirati predikat putanja kojim pronalazimo putanje od jednog čvora do drugog.

Definirati rekurzivno pravilo kojim kažemo:

postoji putanja od čvora do samog sebe,

postoji putanja od čvora do čvora s kojim je spojem,

postoji putanja od čvora a do čvora c ako je a spojen sa čvorom b od kojega postoji putanja do c.

Slika V3-2. Graf vezan uz zadatak 3

Zadatak 3.6.4. Napisati bazu za obiteljsko stablo prikazano na Slici V3-4 koristeći predikate

majka i otac. Napisati pravila za predikate roditelj i baka.

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

254

Slika V3-4. Obiteljsko stablo vezano uz zadatak 4

VJEŽBA 4 - UVOD U PYTHON

Python je interpretirani programski jezik koji je kreirao 1991. g. nizozemski programer Guido

van Rossum (Google, Dropbox). Ime je dobio po seriji „Monthy Python’s Flying Circus”. Sintaksa mu je

slična C-u, što znači da je jednostavan za korištenje i može ga se lako naučiti

113

. Python je danas jako

popularan među programerima koji se bave umjetnom inteligencijom jer je jako jednostavan i jer za njega

postoji mnoštvo biblioteka vezanih za umjetnu inteligenciju.

Programi napisani u Pythonu imaju ekstenziju .py, a pokreću se s python ime_programa.py ili

python3 ime_programa.py, ovisno o instaliranoj verziji Pythona. Python ima mnoštvo raznih

biblioteka, a one koje se najčešće koriste u strojnom učenju su:

•

NumPy - za znanstvene proračune

•

SciPy - za znanstvene proračune

•

Scikit-learn - za strojno učenje

•

Pandas - za obradu podataka

•

OpenCV – za digitalnu obradu i analizu slike

•

Pygame – za izradu računalnih igara.

Python podržava dva načina unosa komentara. U prvome načinu komentari započinju znakom #,

a u drugom načinu komentari su omeđeni znakovima '' i "" koji se koristi u slučajevima kada je potrebno

brzo komentirati više linija koda.

Primjeri komentara u Pythonu:

# ovo je komentar

"" ovo je komentar koji se

proteže u dvije linije ""

113

Dobra škola za on-line učenje Pythona je: https://www.w3schools.com/python/python_intro.asp

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

255

Primjer ispisa znakovnog niza u Pythonu:

print ("Pozdrav!") # Python podržava dvostruke navodnike.

print ('Pozdrav!') # Python podržava jednostruke navodnike.

Za razliku od većine programskih jezika, Python ne sadrži vitičaste zagrade za označavanje

pripadnosti dijela koda nekom uvjetu, petlji ili funkciji. Umjesto vitičastih zagrada u Pythonu se koristi

tzv. uvlačenje linija (tabovi). Sve linije koda koje su uvučene ispod određenog uvjeta, petlje ili funkcije

pripadaju tom uvjetu, petlji ili funkciji.

Primjer petlje koja ispisuje brojeve od 0 do 9:

for (i in range (0, 10)):

print (i)

Važno je imati na umu da Python razlikuje razmake (engl. Space) i tabove, te je u programskom

kodu potrebno konzistentno koristiti tabove za uvlačenje linija koda, ili pak konzistentno razmake. Često

se dogodi da početnici u Pythonu malo koriste tabove a malo razmake u istome programu, a to naposljetku

rezultira greškom. Važno je zapamtiti da jedan tab ili određeni broj razmaka koji ukupno

odgovaraju veličini tog taba u Pythonu nije jednako!

U Pythonu se ne označavaju tipovi varijabli, već Python na temelju vrijednosti koja se dodijeli

varijabli sam zaključi kojem tipu podataka ona pripada (npr. je li to int, float, string, itd.). Na primjer:

a = 10.0

b = 2

c = a / b

print("Vrijednost varijable c je " + str(c)) # c = 5.0

U gornjem primjeru možemo vidjeti da je Python sam zaključio da je varijabla c realni broj, a ne

cijeli. Nadalje, možemo vidjeti i da se unutar funkcije print za ispis brojeva koristi funkcija str koja brojeve

pretvara u znakovne nizove (tj. stringove), dok znak '+' vrši spajanje znakovnih nizova (tj. konkatenaciju).

U Pythonu se znakovi s tipkovnice koje korisnik unosi čitaju pomoću funkcije input(). Na primjer:

print("Unesi neki broj: ")

broj = int(input()) # Pretvaramo string u broj.

if (broj > 10):

print("Broj je veći od 10!")

Primjer jednostavnog programa u Pythonu:

# ovo je komentar

print ("Kako se zoves?")

ime = input()

print ("Bok, " + ime + "!")

print (ime + ", koji je tvoj najdrazi grad?")

grad = input()

if (grad == "Split"):

print ("U tome se gradu trenutno nalazimo!")

elif (grad == "Zagreb"):

print (grad + " je glavni grad Hrvatske!")

else:

print (grad + " je lijep grad!")

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

256

V4.1 Uvjetni izrazi

Python podržava mnoštvo uvjetnih izraza poput '==', '!=', '<', '>', '<=' i '>=', te

if ... elif ... else naredbi koji se često koriste. Ovi se uvjetni izrazi koriste na sličan način kao

i u programskim jezicima C, C++, C#, Java, itd.

Primjeri uvjetnih izraza u Pythonu:

a = 4

b = 6

c = -1

d = 0

e = 11

if ( (a == 4) and (b < 10) ): # Logičko I se u Pythonu piše 'and'

print(c)

elif ( (a > 4) or (b < 0) ): # Logičko ILI se u Pythonu piše 'or'

print(d)

if ( not(d > 0) ): # Logička negacija se u Pythonu piše 'not'

print(e)

else:

print(e)

V4.2 Naredbe ponavljanja

Python podržava mnoštvo naredbi ponavljanja poput while i for petlji koje se često koriste.

Primjer while petlje:

i = 0

while (i < 10):

print(i) # Ispisuju se brojevi od 0 do 9.

i = i + 1

Primjeri for petlje:

i = 0

for i in range(0,10):

print (i) # Ispisuju se brojevi od 0 do 9.

i = 0

for i in range(10):

print (i) # Ispisuju se brojevi od 0 do 9.

V4.3 Funkcije

Funkcije se u Pythonu definiraju pomoću ključne riječi def. Na primjer:

def imeFunkcije():

print("Unesi neki string: ")

nekiString = input()

print("Unijeli ste slijedeci string: " + nekiString)

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

257

Ako funkcija u Pythonu treba vratiti neku vrijednost, onda se to radi pomoću naredbe return. Na

primjer:

def zbrajanje(a, b): # Funkcija zbrajanje prima argumente a i b.

c = a + b

return c # Funkcija vraća varijablu c.

V4.4 Nizovi i matrice

Nizove je u Pythonu jednostavno definirati. Na primjer:

niz1 = [1, 2, 3, 4, 5] # Niz brojeva.

niz2 = ["prvi", "drugi", "treci"] # Niz stringova.

print (niz1[0]) # Ispiši prvi element prvog niza.

print (len(niz2)) # Ispiši veličinu drugog niza.

U Pythonu se rad s matricama najjednostavnije obavlja korištenjem biblioteke numpy. Na

primjer:

import numpy as np # np ćemo koristiti kao skraćeni oblik zapisa za numpy.

matrica = np.zeros((3,3)) # Stvaramo matricu dimenzija 3x3 punu nula.

print(matrica) # Ispisujemo matricu.

matrica[0][0] = 1 # Mijenjamo vrijednost elementa matrice.

V4.5 Zadaci

Zadatak 4.5.1. Napisati program u Pythonu koji u ovisnosti o tome koji broj korisnik upiše

provjerava je li taj broj bez ostatka djeljiv s 2.

Zadatak 4.5.2. Napiši program u Pythonu koji funkcionira kao jednostavni kalkulator za osnovne

aritmetičke operacije zbrajanje, oduzimanje, množenje i dijeljenje.

Zadatak 4.5.3. Napiši program u Pythonu za množenje dviju matrica.

VJEŽBA 5 - STROJNO UČENJE U PYTHONU

Strojno učenje (engl. Machine Learning) je dio umjetne inteligencije koji proučava načine na

koji programi mogu učiti i zaključivati. Postoje tri vrste strojnog učenja:

•

nadzirano učenje (engl. Supervised Learning),

•

nenadzirano učenje (engl. Unsupervised Learning),

•

polunadzirano učenje (engl. Semi-supervised Learning) od kojeg je najpoznatije pojačano

učenje (engl. Reinforcement Learning).

V5.1 Nadzirano učenje

Nadziranim učenjem pokušava se pronaći način kako, na temelju ulaznih podataka za koje je

poznato kojim klasama pripadaju, klasificirati nove podatke. Nadzirano učenje obično uključuje bazu

znanja i metodu zaključivanja. Problem nadziranog učenja je nemogućnost ispravnog postupanja s novim

informacijama koje se nisu koristile u fazi treniranja.

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

258

Ekspertni ili stručni sustavi (engl. Expert Systems) često koriste metode nadziranog učenja jer

nastoje emulirati znanje ljudskih stručnjaka u određenom području. Primjer jednostavnog ekspertnog

sustava koji identificira jednu od sljedeće tri životinje - papiga, vrabac, riba:

print("Može li životinja letjeti?")

let = input()

if (let == "da"):

print("Može li životinja govoriti?")

govor = input()

if (govor == "da"):

print("Papiga")

else:

print("Vrabac")

else:

print("Riba")

Primjer upotrebe nadziranog učenja u ekspertnom sustavu je klasifikator stabla odluke (engl.

Decision Tree Classifier). Klasifikator stabla odluke temelji se na strukturi sličnoj dijagramu toka kod

kojeg:

•

unutarnji čvorovi predstavljaju značajku ili atribut

•

grane predstavljaju pravila odluke, a

•

krajnji čvorovi ishod odluke.

Primjer baze znanja s kojom ćemo trenirati klasifikator stabla odluke dan u tablici V5-1. Značajke

na temelju kojih se odluka donosi su vrijeme, temperatura i vjetar, a ishod je binaran, utakmica će se

igrati (da) ili neće (ne).

Tablica V5-1. Primjer baze znanja s kojom ćemo trenirati klasifikator stabla odluke

vrijeme

temperatura

vjetar

utakmica ?

oblačno

23 °C

umjeren

sunčano

27 °C

slab

oblačno

-10 °C

jak

sunčano

-30 °C

slab

kišno

18 °C

slab

sunčano

0 °C

jak

Kada se baze znanja koriste u praksi, mogu se u memoriju računala spremiti na mnoštvo

različitih načina. Način koji se najčešće koristi u Pythonu je spremanje baze znanja u obliku CSV (engl.

Comma Separated Values) formata. Na primjer, CSV oblik podataka prikazanih u tablici V-2 koji možemo

nazvati train_dataset.csv bio bi:

vrijeme,temperatura,vjetar,utakmica

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

259

oblacno,23,umjeren,da

suncano,27,slab,da

oblacno,-10,jak,ne

suncano,-30,slab,ne

kisno,18,slab,ne

suncano,0,jak,ne

Stablo odluke za atribute vrijeme i temperatura prikazuje slika V5-1

Slika V5-1. Stablo odluka za podatke iz tablice V5-2

Postupak klasifikatora stabla odluke sastoji se od nekoliko koraka prikazanih na slici V5-2.

Slika V5-2. Grafički prikaz algoritma klasifikatora stabla odluke

Stablo odluke formira se na temelju podataka za treniranje danih u tablici V5-2.

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

260

Prvi korak je izbor najboljih atributa koristeći mjere za izbor atributa (engl. ASM – Attribute

Selection Measures) koje predstavljaju heurističku mjeru na temelju koje se podaci dijele u manje

podskupove na najbolji mogući način. Podijeljeni podaci rezultat ovog su postupka, Nakon toga kreće

izgradnja stabla odluke ponavljajući ovaj proces za svaki podskup sve dok:

•

nema više preostalih atributa

•

nema više ishoda odluke ili

•

sve dobivene n-torke (engl. touples) pripadaju istoj vrijednosti atributa.

Python u okviru biblioteke funkcija scikui-learn

114

ima funkciju

DecisionTreeClassifier()

115

kojom se realizira ovaj postupak. Funkcija ima tri parametra

kojima je moguće optimirati postupak izgradnje stabla odluke. Prvi je odabir postupka za izbor atributa

criterion=”.”. Dostupne su dvije mjere

116

•

Ginijev koeficijent koji je zadana (default) vrijednost ili

•

entropija (criterion=”entropy”).

Ginijev koeficijent (engl. Gini Index) je statistička mjera za izračun neravnomjerne raspodjele,

a uveo ga je još 1912. g. talijanski statističar Corrado Gini (1884.-1965.) u području ekonomije. Ginijev

koeficijent razmatra binarnu podjelu svakog atributa, te računa otežanu sumu vjerojatnosti te podjele.

!"#"

' ()*(

$ 2!

gdje je P

vjerojatnost da n-torka iz D pripada jednoj od klasa ishoda odluke. Kako imamo binarnu

podjelu, svaki od atributa A dijeli skup D na dva podskupa D1 i D2, a vrijednost Ginijevog koeficijenta

ove podjele je:

!"#"

(.!"#"

gdje je

kardinalnost (broj elemenata) pojedinog skupa. Onaj atribut A koji ima najmanji Ginijev

koeficijent bira se kao atribut na kojem će se raditi podjela kod izgradnje stabla odluke. Ako atribut ima

kontinuiranu vrijednost (kao npr. temperatura u tablici V-2) uzima se par po par susjednih vrijednosti pa

se računa razlika Ginijevih koeficijenata:

2!"#"

' !"#"

*(.!"#"

te se odabire onaj za koji je ova razlika najmanja.

Entropija ili informacijsko pojačanje (engl. Information Gain) temelji se na proračunu razlike

informacijske entropije prije dijeljenja podataka u podskupove i srednje entropije nakon djeljenja

podataka u podskupove. Informacijska entropija nekog skupa podataka je na neki način mjera uređenosti

tog skupa. Što je veće informacijsko pojačanje, to je i veća uređenost skupa i bolja podjela.

4#56

' ()*(

.768

$ 2!

gdje je P

isto kao prije vjerojatnost da n-torka iz D pripada jednoj od klasa ishoda odluke.

4#56

(.4#56

$ 2!

Informacijsko pojačanje za podjelu po atributu A računa se izrazom:

!;"#

' 4#56

*(.4#56

114

https://scikit-learn.org/stable/index.html

115

https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html

116

Više detalja o mjerama za izbor atributa u

http://www.ijoart.org/docs/Construction-of-Decision-Tree--Attribute-Selection-Measures.pdf

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

261

Bira se onaj atribut koji ima najveće informacijsko pojačanje.

Kad je postupak gotov treba nam i skup podataka za testiranje. U našem primjeru to je

test_dataset.csv kojeg formiramo iz tablice V5-2:

Tablica V5-2. Podaci za testiranje klasifikatora stabla odluke treniranog podacima iz tablice V5-1

vrijeme

temperatura

vjetar

utakmica?

kišno

3 °C

umjeren

kišno

27 °C

slab

oblačno

10 °C

slab

sunčano

-1 °C

slab

kišno

20 °C

jak

sunčano

0 °C

umjeren

Za rješenje ovog zadatka trebaju sljedeće Python biblioteke:

•

csv – Comma Separated Value

•

pandas – Python Data Analysis Library – PIL --> Image – Python Imaging Library

•

sklearn.metrics --> accuracy_score – analiza točnosti

•

PIL --> Image – Python Imaging Library

•

sklearn --> tree – stabla odluke

•

numpy – za znanstvene proračune matplotlib.pyplot – za crtanje 2D grafova

•

sklearn.preprocessing --> LabelEncoder – za mijenjanje kategoričnih vrijednosti iz baze znanja

u numeričke

Cijeli Python kod postupka je:

import csv

import pandas as pd

from sklearn.metrics import accuracy_score

from sklearn import tree

import numpy as np

from sklearn.preprocessing import LabelEncoder

#inicijaliziraj LabelEncoder

le = LabelEncoder()

# ucitaj csv dokument za treniranje

print("\n Podaci za treniranje")

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

262

df_train = pd.read_csv('train_dataset.csv', sep = ',',header = 0)

print(df_train)

# ucitaj csv dokument za testiranje

print("\n Podaci za testiranje")

df_test = pd.read_csv('test_dataset.csv', sep = ',',header = 0)

print(df_test)

# zamjena kategoričkih varijabli numeričkim

for col in df_test.columns.values:

if df_test[col].dtypes == 'object':

data = df_train[col].append(df_test[col])

le.fit(data.values)

df_train[col] = le.transform(df_train[col])

df_test[col] = le.transform(df_test[col])

# podaci za treniranje

print("Podaci za treniranje:")

print(df_train)

print("\n")

# podaci za testiranje

print("Podaci za testiranje:")

print(df_test)

print("\n")

# podjela podataka u vektore atributa(X) i ishode(y)

X_train, y_train = df_train.iloc[:,:-1], df_train.iloc[:, -1]

X_test, y_test = df_test.iloc[:,:-1], df_test.iloc[:, -1]

print("Podaci:")

print(X_train)

print("\n")

print("Labele:")

print(y_train)

print("\n")

# klasifikacija

clf = tree.DecisionTreeClassifier()

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

263

clf.fit(X_train, y_train)

# tocnost na train setu

print(clf.score(X_train, y_train))

predicted = clf.predict(X_test)

print(predicted)

print("\n")

print ("Tocnost je ", accuracy_score(y_test,predicted)*100)

print("\n")

V5.2 Nenadzirano učenje

Nenadzirano učenje koristi se za pronalazak strukture u podacima za koje ne znamo kojoj

kategoriji pripadaju. Primjeri primjene nenadziranog učenja su npr. analiza piksela na slici u svrhu

određivanja postojećih klasa boje na slici ili grupiranje pacijenata koji su imali jednu bolest s nekom

drugom bolešću.

Primjer algoritma nenadziranog učenja je algoritam k-sredine (engl. k-means Algorithm) kojim

se provodi klasteriranje u n klasa. Shematski prikaz rada ovog algoritma dan je na slici V5-3 gdje su

prikazani koraci klasteriranja podataka u 3 klase.

Python u okviru biblioteke funkcija scikit-learn ima funkciju KMeans() za proračun algoritma

k-sredine

117

Slika V5-3. Shematski prikaz rada algoritma k-sredina

117

https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

264

V5.3 Pojačano učenje kao primjer polunadziranog učenja

Polunadzirano učenje sadrži karakteristike i nadziranog i nenadziranog učenja. Ovakav način

učenja može se koristiti prilikom konstrukcije algoritama za klasifikaciju djelomično označenih podataka.

Na primjer pretpostavimo da radimo klasifikator kojem je zadatak prepoznavati slike automobila pri

čemu su tijekom faze treniranja korišteni podaci od kojih je samo jedan manji dio označen (npr. od 1000

slika algoritmu je kazano da 200 slika sigurno sadržava automobile, a za preostalih 800 slika algoritam

ne dobiva informacije o tome sadrže li automobile ili ne).

Pojačano učenje je primjer algoritma polunadziranog učenja koje se temelji na sustavu nagrada

i kazni. Obično se koristi u agentskim sustavima. Primjer upotrebe pojačanog učenja je konstrukcija

automatskih igrača u računalnim igrama tzv. NPC-ova od engl. Non-Player Character. U programskom

Python alatu OpenAI Gym

118

nalaze se sve funkcije za razvoj i usporedbu različitih postupaka pojačanog

učenja, na primjer implementaciju Q-učenja.

V5.4 Zadaci

Zadatak 5.4.1. Napišite jednostavni ekspertni sustav koji pogađa na koju vrstu vode (jezero, more,

potok, rijeka) korisnik misli.

Zadatak 5.4.2. Primjeni Python program klasifikatora stabla odluke za datoteku o autentičnosti

novčanica iz repozitorija datoteka strojnog učenja University of California

119

. Autentičnost

novčanica predviđa se na temelju četiri atributa koji su izvučeni sa slike novčanice i pripadaju

području napredne analize digitalne slike: varijanca wavelet transformirane slike, kurtozis

slike, entropija i nakrivljenost slike (engl. variance of wavelet transformed image, curtosis of

the image, entropy, and skewness of the image). U zadnjoj koloni je binarna informacija koja kaže

je li novčanica lažna (0) ili prava (1). Podatke podijeli u dvije skupine (80% lažnih i pravih za

treniranje i ostatak za testiranje).

Zadatak 5.4.3. Napiši program u Pythonu za klasteriranje u 3 klase vina algoritmom k-sredine iz

datoteke vina s repozitorija datoteka strojnog učenja University of California

120

koja sadrži podatke

ispitivanja 178 vina iz jedne talijanske regije. Klasteriranje provedi u dvodimenzionalnom prostoru

na temelju varijabli 'alchocol' i 'OD280/OD315 of diluted wines'.

Zadatak 5.4.4. Napiši program u Pythonu koji pomoću Q-pojačanog učenja rješavanje labirint sa

slike V5-4.

Slika V5-4. Labirint koji treba riješiti u zadatku 4 (pojačana linija je zid, što znači da se npr. ne

može ići iz 1 u 6)

118

https://gym.openai.com

119

https://archive.ics.uci.edu/ml/datasets/banknote+authentication – za repozitorij su zaslužni: Dua, D. and Graff,

C. (2019). UCI Machine Learning Repository [ http://archive.ics.uci.edu/ml ]. Irvine, CA: University of California,

School of Information and Computer Science.

120

https://archive.ics.uci.edu/ml/datasets/Wine - za repozitorij su zaslužni autori iz fusnote 107.

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

265

Dozvoljena su samo horizontalna i vertikalna kretanja, a način nagrađivanja/kažnjavanja uzmite

iz poglavlja 6.5.1. Kako izgleda konačna Q-matrica?

VJEŽBA 6 - LINEARNA REGRESIJA

Linearna regresija je metoda nadziranog strojnog učenja koja se koristi za predviđanje

kontinuiranih varijabli linearnom hipotezom temeljem više vrijednosti (npr. predviđanje cijena kuća u

ovisnosti o površini, lokaciji, orijentaciji, opremanju i sl.). U ovoj laboratorijskoj vježbi predviđat ćemo

cijene određenih objekata na tržištu na temelju njihovih značajki. Python u okviru biblioteke funkcija

scikit-learn i modula LinearRegression ima funkciju LinearRegression() za proračun linearne

regresije

121

V6.1 Zadaci

Zadatak 6.1.1. Prikupite podatke o cijenama određenih objekata koji su trenutno na tržištu te o

značajkama tih objekata. Smjernice:

- Što više informacija prikupite, algoritam koji ćete razviti u nastavku laboratorijske vježbe bit

će točniji. Prikupite najmanje 40 podataka.

- Ako ne pronađete određenu informaciju za neki objekt, označite taj podatak upitnikom.

- Podaci koje trebate prikupiti ovise o grupi laboratorijskih vježbi u kojoj odrađujete vježbu na

način prikazan u tablici V6-1.

Tablica V6-1. Teme po grupama

Tablica V6-2 Primjer podataka vezanih uz prodaju nekretnina

121

https://scikit-

learn.org/stable/modules/generated/sklearn.linear_model.LinearRegression.html#sklearn.linear_model.LinearRegr

ession

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

266

Tablica V6-3. Primjer podataka vezanih uz prodaju rabljenih automobila

Tablica V6-4. Primjer podataka vezanih uz prodaju rabljenih motocikla

Tablica V6-5. Primjer podataka vezanih uz nova prijenosna računala na tržištu

Tablica V6-6. Primjer podataka vezanih uz prodaju rabljenih plovila

Tablica V6-7. Primjer podataka vezanih uz prodaju novih mobitela

Zadatak 6.1.2. Podatke prebacite u CSV (engl. Comma Separated Value) format i sačuvajte kao

datoteku s ekstenzijom .csv. Primjer CSV datoteke:

Cijena,Povrsina,Lokacija,Kat,Dizalo,Privatni_parking,Balkon

600000,130,Split (Meje),3,Ne,Da,Da

300000,65,Split (Centar),2,Ne,Ne,Da

60000,30,Split (Radunica),1,Ne,Ne,Ne

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

267

Zadatak 6.1.3. CSV datoteku iz prethodnog zadatka podijelite na dva dijela - pola podataka

spremite u datoteku train.csv (na ovim ćemo podacima trenirati algoritam) a pola u test.csv

(na ovim ćemo podacima testirati algoritam).

Zadatak 6.1.4. Napišite program u Pythonu koji će pomoću biblioteke scikit-learn (i modula

LinearRegression) predviđati cijene objekta zadanog u zadatku 1. Primjer programa za

klasifikaciju podataka pomoću scikit-learn biblioteke možete pronaći u primjerima vježbe 5.

VJE

BA 7 – NAIVNI BAYESOV KLASIFIKATOR

Naivni Bayesov klasifikator (engl. Naive Bayes Classifier) jedan je od najjednostavnijih

klasifikatora u strojnom uc$enju, i c$esto daje dosta dobre rezultate. Budući da ne zahtijeva sloz$ena

rac$unanja, jako je brz u usporedbi s drugim klasifikacijskim algoritmima. Temelji se na Bayesovom

teoremu:

p(a|b)=p(b|a)

p(a) / p(b)

gdje su:

p(a|b) – vjerojatnost da se dogodi događaj a ako se je dogodio događaj b

p(a) – vjerojatnost da se dogodi događaj a

p(b|a) – vjerojatnost da se dogodi događaj b ako se je dogodio događaj a

p(b) – vjerojatnost da se dogodi događaj b.

Ime „naivni” dobio je zato što se u radu ovog klasifikatora pretpostavlja da su sve varijable u

ulaznim podacima neovisne jedna o drugoj, što vrlo često nije istina. U formuli za proračun$p(a|b) dio p(b)

se često može zanemariti. Primjer naivnog Bayesovog klasifikatora za ulazne podatke s više varijabli

možete pronaći na linku: https://www.youtube.com/watch?v=ZAfarappAO0.

Tablica V7-1 Primjer podataka za klasifikaciju

kolegij

ocjena

matematika

fizika

Tablica V7-2 Tablica koja prikazuje koliko puta se je određena ocjena pojavila za određeni kolegij

kolegij

ocjena: 1

ocjena: 2

ocjena: 3

ocjena: 4

ocjena: 5

matematika

fizika

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

268

Računamo vjerojatnost da se u ulaznim podacima pojavi kolegij matematika:

p(matematika)= 6 / 10 = 0,6

Računamo vjerojatnost da se u ulaznim podacima pojavi kolegij fizika:

p(fizika)= 4 / 10 = 0,4

Računamo vjerojatnost da se u ulaznim podacima pojavi ocjena 1:

p(ocjena1)= 1/ 10 = 0,1

Računamo vjerojatnost da se u ulaznim podacima pojavi ocjena 2:

p(ocjena2)= 0 / 10 = 0

Računamo vjerojatnost da se u ulaznim podacima pojavi ocjena 3:

p(ocjena3)= 2/10 = 0,2

Računamo vjerojatnost da se u ulaznim podacima pojavi ocjena 4:

p(ocjena4)= 4 / 10 = 0,4

Računamo vjerojatnost da se u ulaznim podacima pojavi ocjena 5:

p(ocjena5)= 3/ 10 = 0,3

Primjer računanja vjerojatnosti da iz kolegija matematika bude ocjena 5:

p(ocjena5 | matematika)=p(matematika | ocjena5)

p(ocjena5) / p(matematika) =

= (1/6)

0,3 / 0,6 = 0,0833

Primjer Python programa za računanja vjerojatnosti da se određeni kolegij pojavi u ulaznim

podacima koji su sačuvani u datoteci s ekstenzijom .csv (i imaju oblik ime_kolegija,ocjena):

import csv

import pandas as pd import numpy as np

# ucitaj CSV dokument za treniranje

print("Podaci za treniranje")

df_train = pd.read_csv('train.csv', sep = ',', header = 0) print(df_train)

# izdvajanje stupaca iz ulaznih podataka stupac1_train = df_train.iloc[:, 0]

stupac2_train = df_train.iloc[:, 1]

br_matematika = 0 br_fizika = 0

for i in range (0, stupac1_train.size):

if (stupac1_train[i] == "Matematika"):

br_matematika = br_matematika + 1 if (stupac1_train[i] == "Fizika"):

br_fizika = br_fizika + 1

p_matematika = 0

p_fizika = 0

p_matematika = float(p\_matematika) p_fizika = float(p\_fizika)

# vjerojatnost da se u ulaznim podacima pojavi matematika p_matematika = br_matematika

/ (br_matematika + br_fizika)

# vjerojatnost da se u ulaznim podacima pojavi fizika p_fizika = br_fizika /

(br_matematika + br_fizika)

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

269

V7.1 Zadaci

Zadatak 7.1.1. Prikupite proizvoljne ulazne podatke koje ćete koristiti prilikom treniranja i

testiranja naivnog Bayesovog klasifikatora.

Zadatak 7.1.2. Za proizvoljne ulazne podatke koje ste prikupili u 1. zadatku konstruirajte naivni

Bayesov klasifikator u Pythonu. Nemojte koristiti ugrađenu funkciju za ovaj klasifikator, već

napišite sami svoju (tj. napišite funkciju koja će sama računati vjerojatnosti kao što su vjerojatnost

da se u ulaznim podacima pojavi kolegij matematika, vjerojatnost da se u ulaznim podacima pojavi

kolegij fizika, vjerojatnost da se za kolegij fizika pojavi ocjena 5 itd.).

Zadatak 7.1.3. Usporedite rezultate koje ste dobili s rezultatima koje daje ugrađena funkcija za

naivni Bayesov klasifikator iz scikit-learn biblioteke u Pythonu.

VJEŽBA 8 – UMJETNE NEURONSKE MREŽE U PYTHONU

Umjetne neuronske mreže (engl. ANN – Artificial Neural Networks) dio su strojnog učenja koji

zadatke rješava imitiranjem biološke neuralne mreže. Iako se pojmovi „umjetne neuronske mreže” i

„neuronske mreže” razlikuju, u računarstvu se često koriste kao sinonimi, tj. riječ „umjetne” obično se ne

naglašava, nego se podrazumijeva.

Duboko učenje (engl. Deep Learning) je naprednija verzija neuronskih mreža. Riječ „duboko”

samo naglašava da ova metoda strojnog učenja koristi više razina međuslojeva, tj. dublja je od uobičajenih

neuronskih mreža.

Najčešće primjene neuronskih mreža su:

• klasifikacija

o OCR (engl. Optical Character Recognition) sustavi za automatsko prepoznavanje

teksta

o klasifikacija digitalnih slika

• klasteriranje

o klasifikacija bez poznatih klasa (nenadzirano učenje).

V8.1 Perceptron

Perceptron je najjednostavniji oblik umjetnih neuronskih mreža koje modeliraju biološke

neurone. Više međusobno povezanih perceptrona čini umjetnu neuronsku mrežu koja nakon treniranja

može donositi različite odluke i zaključke, te rješavati složene probleme. Perceptron može imati više

ulaznih podataka, ali samo jedan izlazni. I ulazni i izlazni podaci perceptrona predstavljaju se pomoću

binarnih brojeva. Svaki ulaz u perceptron ima svoju težinu. Ta težina može biti prethodno definirana ili

je neki od algoritama strojnog učenja može automatski izračunati. Shematski prikaz perceptrona

prikazuje slika 6-16.

Zadatak 8.1.1. Kako pomoću jednostavnog perceptrona odlučiti hoćete li ići s prijateljima u

kazalište ili ne? Opis ovog perceptrona prikazuje slika V8-1.

Upute za izradu odgovarajućeg perceptrona:

• predstavite svaki faktor koji utječe na vašu odluku kao ulaz u perceptron

• odredite težine svakog faktora na temelju toga koliko su vam ti faktori važni

• proučite odgovore na vaše uvjete i zbrojite njihove težine

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

270

• definirajte neki prag (engl. Threshold) – ako je zbroj težina veći od tog praga, ići ćete u kazalište,

a ako nije, onda nećete. O definiranom pragu ovisi rad perceptrona.

Slika V8-1. Opis perceptrona koji odlučuje o odlasku u kazalište%

V8.2 Sigmoidni umjetni neuron

Perceptroni uče na način da težine w

... w

pokušavaju podesiti tako da krajnja odluka

perceptrona bude što točnija. Budući da mala promjena u težini jednog faktora može uzrokovati velike

promjene u ponašanju cijelog sustava, umjesto perceptrona koriste se sigmoidni neuroni. Sigmoidni

neuroni se od perceptrona razlikuju po tom što:

• mala promjena u težini nekog od ulaznih faktora uzrokuje male promjene u cijelom sustavu

• izlaz sigmoidnog neurona može poprimiti bilo koju vrijednost iz intervala

[-1, 1], a ne samo -1 ili 1 kao kod perceptrona.

V8.2.1 Aktivacijska funkcija

Aktivacijska funkcija je krivulja u obliku slova "S". Slična je sigmoidnoj funkciji iz logističke

regresije, samo što je spuštena tako da daje izlazne vrijednosti u intervalu [-1 , 1], a kreira se na primjer

pomoću hiperbolnog tangesa:

' =>?@

Aktivacijska funkcija će broj koji dobije kao ulazni podatak prebaciti u broj iz intervala [-1, 1].

Njezin zadatak je uvođenje nelinearnosti u neuralnu mrežu jer su ulazni podaci najčešće nelinearni.

Python kod za aktivacijsku funkciju i njenu derivaciju:

import numpy

def izracunaj_sigmoid(x)

y = (numpy.exp(x) - numpy.exp(-x)) / (numpy.exp(x) + numpy.exp(-x))

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

271

return y

def izracunaj_sigmoid_derivaciju(s)

y = 1 – s * s

return y

Osim ove aktivacijske funkcije koriste se i neke druge funkcije, a danas posebno ispravljena

linearna funkcija (engl. ReLU – Rectified Linear Unit) i njena modificirana verzija parametarska

ReLU (engl. Parametric ReLU):

B<C

(D;(< E F

(D;(< G F

Ako je a = 0,01 naziva se propustljiva ReLU (engl. Leaky ReLU). U brojnim primjerima ove aktivacijske

funkcije daju bolje rezultate. Njihove izlazne vrijednosti su u intervalu

[-¥, +¥].

Izlaz sigmoidnog neurona s n ulaza je:

H ' I$

(

$ 2!

/K&

gdje su:

S – aktivacijska funkcija

– težina ulazne veličine

– ulazna veličina

b – tzv. bias (tj. prag s obrnutim predznakom).

Treniranje neuronskih mreža je proces koji obuhvaća pronalazak težina w

i praga b koji bi

minimizirali određenu cijenu (engl. Cost Function). Postoje različite formule koje se koriste za definiciju

ove cijene, a jedan od postupaka kojim se određuju težine w

i prag b je algoritma inkrementalni spust

gradijenta (engl. Incremental Gradient Descent) opisan u poglavlju 6.3.8.

V8.3 Duboko učenje

Duboko učenje (engl. Deep Learning), koje je danas posebno popularno, temelji se na višeslojnoj

neuronskoj mreži koja između ulaznog i izlaznog sloja ima više skrivenih slojeva nego što je to uobičajeno

kod neuralnih mreža. Budući da se često treniraju na velikom broju ulaznih podataka, ponekad je

potrebno imati jako brzo računalo da bi se istrenirale. Čak i na brzim računalima ovaj proces može trajati

danima.

V8.4 Implementacije neuronskih mreža

Programska biblioteka neuronskih mreža može se pronaći u raznim Python bibliotekama, npr.:

• OpenCV (engl. Open Source Computer Library) biblioteka za Python, C, C++, C# i Javu

• SciKit-Learn biblioteka za Python

• WEKA - aplikacija za strojno učenje i sl.

Programske biblioteke dubokog učenja mogu se također pronaći u brojnim razvojnim okruženjima

(engl. Framework), npr.:

• Caffe framework

• TensorFlow sustav za strojno učenje

• Theano biblioteka za Python i sl.

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

272

V8.5 Odabir ulaznih podataka

Neuronske mreže trebaju podatke za fazu treniranja. Ti su podaci obično dani kao vektori

značajki uz koje je vezana oznaka klase.

Primjer ulaznih podataka dan je u tablici V8-1. U ovome primjeru redci u tablici (svi osim prvoga)

predstavljaju piksele slike koji su određene kombinacije crvene, zelene i plave boje (engl. RGB - Red Green

Blue) u 8-bitnom kodiranju koja pripada klasi na slici. Na primjer, prvi piksel čije su vrijednosti prikazane

u tablici ima koordinate boja (85, 212, 55) i zna se da pripada klasi „vegetacija”. Što mislite koju bi od

ponuđenih značajki bilo najbolje koristiti za klasifikaciju?

Tablica V8-1. Primjer ulaznih podataka za algoritme strojnog učenja

Klasa

212

Vegetacija

159

Vegetacija

153

194

Nebo

199

194

Nebo

Odabir najboljih značajki za klasifikaciju je područje istraživanja grane strojnog učenja koja se

naziva odabir značajki (engl. Feature Selection). Postoje različiti algoritmi koji pronalaze najbolje

značajke, no najpoznatiji je PCA (engl. Principal Component Analysis) algoritam koji smo opisali u

poglavlju 6.4.2.

V8.6 Zadaci

Zadatak 8.6.1. Napišite program u Pythonu koji se ponaša kao jednostavni perceptron. Proizvoljno

odaberite temu o kojoj će vaš perceptron odlučivati.

Primjer koda:

print('Hoce li vrijeme biti suncano?')

x1 = input() ; čeka input sa tipkovnice

if (x1 == 'da'):

w1 = 2

else:

w1 = 0

Zadatak 8.6.2. Napišite program u Pythonu koji bi se ponašao kao sigmoidni neuron. Radi

jednostavnosti, ograničite ulazne podatke na 0, 0,5 ili 1. Možete iskoristiti programski kod iz

prethodnog zadataka, ali ga promijenite na način da program računa izlaz pomoću neke od

aktivacijskih krivulja.

VJEŽBA 9 - UMJETNA INTELIGENCIJA U RAČUNALNIM IGRAMA

Umjetna inteligencija (UI) dosta se koristi prilikom izrade računalnih igara. U računalnim

igrama prvenstveno se koristi tzv. slaba umjetna inteligencija koja je usmjerena na rješavanja problema

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

273

iz neke uske domene, a najčešće se koristi za vođenje automatskih virtualnih likova (engl. NPC –

Non-Player Characters).

U računalnim igrama koriste se dva pristupa umjetnoj inteligenciji: deterministička i

nedeterministička. U prošlosti se je češće koristila deterministička, zato što su stručnjaci za razvoj igara

prvenstveno bili usredotočeni na što bolju grafiku u računalnoj igri, dok se danas obje vrste podjednako

koriste.

V9.1 Deterministički postupci umjetne inteligencije

Karakteristike determinističkih postupaka umjetne inteligencije su:

• brza, jednostavna, lagana za implementaciju i testiranje

• programer mora programirati sve akcije i reakcije automatskih igrača

• igra može postati predvidljiva jer možete naučiti što očekivati od automatskog igrača budući

da automatski igrač ne uči, tj. ne razvija se tijekom igre i

• igra može postati dosadna.

Primjer determinističke UI bio bi programiranje automatskog igrača koji prati računalni lik

kojega korisnik kontrolira na način da uspoređuje koordinate korisničkog igrača s onima automatskog

igrača – kada se preklope, automatski igrač je ulovio korisničkog igrača.

V9.2 Nedeterministički postupci umjetne inteligencije

Karakteristike nedeterminističkih postupaka umjetne inteligencije su:

• igra je nepredvidljiva

• automatski igrači uče od živih igrača, pa se razvijaju tijekom vremena

• igra ne postaje dosadna i

• igru nije jednostavno testirati.

V9.3 Tehnike umjetne inteligencije u računalnim igrama

U računalnim igrama koriste se različite tehnike umjetne inteligencije. Neke od njih smo već

upoznali, a neke su specifične baš za računalne igre:

• pronalazak optimalnog puta različitim postupcima pretraživanja (engl. Pathfinding)

• logički automati koji se oslanjaju na neizrazitu logiku (engl. Fuzzy State Machines)

• konačni automati (engl. Finite State Machines)

• stabla ponašanja (engl. Behavior Trees)

• varanje (engl. Cheating) itd.

V9.3.1 Pronalazak optimalnog puta

Postupci pretraživanja koji se najčešće koriste za automatski pronalazak optimalnog puta u

računalnim igrama su

122

Vizualizacije većine ovih algoritama možete pronaći na sljedećem linku:

https://www.redblobgames.com/pathfinding/a-star/introduction.html .

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

274

• slijepa pretraživanja, npr. pretraživanje u širinu (engl. Breadth First Search) ili

pretraživanje u dubinu (engl. Depth First Search)

• optimalno usmjereno pretraživanje, npr. Dijkstra algoritam ili pretraživanje jednolikim

troškom (engl. Uniform Cost Search)

• heurističko potraživanje, npr. pohlepno pretraživanje (engl. Greedy Search)

• kombinacija optimalnog i heurističkog pretraživanja, npr. A* pretraživanje.

Od svih nabrojenih postupaka pretraživanja koji se koriste za pronalazak optimalnog puta

izdvojit ćemo možda najboljeg od njih, odnosno A* algoritam pretraživanja koji smo detaljno opisali u

poglavlju 3.6.3. Ovaj algoritam traži put od početnog bloka do zadanog cilja na način da pregledava

susjedne blokove i pomakne se na onaj koji ima najmanju cijenu. Cijena je u ovome slučaju definirana

kao:

f(s) = c + h

gdje je:

• c – cijena koju je potrebno stvarno platiti da bi se od trenutnog bloka prešlo na susjedni (ne

mora biti jedinstvena za sve blokove) i

• h – heuristička procjena puta (broja blokova) koje je potrebno prijeći od susjednog bloka do

cilja.

Heuristička procjena blokova koje je potrebno prijeći od određenog bloka do cilja može se

izračunati na više načina (detalji u poglavlju 3.5), a jedna od najčešće korištenih je Manhattanska

udaljenost:

h = | x - x

cilj

| + | y – y

cilj

Primjer pronalaska optimalnog puta pomoću A* algoritma dan je na slici V9-1. Na slici se

pretpostavlja da su na početku sva polja slobodna osim onih označenih sa #, a cijena prelaska iz jedno

polje u drugo je ista za sva polja.

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

275

Slika V9-1. Primjer pronalaska optimalnog puta pomoću A* algoritma

V9.3.2 Konačni automati

Kod upotrebe konačnih automata u računalnim igrama određuju se sve situacije u kojima se

računalni lik može zateći, te se programiraju reakcije tog lika u svakoj od tih situacija. Ovo znači da su

sve reakcije automatskih igrača unaprijed zadane. Zbog toga oni spadaju u determinističke postupke

umjetne inteligencije, pa su nedostaci:

• predvidljivost – nakon nekog vremena igrač može pogoditi što će automatski lik učiniti u

određenoj situaciji i

• složenost – problemi kod implementacije prilikom dodavanja novih stanja.

V9.3.3 Stabla ponašanja

Stabla ponašanja (engl. Behavior Trees) su potkategorija konačnih automata. Blokovi od kojih

su ovi automati izgrađeni su akcije, a ne stanja. Jednostavniji su za dodavanje novih blokova od konačnih

automata. Često se koriste zajedno s konačnim automatima.

Primjer stabla ponašanja za jednostavnu računalnu igricu dan je na slici V9-2.

Slika V9-2. Stablo ponašanja za jednostavnu računalnu igru

V9.3.4 Logički automati koji se oslanjaju na neizrazitu logiku

Logički automati koji se oslanjaju na neizrazitu logiku (engl. Fuzzy Logic) dopuštaju više

mogućih stanja. Mogu koristiti vjerojatnosti da bi odlučili u koje će stanje prijeći, ili mogu slučajno

odlučivati u koje će od mogućih stanja prijeći. Igre koje koriste ovakvu logiku su nepredvidljive. Dobro

modeliraju ljude, jer su i oni često nepredvidljivi. Grupe likova u igrama mogu se dobro modelirati pomoću

ovih automata jer će se likovi ponašati različito (a ne morate ih sve posebno programirati). Zbog toga oni

spadaju u nedeterminističke postupke umjetne inteligencije.

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

276

V9.3.5 Varanje

Varanje se u računalnim igrama događa kada automatski igrač ima pristup informacijama

vezanim za igrača kojeg korisnik kontrolira, te ih koristi kako bi ga pobijedio. Kada korisnik shvati da

računalo vara, može odustati od igre jer su mu šanse za pobjedu male ili nikakve. Zbog ovoga je varanje

potrebno držati na određenoj razini koja bi igru učinila zanimljivom i napetom.

V9.4 PYGAME BIBLIOTEKA

Pygame je biblioteka za Python koja implementira različite funkcije za stvaranje videoigara.

Izvrstan tutorial za izradu videoigara u Pythonu uz korištenje Pygame biblioteke dostupan je na linku:

https://www.youtube.com/channel/UCJbPGzawDH1njbqV-D5HqKw.

V9.5 Zadaci

Zadatak 9.5.1. Pomoću A* algoritma u Pythonu pronađite put kroz labirint prikazan u tablici V8-

1. Pretpostavite da u tablici 0 predstavlja prazno polje, 1 početno polje, 2 cilj, 3 prepreku, te 4 polje

koje ste već posjetili. Prilikom pronalaska optimalnog puta kroz labirint vaš algoritam mora

slijediti određena pravila: dozvoljeno je kretati se samo lijevo, desno, gore i dolje, te nije dozvoljeno

2 puta posjetiti isto polje. U koliko koraka algoritam dođe do cilja?

Tablica V9-1 Labirint vezan uz zadatak 1

Stvaranje matrice u Pythonu:

labirint = numpy.matrix([[0, 0, 3, 0, 2], [0, 0, 0, 0, 0], [0, 3, 3, 0, 0], [1, 0, 0, 0, 0]])

Zadatak 9.5.2. Nadogradite algoritam iz zadatka 1 na način da je dozvoljeno i dijagonalno

kretanje. Promijenite funkciju za računanje heuristike – nemojte koristiti Manhattan udaljenost,

nego uzmite u obzir i dijagonalno kretanje pa koristite Euklidsku udaljenost. U koliko koraka

algoritam dođe do cilja?

Zadatak 9.5.3. Nadogradite algoritam iz zadatka 2 na način da je moguće posjećivati već posjećena

polja, te ga testirajte na labirintu prikazanom u tablici V9-2. U koliko koraka algoritam dođe do

cilja?

Tablica V8-2 Labirint vezan uz zadatak 3

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

277

Zadatak 9.5.4. U Pythonu napravite jednostavnu igru u kojoj računalni lik (možete ga predstaviti

pomoću bloka) sam pronalazi put kroz labirint pomoću A* algoritma. Računalni lik treba doći do

predefiniranog cilja (kvadrat crvene boje). Sami definirajte statične kvadrate u labirintu koji će

predstavljati prepreke. Na primjer, plavi kvadrati mogu predstavljati vodu, zeleni šumu, a sivi

planine. Primjer prozora u kojemu bi bila ovakva igra dan je na slici V9-3.

Slika V9-3. Primjer jednostavne igre u Pythonu

Zadatak 9.5.5. Modificirajte algoritam iz prethodnog zadatka na način da je moguće kretanje

preko prepreka, ali cijena kretanja preko prepreka nije 1, nego veća od 1. Na primjer, cijena

kretanja kroz šumu je 2, preko vode 3, a preko planine 4. Ove cijene definirajte na početku

programa.

Zadatak 9.5.6. Modificirajte algoritam iz prethodnog zadatka na način da računalni lik i prepreke

ne predstavljaju blokovi, već slike. Slike možete dobiti na dva načina: u GIMP-u sami nacrtajte

računalni lik, šumu, planinu i vodu, ili na internetu pronađite slike koje su vam potrebne, a koje

imaju edukacijsku licencu.

VJEŽBA 10 - OBRADA PRIRODNOG JEZIKA

Obrada prirodnog jezika (engl. NLP – Natural Language Processing) je dio umjetne inteligencije

koji se bavi analizom i razumijevanjem napisanog ili izgovorenog teksta. U NLP postupke spada:

• automatsko sažimanje teksta

• potraga za sličnim dokumentima

• prepoznavanje govora

• automatsko generiranje teksta, itd.

U ovoj laboratorijskoj vježbi napravit ćemo jednostavni program u Pythonu koji bi iz pisanih

recenzija nekog filma mogao donijeti odluku o tome je li film bio uspješan ili ne.

V10.1 Zadaci

Zadatak 10.1.1. Kreirajte recenzije.txt datoteku koja sadrži par različitih recenzija za neki film.

Svaki redak te datoteke neka sadrži jednu recenziju. Možete koristiti recenzije dane u nastavku

teksta ili napisati sami svoje recenzije.

Primjeri recenzija nekog filma:

DODATAK: PROGRAMIRANJE U PROGRAMSKIM JEZICIMA UMJETNE INTELIGENCIJE

278

Best movie ever! I'm really glad I watched it. It was such fun!

It was ok. Nothing special. I've seen worse movies.

Horrible movie. Hated every second of it. Would not recommend to anyone.

I had a blast while eatching this movie. It was so funny. My family loved it. It is a great family

movie.

Cool movie. Loved the actors and the plot.

Super! Loved it!

Could not wait for this movie to end - it was so boring.

Loved the main actress! She really portrayed the character well.

I recommended this movie to all my friends and family and they all loved it.

It was so funny that I wish they would make a sequel. Would definitely recommend.

Primjer učitavanja tekstualne datoteke u Pythonu:

datoteka = "recenzije.txt"

# ucitavanje tekstualne datoteke

with open(datoteka) as f:

sadrzaj = f.read().splitlines()

print(sadrzaj)

print("Broj recenzija u datoteci: " + str(len(sadrzaj)))

for i in range (0, len(sadrzaj)):

print("Recenzija: " + str(sadrzaj[i]))

sadrzaj_bez_delimitera = sadrzaj[i].replace('.', '')

sadrzaj_bez_delimitera = sadrzaj_bez_delimitera.replace(',', '')

sadrzaj_bez_delimitera = sadrzaj_bez_delimitera.replace('!', '')

sadrzaj_bez_delimitera = sadrzaj_bez_delimitera.replace('-', '')

print("Recenzija bez delimitera: " + str(sadrzaj_bez_delimitera))

rijeci_iz_trenutne_recenzije = sadrzaj_bez_delimitera.split()

print("Rijeci u recenziji: " + str(rijeci_iz_trenutne_recenzije))

Zadatak 10.1.2. Napišite program u Pythonu koji će učitati recenzije iz datoteke recenzije.txt i

ispisati ih.

Zadatak 10.1.3. Proučite recenzije u datoteci recenzije.txt. Koje riječi označavaju pozitivno

mišljenje o filmu, a koje negativno? Spremite te riječi u dvije zasebne liste ili pak spremite svaku

riječ u zasebni string. Ove riječi sada predstavljaju vaš rječnik ili vokabular (engl. Vocabulary).

Zadatak 10.1.4. Napišite petlju u Pythonu koja prolazi kroz svaku recenziju posebno i bilježi

koliko puta se je u toj recenziji pojavila neka pozitivna riječ, te koliko puta se je pojavila neka

negativna riječ. Ako su se više puta u recenziji pojavile pozitivne riječi, ocijenite tu recenziju kao

pozitivnu. Ako su se više puta u recenziji pojavile negativne riječi, ocijenite tu recenziju kao

negativnu. Ako se u recenziji nije pojavila nijedna riječ iz vašeg rječnika, ignorirajte tu recenziju.

Zadatak 10.1.5. Odredite postotak korisnika koji su filmu dali pozitivnu recenziju, te postotak

korisnika koji su filmu dali negativnu recenziju.