Wykres wzrostu szybkości komputerów na przestrzeni lat źródło własne

Przy tym nie musimy brać pod uwagę możliwości najnowszej generacji komputerów zwanych kwantowymi, które to zawrotne tempo rozwoju informatyki jeszcze podkręcą.

Mimo wszystko jednak nadal musimy do rozwiązywania problemów z użyciem komputerów podchodzić z pokorą, jaką wykazał Alan Turing.

W 1936 r. dowiódł, że zaproponowany przez niego teoretyczny model komputera nie rozwiąże zaproponowanego przez niego problemu matematycznego.

W ten sposób wykazał tzw. nierozstrzygalność problemu. Okazało się, że model komputera nazwany wkrótce Maszyną Turinga stanowi uniwersalne uogólnienie wszystkich klasycznych (niekwantowych) komputerów. Obecnie jego znajomość to wymóg stawiany wszystkim studentom pierwszych lat informatyki. Dzisiaj częściej trafiamy na problemy, które co prawda da się rozwiązać w skończonym czasie, ale ten czas nawet w przypadku najszybszych komputerów wymaga całych lat obliczeń.

Te pierwsze odkrywamy, gdy znajdujemy dla niego algorytm wielomianowy, a drugie zazwyczaj, gdy dowiedziemy jego silnego (wielomianowe) powiązania z problemem wcześniej sklasyfikowanym jako trudny. Pionierem takiego podejścia na Politechnice Poznańskiej jest prof. Błażewicz, którego rozprawa habilitacyjna była dla mnie jako studenta doskonałym podręcznikiem złożoności obliczeniowej.

Obrazują to dwa przykładowe problemy z zupełnie różnych, ale bardzo współczesnych dziedzin zastosowań informatyki, które natchnęły naukowców informatyków z Instytutu Informatyki Politechniki Poznańskiej do wyznaczania dla nich tych granic.

Jak tanio zrobić duże zakupy?

Krótka odpowiedź dla większości wydaje się oczywista – kupuj w Internecie. Problem do rozwiązania najlepiej demonstruje zadanie, jakie w 2016 r. mieli do rozwiązania uczestnicy szkolnego konkursu KOALA.

W poniższej tabeli na przecięciu kolumn z kolejnymi sklepami i wierszy z tytułami książek znajdują się ceny danego tytułu oferowanego w danym sklepie:

Ponadto zryczałtowane koszty dostawy towarów wynoszą w każdym sklepie 4 zł i są niezależne od liczby kupowanych w nim towarów.

Pod względem matematycznym problem sprowadza się do znalezienia takiego przypisania każdego artykułu do sklepu, w którym będzie on kupowany, aby suma cen zakupu towarów plus suma kosztów dostawy była jak najmniejsza. Takich możliwości dla n sklepów i m towarów jest łącznie m do potęgi n.

W naszym przykładzie będzie to 10 miliardów cykli obliczeniowych, co przełoży się na siedem godzin obliczeń w środowisku Python.

Wynika z tego prosty, ale dla większych wartości m i n bardzo czasochłonny algorytm.

Analiza złożoności obliczeniowej tego problemu wykazała, że jest on obliczeniowo trudny, co oznacza, że praktycznie nie da się napisać programu, który znajdzie minimum w sensownym czasie dla problemów o dużej liczbie artykułów do kupienia i dużej liczbie sklepów. Nawet szybkie komputery mogą dla nich wymagać lat obliczeń. Dla takiego problemu i pokrewnych trzeba poszukiwać algorytmów co prawda suboptymalnych, ale szybkich.

Jak odczytać łańcuch DNA?

DNA i RNA składające się z długiego łańcucha czterech rodzajów zasad to podstawowy kod każdej istoty żyjącej na Ziemi. To on wyznacza różnice w budowie ciała pomiędzy gatunkami, ale również tymi spokrewnionymi. W przypadku ludzi nić DNA liczy około 3 miliardów takich elementów.

Z pewnym matematycznym uproszczeniem możemy założyć, że DNA to łańcuch znaków z jedynie czteroelementowego alfabetu: G, T, C i A.

Odczytywanie DNA, jako że to taki długi łańcuch, jest bardzo kłopotliwe. Metody czysto biochemiczne są zdolne do odczytywania jedynie kilkunastoelementowych łańcuchów DNA. Jak więc odczytać cały tak długi łańcuch?

Obecnie najpopularniejszą metodą jest hybrydyzacja, czyli dzielenie długich łańcuchów na krótsze.

Korzysta się wtedy ze specjalnych enzymów potrafiących podzielić dowolnie długi łańcuch na kilkunastoelementowe łańcuchy. Podziały dla poszczególnych łańcuchów różnią się i np. łańcuch: ACTACAG może zostać podzielony na wiele różnych sposobów (A,CT,AC,AG),(AC,TA,CAG),(AC,T,A,CA,G), które współistnieją w tym samym roztworze. Takie odcinki potrafi zeskanować specjalne urządzenie biochemiczne, tzw. czip, wczytując kodowanie tych odcinków DNA wprost do komputera.

Zatem przykładowe zadanie mogłoby wyglądać:

Dla odcinków: ACTA, CTAT, CGAC, ATACGA, ACGT, ACGA, GACG, TACG, GACTA, TATA, należy znaleźć najkrótszy łańcuch, z którego jednak można pojedynczo powycinać wszystkie odcinki składowe.

To przykładowe odcinki uzyskane po podziale DNA za pomocą specjalnych enzymów. Jego ręczne rozwiązanie jest możliwe, ale przebiega dosyć mozolnie i łatwo się pomylić. W prostym programie napisanym w Pythonie w celach popularyzacji programowania wśród nastolatków przykładowe wyniki sekwencjonowania DNA metodą hybrydyzacji prezentują się następująco:

GACTA

   TATA

       CGAC

  CTAT

      ACGA

    ATACGA

         ACGT

        GACG

     TACG

 ACTA

GACTATACGACGT

Okazuje się, że dla dokładnie tego problemu istnieje szybki algorytm znajdujący owo minimalne rozwiązanie. Jednak zwykle należy przyjąć, że w roztworze pojawiają się odcinki, których nie ma w oryginalnej sekwencji (tak zwane błędy dodatnie) i brakuje w nim odcinków, które powinny być (tak zwane błędy ujemne). Wtedy nasz problem staje się obliczeniowo trudny i trzeba stosować algorytmy przybliżone.

________

„Polscy naukowcy donoszą” to cykl artykułów na Wyborcza.pl. Zwróciliśmy się do profesorów, doktorów i asystentów, żeby zechcieli opowiedzieć naszym czytelnikom o swoich najnowszych dokonaniach, odkryciach, eksperymentach i wynalazkach zmieniających świat. Chcemy, żeby głos polskich naukowców był lepiej słyszalny.

Jeśli pracujecie Państwo naukowo i chcielibyście wystąpić w naszym cyklu, prosimy o kontakt na e-maila: naukagw@agora.pl.

Tekst publikujemy za zgodą wydawcy Gazety Wyborczej.