5032124677

1_

Projektowanie i analiza algorytmów

Stworzenie programu rozwiązującego konkretny problem jest procesem wieloetapowym. Proces ten rozpoczyna się od sformułowania problemu i jego specyfikacji, po czym następuje projektowanie rozwiązania, które musi zostać następnie zapisane w postaci konkretnego programu, czyli zaimplementowane. Konieczne jest udokumentowanie oraz przetestowanie implementacji, a rozwiązanie wyprodukowane przez działający program musi zostać ocenione i zinterpretowane. W niniejszym rozdziale zaprezentowaliśmy nasze podejście do wymienionych kroków, następne rozdziały poświęcone są natomiast algorytmom i strukturom danych, składającym się na większość programów komputerowych.

1.1. Od problemu do programu

Wiedzieć, jaki problem tak naprawdę się rozwiązuje — to już połowa sukcesu. Większość problemów, w swym oryginalnym sformułowaniu, nie ma klarownej specyfikacji. Faktycznie, niektóre (wydawałoby się) oczywiste problemy, jak „sporządzenie smakowitego deseru” czy też ,rachowanie pokoju na świecie” wydają się niemożliwe do sformułowania w takiej postaci, która przynajmniej otwierałaby drogę do ich rozwiązania za pomocą komputerów. Nawet jednak, gdy dany problem wydaje się (w sposób mniej lub bardziej oczywisty) możliwy do rozwiązania przy użyciu komputera, pozostaje jeszcze trudna zazwyczaj kwestia jego parametryzacji. Niekiedy bywa i tak, że rozsądne wartości parametrów mogą być określone jedynie w drodze eksperymentu.

Jeżeli niektóre aspekty rozwiązywanego problemu dają się wyrazić w kategoriach jakiegoś formalnego modelu, okazuje się to zwykle wielce pomocne, gdyż również w tych kategoriach poszukuje się rozwiązania, a dysponując konkretnym programem można określić (lub przynajmniej spróbować określić), czy faktycznie rozwiązuje on dany problem. Także — abstrahując od konkretnego programu — mając określoną wiedzę o modelu i jego właściwościach, można na tej podstawie podjąć próbę znalezienia dobrego rozwiązania.

Na szczęście, każda niemal dyscyplina naukowa daje się ująć w ramy modelu (modeli) z jakiejś dziedziny (dziedzin). Możliwe jest modelowanie wielu problemów natury wybitnie numerycznej w postaci układów równań liniowych (w ten sposób oblicza się m.in. natężenia prądu w poszczególnych gałęziach obwodu elektrycznego czy naprężenia w układzie połączonych belek) bądź równań różniczkowych (tak prognozuje się wzrost populacji i tak znajduje się stosunki ilościowe, w jakich łączą się substraty reakcji chemicznych). Rozwiązywanie problemów natury tekstowej czy symbolicznej odbywa się zazwyczaj na podstawie rozmaitych gramatyk wspomaganych zazwyczaj