Różnice

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

Odnośnik do tego porównania

Both sides previous revision Poprzednia wersja
Nowa wersja
Poprzednia wersja
pl:miw:2009:piw09_clp [2009/06/08 10:31]
piw09
pl:miw:2009:piw09_clp [2017/07/17 08:08] (aktualna)
Linia 46: Linia 46:
 W większości przypadków propagacja ograniczeń nie prowadzi do rozwiązania (jak to zostało przedstawione w powyższym przykładzie). Dlatego programowanie z ograniczeniami jest ściśle związane z dystrybucją połączoną z poszukiwaniem. \\ W większości przypadków propagacja ograniczeń nie prowadzi do rozwiązania (jak to zostało przedstawione w powyższym przykładzie). Dlatego programowanie z ograniczeniami jest ściśle związane z dystrybucją połączoną z poszukiwaniem. \\
 **Dystrybucja** polega na wprowadzeniu dodatkowego ograniczenia (często jest to przyporządkowanie jednej wartości do zmiennej, a zadaniem dystrybucji jest odpowiednie wybranie zmiennej i wartości). Kiedy to nastąpi sprawdzana jest spójność poprzez propagację ograniczeń i istnieją trzy możliwości:​\\ **Dystrybucja** polega na wprowadzeniu dodatkowego ograniczenia (często jest to przyporządkowanie jednej wartości do zmiennej, a zadaniem dystrybucji jest odpowiednie wybranie zmiennej i wartości). Kiedy to nastąpi sprawdzana jest spójność poprzez propagację ograniczeń i istnieją trzy możliwości:​\\
- ​   ​* znalezione zostanie rozwiązanie (wszystkie zmienne mają po jednej wartości w swojej domenie)\\ +  ​* znalezione zostanie rozwiązanie (wszystkie zmienne mają po jednej wartości w swojej domenie)\\ 
-    ​* domeny niektórych zmiennych zostaną zawężone, ale jednoznaczne rozwiązanie nie jest wciąż wyznaczone, więc dystrybucja jest dokonywana na kolejnej zmiennej\\ + 
-    ​* dodatkowe ograniczenie jest niespójne z pozostałymi ograniczeniami,​ więc proces nawrotu jest dokonywany, a wybrana wartość z domeny wybranej zmiennej jest usuwana\\+  ​* domeny niektórych zmiennych zostaną zawężone, ale jednoznaczne rozwiązanie nie jest wciąż wyznaczone, więc dystrybucja jest dokonywana na kolejnej zmiennej\\ 
 + 
 +  ​* dodatkowe ograniczenie jest niespójne z pozostałymi ograniczeniami,​ więc proces nawrotu jest dokonywany, a wybrana wartość z domeny wybranej zmiennej jest usuwana\\ 
 + 
  
 Ten proces jest dokonywany iteracyjnie i jest nazywany **poszukiwaniem**. Poszukiwanie jest odpowiedzialne za zatrzymanie;​ po znalezieniu pierwszego rozwiązania lub pewnej liczby rozwiązań lub wszystkich rozwiązań. Poszukiwanie tworzy tzw. drzewo poszukiwań,​ gdzie każdy węzeł jest stanem zmiennej. ​ Ten proces jest dokonywany iteracyjnie i jest nazywany **poszukiwaniem**. Poszukiwanie jest odpowiedzialne za zatrzymanie;​ po znalezieniu pierwszego rozwiązania lub pewnej liczby rozwiązań lub wszystkich rozwiązań. Poszukiwanie tworzy tzw. drzewo poszukiwań,​ gdzie każdy węzeł jest stanem zmiennej. ​
