ScanImage002 (11)

Tsm B5S?

WPROWADZENIE

kacjach. Zaczniemy od rozwiązania prostego, intuicyjnego, by następnie poszukać wskaźników pomocnych przy jego ocenie. Po ich wyznaczeniu zrozumiemy, jak można algorytm poprawić. Po kilku iteracjach tego procesu dojdziemy do efektywnego i użytecznego algorytmu. Ten przykład-prototyp dobrze ilastruje metodykę stosowaną w całym podręczniku.

Rozdział kończy się krótkim omówieniem treści książki, zawierającym zwięzły opis poszczególnych jej części oraz ich wzajemnych relacji.

1.1. Algorytmy

Pisząc program komputerowy, postępujemy na ogół zgodnie z metodą, która została już wcześniej opracowana do rozwiązania jakiegoś zadania. Metoda ta jest często niezależna od konkretnego komputera i najprawdopodobniej w jednakowym stopniu odpowiednia dla różnych maszyn oraz języków' programowania. Aby poznać sposób podejścia do zadania, musimy raczej przeanalizować samą metodę, a nie konkretną jej realizację w postaci programu komputerowego. Pojęcie algorytmu jest wykorzystywane w informatyce do opisania metody rozwiązywania zadań nadającej się do zastosowania w dowolnym komputerze i dowolnym języku programowania. Algorytmy stanowią trzon informatyki. Sągłówmym obiektem zainteresowania naukowców' i inżynierów w wielu, jak nie w większości, dziedzin techniki.

Większość algorytmów, jakimi się zajmiemy, obejmuje metody organizacji danych biorących udział w' obliczeniach. Obiekty powstałe w len sposób nazywane są strukturami danych. Rówmicż one stanowią jeden z ważniejszych nurtów badań informatyki. Tak więc algorytmy i struktur)' danych są nierozerwalne. W tej książce prezentowany jest pogląd, iż struktury danych stanowią produkt uboczny lub końcowy algorytmu. Z tego też względu musimy je badać po to, aby lepiej zrozumieć algorytmy. Proste algorytmy mogą niekiedy wymagać złożonych struktur danych, a skomplikowane - prostych. Podręcznik zawiera liczne analizy właściwości wielu typów' struktur danych, mógł więc równie dobrze nosić tytuł,Algorytmy i struktury danych w C++”.

Jeżeli do rozwiązania zadania zaprzęgamy komputer, do dyspozycji mamy z. reguły wiele różnych możliwości. W przypadku zadań prostych nic ma znaczenia, z której z nich skorzystamy, o ile oczywiście daje ona poprawne rozwiązanie. W przypadku zadań pow-ażniejszych (albo sytuacji, kiedy potrzebujemy rozwiązać ogromną liczbę drobnych zadań cząstkowych) okazuje się jednak, że potrzebujemy metod optymalnego gospodarowania czasem i pamięcią.

Główmym cclcm poznawania zasad prawidłowego konstruowania i analizowania algorytmów'jest to, że dzięki nim otrzymuje się możliwość ogromnych oszczędności zasobów', posuniętych czasem do tego stopnia, że bez nich rozwiązanie zadania byłoby w ogóle niemożliwe. W zastosowaniach polegających na przetwarzaniu milionów obiektów nikogo nie powinno zdziwić, iż można znaleźć lepszy (ściślej: prawidłowo skonstruowany) algorytm, który będzie miliony razy szybszy od amatorskiego. Przykład takiej sytuacji zobaczymy w podrozdziale 1.2 i w w^riclu innych fragmentach tej książki. Z kolei inwestowanie dodatkowych funduszy' lub poświęcanie dodatkowego czasu na zakup i zainstalowanie nowego komputera w nadziei na przyspieszenie prędkości wykony w-anych za jego pomocą programów daje zysk w postaci najwyżej dziesięcio- lub stukrotnego przyspieszenia. Przemyślane koncepcje algorytmiczne to szczegół-