Różnice

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

Odnośnik do tego porównania

pl:miw:2009:piw09_clp [2009/06/07 19:17]
piw09
pl:miw:2009:piw09_clp [2017/07/17 10:08]
Linia 1: Linia 1:
-====== Opis ====== 
-Joanna Jaworek, [[jaworek.joanna@gmail.com]] \\ 
-**Temat: Programowanie z wykorzystaniem ograniczeń CLP. Sekwencjonowanie DNA- projekt z wykorzystaniem biblioteki JPL swi-prolog.** 
- 
-====== Wstęp ====== 
-Niniejsza praca składa się z sześciu rozdziałów:​ programowanie logiczne, programowanie logiczne z ograniczeniami,​ CHR, problemy NP-trudne, sekwencjonowanie DNA oraz podsumowanie. Celem pierwszych dwóch rozdziałów jest przedstawienie koncepcji programowania w prologu oraz zaprezentowanie kilku zaimplementowanych przykładów. Rozdział trzeci przedstawia ciekawe wykorzystanie programowania CLP/CHR do rozwiązywania problemów NP-trudnych,​ czyli o dużej złożoności czasowej. Tutaj także zaprezentuję aplikację umożliwiającą testowanie programów. Rozdział czwarty odwołuje się do ostatnich nowinek ze świata nauki, które pokładają dużą nadzieję w sekwencjonowanie DNA właśnie w prologu. Rozdział ten także zawiera moją własną implementację prostego sekwencjonowanie DNA. Ostatni rozdział to podsumowanie referatu oraz przedstawienie innych ​ implementacji platform oraz narzędzi opartych na CLP. 
- 
-====== Programowanie logiczne ====== 
-===== Teoria ===== 
-Programowanie logiczne narodziło się  na początku lat 70-tych jako rezultat wcześniejszych prac w zakresie automatycznego dowodzenia twierdzeń i sztucznej inteligencji. Jednak dopiero w chwili opracowania języka PROLOG nabrało walorów praktycznej użyteczności. Metoda programowania w języku logiki stała się podstawą opracowanie języka maszynowego oraz języka programowania wiedzy. Podstawową cechą odróżniającą programowanie logiczne od konwencjonalnych technik programowania jest reprezentowanie wiedzy w sposób jawny, niezwiązany ze sposobem jej użycia w celu rozwiązania problemów drogą rozumowania dedukcyjnego. Pojęcie programowania logicznego jest często źle zdefiniowane. Według Roberta Kowalskiego,​ będącego jednym z głównych twórców teorii programowania logicznego, opiera się ona na dwóch podstawowych założeniach:​\\ 
- ​  ​ * Traktowanie logiki jako języka programowania\\ 
- ​  ​ * Oddzielenie logiki programu od sterowania 
- 
- 
-===== Prolog a programowanie w logice ===== 
-Język programowania PROLOG będący jednym z najbardziej rozpowszechnionych systemów programowania w języku logiki oparty jest w zasadniczej części na języku klauzul Horna, który stanowi podzbiór języka klauzulowego postaci logiki. \\ 
- 
-Szereg technologii wykozystywanych jest w Prolog'​u w celu ułatwienia programowania w logice. Należą do nich m.in. CLP,​CLP(FD),​CLP(QR),​CHR.\\ 
- 
-====== Constraint logic programming -programowanie z ograniczeniami ====== 
-===== Teoria ===== 
-Programowanie logiczne z ograniczeniami (//​Constraint Logic Programming CLP//) stało się w ostatnich latach popularnym sposobem modelowania i rozwiązywania wielu problemów z dziedziny:​\\ 
- ​  ​ * sztucznej inteligencji\\ 
- ​  ​ * problemów kombinatorycznych\\ 
- ​  ​ * przetwarzania mowy\\ 
- ​  ​ * harmonogramowania\\ 
- ​  ​ * przetwarzania języków naturalnych (konstruowanie efektywnych parserów)\\ 
- ​  ​ * systemów baz danych (zapewnienie spójności danych)\\ 
- ​  ​ * biologii molekularnej (sekwencjonowanie DNA)\\ 
- ​  ​ * inżynierii elektronicznej (lokalizacja błędów)\\ 
- ​  ​ * projektowania obwodów drukowanych\\ 
- 
-Jego główną zaletą jest deklaratywność,​ czyli sformułowanie zadania jest od razu programem rozwiązującym to zadanie. Programowanie to bazuje na modelowaniu zadania jako problemu spełnienia ograniczeń (Constraint Satisfacton Problem CSP). Ograniczenia są zależne od dziedzin zmiennych, których dotyczą. Najpopularniejszą i pierwszą dziedziną zmiennych była skończona dziedzina liczb naturalnych. Innymi dziedzinami są: skończone zbiory, drzewa, rekordy, przedziały rzeczywiste. Najistotniejszą cechą i największą zaleta programowania z ograniczeniami jest ich propagacja . 
- 
-===== Propagacja ograniczeń ===== 
-Propoagacja ograniczeń sprawiła, że ta technika stała się najlepsza metodą dla wielu problemów kombinatorycznych. Zasadą działania propagacji jest usuwanie wartości nie spełniających ograniczeń z domen zmiennych. Języki do programowania z ograniczeniami mają możliwość wyrażania zmiennych z zakresu domen liczb naturalnych (najczęściej stosowane), przedziałów liczb rzeczywistych,​ zbiorów i innych.\\ 
- ​Przykład:​\\ 
-x €{1..5}, y €{1..6}\\ 
-Gdy na powyższe dwie zmienne wprowadzimy ograniczenie\\ 
- ​x>​y+1,​ wtedy\\ 
-propagacja ograniczeń zredukuje powyższe domeny do następujących wartości:​\\ 
-x €{3, 4, 5}, y €{1, 2, 3}\\ 
-ponieważ wartości {1, 2} z domeny x nie spełniają ograniczenia x>y+1 dla żadnej z wartości z domeny y. Podobnie można rozpatrywać wartości {4, 5, 6} z domeny y. Jednak możemy wprowadzić takie ograniczenie jak x+y=6, które nie usuwa żadnych wartości z domen. Ograniczenia nie są zazwyczaj tak proste ja to przedstawiono,​ często łączą ze sobą wiele zmiennych, a metody usuwania poszczególnych wartości, zwane algorytmami filtracyjnymi są bardzo złożone. Sama propagacja z ograniczeniami rzadko daje rozwiązanie. Dlatego jest ona zawsze łączona z dystrybucją i poszukiwaniem. 
- 
-===== Dystrybucja i poszukiwanie ===== 
-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:​\\ 
- ​  ​ * 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\\ 
- 
-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. ​ 
- 
-===== Ograniczenia ===== 
- 
- 
-Wyróżniamy następujące ograniczenia:​\\ 
-  * **arytmetyczne**(porównywanie dwóch liczb: ≤, ≥, ≠,​=,<,>​)\\ 
-  * **logiczne**:​\(#​\ Q-zaprzeczenie,​ P #/\ Q -and, P#/Q -xor, P #\/ Q-or)\\ 
-  * dziedziny ograniczone- np. liczby całkowite, naturalne, specyfikacja dziedziny poprzez wypisanie wszystkich elementów\\ 
-  * drzewa i listy 
- 
- 
- 
- 
-===== Moduły CLP ===== 
-==== clpfd (Constraint Programming Language over Finite Domains) ==== 
-==== clp_distinct ==== 
-==== CLP(Q,R) Constraint Logic Programming over Rationals or Reals ==== 
-===== Wady CLP ===== 
-====== CHR -Constraint Handling Rules ====== 
-===== Program z przykładami ===== 
-==== Przykłady ==== 
-==== Implementacja ==== 
-====== Sekwencjonowanie DNA ====== 
-===== Teoria ===== 
-===== Implementacja sekwencjonowania DNA w PROLOGu ===== 
-==== Wybór środowiska ==== 
-==== Interfejs użytkownika ==== 
-====== Podsumowanie ====== 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
- 
  
pl/miw/2009/piw09_clp.txt · ostatnio zmienione: 2019/06/27 15:50 (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