Linia 69: Linia 73:
  
 ==== clpfd (Constraint Programming Language over Finite Domains) ==== ==== clpfd (Constraint Programming Language over Finite Domains) ====
 +CLPFD jest modułem CLP i bazuje przede wszystkim na dziedzinie liczb całkowitych. Predykaty modułu umożliwiają m.in.  określanie relacji/​ograniczeń,​ konwersję wyrażeń do ich wartości liczbowej, tak że rozrastanie się wyrażeń może postępować we wszystkich kierunkach, systematyczne poszukiwanie rozwiązań. Wyrażeniem w module CLP(FD) może być liczba całkowita, zmienna.\\
 + ​Operacje które można wykonywać: ​ dodawanie i odejmowanie wyrażeń, ​ mnożenie, szukanie minimum lub maksimum dwóch wyrażeń, reszta z dzielenia wyrażeń przez siebie, wartość bezwzględna,​ dzielenie liczb całkowitych. Natomiast ograniczenia wynikające z relacji to, jak już wcześniej opisałam i przedstawiłam w tabelce: ≠ ,=,> , ≥ , < ,≤ .\\
 +**Przykład**\\
 +Poniższy przykład przedstawia wykorzystanie ograniczeń i porównywanie wyrażeń przy pomocy modułu CLP(FD). \\
 +Zagadka SEND+MORE=MONEY:​\\
 +<​code>​
 +:- use_module(library(clpfd)).
 + ​puz([S,​E,​N,​D,​M,​O,​R,​Y]) :-
 + Vars = [S,​E,​N,​D,​M,​O,​R,​Y],​
 + Vars ins 0..9,
 + ​all_different(Vars),​
 +sum(S,​E,​N,​D,​M,​O,​R,​Y).
 +
 + ​sum(S,​E,​N,​D,​M,​O,​R,​Y):​-
 +S*1000 + E*100 + N*10 + D +M*1000 + O*100 + R*10 + E #= M*10000 + O*1000 + N*100 + E*10 + Y,
 + M #\= 0, S #\= 0.
 +</​code>​
 +Na początku inicjalizujemy moduł clpfd, a następnie tworzymy zmienne Vars I określamy, że powinny należeć do zbioru od 0..9. Var ins oznacza, że liczby będą ​ dokładnie z zakresu od 0..9(jednocyfrowe) bez możliwości tworzenia liczb dwucyfrowych. All different(Vars ) zapewnia, że wszystkie zmienne będą różne.\\
 +
 ==== clp_distinct ==== ==== clp_distinct ====
 +CLP_distinct jest to biblioteka, która dostarcza nam ograniczenia na zmienne. Określa w jakim przedziale powinny znajdować się zmienne np. <​code>​vars_in([X,​Y,​Z],​[1,​2,​3])</​code>​\\
 + ​Można także wywołać predykat, który określi, że zmienne powinny być różne: ​
 +**All_distinct(Vars)**\\
 +Aby otrzymać konkretne wartości, a nie przedziały,​ wtedy stosujemy predykat **label/​1**.\\
 +Przykład:​\\
 +<​code>​ [X,Y] in 1..3, vars_in([X, Y],[1, 2]), all_distinct([X,​ Y]), label([X, Y]).</​code>​\\
 +
 +Kolejny ciekawy predykat to All_different.\\
 +Przykład:
 +<​code>?​- [X,Y,Z] in 0..1, all_different([X,​Y,​Z]).
 +
 +        X = _G180{0..1}
 +        Y = _G183{0..1}
 +        Z = _G186{0..1} ;
 +</​code>​\\
 +Jednak w przeciwieństwie do **All_distinct**,​ **all_different** nie wykrywa braku rozwiązania (patrz przykład powyżej). Dopiero po dodaniu predykatu label/1 wynik jest poprawny-false.
 +
 ==== CLP(Q,R) Constraint Logic Programming over Rationals or Reals ==== ==== CLP(Q,R) Constraint Logic Programming over Rationals or Reals ====
 +**CLP(Q,R) Constraint Logic Programming over Rationals or Reals** jest to kolejny moduł, który ułatwia programowanie z ograniczeniami. Służy on do modelowania problemów na zbiorze liczb rzeczywistych i wymiernych. Biblioteka CLP(Q,R) składa się z dwóch modułów:
 +  * CLP(Q)-dla liczb wymiernych:
 +<​code>​use_module(library(clpq))</​code>​
 +
 +  * CLP(R)-dla liczb rzeczywistych:​
 +<​code>​use_module(library(clpr))</​code>​
 +
 +Większość predykatów dla modułu CLP(Q) oraz CLP(R) są takie same i należą do nich:\\
 +^ Predykaty ​  ​^ ​  ​Opis ​                 ^
 +| + Expr           ​| ​  unary plus       |
 +| - Expr            |       unary minus  |
 +| Expr + Expr      |   ​addition ​ |
 +| Expr - Expr      |   ​subtraction ​ |
 +| Expr * Expr    |    multiplication ​ |
 +| Expr / Expr     ​| ​    ​division ​ |
 +| abs(Expr) ​       |     ​absolute value | 
 +| sin(Expr) ​        ​| ​    ​trigonometric sine | 
 +| cos(Expr) ​         |   ​trigonometric cosine ​ |
 +| tan(Expr) ​   |         ​trigonometric tangent ​ |
 +| pow(Expr,​Expr) ​ |  raise to the power  |
 +| exp(Expr,​Expr) ​ |  raise to the power  |
 +| min(Expr,​Expr) ​ |  minimum of the two arguments | 
 +| max(Expr,​Expr) ​  | maximum of the two arguments | 
 +
 +
 + 
 +
 +Ograniczenia:​\\
 +
 +^Ograniczenia ^Opis ^
 +| Expr =:= Expr  | equation| ​    
 +| Expr  =  Expr  | equation| ​    
 +| Expr  <  Expr  | strict inequation |     
 +| Expr  >  Expr  | strict inequation| ​    
 +| Expr =<  Expr  | nonstrict inequation| ​    
 +| Expr >=  Expr   | nonstrict inequation |    ​
 +| Expr =\= Expr   | disequation |   
 +
 +
 +
 +Wyjątek pomiędzy bibliotekami stanowi predykat: **bb_inf/4 w CLP(Q) i bb_inf/5 w CLP(R)**.Predykaty te obliczają kres dolny wyrażenia. Różnią się jedynie tym, że dla liczb rzeczywistych określamy jeszcze ​ zakres dla którego liczba będzie zaokrąglana do liczby całkowitej.\\ ​
 +
 +Używanie dwóch bibliotek jest dozwolone w jednym programie, jednak trzeba je zadeklarować oddzielnie. Błędy w działaniu programu pojawiają się, gdy dla tych samych zmiennych stosujemy predykaty z różnych bibliotek.
 +
 + 
 +  ​
 + 
 + 
 +
 +
 ===== Wady CLP ===== ===== Wady CLP =====
 +Biblioteka CLP pomimo swojej złożoności ​ i wielu dodatkowych modułów ​ z których programiści mogą korzystać często nie wystarcza by szybko i wydajnie rozwiązywać złożone problemy.\\
 + W celu zmodyfikowania istniejących ograniczeń lub stworzenia nowych, dokładniejszych reguł został stworzony specjalny język programowania **CHR (z ang. Constraint Handling Rules)**, który umożliwia szybsze tworzenie programów i ich optymalizację. ​
 +
 ====== CHR -Constraint Handling Rules ====== ====== CHR -Constraint Handling Rules ======
 +
 +**CHR** jest __deklaratywnym językiem programowania__,​ który ​ został stworzony przez Thom Frühwirth w 1991 roku.  Jest używany jako język wysokiego poziomu do rozwiązywania takich problemów jak:
 +  *  weryfikacja danych
 +  *  rozumowanie abdukcyjne
 +  *  systemy wieloagentowe
 +  *  analiza języka naturalnego , czy kompilacji.\\
 + ​Język Constraint Handling Rules jest zaimplementowany w SWI-Prologu i dostępny od wersji 5.6.0.\\
 +\\
 +Dołączenie biblioteki następuje poprzez:
 +<​code>:​- use_module(library(chr)).</​code>​\\
 +
 +**Przykład:​** \\
 +Ponizszy przykład przedstawia zasadę działania CHR. Pokazuje w jaki sposób określić znak  nierówności ≤ (http://​www.sics.se/​sicstus/​docs/​3.7.1/​html/​sicstus_34.html#​SEC290):​\\
 +
 +<​code>:​- use_module(library(chr)).
 +
 +handler leq.
 +constraints leq/2.
 +:- op(500, xfx, leq).
 +
 +reflexivity ​ @ X leq Y <=> X=Y | true.
 +antisymmetry @ X leq Y , Y leq X <=> X=Y.
 +idempotence ​ @ X leq Y \ X leq Y <=> true.
 +transitivity @ X leq Y , Y leq Z ==> X leq Z.</​code>​
 +
 +Jak widzimy reguła składa się z 4 części : __zwrotności,​ antysymetrii,​ idempotentności i przechodniości__. Ich nazwy poprzedzają znak @, a po nich występują predykaty zdefiniowane przez użytkownika (heads), wbudowane (guards) lub oba rodzaje ograniczeń (body), definiujące własności relacji. \\
 +
 +
 +Ciekawy jest sposób wywołania funkcji:\\
 +<​code>?​- leq(X,Y), leq(Y,Z). </​code>​
 +
 +Jako wynik działania otrzymujemy Yes, co oznacza, że dla X≤Y, Y≤Z to **X≤Z**.
 +
 ===== Program z przykładami ===== ===== Program z przykładami =====
-==== Przykłady ==== 
 ==== Implementacja ==== ==== Implementacja ====
 +Projekt został napisany w Javie z wykorzystaniem SWI Prolog’u.
 +Funkcje, które realizuje aplikacja to:\\
 +* Obliczanie wartości silni
 +  * Obliczanie n-tego wyrazu ciągu Fibonacciego
 +  * Obliczanie pierwiastków równania kwadratowego
 +  * Obliczanie kolorów dla 6 zdefiniowanych państw
 +  * Problem plecakowy
 +  * Problem n-królowej
 +
 +
 +
 +
 +==== Interfejs użytkownika ====
 +Interfejs użytkownika został stworzony przy pomocy biblioteki SWING.\\
 +{{:​pl:​miw:​2009:​asia1.png|}}\\
 +Wynik działania dla problemu plecakowego:​\\
 +{{:​pl:​miw:​2009:​asia2.png|}}
 +
 ====== Sekwencjonowanie DNA ====== ====== Sekwencjonowanie DNA ======
 ===== Teoria ===== ===== Teoria =====
 +**Sekwencjonowanie DNA** to procedura w której odczytuje się dokładną kolejność zasad (A, C, T i G) tworzących cząsteczkę DNA.\\
 +Przykład sekwencji DNA (początek operonu laktozowege E. coli):\\
 +   <​code>​ GACACCATCGAATGGCGCAAAACCTTTCGCGGTATGGCATGATAGCGCCCGGAAGAGAGTCAATTCAGGG</​code>​\\
 +
 +Poniższy rysunek przedstawia etapy sekwencjonowanie DNA.\\
 +{{:​pl:​miw:​2009:​asia3.gif|}}\\
 +Źródło:​http://​www.scq.ubc.ca/​genome-projects-uncovering-the-blueprints-of-biology/​ \\
 +
 +Obecnie metoda odczytu została zautomatyzowana dzięki wykorzystaniu znakowanych fluorescencyjnie trifosforanów dideoksynukleotydów i pozwala na odczyt 300-1000 par zasad z jednej kapilary lub linii na żelu.\\
 +Autorem alternatywnej metody sekwencjonowania DNA, z wykorzystaniem specyficznej,​ chemicznej degradacji DNA, byli Walter Gilbert i Allan Maxam (metoda Maxama-Gilberta). Gilbert wraz z Frederickiem Sangerem otrzymali za to osiągnięcie nagrodę Nobla. Metoda Maxama-Gilberta obecnie jest rzadko stosowana.\\
 +Nowoczesne masowo równoległe aparaty do sekwencjonowania DNA są w stanie pracować z szybkością rzędu milionów par zasad na godzinę. Tranzystory polowe DNA umożliwiają użycie natywnego DNA w hybrydyzacji do mikromacierzy i odczyt w czasie rzeczywistym.\\
 +
 +**Diagnostyka genetyczna** jest prężnie rozwijającą się dziedziną, wykorzystującą najnowsze osiągnięcia technologiczne,​ naukowe, informatyczne i medyczne. ​ Dzięki postępowi który dokonał się w ostatnich latach możliwe jest przeprowadzenie badań i uzyskanie istotnych informacji medycznych wyprzedzających kliniczne pojawienie się schorzenia. Jest to bardzo istotny aspekt dla zdrowia pacjenta. Dzięki niemu może jeszcze przed pojawieniem się choroby- najczęściej śmiertelnej- jej zapobiec. Mając do dyspozycji narzędzie w postaci testów genetycznych można z dużym prawdopodobieństwem określić ryzyko zachorowania,​ uzupełnić i potwierdzić obecność dziedzicznego obciążenia genetycznego,​ a przede wszystkim rozpocząć odpowiednią terapię lub po prostu częściej przeprowadzać badania kontrolne. \\
 +Obecnie podczas testowania genetycznego możemy wykryć mutacje/​zmiany powodujące takie choroby jak na przykład:
 +• czerniak złośliwy\\
 +• rak piersi\\
 +• rak prostaty\\
 +• choroby nowotworowe\\
 +• HPV\\
 +• Rak tarczycy\\
 +• Mukowiscydoza\\
 +• Alzheimer\\
 +
 ===== Implementacja sekwencjonowania DNA w PROLOGu ===== ===== Implementacja sekwencjonowania DNA w PROLOGu =====
 ==== Wybór środowiska ==== ==== Wybór środowiska ====
 +Projekt został napisany w Javie z wykorzystaniem SWI Prolog’u.\\
 +Funkcje, które realizuje aplikacja to:\\
 +• Tworzenie komplementarnej nici DNA\\
 +• Porównywanie dwóch nici - czy są komplementarne\\
 +• Sprawdzanie,​ czy w sekwencji DNA znajduje się odpowiednia/​dowolna sekwencja\\
 +• Próba rozpoznawania mukowiscydozy\\
 +• Rozpoznawanie guzowatości korzenia na podstawie sekwencji DNA \\
 +• Rozpoznawanie błędów addycji/​delecji/​inwersji \\
 +
 +**Rozpoznawanie guzowatości korzenia na podstawie sekwencji DNA** \\
 +Rozpoznanie guzowatości korzenia( crown Gall tumor) następuje poprzez znalezienie sekwencji „TATA box”. TATA box jest to sekwencja w której znajdują się tylko zasady azotowe takie jak: adenina (A) oraz tymina (T). \\
 +TATA Box może mieć postać: TATA. TAATA, AATAATa,​AATATA,​ATATA\\
 +
 +**Rozpoznawanie ​ mutacji segmentowych -błędów addycji/​delecji/​inwersji** ​
 + 
 +Do __mutacji segmentowych/​punktowych__ zaliczamy- __addycję, delecję oraz inwersję__. Wszystkie z tych zmian charakteryzują się najczęściej występowaniem tych samych zasad azotowych obok siebie. Mutacje punktowe mogą powodować takie choroby jak:  albinizm, anemię sierpowatą czy hemofilię.\\
 +{{:​pl:​miw:​2009:​asia3.png|}}\\
 +Źródłow: Wykłady MSIB AGH  \\
 +**Porównywanie dwóch nici - czy są komplementarne** \\
 +Brak komplementarności nici powoduje mutacje np. nowotworowe i powoduje niewłaściwe kodowanie białek.\\
 +**Próba rozpoznawania mukowiscydozy**\\
 +Powodem mukowiscydozy jest mutacja odcinka genomu CFTR. Odcinek zmutowany nazywamy: ∆F508.
 +{{:​pl:​miw:​2009:​asia4.png|}}\\
 +Źródło: http://​genome.gsc.riken.go.jp/​hgmis/​posters/​chromosome/​cftr.html \\
 + 
 +
 +
 ==== Interfejs użytkownika ==== ==== Interfejs użytkownika ====
 +**Wybór środowiska** \\
 +Projekt ​ napisany w języku JAVA, przy użyciu biblioteki graficznej Swing zintegrowany z SWI Prolog. Program charakteryzuje się modułową budową, umożliwiającą dodawanie funkcjonalości (na przykład nowych sposobów ekstrakcji cech). \\
 +**Interfejs użytkownika** \\
 +Interfejs użytkownika powstał dzięki wykorzystaniu biblioteki Java Swing. Interfejs użytkownika składa się z siedmiu paneli i pozwala na intuicyjne poruszanie się między nimi. \\
 +
 +Po uruchomieniu aplikacji mamy możliwość zapoznania się z możliwościami aplikacji:
 +{{:​pl:​miw:​2009:​asia5.png|}}\\
 +Przykład dla nici komplementarnej:​\\
 +{{:​pl:​miw:​2009:​asia6.png|}}\\
 +
 +Przykład dla rozpoznawania sekwencji mukowiscydozy:​\\
 +{{:​pl:​miw:​2009:​asia7.png|}}\\
 +
 ====== Podsumowanie ====== ====== Podsumowanie ======
 +Prolog wykorzystuje szereg technologii w celu optymalnego rozwiązywania skomplikowanych problemów. Programista może skorzystać z CLP, CHR ale także z clpfd, clp_distinct,​ czy modułu Simplex. Pomimo tego, że Prolog został stworzony w 1971 roku nadal prężnie się rozwija i rozszerza moduły. ​ Prolog jest zaawansowanym a zarazem prostym językiem programowania. Umożliwia pisanie długich skomplikowanych programów w dosłownie kilku linijkach.\\
 +**Zastosowanie Prolog’a :**\\
 +
 +• Inteligentne Systemy - programy, które wykonują przydatne zadania przez używanie technik sztucznej inteligencji. \\
 +
 +
 +• Systemy ekspertowe - inteligentne systemy, które potrafią podejmować decyzje na poziomie ludzkiego eksperta. \\
 +
 +• Naturalne systemy językowe - które mogą analizować i odpowiadać na zadane pytania w formie zrozumiałej dla człowieka\\ ​
 +
 +• Systemy relacyjnej bazy danych \\
 +
 +**Ciekawe gotowe produkty:​**\\
 +
 +• “Expert System for Selecting Chemical Processing Agitators” (AstraZeneca) – system ekspertowy pomocny chemikom przy mieszaniu różnych substancji\\
 +
 +• "Tax Assistant” (VerTec Solutions) – asystent podatkowy \\
 +
 +• Intelligent Testing (Pacific AI) – narzędzie do treningu i testowania wiedzy (np. studenta) \\
 +
 +• Virtual Pal - First Seamless Natural Language Self-Help (APIIT ) – Ekspert pomagający na stronie WWW \\
 +
 +• Breast Cancer Decision Guide – Internetowy doradca w sprawach raka piersi \\
 +
 +• Configuration Advice (Xircom Inc.) – Doradca w sprawach konfiguracji sprzętu komputerowego \\
 +
 +• FleetPlan – system ekspercki dla sieci lotniczych, który ostatecznie ma „zwiększyć” zyski firmy lotniczej \\
 +
 +• PDC-Booking - system skutecznego zarządzania zasobami całego szpitala (wykorzystanie personelu, sprzętu, pokojów,​etc.) \\
 +
 +
 +====== Źródła ======
 +===== Dokumentacja =====
 +===== Źródła kodów =====
 +  - Źródło dla aplikacji -przykłady\\
 +{{:​pl:​miw:​2009:​prolog.rar|}}\\
 +  - Źródło dla aplikacji -sekwencjonowanie DNA\\
 +{{:​pl:​miw:​2009:​sekwencjonowanie.rar|}}\\
 +
 +
 +
  
  
pl/miw/2009/piw09_clp.1244457065.txt.gz · ostatnio zmienione: 2017/07/16 23:25 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0