[Zk] 16.5.2008

Přednáška je věnována neprocedurálnímu programování. Většina semestru je věnována programování v jazyku Prolog, ve kterém studenti i ladí zápočtové programy. Informativně se studenti seznámí i s jazykem LISP a neprocedurálními částmi programovacích systémů.
bartolomej

[Zk] 16.5.2008

Příspěvek od bartolomej »

1.) PROLOG: Hladovym algoritmom pomocou heuristiky najst minimalne ofarbenie grafu.

2.) PROLOG: Z postfixneho zapisu n-arneho stromu vytvorit n-arny strom.

napr:
(hodnota,pocet synov)
IN: postfix = [('b',0),('e',0),('f',0),('c',2),('d',0),('a',3)]
OUT: NodeN 'a' [NodeN 'b' [],NodeN 'c' [NodeN 'e' [],NodeN 'f' []],NodeN 'd' []]

3.) HASKELL: Mame zadany orientovany graf. Treba vyhodit vs.hrany (u,v), pre ktore existuje cesta dlzky 2 z u do v.

4.) HASKELL: Na vstupe mame obdlzniky(okna), mame zistit ci sa nejake prekryvaju.

type Rozmer = (Int,Int)
type Obd = (Int,Int,Rozmer) // (sur_x,sur_y,(sirka,vyska))

data Maybe a = Nothing | Just a

Ulohou bolo napisat funkciu:
prusek :: [Obd] ->Maybe (Obd,Obd) //dostane okna a vrati Kolidujucu dvojicu

5.)Vs o negacii v Prologu
peterblack
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 10. 12. 2006 19:26

Re: [Zk] 16.5.2008

Příspěvek od peterblack »

mno zkouska je zamnou...ale stejne mi prijde Prolog jako takovy zly Voodoo :) Haskell mi sednul mnohem vic
a Hric je pomerne hodnej pan...nevim proc me vzdycky tak desil

pro zajimavost moje reseni 2:
(zachovava poradi)

Kód: Vybrat vše

rs([],S,S).
rs([(X,Y)|Z],S,Vysl):-
  rozdel(S,Y,SY,S2),
  rs(Z,[nt(X,SY)|S2],Vysl).

rozdel(S,0,[],S).
rozdel([S|SS],Y,SY,S2):-
  Y1 is Y-1,
  append(S1,[S],SY),
  rozdel(SS,Y1,S1,S2).  
  
spustrs:-rs([(b,0),(d,0),(e,0),(c,2),(a,2)],[],X), write(X). 
A od kolegy reseni 4:

Kód: Vybrat vše

type Rozmer = (Int, Int)
type Obd = (Int, Int, Rozmer)

prekryti :: [Obd] -> Maybe (Obd,Obd)
prekryti sObd
	| (seznamKolizi == []) = Nothing
	| otherwise = Just (head seznamKolizi)
		where
			seznamKolizi = [(a,b) | a <- sObd, b <- (filter (/=a) sObd), prekryvajiSe a b]
			
prekryvajiSe :: Obd -> Obd -> Bool
prekryvajiSe (zx1,zy1,(xz1,yz1)) (zx2,zy2,(xz2,yz2)) =
	if ((zx1 < zx2) && (kx1 > zx2)) then
	  if ((zy1 < zy2) && (ky1 > zy2)) then True
	  else if ((zy2 < zy1) && (ky2 > zy1)) then True
	  else False
	else False
		where
			kx1 = zx1 + xz1
			ky1 = zy1 + yz2
			kx2 = zx2 + xz2
			ky2 = zy2 + yz2


-- dotaz1: prekryti [(0,0,(6,4)),(6,5,(2,2)),(7,6,(9,8))]
-- dotaz2: prekryti [(2,0,(2,5)),(0,2,(5,1))]
Naposledy upravil(a) peterblack dne 17. 5. 2008 16:22, celkem upraveno 1 x.
lickra
Matfyz(ák|ačka) level I
Příspěvky: 21
Registrován: 13. 6. 2006 22:24

Re: [Zk] 16.5.2008

Příspěvek od lickra »

PROLOG: Hladovym algoritmem pomoci heuristiky najit minimalne obarbeni grafu.

Kód: Vybrat vše

 
obarvi([],_,[],_).
obarvi([(I-J)|T],Uz,[(J-N)|Z],Max):-otoc([(I-J)|T],J,OTOC),
									seznamMax(Max,Z),
									zjistiMinBarvu(J,OTOC,Uz,Z,N),
									dejdoUZ((J-N),Uz),
									maximum(Max,N,Max1),
									obarvi(T,Uz,Z,Max1).
									
zjistiMinBarvu(_,[],Z,N):-minimum(Z,N). 
zjistiMinBarvu(J,[(I-J)|T],Uz,Z,N):-member(I,UZ),
									barva(I,Uz,F),
									delete(Z,F,Z1),
									zjistiMinBarvu(J,T,Uz,Z1,N).

