To jest stara wersja strony!


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

Ograniczenia

Arytmetyczne

Logiczne

Listy i liczby rzeczywiste

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.1244394349.txt.gz · ostatnio zmienione: 2019/06/27 15:58 (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