Opracowanie algorytmu oraz jego implementacji, które rozwiązują zadany problem, przebiega zazwyczaj w następujących etapach:

Dalsze rozważania w tym rozdziale dotyczą etapu (b).

Nieformalnie, algorytm jest poprawny, jeśli dla wszystkich poprawnych danych wejściowych kończy działanie i zwraca dane wyjściowe będące rozwiązaniem zadanego problemu. W opisie problemu zazwyczaj precyzuje się, jakie są dane wejściowe, na podstawie których należy obliczyć dane wyjściowe stanowiące rozwiązanie. Podane są także warunki, które muszą spełniać zarówno dane wejściowe, jak i wyjściowe. Spełnienie warunków dotyczących danych wyjściowych gwarantuje, że są one poprawnymi rozwiązaniami problemu. Warunki te zapisuje się formalnie za pomocą asercji wejściowej oraz asercji wyjściowej, które tworzą razem specyfikację problemu. Asercja jest funkcją przyjmującą wartość logiczną (boolowską) prawda (ang. true) albo fałsz (ang. false), której argumentami są zmienne używane w algorytmie (lub programie). Zwykle wyraża się ją jako zdanie logiczne zawierające zmienne algorytmu. Każda asercja odnosi się do określonego punktu algorytmu. Gdy obliczenia osiągają ten punkt, asercja powinna być spełniona, czyli jej wartość powinna wynosić true. Innymi słowy, w miarę jak algorytm zmienia stan pamięci, wartości zmiennych w asercji powinny zapewnić jej spełnienie w odpowiednim momencie. Algorytm rozwiązujący problem jest poprawny, jeśli dla każdego poprawnego egzemplarza danych wejściowych zakończy swoje działanie i zwróci wynik spełniający warunki specyfikacji, to jest, przekształci dane wejściowe spełniające asercję wejściową w dane wyjściowe spełniające asercję wyjściową.

Algorytm jest całkowicie poprawny, jeśli spełnia:

Warunek częściowej poprawności algorytmu A zapisujemy jako:

gdzie p to asercja wejściowa (warunek początkowy), a q to asercja wyjściowa (warunek końcowy). Zgodnie z tym zapisem, algorytm A jest częściowo poprawny, jeśli dla każdego przypadku, gdy dane wejściowe spełniają {p} , algorytm - jeśli się zakończy - zwraca dane wyjściowe spełniające {q} .

Załóżmy, że algorytm A rozwiązuje następujący problem: dany jest zbiór n liczb całkowitych, gdzie n?1 . Należy znaleźć największy element tego zbioru. Zbiór jest reprezentowany przez tablicęD:?????[1..n] ????????? . Wówczas warunek częściowej poprawności algorytmu ma postać:

To oznacza, że algorytm A jest częściowo poprawny, jeśli dla dowolnego n?1 , po zakończeniu działania algorytmu, zmienna M będzie zawierać największą wartość w tablicy D.

Aby wykazać całkowitą poprawność algorytmu, należy także udowodnić, że spełnia on warunek stopu. Jeśli algorytm nie kończy działania, nie można ocenić, czy asercja wyjściowa jest spełniona - ponieważ wynik nigdy nie zostaje zwrócony.

Rozważmy instrukcję while przedstawioną na rys. 2.1.

Wykonanie tej instrukcji nigdy się nie kończy, ponieważ warunek w wierszu 22.1 jest źle sformułowany - zmienna b przyjmuje tylko wartości nieparzyste. W ogólnym przypadku, wykazanie, że obliczenia algorytmu doprowadzą do punktu końcowego, może nie być łatwe. Rozważmy algorytm, którego celem jest przekształcenie dowolnej dodatniej liczby całkowitej n do wartości 1 (rys. 2.2).

Przeanalizujmy kilka przykładów:

Zauważmy, że dla wartości początkowych n z zakresu [1, 7]obliczenia algorytmu się kończą, ale nie jest jasne, czy sprawdzając kolejne wartości n, natrafimy na wartość, dla której algorytm nie kończy swego działania. Według obecnego stanu wiedzy, brakuje dowodu, że algorytm ten spełnia warunek stopu1.

Zanim przedstawimy model obliczeń sekwencyjnych, pokrótce omówimy, jak obecnie działają programy tego typu. Współczesne komputery wyposażone są w procesory, które wykonując program sekwencyjny, mogą realizować niektóre operacje programu równolegle. Przykładowo, rozważmy następujące instrukcje:

