Programowanie/Wstęp/Algorytmy

Algorytm - definicja nieformalna

Algorytm jest to, najprościej mówiąc, "przepis" na wykonanie jakiegoś zadania. W swej istocie niczym nie różni się od przepisu z książki kucharskiej. Stanowi zatem ciąg czynności, które należy wykonać w odpowiedniej kolejności, aby otrzymać oczekiwany rezultat. Algorytm jest podstawowym pojęciem programistycznym. Choć różne języki programowania mogą ze względu na swoją naturę wymuszać pewne określone sposoby wykonania jakiegoś zadania, to jednak najczęściej algorytm jest schematem ideowym i przez to ponadjęzykowym, a więc i uniwersalnym. Jest zatem pewnym "pomysłem", który potem może w trakcie dalszego rozwoju przechodzić pewne zmiany (dostosowanie do narzędzi, okoliczności, itp.).

Umiejętność odpowiedniego myślenia algorytmicznego jest konieczna dla każdego programisty. Specyfika poszczególnych języków programowania uczy programistę określonego sposobu myślenia adekwatnego do wymogów danego języka programowania, co skutkuje także tym, iż w różnych językach szczegółowe algorytmy na wykonanie tego samego zadania mogą być znacząco inne. Jednakże podstawowe rysy pewnego algorytmicznego sposobu myślenia są niezmienne. Jedynie akcent (środek ciężkości) jest inaczej położony w poszczególnych językach. I tak można wyróżnić np. programowanie funkcyjne, proceduralne, obiektowe i inne. Te nazwy biorą się od najbardziej charakterystycznych (istotnych) cech algorytmów powstających w takowych paradygmatach programowania. Programowanie proceduralne stanowi zatem pewien zbiór procedur, które składają się na bardziej złożone procedury (funkcje) itd., i stanowią pewną nierozłączną całość, przez co cały program jest jedną wielką procedurą. W paradygmacie obiektowym program też jest jedną wielką procedurą, ale nie jest nierozłączną procedurą. Można go podzielić na mniejsze części i np. testować je samodzielnie. Przypomina to jak gdyby maszynę, która składa się ze połączonych ze sobą elementów - można ją rozłożyć na części pierwsze i każdą z nich zbadać oddzielnie np. w poszukiwaniu błędu.

Podsumowując - algorytm jest bardzo ważnym pojęciem w programowaniu i dobre jego rozumienie pozwala na dobrą orientację w tematyce programowania. Każdy aspirant programowania koniecznie musi przeczytać jakiś wstęp do algorytmiki lub tym podobną publikację.

Algorytm w programowaniu imperatywnym

Procesor komputera działa w ten sposób, że pobiera instrukcje i wykonuje je bez zastanawiania się nad ich prawidłowością. Pisanie programu komputerowego jest zatem wydawaniem komputerowi rozkazów. Komputer wykona taki rozkaz bez gadania. To programista bierze na siebie odpowiedzialność za rezultaty. Z tego powodu podstawą do napisania programu jest znajomość algorytmu rozwiązania danego zagadnienia. Jeżeli znamy algorytm - możemy go zaimplementować w rozmaitych językach programowania.

Algorytm a języki programowania

Oczywiście każdy język ma dedykowany obszar zastosowania. Istnieje sporo niuansów. Przykładowo języki imperatywne mają różne mechanizmy zarządzania pamięcią, różne sposoby reprezentacji tablic i (to chyba najistotniejsze) różne wbudowane funkcjonalności ułatwiające pracę w dedykowanym obszarze zastosowania.

Mimo to wszystkie języki imperatywne traktują komputer jako wykonawcę rozkazów oraz posiadają trzy podstawowe konstrukcje algorytmiczne. Dzięki temu podstawowe idee programowania są dla nich wspólne.

Sposoby zapisu algorytmów

Istnieje kilka sposobów zapisu algorytmów.

Pierwszym jest nieformalny język programowania - IPL (Informal Programming Language). Język ten pozwala na zapis algorytmów w sposób strukturalny (przy pomocy trzech struktur programistycznych) oraz operacji zapisanych w sposób mniej lub bardziej nieformalny (później można je przetłumaczyć na dowolny język imperatywny). Schematy zostaną omówione przy okazji nauki programowania w języku C.

Drugi sposób to schematy Nassi-Schneidermana (schematy NS). Schematy NS pozwalają także na projektowanie strukturalne. Każdy prostokąt jest traktowany jako blok, który może być dzielony na mniejsze podbloki przy pomocy konstrukcji strukturalnych. Zostanie to omówione szczegółowo przy okazji prezentacji tychże schematów.

Trzecim sposobem zapisu algorytmów są schematy blokowe. Jest to sposób najbardziej elastyczny, jednak wymagający dużej rozwagi. W przeciwieństwie do schematów NS, poszczególne bloki są połączone przejściami zobrazowanymi w formie linii. Powoduje to możliwość prawie dowolnego łączenia różnych fragmentów algorytmu (np. przejście pomiędzy odległymi fragmentami algorytmu), co potrafi uczynić taki zapis trudnym do zrozumienia i ewentualnego usunięcia błędów. Z tego powodu nie jest to sposób zalecany do nauki. Mimo to, czasami odpowiednio starannie udokumentowane zastosowanie przeskoku potrafi paradoksalnie uprościć zrozumienie algorytmu. Ponadto w językach niskiego poziomu (asembler) jest to jedyny sposób zapisu algorytmu. Z tego powodu zostanie on także omówiony później.

formalnej analizy poprawności algorytmu

metoda wykazywania poprawności algorytmów:

• częściowa poprawność : metoda niezmienników
• całkowitą poprawność algorytmu K względem warunku wejściowego $\alpha$ i wyjściowego $\beta$ ( Warunki $\alpha$ i $\beta$ nazywa się też specyfikacją algorytmu)