Pisz programy z głową

Bardziej praktyczni informatycy szybko po ukończeniu studiów zapominają o teoretycznych podstawach swojej dziedziny. Tymczasem w rozwiązywaniu wielu problemów pomogłaby im wiedza o nierozstrzygalności zagadnień czy złożoności obliczeń.

Bardziej praktyczni informatycy szybko po ukończeniu studiów zapominają o teoretycznych podstawach swojej dziedziny. Tymczasem w rozwiązywaniu wielu problemów pomogłaby im wiedza o nierozstrzygalności zagadnień czy złożoności obliczeń.

W działalności naukowej Instytutu Informatyki Uniwersytetu Jagiellońskiego dużą wagę przykładamy do problemów teoretycznych, związanych z brakiem rozstrzygalności zagadnień informatycznych drogą algorytmiczną. Wiele z nich jest związanych z praktyką programistyczną. Dlatego szukamy odpowiedzi na pytanie, w jaki sposób rozstrzygać problemy algebraiczne, jak również badamy pod tym kątem funkcjonalne języki programowania, których teoretyczna idea jest opisywana przez prosty rachunek lambda.

Walka z "pętleniem"

Każdemu programiście często zdarza się, że napisany przez niego program nie zatrzymuje się po uruchomieniu, co w slangu informatycznym nazywamy "pętleniem się" programu. Zatem naturalną potrzebą świata informatycznego byłoby skonstruowanie takiego superprogramu, który umiałby wykrywać pętlenie się innych programów zanim zostaną one uruchomione.

Na wejściu nasz superprogram miałby programy i poprawnie dokonywał ich analizy, po czym odpowiadać TAK lub NIE w zależności od tego czy się "pętlą". Stosunkowo elementarnym wynikiem teorii rekursji jest pokazanie, że nie istnieje taki superprogram. Jesteśmy więc skazani na żmudne testowanie oprogramowania. Co gorsza, nie ma nadziei na to, że kiedyś ten problem zostanie przełamany za pomocą szybko działających i wydajnych komputerów, ponieważ ograniczenia nie leżą w prędkości, tylko w niealgorytmicznej naturze problemu.

Byłoby dobrze posiadać inny superprogram, który umiałby poprawnie ocenić, czy dwa programy są semantycznie równoważne, czyli czy produkują takie same wyniki dla tych samych danych. Pozwoliłoby to na uniknięcie uciążliwego testowania oprogramowania. Dowodzi się, że nie istnieje również algorytmiczne rozwiązanie problemu równoważności.

Nierozstrzygalność problemów łączy się też z zagadnieniem automatycznej dedukcji, która leży u podstaw sztucznej inteligencji. Jest rzeczą niezmiernie pożądaną, aby dowodzenie twierdzeń matematycznych mogło być całkowicie zautomatyzowane. Niestety, już w logice, która używa pojęcia kwantyfikatora, jest to nie do zrealizowania ze względu na niealgorytmiczność problemu. Należy dodać, że w logice zdaniowej, takiej jaką pamiętamy ze szkoły, zagadnienie jest rozstrzygalne przy użyciu tzw. tabel zerojedynkowych.

Można by odnieść wrażenie, że problemy te są sztuczne i w rzeczywistości informatycznej nie występują. Niestety, nic bardziej fałszywego. Już prosta analiza teoriomnogościowa pokazuje, że zagadnień rozstrzygalnych jest niezmiernie mało w porównaniu do nierozstrzygalnych. Zbiór zagadnień rozstrzygalnych jest zbiorem o "mierze zero" w stosunku do wszystkich zagadnień. Dobrą analogią jest stwierdzenie, iż zbiór ten jest, taki jak zbiór liczb naturalnych w porównaniu do zbioru liczb rzeczywistych wszystkich problemów, którymi mogłaby zajmować się informatyka. Jednym słowem - to, co daje się algorytmicznie rozwiązywać, jest rzadkością.

Wydajność programów

Teoretyków Instytutu Informatyki UJ interesuje też tzw. złożoność obliczeniowa. Jeżeli już wiemy, że dane zagadnienie jest rozstrzygalne, naturalnym pytaniem jest, jak złożony jest najprostszy algorytm, który go rozwiązuje. Paradygmat złożoności jest następujący: jak szybko wzrasta długość obliczeń wraz ze wzrostem rozmiaru problemu. Badane są zarówno górne, jak i dolne oszacowania złożoności konkretnych problemów, relacje między całymi klasami złożoności. Dużą liczbę takich problemów dostarcza np. teoria grafów. Ostatnio poddano badaniom ciekawe zagadnienia związane z izomorficznością pewnych klas grafów. Można na to patrzeć, tak jak na uogólnienie problemu rozpoznawania obrazów lub dopasowywania do wzorca.

Łatwo pokazać, że wyszukiwanie danych w uporządkowanej bazie nie może być szybsze niż logarytm z jej wielkości. Przykładowo - jeżeli rozmiar książki telefonicznej powiększy się 8 razy, to będziemy musieli wykonać o 3 kroki więcej na znalezienie nazwiska (nawet gdy robi to komputer). Dowiedziono, że nie można tego wykonać szybciej niż z prędkością logarytmiczną.

Znamy też problemy, gdzie nakład obliczeń wzrasta lawinowo wraz z rozmiarem problemu. Dobrym przykładem jest tabelkowe dowodzenie twierdzeń w logice zdaniowej (przy automatyzacji dowodzenia). Jeżeli długość formuły, którą chcemy dowieść, wzrośnie "n" razy, to liczba obliczeń potrzebna, aby jej dowieść, wzrasta 2n razy. To, oczywiście, przesądza o nieefektywności algorytmu. Niestety, nie ma algorytmicznie szybszych.

Prof. Marek Zaionc jest dyrektorem Instytutu Informatyki Uniwersytetu Jagiellońskiego, e-mail: [email protected].

W celu komercyjnej reprodukcji treści Computerworld należy zakupić licencję. Skontaktuj się z naszym partnerem, YGS Group, pod adresem [email protected]

TOP 200