Programy a algorytmy

Z Otwarta edukacja
Skocz do: nawigacja, szukaj

Algorytmem nazywamy ścisły przepis. Program zawiera implementację algorytmów.

Programowanie jest czasem mylone z układaniem algorytmów, które mogą być trudne i skomplikowane. Najczęściej jednak korzystamy z gotowych implementacji! Jeśli już trzeba wymyślić i zaimplementować jakiś algorytm – w większości przypadków jest on trywialny. Jak sobie poradzić z takimi trywialnymi przypadkami – opisano w rozdziale „Implementacja algorytmów”. Na wstępie musimy jednak przyswoić sobie pojęcie sterowania (albo inaczej sterowania przepływem) w programach działających zgodnie z jakimś algorytmem.

Sterowanie

Jak wspomniano w rozdziale poświęconym logice ([Logika_i_instrukcje_warunkowe]) – programy są wykonywane w sposób sekwencyjny - operacja po operacji. Człowiek też nie potrafi myśleć o wielu rzeczach równocześnie. Dlatego tworzone przez niego algorytmy to opis kolejnych operacji, wykonywanych sekwencyjnie (jedna po drugiej). Zakładamy, że komputer także będzie odczytywał kolejne instrukcje i zgodnie z nimi zmieniał dane. Przy tym założeniu powstało wiele języków przystosowanych do zapisu algorytmów (zwanych czasem dlatego językami algorytmicznymi). Warto jednak zdawać sobie sprawę z tego, że nie jest to jedyny sposób sterowania przepływem w programach. Można zatem wyróżnić:

1. Sterowanie sekwencyjne. Program wykonuje krok po kroku zadany algorytm.

2. Sterowanie zdarzeniami. Każdy kto posługiwał się arkuszem kalkulacyjnym wie, że zmienia się on natychmiast po wpisaniu danych. Nie potrzeba uruchamiać dodatkowej funkcji przeliczania. Ona się wykonuje wskutek zaistnienia zdarzenia – zmiany danych. Podobnie jest w programach sterujących złożonymi maszynami, czy nawet programach systemowych (system operacyjny) zwykłego komputera lub komórki. Programowanie w tym wypadku polega na opisaniu reakcji na zdarzenie.

3. Sterowanie danymi. Strona internetowa nie jest zapisem instrukcji – co krok po kroku powinien zrobić komputer, by wykonać zadanie jej wyświetlenia. Jest to opis oczekiwanego efektu. Do tego opisu można użyć języka HTML, XHTML, XML+XSLT i paru innych (to cała odrębna dziedzina wiedzy). To nie jest jedyny przypadek, gdy opisujemy efekt (co ma być zrobione), a nie jak to zrobić. Podobną własność ma programowanie w logice (język Prolog). Taki program składa się ze zbioru logicznych klauzul (zdania otwarte) tworzących bazę wiedzy. Pojawienie się zapytania (klauzuli z niewiadomymi) powoduje uzgodnienie podanych danych z całą bazą, w celu odpowiedzi na pojawiające się w danych znaki zapytania.

Pętle

Drugim poza sterowaniem pojęciem, które musimy zrozumieć zanim przejdziemy do algorytmów jest pojęcie pętli. Zamiast pisać po kolei: 2x2=4, 3x3=9, …. itd., możemy nakazać programowi by dla wszystkich liczb od 1 do 9 wypisał ich kwadraty. Coś w rodzaju:

dla liczb od 1 do 9 drukuj(liczba*liczba)

Oczywiście zapis będzie różny w różnych językach programowania (zazwyczaj pojawi się na początku angielskie słowo ‘for’). Takie wielokrotne wykonywanie zdefiniowanych operacji nazywa się pętlą. Pętla typu for (taka jak wyżej) jest obecnie najczęściej stosowana w powiązaniu z przeglądaniem zboru sekwencyjnego (dla liczba w zbiorze [1..9] …..). To nie jest jednak jedyny rodzaj pętli. Wyróżnia się także pętle typu while – czyli wykonywanie tych samych czynności pod pewnymi warunkami (póki istnieją warunki wyrażone przez tak zwany niezmiennik pętli – wyrażenie logiczne) oraz pętla typu repeat – czyli wykonywanie operacji tak długo, aż osiągniemy zamierzony efekt – cel wyrażony także przez wyrażenie logiczne. W pętli while warunek sprawdzamy na początku, a wykonanie operacji następuje, gdy jest on prawdziwy (jeśli nie – sterowanie przechodzi do miejsca po pętli). W pętli repeat warunek sprawdza się na końcu, a gdy jest spełniony – nie następuje nawrót do początku. Pętle te są równoważne i czasem występuje tylko pierwsza z nich (while) – która jest bardziej naturalna (to jakby zwielokrotnienie instrukcji warunkowej). Lepsze zrozumienie tego zagadnienia zapewni lektura części dotyczącej implementacji algorytmów.

czytaj dalej: Implementacja algorytmów