Używamy cookies i podobnych technologii m.in. w celu świadczenia usług i w celach statystycznych. Możesz określić warunki przechowywania lub dostępu do plików cookies w Twojej przeglądarce, w jej ustawieniach. Jeżeli wyrażasz zgodę na zapisywanie informacji zawartej w cookies, kliknij „Zamknij”. Jeżeli nie wyrażasz zgody – zmień ustawienia swojej przeglądarki.Więcej informacji znajdziesz w naszej Polityce cookies.

Zamknij informację o cookies
.

Ośrodek  Przetwarzania  Informacji  –  Państwowy  Instytut  Badawczy

Całkiem trudne zadanie: algorytm na oznaczenie całki

Obliczanie całki bywa procesem tyleż twórczym, co skomplikowanym. Maciejowi Kowalskiemu z OPI PIB udało się napisać program, który to upraszcza. Zadanie czekało na rozwiązanie ponad dekadę.

SPOJ http://spoj.com/ to największy na świecie serwis typu online judge, gdzie programiści mogą sprawdzić swoje umiejętności poprzez rozwiązywanie różnych problemów algorytmicznych. Na śmiałków czekają zadania o różnym stopniu trudności, które można rozwiązać w różnych językach programowania. Rozwiązaniem jest kod źródłowy programu w wybranym języku. Odpowiedzi wysyła się do serwisu poprzez specjalny formularz, a kod jest weryfikowany pod kątem czasu wykonania i jakości rozwiązania.

Przez kilkanaście lat istnienia SPOJ 725 tysięcy programistów z całego świata zgłosiło 24 miliony rozwiązań kilkudziesięciu tysięcy problemów programistycznych.

Nie wszystkie zadania szybko znajdują rozwiązanie. Zadanie DISCOVER było jednym z tych, na których rozwiązanie trzeba było poczekać ponad dekadę. Wyzwanie podejmowało niewielu programistów, a od roku 2008, kiedy je wystawiono, nikt nie zaproponował prawidłowego rozwiązania. Zapewne dlatego, że plasuje się na trzecim miejscu według wskaźnika trudności https://www.spoj.com/problems/challenge/sort=-7 (mierzonego odsetkiem prawidłowych rozwiązań).

Zadanie dotyczy obliczania całki oznaczonej, czyli istotnego zagadnienia liczącej już sobie 200 lat analizy matematycznej. Dokładny opis zadania można znaleźć na stronie SPOJ https://www.spoj.com/problems/DISCOVER/. Programiści muszą napisać kod, który będzie działał w przypadkach testowych i upora się z zadaniem w nie więcej niż 4 sekundy.

Dlaczego napisanie programu, który obliczałby całki, do tej pory się nie udało? Tłumaczy nam Maciej Kowalski, zastępca kierownika Laboratorium Inżynierii Lingwistycznej OPI PIB i specjalista badawczo-techniczny. – Problem DISCOVER można porównać do balansowania kijem na dłoni. Najpierw musimy rozwiązać problem parsowania, czyli przełożenia matematycznej notacji na język programowania. Potem jeszcze czeka nas problem z wyliczaniem całki. To jest drugi kij, który postawiliśmy na tym pierwszym.

Ta ekwilibrystyczna sztuka właśnie się Kowalskiemu udała. Po jedenastu latach od umieszczenia zadania na platformie SPOJ jako pierwszy zaproponował udane rozwiązanie problemu. – Pierwszym wyzwaniem, z którym musi się uporać programista, jest przełożenie matematycznego wzoru na język programowania. Matematyczny zapis wymusza pewną kolejność operacji, którą każdy zna jeszcze ze szkoły podstawowej (najpierw wykonujemy działania w nawiasach, potem potęgowanie i pierwiastkowanie, później mnożenie i dzielenie, a na końcu dodawanie i odejmowanie). Nie jest to sprawa prosta, zwłaszcza jeśli zadamy komputerowi złożoną funkcję – mówi Kowalski.

Kolejna sprawa to samo obliczanie całki – nie ma tu jednej metody. Algorytm (opracowany w 1968 r. przez matematyka i specjalistę od algebry komputerowej Roberta Henry’ego Rischa) pozwala sprawdzić, czy dana całka jest możliwa do obliczenia, i ją wyznaczyć. Często jednak takie obliczenia są zbyt długie i skomplikowane do praktycznych zastosowań. Całki pozwala też obliczyć na przykład Mathematica, oprogramowanie autorstwa Stephena Wolframa, które powstało w oparciu o język specjalnie stworzony do przekładania pytań w języku naturalnym na problemy rozwiązywalne przez komputery. Jednak jest na tyle złożone, że – jak podaje opis zadania DISCOVER na platformie SPOJ – „niewielu studentów jest w stanie opanować jego użycie”.

W praktyce zwykle całkuje się numerycznie, czyli oblicza całkę w przybliżeniu. W uproszczeniu można ją zdefiniować jako powierzchnię pola pod wykresem funkcji. Pole to można podzielić na niewielkie fragmenty, a potem obliczyć sumę pól wszystkich wąskich przedziałów pomiędzy wykresem funkcji a osią współrzędnych (istnieją metody prostokątów, trapezów, parabol oraz metody losowe). – Tu też czyhają pułapki. Jeśli chcemy całkę wyznaczyć z dużą dokładnością (DISCOVER zakładał, że z dokładnością do szóstego miejsca po przecinku), nasze prostokąty czy trapezy muszą być bardzo wąskie. Są funkcje, które w pewnych miejscach mają wartości nieskończone. Odpowiednio wąski przedział może więc trafić w miejsce, gdzie wartość całki będzie nieskończona. Nawet skończone, ale zbyt duże wartości mogą nie mieścić się w pamięci komputera (problem DISCOVER narzuca ograniczenie pamięci operacyjnej). Trzeba więc zachować delikatną równowagę między podziałem na odpowiednio wąskie przedziały, żeby obliczenie było dokładne, a uniknięciem zbyt dużych lub nieskończonych wartości – tłumaczy Kowalski.

Grafika: iStock by Getty Images