Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
Nowa wersja
Both sides next revision
|
pl:miw:2009:piw09_clp [2009/06/08 12:31] piw09 |
pl:miw:2009:piw09_clp [2009/06/08 13:53] piw09 |
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. |
| |
==== 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 ====== |
| |