ALG6
26 RozdziaH. Zanim wystartujemy 1.5
metody niezmienników (zwanej niekiedy metodą Floyda). Mając dany algorytm, możemy łatwo wyróżnić w nim pewne kluczowe punkty, w których dzieją się interesujące dla danego algorytmu rzeczy Ich znalezienie nie jest zazwyczaj trudne: ważne są momenty inicjalizacji zmiennych, którymi będzie operować procedura, testy zakończenia algorytmu, „pętla główna”... W każdym z tych punktów możliwe jest określenie pewnych zawsze prawdziwych warunków - tzw. niezmienników. Można sobie zatem wyobrazić, że dow'ód formalnej poprawności algorytmu może być uproszczony do stwierdzenia zachowania prawdziwości niezmienników dla dowolnych danych wejściowych.
Dwa typowe sposoby stosowane w praktyce to:
• sprawdzanie stanu punktów kontrolnych przy pomocy debuggera (odczytujemy wartości pewnych „ważnych” zmiennych i sprawdzamy, czy zachowują się „poprawnie” dla pewnych „reprezentacyjnych” danych wejściowych').
• formalne udowodnienie (np. przez indukcję matematyczną) zachowania niezmienników dla dowolnych danych wejściowych.
Zasadnicza wadą powyższych zabiegów jest to, że są one nużące i potrafią łatwo zabić całą przyjemność związaną z efektywnym rozwiązywaniem problemów przy pomocy komputera. Tym niemniej Czytelnik powinien być świadom istnienia również i tej strony programowania. Jedną z prostszych (i bardzo kompletnych) książek, którą można polecić Czytelnikowi zainteresowanemu formalną teorią programowania, metodami generowania algorytmów i sprawdzania ich własności, jest [Gri84] - entuzjastyczny wstęp do niej napisał sam Ui jkstra’. co jest chyba najlepszą rekomendacją dla tego typu pracy. Inny tytuł o podobnym charakterze, [Kal90], można polecić miłośnikom formalnych dowodów i myślenia matematycznego. Metody matematycznego dowodzenia poprawności algorytmów są prezentowane w tych książkach w pewnym sensie niejawnie: zasadniczymi celem jest dostarczenie narzędzi, które umożliwią r/mvz'-automatyczne generowanie algorytmów.
Każdy program „wyprodukowany” przy' pomocy tych metod jest automatycznie poprawny - pod warunkiem, że nie został „po drodze” popełniony jakiś błąd. „Wygenerowanie” algorytmu jest możliwa dopiero po jego poprawnym zapisaniu wg schematu:
: Stwierdzenia: „ważne zmienne", „poprawne" zachowanie programu, „reprezentatywne” dane wejściowe etc. należą do gatunku bardzo nieprecyzyjnych i są ściśle związane z konkretnym programem, którego analizą się zajmujemy.
5 Jeśli już jesteśmy przy nim, to warto polecić przynajmniej pobieżną lekturę [DF89], która stanowi dość dobry wstęp do metodologii programowania.
Wyszukiwarka
Podobne podstrony:
ALG8 18 Rozdziali. Zanim wystartujemy dopóki a>0 wykonuj; podstaw za c resztę z dzielenia a prze
ALG0 20 Rozdział 1. Zanim wystartujemy (Na marginesie warto dodać, że przedsiębiorstwo Hollcritha
ALG2 22 Rozdział 1. Zanim wystartujemy programowania nic znikły bynajmniej z horyzontu: Dijkstra, H
ALG4 24 Rozdział 1. Zanim wystartujemy Aby zaradzić zaanonsowanym wyżej problemom, przyjęło się zwy
ET6 26 Rozdział 2. Podstawowa terminologia turystyczna Tabela 2.2. Podział ruchu turystycznego ze w
ALG6 36 Rozdział 2. Rekurencja każemy. W rozdziale 9 zostanie omówiona ciekawa technika programowan
ALG6 46_ _ Rozdział2. Rekurencja rekurencyjnych jest pamięcioźerność: wielokrotne wywołania rekuren
ALG6 56 Rozdział 3. Analiza sprawności algorytmów jest intuicyjnie bardzo proste, dalej będziemy uż
ALG6 66 Rozdział 3. Analiza sprawności algorytmów return pos; else //element zost
ALG6 76 Rozdział 3. Analiza sprawności algorytmów Analogicznie dla 2 otrzymamy: Vn > 1, A(n,2) =
ALG6 86 Rozdział 4. Algorytmy sortowania zamiany sąsiadujących ze sobą elementów, a druga będzie wy
ALG 6 96 Rozdział 5. Struktury danych Rys. 5 - 3. FCOOh FCI4h FFEEh Przykład listy jedno-kierunk
ALG6 106 Rozdziała. Strukturydanjt 5.1 będzie ich fuzją. Rekurencyjny zapis tego procesu jest bardz
ALG6 116 Rozdział 5. Struktury danych Iisla2.li int alfabetycznie(ELEMENT *q],ELEMENT *q2) { II czy
więcej podobnych podstron