Nagyhatékonyságú Deklaratív Programozás 2012 őszi félév, Információk

Nagyhatékonyságú Deklaratív Programozás, 2012 ő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

(2012.12.17) A gyakorlatok anyaga letölthető innen,

(2012.12.17) A nagy házi feladat beadható az ETS-rendszer segítségével. A keretprogram és a tesztesetek letölthetőek innen,

(2012.12.16) A 3.-4. kisházi beadható az ETS-rendszer segítségével.

(2012.11.19) A nagy házi feladat kiírása olvasható.

(2012.11.12) A második kisházi beadható az ETS-rendszer segítségével, november 26.-ig

(2012.09.24) SICStus Prolog 4.2.1 licensz igényelhető az ETS-rendszerben

(2012.09.24) Az első kisházi beadható az ETS-rendszer segítségével, október 2.-ig

(2012.09.24) A példaprogram-gyűjtemény frissítve

(2012.09.03) Előadások: kedd 8:15-10:00, IE.218 (minden héten, kivéve 10.23)

(2012.09.03) Gyakorlatok: csütörtök 14:15-16:00, IB,144 (páratlan heteken, kivételesen az 1. hét helyett a 2. héten lesz gyakorlat)
A gyakorlatok időpontjai tehát: 09.13, 09.20, (10.04: Qpa miatt szünet), 10.18, (11.01: Mindenszentek ünnepe miatt elmarad) 11.15, 11.29.

Nagy házi feladat

A házi feladat kiírása. A házi feladat keretprogramja 271 tesztesettel együtt letölthető innen. A beadáskor használt tesztesetek rendre a következő sorszámmal szerepelnek ebben a zip file-ban: 227,234,099,236,229,165,271,233,237,256.

A 2012. évi NDP előadás fóliái

Kisebb változások még lehetségesek.

A 2002. évi előadásokról készült jegyzet-kézirat

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 megoldása bináris formában, a SICStus Prolog 4.2.0 és 4.2.1 változataihoz.

1. kis házi feladat:

A kiírás innen letölthető. A kiírás kiegészítéseként pontosítjuk a count/2 predikátummal szembeni elvárásokat:

ne csináljon választási pontot (lásd a 4. futási példát a fólián).
count(L, N)-ben, ha az L lista N db eleméről kiderül, hogy 1-es, akkor nem vár további változó-behelyettesítésre és a fennmaradó változókat behelyettesíti 0-ra. Pl. a `count([X,Y,Z], 1), Z=1' célsorozat az `X=0, Y=0, Z=1' eredményt adja.
count(L, N)-ben, ha az L lista len(L)-N db eleméről kiderül, hogy 0, akkor nem vár további változó-behelyettesítésre és a fennmaradó változókat behelyettesíti 1-re. Pl. a `count([X,Y,Z], 2), Z=0' célsorozat az `X=1, Y=1, Z=0' eredményt adja.

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 beadható.

A beadási határidő 2012. október 2., kedd, 24 óra.
A határidőig beadott, jól működő programokra 2 pluszpont jár.
A házi feladat ez után a határidő után is beadható, 1 pluszpontért.

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.

A beadási határidő 2012. november 26, 24 óra.
A határidőig beadott, jól működő programokra 2 pluszpont jár.
A házi feladat ez után a határidő után is beadható, egészen a vizsga napjáig, 1 pluszpontért.

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ó.