W wykonaniu sekwencyjnym tych instrukcji najpierw przebiega operacja dodawania, a po jej zakończeniu, po przypisaniu wyniku do zmiennej x, wykonywana jest operacja mnożenia i przypisanie wyniku do zmiennej y. Instrukcje te mogą być wykonane równolegle, ponieważ współczesne procesory potrafią przetwarzać więcej niż jedną instrukcję w jednym cyklu pracy (ang. instruction-level parallelism). W tym celu procesory wyposaża się w odpowiednią liczbę jednostek funkcjonalnych, które umożliwiają potokowe wykonanie instrukcji (ang. pipelining).

Załóżmy, że proces wykonywania instrukcji składa się z sześciu kolejno wykonywanych operacji: pobrania instrukcji z pamięci, jej dekodowania, wyznaczenia adresów argumentów, pobrania argumentów, wykonania operacji określonej przez kod instrukcji oraz zapisania otrzymanego wyniku do pamięci. Ciąg tych operacji tworzy potok. Poszczególne operacje w potoku nazywamy etapami, zatem rozważamy potok 6-etapowy. Dla uproszczenia przyjmujemy, że każdy etap potoku wykonany jest w jednym cyklu pracy procesora2. Załóżmy, że procesor wyposażony jest w jednostki funkcjonalne J1, J2, ..., J6, z których każda odpowiada za wykonanie jednego etapu potoku. Wykonanie potokowe kolejnych instrukcji pokazano na rys. 1.4. W pierwszym cyklu pracy jednostka J1 pobiera z pamięci instrukcję i1 i przekazuje ją jednostce J2 do dekodowania.

W drugim cyklu jednostka J2 dekoduje instrukcję i1, a J1 pobiera instrukcję i2. Pod koniec cyklu jednostki J1 i J2 przekazują wyniki swego działania odpowiednio do jednostek J2 oraz J3, i tak dalej. Zauważmy, że przy ciągłym strumieniu instrukcji kolejne z nich opuszczają potok w każdym cyklu pracy procesora. Na przykład, na rys. 1.4 instrukcja i1 jest wykonana w cyklu 6, instrukcja i2 w cyklu 7, i tak dalej. Wykonując instrukcje (1.1) sekwencyjnie, potrzebowalibyśmy 2?6 =12  cykli.

Dalszy wzrost szybkości obliczeń umożliwiają procesory superskalarne, które pozwalają na jednoczesne wykonywanie wielu instrukcji w jednym cyklu pracy. W takich procesorach zwielokrotnia się jednostki funkcjonalne, na przykład arytmetyczno-logiczne dla liczb zmiennopozycyjnych i całkowitych, a także inne wyspecjalizowane jednostki. Ważnym elementem procesora superskalarnego jest specjalna jednostka pobierania instrukcji, zdolna do pobierania z pamięci wielu instrukcji jednocześnie, pracując być może w sposób potokowy. Jednostka ta przekazuje instrukcje do jednostki dekodującej, która określa, czy instrukcje mogą być wykonane jednocześnie (czyli są niezależne), czy też istnieją między nimi zależności uniemożliwiające ich równoległe wykonanie.

Jednym z głównych problemów projektowania architektur komputerów jest różnica w szybkości działania procesorów i pamięci operacyjnej. Współczesne procesory są znacznie szybsze niż pamięć główna. Rozwiązaniem tego problemu jest zastosowanie hierarchicznego systemu pamięci, składającego się z pamięci głównej oraz dwóch pamięci podręcznych L1 i L2 (ang. cache memory)3. Pamięci podręczne mają znacznie mniejszą objętość od pamięci głównej, ale są wielokrotnie szybsze. Niższy poziom (L1) jest szybszy, ale mniejszy od poziomu wyższego (L2), który jest nieco wolniejszy, ale ma większą pojemność. Szybsze przetwarzanie danych przy użyciu pamięci podręcznych jest możliwe dzięki zjawisku lokalności odwołania. Jeśli w programie wystąpiło odwołanie do pewnej komórki pamięci, to istnieje duże prawdopodobieństwo, że w niedalekiej przyszłości nastąpi kolejne odwołanie do tej samej lub sąsiadującej komórki. Wówczas do pamięci podręcznej przenoszony jest cały blok komórek zawierający adres wykorzystywany aktualnie przez program. Pamięci podręczne przechowują instrukcje oraz dane programu, które mogą być z nich pobierane szybciej niż z pamięci głównej, a równocześnie z wszystkich modułów podręcznych, co dodatkowo przyspiesza obliczenia.

