Programowanie dynamiczne

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Programowanie dynamiczne – technika lub strategia projektowania algorytmów, stosowana przeważnie do rozwiązywania zagadnień optymalizacyjnych. Jest alternatywą dla niektórych zagadnień rozwiązywanych za pomocą algorytmów zachłannych. Wynalazcą techniki jest amerykański matematyk Richard Bellman, uhonorowany za to odkrycie medalem (ang. IEEE Medal of Honor) przez IEEE w 1979 roku.

Własność optymalnej podstruktury – jest własnością problemów, które można rozwiązywać za pomocą algorytmów. Mówi się, że dany problem ma własność optymalnej podstruktury, jeżeli jego optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów.Najdłuższy wspólny podciąg (NWP, ang. longest common subsequence) – najdłuższy podciąg znaków, które występują w tej samej kolejności w dwóch porównywanych łańcuchach. Elementy podciągów nie muszą przy tym leżeć obok siebie (tym różni się ten problem od problemu najdłuższego wspólnego podłańcucha, ang. longest common substring). Rozwiązanie tego problemu jest bardzo przydatne przy pisaniu programów mających na celu wykrycie zmian w dokumentach lub plikach, lub przy pisaniu programów służących do identyfikacji plagiatów.

Programowanie dynamiczne opiera się na podziale rozwiązywanego problemu na podproblemy względem kilku parametrów. W odróżnieniu od techniki dziel i zwyciężaj podproblemy w programowaniu dynamicznym nie są rozłączne, ale musi je cechować własność optymalnej podstruktury. Zagadnienia odpowiednie dla programowania dynamicznego cechuje również to, że zastosowanie do nich metody siłowej (ang. brute force) prowadzi do ponadwielomianowej liczby rozwiązań podproblemów, podczas gdy sama liczba różnych podproblemów jest wielomianowa.

Algorytm pseudowielomianowy – algorytm, którego czas działania jest ograniczony przez wielomian od wielkości wejścia, przy założeniu, że wejście jest zapisane w sposób unarny. Równoważnie: jest to algorytm, którego czas działania jest ograniczony przez wielomian od wielkości wejścia i maksymalnej wartości liczbowej występującej w opisie problemu.Algorytm Viterbiego – algorytm dekodujący opracowany przez Andrew Viterbiego i opublikowany przez niego w 1967 roku w IEEE Transactions on Information Theory, IT-13 w artykule Error bounds for convolutional codes and an asymptotically optimum decoding algorithm (str. 260-269).

Zazwyczaj jednym z parametrów definiujących podproblemy jest liczba elementów znajdujących się w rozpatrywanym problemie, drugim jest pewna wartość liczbowa, zmieniająca się w zakresie od 0 do największej stałej występującej w problemie. Możliwe są jednak bardziej skomplikowane dobory parametrów, a także większa ich liczba. Ponieważ jednak uzyskiwany algorytm zazwyczaj wymaga pamięci (i czasu) proporcjonalnego do iloczynu maksymalnych wartości wszystkich parametrów, stosowanie większej ilości parametrów niż 3-4 rzadko bywa praktyczne.

Biblioteka Narodowa Izraela (hebr. הספרייה הלאומית; dawniej: Żydowska Biblioteka Narodowa i Uniwersytecka, hebr. בית הספרים הלאומי והאוניברסיטאי) – izraelska biblioteka narodowa w Jerozolimie.Library of Congress Control Number (LCCN) – numer nadawany elementom skatalogowanym przez Bibliotekę Kongresu wykorzystywany przez amerykańskie biblioteki do wyszukiwania rekordów bibliograficznych w bazach danych i zamawiania kart katalogowych w Bibliotece Kongresu lub u innych komercyjnych dostawców.

