ScanImage003 (11)

1.1. ALGORYTMY

nic ważny element procesu rozwiązywania poważnych zadań, niezależnie od obszaru zastosowań.

Kiedy stajemy przed koniecznością napisania złożonego programu komputerowego, wiele wysiłku musimy włożyć w zrozumienie problemu, zdefiniowanie konkretnego zadania, które ma zostać rozwiązane, poradzenie sobie z jego złożonością i rozkład na zadania mniejsze, a więc prostsze w implementacji. Często zdarza się tak, że zadania cząstkowe powstałe z dekompozycji dużego zadania na mniejsze są trywialne. W większości wypadków jednak dochodzi się do pewnego zbioru algorytmów, których realizacja jest krytyczna dla całej aplikacji, ponieważ pochłoną one większość zasobów systemowych. To właśnie na algorytmach tego typu skoncentrujemy się w niniejszej książce. Przeanalizujemy wiele fundamentalnych algorytmów wykorzystywanych do rozwiązywania zadań z bardzo szerokiego spektrum zastosowań.

Obecnie coraz bardziej popularne staje się korzystanie w obrębie jednego systemu ze wspólnych programów', dlatego też nie można wyrokować, czy będzie się używać sporej czy niewielkiej części algorytmów z tej książki. Implementacje większości najważniejszych algorytmów są dostępne tu i ów^rdzie, na przykład w bibliotece C++ Standard Template Library. Jednak zaimplementowanie uproszczonych ich wersji nie jest bezcelowe, pomoże nam bowiem lepiej zrozumieć te algorytmy, a tym samym efektywniej ich używać i ewentualnie poprawiać ich zaawansowane wersje z biblioteki. Co ważniejsze, konieczność niezależnego realizowania prostych algorytmów' pojawia się często. Głównym powodem tego stanu rzeczy jest to, że zbyt często stajemy w obliczu kompletnie nowych środowisk przetwarzania (sprzętowych i programowych), wyposażonych w nowe funkcje niedostępne w starych systemach. Skorzystanie z istniejących rozwiązań, a więc zignorow'anie nowych możliwości systemu, oznaczałoby niepełne wykorzystywanie nowego środowiska.

inaczej mówiąc, często pojawia się konieczność ponownej implementacji algorytmów' istniejących od lat, ale takiej implementacji, która będzie ściśle dopasowana do nowego problemu (starego problemu w now'ych szatach, żeby być ścisłym). Możliwość polegania na procedurach systemowych, która zapewniłaby lepszą przenośność rozwiązań i ich dłuższy czas życia, jest ostatnio mniej powszechnie wykorzystywana. Istnieje jeszcze inna przyczyna ponownego implementowania typowego algorytmu: mimo rozwoju języków' programowania i nowych możliwości, jakimi dysponuje C h , mechanizmy używane do współużytkowania oprogramowania nic zawsze wystarczajądo tego, by dało się za ich pomocą wygodnie dopasować uogólnione programy biblioteczne do wymogów' bardzo konkretnego zadania.

Programy komputerowe są często zbyt optymalizowane. Niejednokrotnie nie warto ponosić trudów związanych z ponowną implementacją algorytmu i opracowywaniem najbardziej efektywnego rozwiązania, jeżeli algorytm nie będzie przeznaczony do rozwiązywania dużych zadań. Na ogół wystarcza stosunkowo prosta, aczkolwiek staranna implementacja. Możemy mieć pewność, że będzie ona działać i prawdopodobnie będzie tylko pięć do dziesięciu razy wolniejsza od najlepszej, co w praktyce oznacza dodatkowych kilka sekund pracy programu. Z kolei właściwy wybór algorytmu może skracać czas działania programu sto, tysiąc i wdęcej razy, co może się przekładać na minuty', godziny, a nawet większe jednostki czasu. W tej książce skoncentrujemy się na najprostszych rozsądnych implementacjach najbardziej typowych algorytmów.

5