Nagyhatékonyságú Deklaratív Programozás, 2010 őszi félév
Információk
Ez a lap a Nagyhatékonyságú Deklaratív Programozás tárgy anyagára vonatkozó
információkat tartalmaz.
Friss hírek
(2011.01.16) A nagy házi feladathoz (idén először a tárgy
történetében) létraverseny is kapcsolódik.
A részleteket lásd alább.
(2011.01.12) Az első vizsga feladatsora letölthető innen.
(2010.09.19) Az első három hét előadásain szereplő példaprogramok
letölthetők. Az első kisházi kiírása (egy kiegészítéssel együtt) valamint
a csak futtatható mintamegoldás letölthető.
(2010.09.07) Az NDP ETS-rendszere
működik: A SICStus Prolog 4.1.2 rendszer letölthető.
(2010.09.07) Előadások: szerda 16:15-17:45, IB.134 (minden héten)
(2010.09.07) Gyakorlatok: csütörtök 10:15-11:45, IB.144 (páros
heteken)
A gyakorlatok időpontjai tehát: 09.16, 09.30, 10.14, 10.28, 11.11,
11.25, 12.09.
Nagy házi feladat
A házi feladat kiírása.
Létraverseny
A létraversenyben úgy
lehet részt venni, hogy a házi feladat programszövegében elhelyezzünk egy
letraversenyteszt. tényállítást, és közönséges nagy házi
feladatként beadjuk. Ez esetben az ETS nem az alaptesztesetekkel
futtatja a programot, hanem a 11.-20. sorszámot viselő nagyobb és
nehezebb tesztpéldákkal. Ezek a tesztesetek
letölthetők innen.
A létraversenyben 2011.01.24. 10:00 óráig beadott házi feladattal lehet
részt venni. Csak az utolsó beadás számít. A létraverseny értékelése az
ETS által kiírt "összidő" alapján történik. A három leggyorsabb megoldás
rendre 15, 10 és 5 plusz vizsgapontot kap.
A 2010. évi NLP előadás fóliái (1.-184. fólia)
Az eddig (2010.11.03) vett anyag a 120. fóliáig terjed, az azutáni részek
még változhatnak.
Példaprogramok
- Programok - az első három
előadáson szereplő
példaprogramok szövege, futási példákkal, plusz az első kisházi
1. kis házi feladat:
A kiírás
innen
letölthető. A kiírás kiegészítése itt található.
A kis házi feladat "minta"-megvalósítása (.po formában, tehát futtathatóan,
de nem olvashatóan) és tesztpéldái
letölthetők innen, de a példaprogramokkal
együtt is letölthetők
innen.
Az 1. kis házi feladat beadása:
A KHF az NDP ETS rendszerének
segítségével hamarosan beadható lesz.
2. kis házi feladat:
A kiírás a fóliákon megtalálható, de a szóbanforgó egy
oldal (PDF alakban) innen is
letölthető.
Fontos megjegyzesek:
- Az egyes "szavak" elemei különböző számok
kell legyenek.
- Egyes "szavak"-nak (pl. az egy kockából állóknak)
nincs megadva az összege, tehát ez esetben is x szerepel az összeg
helyén! (Lásd pl. az alábbi tesztpéldák között a
p2
példában a mátrix 4. sorának 3. oszlopában szereplő x\x értéket!).
A kis házi feladat tesztpéldái megtalálhatók
itt.
A 2. kis házi feladat beadása:
A KHF az NDP ETS rendszerének segítségével adható be.
3. kis házi feladat:
Az FD predikátumok jelentését ellenőrző segédprogram letölthető
innen.
A kiírás a fóliákon megtalálható, de a szóbanforgó egy
oldal (PDF alakban) innen is
letölthető.
A kis házi feladat futtatásakor a következő segédeljárást használom:
fdtest([X,Y,Z,B], Goal, [XR,YR,ZR,BR]) :-
domain([X,Y,Z], 0, 9),
'z>max(x,y)'(X, Y, Z) #<=> B,
call(Goal),
fd_dom(X, XR),
fd_dom(Y, YR),
fd_dom(Z, ZR),
fd_dom(B, BR).
A házi feladat beadása:
- Ez a 3. kis házi feladat, ezért a megoldást
egy
khf-nlp3.pl nevű állományba kell helyezni.
Vigyázat! A megoldásban nem írhatók "közönséges",
:- nyakjelű Prolog klózok, csak FD-klózok.
4. kis házi feladat:
A kiírás a fóliákon megtalálható, de a szóbanforgó egy
oldal (PDF alakban) innen is
letölthető.
A kis házi feladat futtatásakor a következő környezetet használom:
:- use_module(library(lists)).
:- assert(clpfd:full_answer).
globtest(Before, Constraint, After, Result) :-
Constraint = max_lt(List, Z),
Goal = (Before, Constraint, After,
fd_doms([Z|List], [ZDom|ListDom])),
( call_residue_vars( Goal, Vars) ->
( is_active(max_lt(_,_), Vars) ->
Result = active(ListDom, ZDom)
; Result = exited(ListDom, ZDom)
)
; Result = failed
).
is_active(Goal, Vars) :-
member(Var, Vars),
frozen(Var, VarF),
in_goal(VarF, Goal).
in_goal(_:Gs, G) :- !,
in_goal(Gs, G).
in_goal((Gs1,Gs2), G) :- !,
( in_goal(Gs1, G) -> true
; in_goal(Gs2, G)
).
in_goal(G, G).
fd_doms([V|Vs], [D|Ds]) :-
fd_dom(V, D),
fd_doms(Vs, Ds).
fd_doms([], []).
step_up(X, _I) :-
nonvar(X), !.
step_up(X, I) :-
X #> I, I1 is I+1,
step_up(X, I1).
Példafutások:
| ?- globtest(true, max_lt([A,B,C],Z), (A in 1..5, B #> 2, Z in 0..6), Result).
Result = active([1..5,3..5,inf..5],4..6) ? ;
no
| ?- globtest(domain([X,Y,Z], 0, 9), max_lt([X,Y],Z), (Z=5, Y=6), Result).
Result = failed ? ;
no
| ?- globtest(true, max_lt([A],Z), (A in {0,9}, Z in {3,6}), Result).
A = 0,
Result = exited([{0}],{3}\/{6}) ? ;
no
| ?- globtest((length(L, 500),domain(L, 1, 5) , X in 5..10000),
max_lt([X|L], Z),
step_up(X, 5), Result).
L = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J|...],
X = 10000,
Result = exited([{10000},1..5,1..5,1..5,1..5,1..5,1..5,1..5,... .. ...|...],10001..sup) ? ;
no
| ?-
Megjegyzések:
- Az utolsó teszt hivatott azt eldönteni, hogy a megoldás használ-e
állapotot, vagy sem. Állapot nélkül ugyanis 500-szor több listaelemet
kell végignéznie...
- Az eredményben a struktúra funktora jelzi, hogy a globális korlát
lefutott-e (
exited), vagy sem (active). Mivel a lefutás pontos
ellenőrzése általában felesleges, ezért az active
elfogadható az exited helyett, de nem fordítva. Például
a fentiek közül az utolsó két esetben a tesztrendszer elfogadja az
active funktorú eredményt, de az első tesztesetben az
exited eredményt nem.
A házi feladat beadása:
- Ez a 4. kis házi feladat, ezért a megoldást
egy
khf-nlp4.pl nevű állományba kell helyezni.
Esettanulmányok:
- Négyzetkirakás - az
előadáson ismertetett négyzetkirakási esettanulmány.
- Torpedó
- az 1999-es házi-feladat (torpedó) mintamegoldása.
- Dominó
A 2000 tavaszi házifeladat (dominó) mintamegoldásai.
Gyakorló vizsga-feladatok:
A korábbi évek vizsga-feladat-sorai:
Az
nhlp-l levelezési lista
A rokon tárgyakról, korábbi félévekről Szeredi
Péter oktatási honlapján található
információ.