Klucz do zaprojektowania algorytmu tą techniką leży w znalezieniu równania rekurencyjnego opisującego optymalną wartość funkcji celu dla danego problemu jako funkcji optymalnych wartości funkcji celu dla podproblemów o mniejszych rozmiarach. Programowanie dynamiczne znajduje optymalną wartość funkcji celu dla całego zagadnienia, rozwiązując podproblemy od najmniejszego do największego i zapisując optymalne wartości w tablicy. Pozwala to zastąpić wywołania rekurencyjne odwołaniami do odpowiednich komórek wspomnianej tablicy i gwarantuje, że każdy podproblem jest rozwiązywany tylko raz. Rozwiązanie ostatniego z rozpatrywanych podproblemów jest na ogół wartością rozwiązania zadanego zagadnienia.

Optymalizacja (matematyka), w matematyce termin optymalizacja odnosi się do problemu znalezienia ekstremum (minimum lub maksimum) zadanej funkcji celu.Problem P (ang. deterministic polynomial - deterministycznie wielomianowy) to problem decyzyjny, dla którego rozwiązanie można znaleźć w czasie wielomianowym.

Niejednokrotnie stosowanie techniki programowania dynamicznego daje w rezultacie algorytm pseudowielomianowy. Programowanie dynamiczne jest jedną z bardziej skutecznych technik rozwiązywania problemów NP-trudnych. Niejednokrotnie może być z sukcesem stosowana do względnie dużych przypadków problemów wejściowych, o ile stałe występujące w problemie są stosunkowo nieduże. Na przykład w przypadku dyskretnego zagadnienia plecakowego jako parametry dynamiczne w metodzie programowania dynamicznego należy przyjąć rozmiar kolejno rozpatrywanych podzbiorów elementów oraz rozmiar plecaka, zmieniający się od 0 do wartości B danej w problemie.

Algorytm siłowy, algorytm brute force (ang. "brutalna siła" tj. niewspomagana umysłem) – określenie algorytmu, który opiera się na sukcesywnym sprawdzeniu wszystkich możliwych kombinacji w poszukiwaniu rozwiązania problemu, zamiast skupiać się na jego szczegółowej analizie.W teorii złożoności obliczeniowej problem NP-trudny (NPH) to taki problem obliczeniowy, którego rozwiązanie jest co najmniej tak trudne jak rozwiązanie każdego problemu z klasy NP.

Programowanie dynamiczne może być również wykorzystywane jako alternatywna metoda rozwiązywania problemów zaliczanych do klasy P, o ile złożoność algorytmu wielomianowego nie jest satysfakcjonująca, a w praktyce, nawet dla dużych instancji problemu, wartości liczbowe występujące w problemie są niewielkie.

IEEE (ang. Institute of Electrical and Electronics Engineers – Instytut Inżynierów Elektryków i Elektroników, wymowa: ‘Eye-triple-E’) – organizacja typu non-profit skupiająca profesjonalistów. Powstała z konsolidacji grup AIEE oraz IRE w 1963 roku. Jednym z podstawowych jej zadań jest ustalanie standardów konstrukcji, pomiarów itp. dla urządzeń elektronicznych, w tym standardów dla urządzeń i formatów komputerowych.Biblioteka Narodowa Francji (fr. Bibliothèque nationale de France, BnF) – francuska biblioteka narodowa, znajdująca się w Paryżu. Przewidziana jest jako repozytorium dla wszystkich materiałów bibliotecznych, wydawanych we Francji. Obecnym dyrektorem Biblioteki jest Bruno Racine.

Przykłady zastosowań[ | edytuj kod]

