Zkouška 14.2.

[luk]

Zdravím všechny dychtivce po informacích ze zkoušky...!
Tak k tomu, co Vás asi zajíma nejvíc...malé příklady (citováno volně ):
Prolog:

Kód: Vybrat vše

1. Zjistěte (efektivně), zda je daný graf obarvitelný 2 barvami a pokud ano, vydejte toto obarvení. 

Kód: Vybrat vše

2. Zrekonstruujte n-ární strom z jeho prefixního zápisu. Na vstupu je seznam dvojic hodnota vrcholu a počet synů. Pro list je tento počet roven 0.

Tady asi není moc co dodat, zadání Haskellu byla štavnatější. Například trojku jsem louskal 6x než jsem pochopil, co se po mne chce
Haskell:

Kód: Vybrat vše

3. Napište morfologickou funkci
(Eq a)=>[(String,a)]->[(a,String,b)]->String->[(String,b)]
Funkce dostane na vstupu slovo (typu String), seznam dvojic kmen (String) a vzor (a) a seznam trojic vzor (a), koncovka (String) a morfologická informace (b). Vydejte seznam všech dvojic (kmen, morfologická informace), kde kmen odpovídá kmenu slova se vzorem vzor a morf. info. vzoru slova s tímto kmenem a příslušnou koncovkou.

Zní to dost strašlivě, ale znamená to tohle. Dostanete slovo, k němu vyzkoušíte všechna rozdělení na kmen a koncovku a vydáte ty dvojice (kmen, morf. info.), kde existuje dvojice (kmen, a) v 1. seznamu a zároveň (a,koncovka,b) v 2. Bůh suď, jestli jsem to vysvětlil líp

Kód: Vybrat vše

4. Na vstupu je přirozené číslo n, Vygenerujte nekonečnou posloupnost (seznam) seznamů délky n uspořádanou maximolexikograficky, tj. seznamy jsou uspořádány nejprve dle maxima a potom lexikograficky.
Př.: n = 2 [[0,0],[0,1],[1,0],[0,2],[1,2],[2,0],[2,1]...

Tak to by bylo, ještě velký příklad, ten mi tentokrát přišel docela jednoduchý (měl jsem ho hodinu před koncem), ale je trouchu dlouhý, tak si dovolím napsat ho do dalšího příspěvku...

[luk]

Velký příklad:

Kód: Vybrat vše

Na vstupu je seznam pravidel a množina faktů. Fakta jsou (prologovské) atomy a pavidla jsou tvaru Číslo:Podmínka==>Akce, kde Podmínka je booleovský výraz složený z faktů a logických spojek and, or, non a Akce je seznam s prvky add(Fakt) a del(Fakt).
Výpočet probíhá následovně:
Najde se první vykonatelné pravidlo, tj. takové, jehož podmínka je splněna a ještě nebylo vykonáno a to se vykoná. Pokud žádné neexistuje, výpočet končí.
Vykonáním pravidla se rozumí provedení všech akcí v seznamu Akce. Akce add přidá fakt do množiny, pokud v ní již není, pokud tam je, akce se nespustí. Akce del odebere fakt z množiny, pokud v ní je, jinak se nevykoná. Výsledky programu jsou dva: nová množina faktů a seznam použitých pravidel tvaru číslo a seznam všech skutečně vykonaných akcí.
V Prologu nadefinujte operátory pro logické spojky a ':', '==>'
V Haskellu definujte typy, fakta jsou Stringy a pravidla trojice (číslo,podmínka,seznam akcí)

Snad jsem to napsal nějak pochopitelně. Teď tu čekám na ústní, tak na mne myslete, kdož si to přečtete

[Hugo]

hmmm...kdybys napsal i neco vyreseneho, vubec bych se nezlobil, kdyz ti to tak pekne odsypalo (zejmena neco z toho velkeho a ze 3.)

[luk]

hmmm...kdybys napsal i neco vyreseneho, vubec bych se nezlobil, kdyz ti to tak pekne odsypalo (zejmena neco z toho velkeho a ze 3.)

No, pro začátek ten težký...alespoň stručně. Nevím, jestli je to ideální řešení, ale Hricovi se celkem zamlouvalo a neměl výhrad (a dal mi za 1 ). Ale zlepšovacím návrhům se nebráním, rád se přiučím

Kód: Vybrat vše

% execute(+Seznam_Pravidel,+Fakta,-Vysledek_Pravidla,-Vysledna_Fakta)
execute([],Fakta,[],Fakta).  % Konec výpočtu - vyčerpána všechna pravidla
execute(Pravidla,Fakta,[PP|Out],VysF):-find_executable_rule(Pravidla,Fakta,Pravidlo),!,execute_rule(Pravidlo,Fakta,PP,VF1),delete(Pravidlo,Pravidla,NewPravidla),execute(NewPravidla,VF1,Out,VysF).
execute(_,Fakta,[],Fakta).   % Konec výpočtu - žádné pravidlo nelze vykonat

% find_executable_rule(+Pravidla,+Fakta,-Pravidlo)
% uspěje, pokud v Pravidlech je vykonatelné pravidlo (pak jej vrátí), jinak selže
find_executable_rule([],_,_):-fail.
find_executable_rule([Pravidlo|T],Fakta,Pravidlo):-is_executable(Pravidlo,Fakta).
find_executable([_|T],Fakta,Pravidlo):-find_executable_rule(T,Fakta,Pravidlo).

% is_executable(+Pravidlo,+Fakta) - uspěje, je-li pravidlo vykonatelné
is_executable(_:Condition==>_,Fakta):-evaluate(Condition,Fakta,true).

% execute_rule(+Pravidlo,+Fakta,-Pouzite,-VysFakta)
execute_rule(N:_==>Action,Fakta,N-UsedActions,VysFakta):-do_it(Action,Fakta,UsedActions,VysFakta).

% do_it(+Seznam_Akcí,+Fakta,-Skutečně_Použité_Akce,-VýsFakta)
do_it([],Fakta,[],Fakta).
do_it([Akce|T],Fakta,[Akce|Out],VysFakta):-was_commited(Akce,Fakta,VF),!,do_it(T,VF,Out,VysFakta).
do_it([_|T],Fakta,Out,VysFakta):-do_it(T,Fakta,Out,VysFakta).

% was_commited(+Akce,+Fakta,-VysFakta) - skusí vykonat akci na faktech, uspěje, pokud se zadařilo
was_commited(add(Fakt),Fakta,[Fakt|Fakta]):-\+member(Fakt,Fakta).
was_commited(del(Fakt),Fakta,VysFakta]):-member(Fakt,Fakta),delete(Fakt,Fakta,VysFakta).