W tej książce będziemy określać złożoność czasową algorytmów, rozumianą jako liczbę operacji elementarnych wykonywanych przez algorytm, aby rozwiązać dany problem. Jak pokazaliśmy wcześniej, wiele operacji może być wykonanych równolegle dzięki potokom i zwielokrotnionym jednostkom funkcjonalnym. Dzięki pamięci podręcznej procesor może jednocześnie pobierać dane z różnych poziomów pamięci. Czy da się to uwzględnić w wyznaczaniu liczby operacji elementarnych? W praktyce jest to bardzo trudne, a na ogół - niemożliwe. Komplikację stanowi również to, że nie wiemy, na jakim komputerze algorytm będzie wykonywany. Architektury komputerów, a w szczególności procesory, są dziś bardzo zróżnicowane. Producenci sprzętu konkurują, tworząc coraz lepsze rozwiązania o wyższej mocy obliczeniowej. Podsumowując, aby możliwe było precyzyjne określanie złożoności czasowej algorytmów, konieczne jest przyjęcie prostego, ale uniwersalnego modelu obliczeń sekwencyjnych.

Model to obiekt teoretyczny lub fizyczny, którego analiza pozwala lepiej zrozumieć dane zjawisko lub proces. Model upraszcza rzeczywistość, uwzględniając jedynie jej najważniejsze cechy. Dzięki temu jest łatwiejszy do analizy niż oryginalny system. Nas interesują modele komputerów, które umożliwiają analizę procesów obliczeniowych. Są one znane jako modele obliczeń i stosuje się je zarówno do analizy, jak i projektowania algorytmów, oraz określania ich złożoności.

Najpowszechniej akceptowanym modelem obliczeń sekwencyjnych jest maszyna o swobodnym dostępie do pamięci (ang. random access machine, RAM). Model RAM4 składa się z procesora oraz pamięci złożonej z potencjalnie nieograniczonej liczby komórek pamięci oznaczanych jako Mi, i=1 , 2, 3, ...(rys. 1.5). Każda komórka pamięci, identyfikowana przez swój adres i, może przechowywać dowolną, skończoną liczbę całkowitą w zapisie binarnym, nawet bardzo dużą. Zakłada się, że czas odczytu lub zapisu wartości z lub do komórki Mi jest niezależny od jej adresu i stały, co implikuje dostęp swobodny, w odróżnieniu od dostępu cyklicznego, charakterystycznego dla pamięci dyskowych. Procesor realizuje instrukcje z określonego, skończonego zbioru, przypominające te spotykane we współczesnych komputerach (tab. 1.1).

W celu realizacji instrukcji, procesor zawiera zbiór rejestrów arytmetycznych R1, R2, ..., Rq, gdzie q>1 , które mogą przechowywać - podobnie jak komórki pamięci Mi - dowolne, skończone liczby w zapisie binarnym. Dodatkowo, procesor jest wyposażony w rejestr sterujący L, zwany licznikiem instrukcji. Po wykonaniu każdej instrukcji, z wyjątkiem JUMP, JPOS, JZERO oraz JNEG, jego wartość zwiększa się o 1. Dla tych instrukcji licznik przyjmuje nową wartość lub zwiększa się o 1, zgodnie z warunkiem instrukcji.

Program RAM to ciąg instrukcji sterujących pracą procesora. Zapisywany jest w jednostce sterującej modelu, a nie w pamięci, co oznacza, że nie może być modyfikowany w czasie wykonywania. Podczas analizowania programu RAM wygodnie jest przyjąć, że składa się on z kroków obliczeniowych, z których każdy podzielony jest na trzy fazy. Dla analizy programu RAM przyjmujemy, że jest on złożony z kroków obliczeniowych, z których każdy składa się z trzech faz: (1) pobrania argumentów operacji z pamięci do rejestrów, (2) wykonania operacji (arytmetycznej, logicznej, sterującej lub wej/wyj), (3) zapisania wyniku operacji do określonej komórki pamięci. Niektóre fazy kroku obliczeniowego mogą być pominięte, jeśli są niepotrzebne w danej instrukcji.

Przykład 1.1.

Podsumowując, model RAM jest modelem uniwersalnym, ponieważ umożliwia opis i analizę obliczeń sekwencyjnych dla dowolnego współczesnego komputera z procesorem jednowątkowym.