Algorytmy programowania dynamicznego są stosowane między innymi w informatyce, matematyce, bioinformatyce, ekonomii, i logistyce. Oto niektóre przykłady zastosowań programowania dynamicznego:

  • Algorytm CYK
  • Algorytm Viterbiego
  • algorytmy znajdujące najdłuższy wspólny podciąg
  • algorytmy rozwiązujące zagadnienie plecakowe
  • Algorytm Earleya
  • znajdowanie rozwiązania problemu optymalnego nawiasowania macierzy
  • Algorytm Floyda-Warshalla
  • obliczanie odległości Levenshteina
  • Algorytm Needlemana-Wunscha (dopasowywanie ciągów)
  • Wybór instrukcji niskiego poziomu w kompilatorach (ang. instruction selection)
  • algorytm znajdujący cykl Hamiltona (problem komiwojażera)
  • estymatory wielopunktowe funkcji skojarzonych Buchalskiego (dyskretyzacja wielomianowa)
  • Bibliografia[ | edytuj kod]

  • Richard Bellman. On the Theory of Dynamic Programming. Proceeding of the National Academy of Sciences (USA). 1952.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 2001. Introduction to Algorithms, 2nd ed. MIT Press & McGraw-Hill. ISBN 0-262-03293-7. Zwłaszcza rozdział 15: 323–69. (klasyczny wykład podręcznikowy na poziomie podstawowym)
  • Juraj Hromkovič. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. 2nd ed. Springer Verlag 2004. ISBN 3-540-44134-4. Rozdział 3.2: 152–7 (zwięzła prezentacja teoretyczna)
  • Kompilator – program służący do automatycznego tłumaczenia kodu napisanego w jednym języku (języku źródłowym) na równoważny kod w innym języku (języku wynikowym) . Proces ten nazywany jest kompilacją. W informatyce kompilatorem nazywa się najczęściej program do tłumaczenia kodu źródłowego w języku programowania na język maszynowy. Niektóre z nich tłumaczą najpierw do języka asemblera, a ten na język maszynowy jest tłumaczony przez asembler.Algorytm Earleya – w informatyce algorytm służący do analizy składniowej na podstawie dowolnej gramatyki bezkontekstowej. Stosuje się go między innymi do przetwarzania języków naturalnych, gdyż inaczej niż większość algorytmów analizy składniowej działa również z gramatykami niejednoznacznymi. Korzysta się też z niego przy tworzeniu interpreterów i kompilatorów języków programowania, zwłaszcza języków specjalizowanych, ponieważ szkielety projektowe oparte na tym algorytmie ułatwiają szybkie tworzenie prototypów (RAD)




    Warto wiedzieć że... beta

    Odległość Levenshteina (edycyjna) – miara odmienności napisów (skończonych ciągów znaków), zaproponowana w 1965 roku przez Władimira Lewensztejna.
    Wielka Encyklopedia Rosyjska (ros. Большая российская энциклопедия, БРЭ) – jedna z największych encyklopedii uniwersalnych w języku rosyjskim, wydana w 36 tomach w latach 2004–2017. Wydana przez spółkę wydawniczą o tej samej nazwie, pod auspicjami Rosyjskiej Akademii Nauk, na mocy dekretu prezydenckiego Władimira Putina nr 1156 z 2002 roku
    Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.
    Paradygmat programowania (ang. programming paradigm) — wzorzec programowania komputerów przedkładany w danym okresie rozwoju informatyki ponad inne lub szczególnie ceniony w pewnych okolicznościach lub zastosowaniach.
    Dyskretny problem plecakowy (ang. discrete knapsack problem) jest jednym z najczęściej poruszanych problemów optymalizacyjnych. Nazwa zagadnienia pochodzi od maksymalizacyjnego problemu wyboru przedmiotów, tak by ich sumaryczna wartość była jak największa i jednocześnie mieściły się w plecaku. Przy podanym zbiorze elementów o podanej wadze i wartości, należy wybrać taki podzbiór by suma wartości była możliwie jak największa, a suma wag była nie większa od danej pojemności plecaka.
    Algorytm Floyda-Warshalla służy do znajdowania najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków w grafie ważonym.
    Hiszpańska Biblioteka Narodowa (Biblioteca Nacional de España) – największa biblioteka w Hiszpanii i jedną z największych na świecie. Znajduje się w Madrycie, a dokładnie przy Paseo de Recoletos.

    Reklama