% Zbývá evaluate a to je velice jednoduché vyhodnocování podmínek, které asi každý dělal na cvičeních
% evaluate(+Podmínka,+Fakta,?Vysledek)

Je to trochu dlouhé, spousta věcí by se dala scuknout, ale mne se to takhle zdá přehlednější, tak snad to pomůže...

Hodně štěstí všem, které ta zkouška ještě čeká

[Polik]

Tedy nečekal jsem, že když z lehkých jeden ignoruji (ta trojka, zadání jsem nějak nepochopil), jeden špatně pochopím (nechal mne ho přepsat, ale nenapsal jsem dvakrát efektivně) a jeden vyřeším "tak trochu exponenciálně" (jednička vyžadující efektivitu), že dostanu za jedna. Ale tak yay K těžkému neměl výhrady (haskell).

[nytram]

Kód: Vybrat vše

execute_rule(N:_==>Action,Fakta,N-UsedActions,VysFakta):-do_it(Action,Fakta,UsedActions,VysFakta).

mohol by niekto blizsie vysvetlit, co je to "N:_==>Action"?

[qwyxyo]

Tak ja pridavam este riesenie tej 4. ulohy. Je to na 3 riadky a nie az tak zlozite, ale komu to napadne za tu dlhu hodku...

Kód: Vybrat vše

gen 1 k = [[x]|x<-[0..k]]
gen n k = [[x] ++ y|x<-[0..k],n>0,y<-(gen (n-1) k)]

generuj n = [vysledok|k <- [0..], vysledok <- [temp|temp <- (gen n k)],maximum vysledok == k]

[luk]

Kód: Vybrat vše

execute_rule(N:_==>Action,Fakta,N-UsedActions,VysFakta):-do_it(Action,Fakta,UsedActions,VysFakta).

mohol by niekto blizsie vysvetlit, co je to "N:_==>Action"?

Přečti si zadání , pravidla jsou v seznamu ve tvaru Číslo:Podmínka==>Akce, N:_==>Action tedy znamená, že si číslo uložím do proměnné N, podmínka mne už nezajímá (zpracována dříve) a do proměnné Action si uložím seznam akcí...