AIwiki

Strona Główna

Dla Studentów

Zima / Winter 2021:

Computer Science: Introduction to AI
ISI: Podstawy Sztucznej Inteligencji

Old specialized AI courses

SMaDA/SMaIDA/AIDA

1. semester:

2. semester:

WSHOP -- Development Workshop

Informatyka (EAIiIB)

1. rok:

2. i 3. rok:

4. rok:

Systemy i technologie wirtualizacji

Studia Dr

HeKatE

Public

The KESE workshop (EN only)
Mindstorms (archive)

Prolog Lab

Część główna

Część fakultatywna

Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

--- pl:prolog:prolog_lab:prolog_lab_3 [2008/10/16 16:57]
wojnicki rozmienianie monet
+++ — (aktualna)
@@ Linia 1: / Linia 1: @@
-====== 3 LAB: Praca z listami w Prologu ======
-===== WPROWADZENIE =====
-==== Temat: Notacja list ====
-Lista to uporządkowany zbiór elementów. Elementem może być dowolna struktura danych w Prologu.
-Listę zapisujemy:
-<code prolog>
-[a,b,c]
-[2,4,6,ala,ma,kota]
-[]
-</code>
-Każda lista składa się z:
-  * głowy (ang. //head//), która jest zawsze 1. elementem listy, oraz
-  * ogona (ang. //tail//), który jest zawsze listą
-Listę od ogona rozdzielamy operatorem ''|'' (pionowa kreska), np.:
-<code prolog>
-?- [X|Y]=[a,b,c,d].
-X = a
-Y = [b, c, d] ;
-</code>
-Dekompozycja i strukturalizacja list jest realizowana głównie przez mechanizm unifikacji, a co za tym idzie w.w. notacja jest jej podstawą. Na przykład:
-<code prolog>
-?- [X,Y|Z]=[a,b,c,d].
-X = a
-Y = b
-Z = [c, d] ;
-?- [X,Y,a]=[Z,b,Z].
-X = a
-Y = b
-Z = a ;
-</code>
-==== Temat: Przynależność do listy ====
-<code prolog>
-nalezy(X,[X|_]).
-nalezy(X,[_|Yogon]) :-
-	nalezy(X,Yogon).
-</code>
-==== Temat: Liczenie elementów ====
-<code prolog>
-dlugosc([],0).
-dlugosc([_|Ogon],Dlug) :-
-	dlugosc(Ogon,X),
-	Dlug is X+1.
-</code>
-==== Temat: Sklejanie list ====
-<code prolog>
-sklej([],X,X).
-sklej([X|L1],L2,[X|L3]) :-
-	sklej(L1,L2,L3).
-</code>
-==== Temat: Dodawanie elementów ====
-<code prolog>
-dodaj(X,L,[X|L]).
-</code>
-W praktyce nie byłby tu potrzebny dodatkowy predykat.
-==== Temat: Usuwanie elementów ====
-<code prolog>
-usun(X,[X|Reszta],Reszta).
-usun(X,[Y|Ogon],[Y|Reszta]) :-
-	usun(X,Ogon,Reszta).
-</code>
-==== Temat: Zawieranie list ====
-<code prolog>
-zawiera(S,L) :-
-	sklej(_,L2,L),
-	sklej(S,_,L2).
-</code>
-==== Temat: Permutacje list ====
-<code prolog>
-permutacja([],[]).
-permutacja([X|L],P) :-
-	permutacja(L,L1),
-	wstaw(X,L1,P).
-permutacja2([],[]).
-permutacja2(L,[X|P]) :-
-	usun(X,L,L1),
-	permutacja2(L1,P).
-</code>
-==== Temat: Odwracanie listy ====
-<code prolog>
-odwroc([],[]).
-odwroc([H|T],L) :-
-	odwroc(T,R),
-	sklej(R,[H],L).
-</code>
-==== Temat: Listy a napisy ====
-Napis w Prologu może być reprezentowany przez:
-  * atom - jest trudny w obróbce,
-  * listę kodów ASCII znaków,
-  * listę jednoliterowych atomów.
-Reprezentacja przy pomocy listy zwiększa możliwości przetwarzania.
-Przydatny predykat:
-<code prolog>
-wypisz([H|T]) :-
-	put(H), wypisz(T).
-wypisz([]).
-</code>
-===== ĆWICZENIA =====
-==== 3.1 Ćwiczenie: Notacja list ====
-Proszę sprawdzić poniższe unifikacje:
-<code prolog>
-?- X=[a,b,c].
-?- [X|Y]=[a,b,c].
-?- [[a,b],c]=[X,Y].
-?- [a(b),c(X)]=[Z,c(a)].
-?- [X|Y]=[a].
-</code>
-Wybieranie wybranego elementu:
-  trzeci([A,B,C|Reszta],C).
-Zdefiniować predykat porównujący 2 wybrane elementy listy, np. 3. i 4.
-Zdefiniować predykat zamieniający 2 wybrane elementy listy, np. 3. i 4.
-==== 3.2 Ćwiczenie: Przynależność do listy ====
-Dopisać predykat ''nalezy'' do pliku //listy-1.pl//
-Sprawdzić i przemyśleć działanie poniższych:
-<code prolog>
-?- nalezy(c,[a,b,c,d]).
-?- nalezy(x,[a,b,c,d]).
-?- nalezy(X,[a,b,c,d]).
-?- nalezy(x,a).
-?- nalezy(X,a).
-</code>
-==== 3.3 Ćwiczenie: Liczenie elementów ====
-Dopisać predykat ''dlugosc'' do pliku //listy-1.pl//
-Sprawdzić i przemyśleć działanie poniższych:
-  ?- dlugosc([a,b,c],X).
-==== 3.4 Ćwiczenie: Sklejanie list ====
-Dopisać predykat ''sklej'' do pliku //listy-1.pl//
-Sprawdzić i przemyśleć działanie poniższych:
-<code prolog>
-?- sklej([a,b],[c,d],X).
-?- sklej([a,b],X,[c,d]).
-?- sklej([a,b],X,[a,b,c,d]).
-?- sklej(A,B,[a,b,c,d,e]).
-?- sklej([1,2,3],[a,b,c],X).
-?- sklej([1,2,3],[a(e),b(f),c(d,g)],X).
-?- sklej(Przed,[5|Po],[1,2,3,4,5,6,7,8,9]).
-?- sklej(_,[A,5,B|_],[1,2,3,4,5,6,7,8,9]).
-?- sklej(A,[x,x,x|_],[a,b,x,x,c,x,x,x,d,e]).
-</code>
-Uwaga: dopisać i przetestować predykat:
-<code prolog>
-nalezy1(X,L) :-
-	sklej(_,[X|_],L).
-</code>
-Zdefiniować predykat:
-  ostatni(Element,Lista).
-Z użyciem i bez użycia ''sklej''.
-==== 3.5 Ćwiczenie: Dodawanie elementów ====
-Dopisać predykat ''dodaj'' do pliku //listy-1.pl//
-Sprawdzić i przemyśleć działanie poniższych:
-<code prolog>
-?- dodaj(a,[c,d],X).
-?- dodaj([a,b],[c,d],X).
-</code>
-==== 3.6 Ćwiczenie: Usuwanie elementów ====
-Dopisać predykat ''usun'' do pliku //listy-1.pl//
-Sprawdzić i przemyśleć działanie poniższych:
-<code prolog>
-?- usun(a,[a,b,a,c,a,a],X).
-?- usun(a,[a,b,c,d],X).
-?- usun(c,[a,b,c,d],X).
-?- usun(c,X,[a,b,c,d]).
-?- usun(1,X,[a,b,c,d]).
-</code>
-Uwaga: dopisać i przetestować predykat:
-<code prolog>
-wstaw(X,L,Duza) :-
-	usun(X,Duza,L).
-</code>
-Uwaga: dopisać i przetestować predykat:
-<code prolog>
-nalezy2(X,L) :-
-	usun(X,L,_).
-</code>
-==== 3.7 Ćwiczenie: Zawieranie list ====
-Dopisać predykat ''zawiera'' do pliku //listy-1.pl//
-Sprawdzić i przemyśleć działanie poniższych:
-<code prolog>
-?- zawiera(a,[a,b,c]).
-?- zawiera([a],[a,b,c]).
-?- zawiera(X,[a,b,c]).
-?- zawiera([X],[a,b,c]).
-?- zawiera([X,Y],[a,b,c]).
-?- zawiera([X,Y,Z],[a,b,c]).
-</code>
-==== 3.8 Ćwiczenie: Permutacje list ====
-Dopisać predykat ''permutacja'' do pliku //listy-1.pl//
-Sprawdzić i przemyśleć działanie poniższych:
-<code prolog>
-?- permutacja([a,b,c],X).
-?- permutacja2([a,b,c],X).
-</code>
-==== 3.9 Ćwiczenie: Odwracanie listy ====
-Dopisać predykat ''odwroc'' do pliku //listy-1.pl//
-Sprawdzić i przemyśleć działanie poniższych:
-<code prolog>
-?- odwroc([a,b,c,d],X).
-?- odwroc([a,b,c,d],[d,c,b,a]).
-</code>
-==== 3.10 Ćwiczenie: Listy a napisy ====
-Sprawdzić i przemyśleć działanie poniższych:
-<code prolog>
-?- write('ala').
-?- write('ala ma kota').
-?- write("ala").
-?- write("ala ma kota").
-?- X = 'a', put(X).
-?- X = 'ala', put(X).
-?- X = "a", put(X).
-?- put(65),put(66),put(67).
-</code>
-Dopisać predykat ''wypisz'' do pliku //listy-1.pl//
-Sprawdzić i przemyśleć działanie poniższych:
-<code prolog>
-?- wypisz("ala ma kota").
-?- permutacja("abc",X),wypisz(X),nl,fail.
-?- wstaw(" ", "abcdefgh",Z),wypisz(Z),nl,fail.
-</code>
-==== 3.11 Ćwiczenie: Zadania do zrealizowania ====
-. Napisz program który obliczy na jakie monety mozna rozmienić zadaną sumę pieniędzy.
-  * Zdefiniuj nominały monet: np. ''moneta(1)'' oznacza monetę jdenozłotową,
-  * Predykt rozmieniający powinien mieć dwa argumenty: ''rozmien/2'', gdzie pierwszy to kwota, a drugi lista nominałów monet na jakie można rozmienić kwotę.
-. zadać cel powodujący usunięcie 3 ostatnich elementów listy L, w wyniku powstaje lista L1, użyć ''sklej''.
-. zadać cel powodujący usunięcie 3 pierwszych elementów listy L, w wyniku powstaje lista L1, użyć ''sklej''.
-. zadać cel powodujący usunięcie 3 pierwszych i ostatnich elementów listy L, w wyniku powstaje lista L2, użyć ''sklej''.
-. zdefiniować predykat ''ostatni1(E,L)'', gdzie E to ostatni element listy L, użyć ''sklej'' (predykat nie jest rekurencyjny).
-. j.w., ''ostatni2(E,L)'', tylko bez ''sklej'' (predykat jest rekurencyjny).
-. zdefiniować parę komplementarnych predykatów ''nieparzysta(L)'' oraz ''parzysta(L)'' wypisujących listy o odpowiednio nie/parzystej długości.
-. zdefiniować predykat ''palindrom(L)'', L jest palindromem, jeżeli czyta się tak samo od przodu i tyłu, np. ''[a,l,a]'', ''[m,a,d,a,m]''. (podpowiedź: można nie/użyć ''odwroc''.)
-. zdefiniować predykat ''przesun(L1,L2)'', gdzie L2, jest przesuniętą rotacyjnie o jeden element L1, np.:
-<code prolog>
-      ?- przesun([1,2,3,4,5,6,7,8],X),przesun(X,Y),przesun(Y,Z).
-      X = [2, 3, 4, 5, 6, 7, 8, 1]
-      Y = [3, 4, 5, 6, 7, 8, 1, 2]
-      Z = [4, 5, 6, 7, 8, 1, 2, 3]
-</code>
-. zdefiniować predykat ''przeloz(L1,L2)'', który zamienia listę liczb (max. 0-9), na listę słów:
-<code prolog>
-      ?- przeloz([1,4,7],X).
-      X = [jeden, cztery, siedem] ;
-      ?- przeloz(A,[dwa,osiem,zero]).
-      A = [2, 8, 0] ;
-</code>
-posługując się faktami:
-<code prolog>
-      znaczy(0,zero).   znaczy(1,jeden).
-      znaczy(2,dwa).    znaczy(3,trzy).
-      znaczy(4,cztery). znaczy(5,piec).
-      znaczy(6,szesc).  znaczy(7,siedem).
-      znaczy(8,osiem).  znaczy(9,dziewiec).
-</code>
-Podpowiedź: predykat ma być rekurencyjny.
-. zdefiniować predykat ''podzbior(L,Z)'', który sprawdza, czy Z zawiera się w L, oraz wypisuje wszystkie możliwe podzbiory L (jeżeli Z jest niewiadoma).
-<code prolog>
-      ?- podzbior([a,b,c],[c]).
-      Yes
-      ?- podzbior([a,b,c],[a,c]).
-      Yes
-      ?- podzbior([a,b,c],X).
-      X = [a, b, c] ;
-      X = [a, b] ;
-      X = [a, c] ;
-      X = [a] ;
-      X = [b, c] ;
-      X = [b] ;
-      X = [c] ;
-      X = []
-</code>
-. zdefiniować predykat ''podziel(L,L1,L2)'', który dzieli listę L, na dwa fragmenty L1 i L2, mniej więcej równej długości (z dokładnością do jednego el.), np.:
-<code prolog>
-      ?- podziel([],X,Y).
-      X = []
-      Y = [] ;
-      ?- podziel([1],X,Y).
-      X = [1]
-      Y = [] ;
-      ?- podziel([1,2],X,Y).
-      X = [1]
-      Y = [2] ;
-      ?- podziel([1,2,3],X,Y).
-      X = [1, 3]
-      Y = [2] ;
-      ?- podziel([1,2,3,4],X,Y).
-      X = [1, 3]
-      Y = [2, 4] ;
-      ?- podziel([1,2,3,4,5],X,Y).
-      X = [1, 3, 5]
-      Y = [2, 4] ;
-      ?- podziel([1,2,3,4,5,6,7,8],X,Y).
-      X = [1, 3, 5, 7]
-      Y = [2, 4, 6, 8] ;
-</code>
-. zdefiniować predykat ''splaszcz'', który zamienia dowolnie zagnieżdżoną listę, w listę płaską (której el. nie są listami). (podstawowe rozwiązanie działa bez nawrotów - nie należy naciskać '';'')
-<code prolog>
-      ?- splaszcz([[a],b,c],X).
-      X = [a, b, c]
-      ?- splaszcz([[a],[b,[d]],c],X).
-      X = [a, b, d, c]
-      ?- splaszcz([a,b,c],X).
-      X = [a, b, c]
-      ?- splaszcz(a,X).
-      X = [a]
-</code>
-====== Komentarze ======
-Z braku lepszego miejsca tutaj studenci wpisują komentarze natury ogólnej do tego lab. 8-)
- --- //[[gjn@agh.edu.pl|Grzegorz J. Nalepa]] 2008/02/20 14:34//
-=== Efektywność odwracania list ===
-  * Predykat podany w sekcji [[prolog_lab_3#tematodwracanie_listy]], tzw. naiwny, używa predykatu sklej, co powoduje jego nieefektywność. Innym rozwiązaniem jest użycie tzw. akumulatora, w którym przechowujemy budowaną na bieżąco listę. Opis procedury: http://www.coli.uni-saarland.de/~kris/learn-prolog-now/html/node51.html#subsec.l6.reverse.acc
-W kolejnych krokach predykat ten buduje listę Accumulator:
-    List: [a,b,c,d]  Accumulator: []
-    List: [b,c,d]    Accumulator: [a]
-    List: [c,d]      Accumulator: [b,a]
-    List: [d]        Accumulator: [c,b,a]
-    List: []         Accumulator: [d,c,b,a]
-Klauzule wyglądają następująco:
-<code prolog>
-odwroc2(L,R) :-
-     odwr2(L,[],R).
-odwr2([H|T],A,R) :-
-     odwr2(T,[H|A],R).
-odwr2([],A,A).
-</code>
-Rezultat: Znaczna poprawa efektywności. Przykładowo dla 8-elementowej listy predykat wykorzystujący sklej wykonuje 90 kroków, zaś używający akumulatora - 20.  (//WF//)
-> Bardzo cenna uwaga! Nie pokazujemy akumulatorów, bo mamy mało czasu. Nie zmienia to faktu, że to akurat warto by dodać do części //Jeśli chcesz wiedzieć więcej// :-)  -- GJN
-> Uwaga techniczna: akcja "niewidzialna ręka" była modna, ale teraz można się podpisywać :) --GJN

pl/prolog/prolog_lab/prolog_lab_3.1224169033.txt.gz · ostatnio zmienione: 2019/06/27 15:59 (edycja zewnętrzna)

Pokaż stronę Poprzednie wersje

Menadżer multimediów Do góry