ScanImage020 (4)

WPROWADZENIE

_:m asa gag am asa sak &&

ukowo ocenę algorytmów, których używamy, i zdobywać doświadczenie w poznawaniu własności implementacji uruchamianych na danych rzeczywistych lub losowych danych testowych.

W taki właśnie sposób będziemy analizować różne algorytmy związane z fundamentalnymi zagadnieniami przedstawianymi w tej książce. Tam, gdzie to będzie możliwe, będziemy postępować zgodnie z kilkoma podstawowymi wskazówkami, którymi kierowaliśmy się w przypadku algorytmów scalania i wyszukiwania z podrozdziału 1.2; niektóre z tych wskazówek są wymienione na poniższej liście:

•    Określić pełną i konkretną specyfikację problemu, łącznie z podstawowymi operacjami abstrakcyjnymi wynikającymi z problemu.

•    Opracować skrupulatnie zwięzłą implementację algorytmu, który się narzuca, jako pierwsze przybliżenie programu rozwiązującego postawione zadanie.

•    Opracować jego poprawione implementacje, oceniając poprawę efektywności w' nowych rozwiązaniach za pomocą testów empirycznych, analizy matematycznej lub obu metod.

•    Znaleźć abstrakcyjne reprezentacje wysokiego poziomu dla struktur danych lub algorytmów, które umożliwiają efektywne projektowanie ulepszonych wersji na wysokim poziomie.

•    Badać najgorsze przypadki wydajności, o ile to możliwe, ale akceptować dobrą wydajność na rzeczywistych danych.

Potencjał spektakularnych ulepszeń w metodach rozwiązywania konkretnych, rzeczywistych zadań (jakie widzieliśmy w podrozdziale 1.2) czyni z analizy algorytmów niezwykle intrygującą dziedzinę informatyki. Niewiele innych gałęzi nauki może się pochwalić możliwością poprawiania oszczędności w gospodarowaniu zasobami o wskaźniki liczone w milionach i miliardach razy.

Co ważniejsze, wraz ze wzrostem mocy obliczeniowych i skali naszych potrzeb w zakresie aplikacji liczących rośnie przepaść pomiędzy szybkimi i wolnymi algorytmami. Zastosowanie nowszego komputera może poprawić wydajność programu 10 razy albo powiększyć dane, które może on przetwarzać, rówmież dziesięciokrotnie. Ale jeżeli używamy algorytmu kwadratowego, jakim jest algorytm szybkiego wyszukiwania, nowemu komputerowi zajmie około 10 razy dhiżej rozwiązywanie zadania 10 razy większego niż staremu komputerowi zajmowało rozwiązywanie zadania pierwotnego! To stwierdzenie może się początkowo wydawać sprzeczne z intuicją, ale łatwo je sprawdzić za pomocą prostej tożsamości (10w)Vl0 - 10w\jak zobaczymy w rozdziale 2. Wraz ze wzrostem mocy obliczeniowej, która pomaga nam zabierać się za coraz większe zadania, wzrasta także doniosłość wydajnych algorytmów'.

Napisanie efektywnego algorytmu jest działaniem intelektualnie satysfakcjonującym, które może mieć bezpośrednie przełożenie praktyczne. Jak zobaczyliśmy na przykładzie problemu połączeniowego, prosto zdefiniowany problem może doprowadzić nas do badań nad całą grupą algorytmów^-, które są nie tylko przydatne i interesujące, ale rówmież intrygujące i niebanalne. Zajmiemy się wieloma pomysłowymi algorytmami, które zostały opracowane w ciągu ostatnich lat dla mnóstwa praktycznych zadań. Wraz z rozszerzaniem się zakresu stosowalności rozwiązań numerycznych na sfery naukowe i komercyjne rośnie również w cenie umiejętność stosowania efektywnych algorytmów do rozwiązywania problemów' znanych oraz umiejętność tworzenia efektywnych rozwiązań dla problemów' nowych.    .