% otoc-otoci hrany tak aby koncili J
% minimum najde min ze seznamu nebo M
% seznamMax vrati seznam [1..Max]
Pozn.: Neni to uplne hladovy algoritmus, najdem vsechny barvy kteryma muzeme barvit a vyberem tu nejmensi, ale hricovi to nevadilo

Druhe reseni vic hladovejsi

Kód: Vybrat vše

zjistiBarvu(S,T,X,X):-jde(S,T,X).
zjistiBarvu(S,T,X,N):- X1 is X+1, zjistiBarvu(S,T,X1,N).

jde([],_,_).
jde([S|Z],T,X):-notmenber((S-X),T), jde(Z,T,X).

barvy([],X,X).
barvy([[V|ZS]|Z],T,X):-zjistiBarvu(ZS,T,1,N),barvy(Z,[(V-N)|T],X).
Prolog 2: Z postfixneho zapisu n-arniho stromu rekonstruovat n-arny strom. Vstup [B-0,E-0,F-0,C-2,D-0,A-3]

Kód: Vybrat vše

rekonstrukce(Vstup,Strom):-reverse(Vstup,Vystup), makeTree(Vystup,_,Strom).

makeTree ( [ Val-0|T], T, t(Val,[]) ).
makeTree ( [Val-N|T], Z, t(Val, Childs) ) :- makeChild ( T, N, Z, Childs ).

makeChild ( T, 0, T, [] ).
makeChild ( T, N, Z, [C|Childs] ) :- makeTree ( T, Zb, C ),N1 = N – 1,
makeChild ( Zb, N1, Z, Childs).
Pozn.: Celkem ok ale drobnost nezachovava poradi synu!!

Haskell 3: V orientovanem acyklickem grafu vyskrtat hrany[u,v] pokud mezi vrcholy u a v existuje cesta delky 2.
vstup je seznam hran. Hrana je dvojprvkovy seznam napr [[1,4],[2,3],[3,4],[4,5]]

Kód: Vybrat vše

proskrtej hrany = gen hrany hrany

gen [] _ = []
gen (x:xs) hrany
			| projdi x vrcholy hrany = gen xs hrany
			| otherwise = x: g xs hrany
			
projdi _ []  _  = False
projdi [x,y] [a:as] hrany
			| (member [x,a] hrany) && (member [a,y] hrany) = True
			| otherwise = projdi [x,y] as hrany

Pozn.: neefektivni protoze se porad prochazeji hrany - lepsi reseni nagenerovat seznam naseledniku a predchudcu pro vsechny vrcholy


Haskell 4: Na vstupu mame obdelniky(okna), mame zistit jestli nejake prekryvaji.


type Rozmer = (Int,Int)
type Obd = (Int,Int,Rozmer)

data Maybe a = Nothing | Just a

Ulohou bylo napsat funkci:
prekryvaji :: [Obd] ->Maybe (Obd,Obd) //dostane okna a vrati kolidujici dvojci

Nevedel sem co je Maybe tak sem generoval seznam -> 4body

Kód: Vybrat vše

prekryvaji [] = []
prekryvaji [x] = []
prekryvaji (x:xs) = (p x xs) ++ prekryvaji xs

--vrati seznam oken ktere se prekryvaji
p _ [] = []
p (a,b,(ar,br)) ((x,y(xr,yr)):zbytek)
					| ((x>a)&&(x<(a+ax))&&(y>b)&&(y<(b+bx))) || () || () || () = ( (a,b,(ar,br)), ((x,y(xr,yr)))) :p (a,b,(ar,br)) zbytek
					| otherwise = p (a,b,(ar,br)) zbytek
					
peterblack
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 10. 12. 2006 19:26

Re: [Zk] 16.5.2008

Příspěvek od peterblack »

hezky reseni...
jenom otazka na 4 "|| () || () || ()" to jsou nejaky specialni haskellovsky kouzla nebo se ti nechtelo psat s podminkama? :)
lickra
Matfyz(ák|ačka) level I
Příspěvky: 21
Registrován: 13. 6. 2006 22:24

Re: [Zk] 16.5.2008

Příspěvek od lickra »

za || () || () .... se doplni podminky pro ostatni rohy, to je test jestli nejaky roh je v tom druhem a obdelnik ma 4 rohy -> dalsi 3 testy
peterblack
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 10. 12. 2006 19:26

Re: [Zk] 16.5.2008

Příspěvek od peterblack »

jo no ale to nepokreje pripad pro tyhle dva obdelniky:

Kód: Vybrat vše

   +-+
+--|-|--+
|  | |  |
+--|-|--+
   +-+
reseni co jsem posilal ja by to snad melo zvladat...
bartolomej

Re: [Zk] 16.5.2008

Příspěvek od bartolomej »

My way:

3.) zmaz g = setDiff g [(u,v) | (u,v)<-g,(a,x)<-g,(y,b)<-g,u==a,x==y,b==v]

4.) na styri porovnania: (kx1 < zx2) || (ky1 < zy2) || (kx2 < zx1) || (ky2 < zy1)
Odpovědět

Zpět na „PRG005 Neprocedurální programování“