| « poprzedni punkt | następny punkt » |
Celem tego wykładu jest przedstawienie różnych problemów algorytmicznych i metod ich rozwiązywania, przedstawienie ważnych i użytecznych algorytmów oraz dokonanie przeglądu podstawowych struktur danych. Rozważymy różne dziedziny aplikacji, koncentrując się jednak na podstawowych technikach konstrukcji algorytmów i podstawowych algorytmach. Na licznych przykładach będziemy śledzili proces przejścia od problemu i jego specyfikacji do gotowego rozwiązania w postaci poprawnego programu. Będziemy się starali wyróżniać w tym procesie algorytm i środowisko, w którym on działa, dając w ten sposób wyraz przekonaniu (za N. Wirthem), że
Program = Algorytm + Struktura Danych.
Pytania, które sobie kolejno postawimy są następujące:
Zadania i problemy algorytmiczne formułujemy najczęściej w języku naturalnym. Tak też będziemy postępować w tym wykładzie. Jednak język naturalny może stwarzać pewne problemy, gdyż jest niejednoznaczny. Będziemy się więc starali przedstawiać problemy na tyle precyzyjnie, aby była możliwa odpowiedź na pytanie, czy dany algorytm jest, czy nie jest rozwiązaniem postawionego problemu. Zanim zabierzemy się do konstruowania algorytmu, określimy precyzyjnie w jakich sytuacjach chcemy go stosować i czego od niego oczekujemy. A wszystko po to, by po napisaniu algorytmu można było przedyskutować jego zgodność z oczekiwaniami. Te wymagania i oczekiwania nazywać będziemy specyfikacją algorytmu. W dalszym ciągu wykładu wielokrotnie pokonamy drogę
problem ---> {specyfikacja} ---> algorytm
i przeanalizujemy poszczególne jej elementy.
Do zapisywania algorytmów będziemy stosować prosty pseudokod, który z łatwością można przepisać na dowolny język wysokiego poziomu. Nie będziemy się tym jednak w zasadzie zajmować: to co nas interesuje najbardziej, to metoda postępowania opisana w algorytmie, a nie jej szczególna implementacja. Chcemy poznać i analizować właśnie tę metodę, a nie jej konkretną implementację.
Najprostszym sprawdzeniem, czy algorytm rzeczywiście rozwiązuje podany problem, jest wykonanie serii testów. Jednak samo testowanie algorytmu nie daje żadnej gwarancji jego poprawności w całej dziedzinie zastosowań. Taką gwarancję może nam dać jedynie dowód poprawności. W tym wykładzie, do dowodzenia poprawności algorytmów będziemy stosowali zazwyczaj technikę niezmienników Hoare.
Specyfikacja, chociaż zwykle przedstawiona bardziej formalnie niż sam problem, nie determinuje jednoznacznie algorytmu. Może zatem się zdarzyć, że mamy wiele różnych algorytmów poprawnych ze względu na tę samą specyfikację. Jak więc mamy zdecydować, które z wielu rozwiązań postawionego problemu jest lepsze? Jakie kryteria powinniśmy stosować przy porównywaniu algorytmów? Najprostsze z nich to prostota i czytelność. Te cechy możemy uzyskać konstruując algorytm strukturalnie, dodając zwięzłe komentarze dotyczące istotnych elementów algorytmu.
Innym kryterium stosowanym przy porównywaniu algorytmów, jest koszt związany z jego realizacją. Naturalną miarą kosztu jest czas potrzebny do realizacji algorytmu. Nie chodzi tu o dokładną liczbę sekund potrzebnych do wykonania algorytmu dla konkretnych danych i na konkretnym komputerze. Chcemy nasze kryterium uniezależnić od konkretnych danych i konkretnego komputera. Poszukiwać więc będziemy zależności między, rozmiarem danych, a liczbą wykonanych operacji. Taka zależność (funkcja), to złożoność algorytmu. Co więcej, zwykle nie będzie nas interesowała dokładna postać tej funkcji, lecz raczej jej zachowanie, gdy rozmiar danych dąży do nieskończoności. Taka uproszczona forma tej funkcji nosi nazwę złożoności asymptotycznej. W punkcie 6 tego wykładu przypomnimy notację asymptotyczną, która służy do określania złożoności asymptotycznej algorytmów.
Analizując zachowanie asymptotyczne różnych funkcji dojdziemy do wniosku, że nie każdy algorytm może być przez nas zaakceptowany. Bywają bowiem problemy, których algorytmy rozwiązania mają tak dużą złożoność, że ich realizacja przy pomocy komputera nie jest możliwa. Przykładem takiego problemu jest problem gry w szachy. Można sobie wyobrazić program do gry w szachy, który jest lepszy od najlepszego gracza, gdyż analizuje wszystkie możliwe kroki i wybiera zawsze ten najlepszy ruch. Chociaż w każdej chwili, w szachach jest tylko skończenie wiele możliwych ruchów i gra kończy się zawsze po skończonej liczbie kroków, to jednak złożoność problemu jest tak wielka, że w praktyce taki algorytm nie mógłby być użyty. Musiałby rozważyć rzędu 1019 możliwych pozycji w każdym ruchu! Nawet bardzo szybkim komputerom zajęłoby to zbyt dużo czasu. Problemy tego typu należą do problemów trudnych informatyki. Będziemy o nich rozmawiać w ostatnim wykładzie.
Na zakończenie zauważmy, że istnieją dobrze postawione problemy matematyczne, które jednak nie mogą być rozwiązane przy pomocy komputera ani teraz, ani nigdy w przyszłości. Nie jest to problem czasu, czy nakładu kosztów. Natura tych problemów jest zbyt złożona aby mógł je rozwiązać algorytm. Takim problemem jest np. badanie prawdziwości zdań arytmetyki. Chociaż arytmetyka jest precyzyjnie określoną teorią matematyczną, to udowodniono, że nie może istnieć żaden algorytm, który dla dowolnej formuły arytmetycznej rozstrzygnie, czy ona jest, czy nie jest twierdzeniem arytmetyki.
Pytanie 1: Jak nazywa się sformalizowany opis wymagań, ktore ma spełniać konkretny algorytm?
| « poprzedni punkt | następny punkt » |