8002824738

POSTĘPY TECHNIKI PRZETWÓRSTWA SPOŻYWCZEGO 2/2011

Wykład inauguracyjny Prof. dr. hab. Marka KOWALSKIEGO Dziekana

Wydziału Informatyki Stosowanej i Technik Bezpieczeństwa Wyższej Szkoły Menedżerskiej w Warszawie

CUDA INFORMATYKI

Magnificencjo, Panie Rektorze!

Rektorze Założycielu!

Wysoki Senacie!

Panie i Panowie Profesorowie!

Dostojni Goście!

Droga Młodzieży Akademicka!

Wielki to zaszczyt dla mnie i szczególnego rodzaju wyróżnienie, że w tak istotnym dla społeczności akademickiej dniu mogę być tu wśród Was i jeszcze jest dana mi możliwość wygłoszenia wykładu inauguracyjnego.

Z serca dziękuję za to władzom naszej uczelni.

Może od razu powiem, że cudów będzie siedem i zaznaczę, że cuda rozumiem szeroko. Każdy, który wymienię jest fenomenem lub czymś dziwnym albo zachwycającym.

1.    Cud przyzwolenia

Jednym z fenomenów informatyki jest jej niemal bezkrytyczny odbiór społeczny manifestujący się niespotykaną w innych dziedzinach życia tolerancją na niedoróbki. Chodzi mi o błędy i niedociągnięcia w dużych programach i systemach komputerowych, o utrzymujący się od dziesięcioleci kryzys oprogramowania. Odpow iedzią na ten kryzys było powstanie w samej informatyce dyscypliny zwanej inżynierią oprogramowania. Dzięki jej metodom kryzys udało się ograniczyć, ale nie wyeliminować. Być może społeczeństwa w swej zbiorowej mądrości i tolerancji wyczuwają, że informatyka to dziedzina łatwa jedy nie w powierzchownej warstwie.

2.    Cud nierozstrzygalności

Dla każdego algorytmu, którego uży wamy należałoby umieć stwierdzić, czy program realizujący ten algorytm zatrzyma się, lub - inaczej mówiąc - nie zapętli się. Może to dotyczyć konkretnych danych wejściowych lub wszystkich (dopuszczalnych) danych. Jeśli program zatrzy muje się dla wszystkich dany ch, mówimy, że ma własność stopu. Niestety, problem stopu jest nierozstrzy-

I

galny, co należy rozumieć w ten sposób, że nie istnieje uniwersalny algorytm rozstrzygający o innych algorytmach, czy zatrzymują się, czy nie. Wiemy to za zasługą Alana Turinga (1912-1954) jednego z największych matematyków' i informatyków XX wieku. Mamy też niebywałe problemy z konkretnymi algorytmami, np. z tym: x:=N; do

if 2|x then x:=x/2 else x:=3x+l until x=l;

Pytanie czy' ten program ma własność stopu pozostaje otwarte i jest treścią tzw. problemu Collatza.

Okazuje się, że problemów nierozstrzygalnych jest więcej. Wymienię tu problem węża domino na pól--plaszczyźnie. Rzecz w tym, aby dla danych dwóch pól półplaszczyzny pokratkowanej tak jak zeszyt do matematyki odpowiedzieć, czy da się je połączyć za pomocą danego zestawu klocków domino, z których każdy jest dopasowany do wymiarów kratek a układanie klocków odbywa się na zasadach domina. Okazuje się że każdy algorytm rozwiązania tego problemu będzie dla pewnych danych (pól półplaszczyzny, które należy połączyć i zestawu klocków ) działał nieskończenie długo lub da błędną odpowiedź.

3. Cud weryfikacji i rozwiązania

Czy dla każdego zagadnienia, dla którego możliwa jest weryfikacja rozwiązania w rozsądnym czasie (NP) możliwe jest rozwiązanie go w rozsądnym czasie (P). W informatyce „rozsądny czas” modeluje się wielomianem od rozmiaru danych. Nie wiemy jaka jest odpowiedź na tak postaw ione py tanie. Wy daję się, że jest nią NIE i to jest właśnie głośna hipoteza „P \ NP”. Jej rozstrzygnięcie jest treścią jednego z siedmiu Problemów Milenijnych, za których rozwiązanie Instytut Matematyczny Claya oferuje po milionie dolarów.