2. Algorytmy i języki programowania
Instrukcje zapisane w programie powinny łącznie realizować jakieś zadanie,
rozwiązywać jakiś problem. Jest oczywiście możliwe napisanie programu,
który składa się z jakichś przypadkowych instrukcji, ale nie ma w tym za
wiele sensu.
Powinniśmy zatem spojrzeć na pojęcie programu z innego (niż "techniczny",
związany z wykonywaniem przez procesor instrukcji) punktu widzenia.
Skoro programy służą do rozwiązywania jakichś problemów, realizacji zadań, to punktem wyjścia programowania
powinno być sformułowanie problemu lub zadania, sposobu jego rozwiązania,
kroków prowadzących do realizacji celu. Innymi słowy - sformułowanie
algorytmu rozwiązania problemu lub wykonania zadania.
ALGORYTM to przepis postępowania prowadzący
do rozwiązania określonego zadania; zbiór poleceń dotyczących pewnych obiektów
(danych) - ze wskazaniem kolejności, w jakiej mają być wykonane; wykonawcą
jest układ, który na sygnały reprezentujące polecenia reaguje ich realizowaniem
- może nim być człowiek lub urządzenie automatyczne, np. komputer.
( źródło: Encyklopedia PWN)
Algorytmy możemy wyrazić w różny sposób: w języku naturalnym, graficznie
- w postaci schematu blokowego lub też w tzw. pseudo-kodzie (wybranym
języku opisu algorytmów, który jest niezależny od konkretnych, dostępnych
języków programowania).
Wyobraźmy sobie np., że zamierzamy kupić nowy komputer i stoi przed
nami zadanie skonfigurowania go i policzenia całkowitej ceny (wg dostępnego
cennika części).
W pierwszym przybliżeniu najprostszy algorytm realizacji tego zadania
możemy opisać w kolejnych krokach
- Wybierz z cennika procesor, zapisz jego cenę
- Wybierz z cennika pamięć RAM, zapisz jej cenę
- Wybierz z cennika płytę główną, zapisz jej cenę
- Wybierz z cennika kartę graficzną, zapisz jej cenę
- Wybierz z cennika dysk twardy, zapisz jego cenę
- Wybierz z cennika CDROM lub DVD, zapisz jego cene
- Wybierz z cennika kartę dźwiękową, zapisz jej cenę
- Wybierz obudowę i potrzebne akcesoria, zapisz ich ceny
- Zsumuj wszystkie ceny
Jest to zapis w języku naturalnym. Graficznie algorytm ten (z pewnymi
skrótami, ale bez zmniejszenia ogólności) moglibyśmy przedstawić w następujący
sposób.
Widzimy tu ściśle określoną sekwencję kolejnych kroków Algorytm ma swój
początek, jego wykonalność i zakończenie pracy są gwarantowane, może być
także wykonywany wielokrotnie, z różnymi danymi - w naszym przypadku różnymi
opcjami, dotyczącymi konfiguracji komputera.
Ten algorytm jest dla nas zrozumiały. Potrafimy go wykonać, choćby z
ołówkiem i kartką papieru.
Powstaje pytanie, w jaki sposób zadanie wyliczenia ceny można powierzyć
komputerowi?
Oczywiście, domyślamy się, że algorytm należy zapisać w jakimś języku
programowania (otrzymamy wtedy program w postaci źródłowej), przetłumaczyć
na język zrozumiały dla procesora ( program w postaci wykonywalnej
), następnie ten "wykonywalny" program uruchomić.
Od razu jednak natkniemy się na pewien podstawowy problem: co tak naprawdę
znaczy sformułowanie "wybierz ..., zapisz cenę."; kogo ma dotyczyć ta sekwencja
instrukcji do wykonania - tylko komputera, czy również nas samych - jako
użytkowników programu realizującego dany algorytm?
Skoro na podstawie algorytmu mamy stworzyć program, a program ma być
wykonywany przez komputer, to algorytm powinniśmy formułować w kategoriach
czynności wykonywanych przez komputer.
Zauważmy więc, że w ogólnym sensie omawiany algorytm realizuje przetwarzanie
jakichś danych wejściowych (podawanych przez użytkownika) w
dane wyjściowe (wynik działania algorytmu).
Musimy sprecyzować: jakie dane i kiedy ma podawać użytkownik i co z tymi
danymi ma robić komputer.
Mamy co najmniej trzy możliwości:
- użytkownik podaje konkretne ceny, program wylicza ich sumę;
- użytkownik podaje charakterystyki składników, program odszukuje np.
w jakiejś internetowej bazie danych ich ceny i sumuje je;
- użytkownik podaje kryteria wyboru konfiguracji sprzętowej, program
według tych kryteriów dokonuje wyboru konkretnych opcji sprzętowych i sumuje
ich ceny.
W pierwszym przypadku nasz algorytm tylko nieco się zmieni. Pamiętajmy:
formułujemy go w kategoriach czynności wykonywanych przez komputer.
1. Zapytaj użytkownika o cenę procesora
2. Zapytaj użytkownika o cenę płyty głównej
...
n-1. Zsumuj podane ceny
n. Podaj użytkownikowi wynik (cenę komputera)
Inne, przedstawione wyżej przypadki, prowadzą do algorytmów znacznie
bardziej skomplikowanych.
Zauważmy jeszcze, że ten prosty algorytm ma bardzo ogólną postać. Przełożenie
go na jakiś język programowania wymaga podjęcia wielu decyzji, np.
- w jaki sposób ma odbywać się interakcja z użytkownikiem: w jaki sposób
pytać go o dane wejściowe i jak pokazywać wynik (dane wyjściowe) ?
- w jaki sposób wykonywać sumowanie: czy przechowywać ceny poszczególnych
składników, czy składać je inkrementalnie mając na wyjściu do dyspozycji
tylko wynikową, sumaryczną cenę?
- w jaki sposób reagować na błędy danych ?
Decyzje te dotyczą zaprojektowania tzw. interfejsu użytkownika
(czyli sposobu komunikowania się programu z użytkownikiem) oraz przemyślenia
struktury algorytmu pod względem odporności na błędy i łatwości
modyfikacji. Np. w naszym algorytmie powinniśmy sprawdzać, czy użytkownik
nie wprowadził czasem danych, które nie są liczbą i zastanowić się, czy
nie przechowywać cen poszczególnych składników komputera, bo być może za
jakiś czas zmienimy zestaw danych wyjściowych i będziemy chcieli pokazać
użytkownikowi "raport z obliczeń", przedstawiający, oprócz sumarycznej ceny,
ceny poszczególnych składników, a może nawet ich procentowy udział w łącznym
koszcie.
Już tylko reagowanie na błędy danych zmieni sekwencję kroków
naszego algorytmu.
Zazwyczaj zresztą rozwiązanie jakiegoś problemu lub wykonanie jakiegoś
zadania wymaga - oprócz jakichś prostych sekwencji kroków: :
- sprawdzania jakichś warunków i na tej podstawie podejmowania decyzji
o wyborze dalszych kroków algorytmu
- iteracyjnego wykonania jakichś fragmentów algorytmu (powtarzania
ich wykonania wielokrotnie, zadaną liczbę razy lub dopóki spełnione sa
jakieś warunki)
Uwzględniając możliwe błędy przy podawaniu danych przez użytkownika oraz
potrzebę przechowywania danych o podanych cenach składników, algorytm
wyliczenia ceny komputera może wyglądac tak:
1. Zapytaj użytkownika o cenę procesora
2. Jeżeli podana cena nie jest liczbą,
powiadom użytkownika o błędzie
i wróć do kroku 1
3. Zapisz cenę procesora (do ew. późniejszego użycia)
4. Zapytaj użytkownika o cenę płyty głównej
5. Jeżeli podana cena nie jest liczbą,
powiadom użytkownika o błędzie
i wróć do kroku 4
6. Zapisz cenę płyty głównej (do ew. późniejszego użycia)
... inne składniki
... inne składniki
n-1. Wylicz sumę cen składników
n. Pokaż wyniki
Na schematach blokowych podejmowanie decyzji przedstawia się w postaci rombu.
Przykład: schemat blokowy algorytmu obliczania podatku.
Algorytmy możemy zapisywać również w pseudo-kodzie, czyli skróconej i
do pewnego stopnia sformalizowanej formie języka naturalnego, niezależnej
od konkretnego języka programowania. Pseudo-kod jest znacznie bliższy
językom programowania niż język naturalny i łatwiej jest przekładać go na
program zapisany w konkretnym języku programowania. W różnych podręcznikach
programowania znaleźć można różne formy pseudo-kodu, sami możemy także opracować
dla siebie własny pseudo-kod.
W pseudo-kodzie możemy posługiwać się pojęciem zmiennej, czyli symbolicznego
oznaczenia danych (więcej o pojęciu zmiennej w następnym wykładzie; teraz
możemy traktować je nieco podobnie jak w matematyce).
Operacje na zmiennych możemy zapisać skrótowo za pomocą operatorów
czyli symboli dodawania, odejmowania, mnożenia, porównania itp. (więcej
o operatorach w następnym wykładzie).
W pseudo-kodzie muszą znajdować się także słowa i wyrażenia, precyzyjnie okreslające
znaczenie fragmentów algorytmu (czynności, instrukcje do wykonania). Np.
podejmowanie decyzji może być zapisane w postaci:
jeżeli (warunek) to ...
albo
jeżeli (warunek) to ...
w przeciwnym razie ...
a pętle iteracyjne (czyli powtarzanie fragmentów algorytmu):
wykonuj dopóki (warunek) ...
wykonuj zmieniając wartość zmiennej i od p do l ...
Natomiast wprowadzanie i wyprowadzanie danych można wyrazić np. za pomocą
słów czytaj, pisz.
Używając symboli +, - i * dla wyrażenia operacji dodawania, odejmowania i
mnożenia, nawiasów (jak w matematyce) do grupowania operacji i specjalnych
słów dla wyrażenia czynności i decyzji, algorytm wyliczenia podatku możemy
teraz zapisać jako:
czytaj dochód
jeżeli (dochód > 74048) to podatek = 17048.44 + 0.4 * (dochód - 74048)
w przeciwnym razie jeżeli (dochód > 37024) to
podatek = 6541.24 + 0.3 * (dochód - 37024)
w przeciwnym razie podatek = 0.19 * dochód - 493.32
pisz podatek
Przy zapisie w ten sposób algorytmu obliczenia ceny komputera natkniemy się
jednak na dwa problemy.
Po pierwsze, błąd przy wprowadzaniu danych zmienia sekwencję kroków algorytmu
i powoduje powrót do kroku wczytywania danych. W pseudo-kodzie moglibyśmy to
zapisać jako instrukcję przejścia do konkretnego fragmentu algorytmu (
idż do ..), oznaczonego jakąś etykietą (etykieta będzie słowem zakończonym
dwukropkiem). Przy okazji, wprowadzimy do naszego pseudo-kodu nawiasy klamrowe,
które będą grupować czynności; np. w kontekście:
jeżeli (warunek) to {
czynność 1
czynność 2
}
przy zajściu warunku zostaną wykonane po kolei czynności podane w nawiasach
klamrowych.
pobieranieDanych1:
pisz "Podaj cenę procesora"
czytaj cenaProcesora
jeżeli (cenaProcesora nie jest liczbą) to {
pisz "Wadliwe dane"
idź do pobieranieDanych1
}
pobieranieDanych2:
pisz "Podaj cenę płyty głównej"
czytaj cenaPłyty
jeżeli (cenaPłyty nie jest liczbą) to {
pisz "Wadliwe dane"
idź do pobieranieDanych2
}
...
cenaWynikowa = suma cen części
pisz cenaWynikowa
Taki sposób zapisu powoduje jednak, że algorytmy (i programy) stają się trudno
czytelne, a ich logika zawikłana i narażona na błędy.
Dlatego w większości języków programowania nie ma już instrukcji goto
( idź do). Zamiast tego stosowane są instrukcje iteracyjne. Jest to również
powód dla którego straciły na popularności schematy blokowe (okazuje się
bowiem, że schematy blokowe nie zawsze, a zawsze niezbyt bezpośrednio przekładają
się na "programowanie bez goto").
Algorytm wyliczenia ceny komputera powinniśmy więc wyrazić w inny sposób,
np. wprowadzając zmienną logiczną o nazwie trzebaPobraćDane, która może przyjmować
dwie symboliczne wartości tak i nie, oraz używając instrukcji
iteracyjnych.
trzebaPobraćDane = tak
wykonuj dopóki (trzebaPobraćDane) {
pisz "Podaj cenę procesora"
czytaj cenaProcesora
jeżeli (cenaProcesora nie jest liczbą) to pisz "Wadliwe dane"
w przeciwnym razie trzebaPobraćDane = nie
}
trzebaPobraćDane = tak
wykonuj dopóki (trzebaPobraćDane) {
pisz "Podaj cenę płyty głównej"
czytaj cenaPłyty
jeżeli (cena
Płyty nie jest liczbą) to pisz "Wadliwe dane"
w przeciwnym razie trzebaPobraćDane = nie
}
...
cenaWynikowa = suma cen części
pisz cenaWynikowa
Na początku zmienna trzebaPobraćDane ma wartość tak i warunek w
wykonuj dopóki jest prawdziwy, zatem rozpoczyna się wykonanie instrukcji
w nawiasach klamrowych. Jeżeli wprowadzone dane (cenaProcesora) nie są liczbą,
to wypisywany jest komunikat "Wadliwe dane", wartość zmiennej trzebaPobraćDane
nie zmienia się i czynności zapisane w nawiasach klamrowych wykonywane są
ponownie (bowiem warunek w wykonuj dopóki nadal jest prawdziwy). W
przeciwnym razie (jeśli cenaProcesora jest liczbą), zmienna trzebaPobraćDane
przybiera wartość nie, wobec czego warunek w wykonuj dopóki
przestaje być prawdziwy i czynności w nawiasach klamrowych nie są kolejny
raz wykonywane, a algorytm kontynuuje działanie od miejsca po zamykającym
nawiasie klamrowym - rozpoczyna pobieranie danych dotyczących ceny płyty
głównej.
Drugi problem, związany z tym algorytmem polega na powielaniu bardzo podobnych
(niemal identycznych) czynności. Zwróćmy uwagę: pobieranie cen dla procesora,
płyty, innych komponentów - wygląda praktycznie tak samo. Moglibyśmy więc
wyodrębnić te czynności i zapisać je jeden raz w postaci tzw. procedury
lub funkcji, a jednokrotnie zapisane w niej czynności wykonywać
wielokrotnie dla różnych komponentów komputera.
Oznacza to, że dzielimy nasz problem obliczenia ceny komputera na dwa podproblemy:
podproblem wprowadzania i weryfikacji danych oraz główny problem właściwych
obliczeń. Każdy z tych problemów możemy rozwiązywać w dużym stopniu niezależnie,
skupiać się każdorazowo na specyficznych w danym kontekście cechach.
Ten sposób tworzenia algorytmów i programów nazywa się programowaniem
strukturalnym.
W następnych wykładache poznamy bliżej pojęcie funkcji i zastosujemy je w
praktyce.
Podsumujmy:
- programy piszemy po to, by rozwiązywać jakieś problemy lub realizować jakieś zadania;
- zanim napiszemy program, który realizuje jakieś zadanie, musimy opracować
algorytm postępowania, prowadzącego do realizacji tego zadania;
- algorytm jest przepisem, zbiorem poleceń wykonywanych na danych,
opisem sposobu przekształcenia danych wejściowych w dane wyjściowe;
- program jest zapisem algorytmu oraz danych w konkretnym języku
programowania;
- po to by program mógł być wykonany przez komputer jego zapis w konktretnym
języku programowania musi być przetłumaczony na język instrukcji rozumianych
przez procesor; takiego tłumaczenia dokonują specjalne programy nazywane translatorami,
kompilatorami i interpreterami.
Zwróćmy szczególną uwagę na to, że w programach nie tylko odzwierciedlamy
kroki ( polecenia, czynności) algorytmów, ale również musimy w jakiś sposób
przedstawiać dane, których czynności te dotyczą. Dane mogą być obrazowane
w różny sposób - mogą być opisywane jako pojedyncze egzamplarze albo jako
zestawy, (powiązanych i/lub w okreslony sposób uporządkowanych) danych. W
tym kontekście mówimy o strukturach danych.
Możemy zatem podać inną od poprzedniej definicję programu (autorstwa N.
Wirtha).
PROGRAM - to skonkretyzowane sformułowanie
abstrakcyjnego algorytmu na podstawie określonej reprezentacji i struktury
danych.
Obie definicje nie są sprzeczne. Pierwsza, przytoczona na wstępie tego wykładu
("program jako zestaw instrukcji wykonywanych przez procesor") akcentuje
działanie, druga ("program jako konkretny zapis algorytmu") akcentuje tworzenie
programu.
Tekst programu zapisujemy w wybranym języku programowania.
Każdy język programowania posiada swój alfabet, czyli zbiór znaków
(liter i cyfr) z których mogą być konstruowane symbole języka (ciągi znaków). Reguły składniowe definiują dopuszczalne sposoby tworzenia symboli
oraz dopuszcalne porządki ich występowania w programie, zaś semantyka
języka okresla znaczenie wybranych symboli. Np. w jakimś języku programowania
możemy się posługiwać alfabetem składającym się z liter, cyfr, znaków specjalnych
(alfabet języka); z liter i cyfr możemy tworzyć nazwy zmiennych, niektóre
ciągi znaków (np. if ) mogą być zarezerwowane i oznaczają instrukcje języka,
sposób łączenia ze sobą symboli jest określony (np. napis if (a == b) a =
0; będzie poprawny składniowo, a napis if a = b a = 0 będzie niepoprawny);
znaczenie ciągów symboli jest okreslone np. a = 3 oznacza przypisanie zmiennej
a wartości 3).
Istnieje wiele (dziesiątki tysięcy) języków programowania. Można je klasyfikować
według różnych kryteriów.
Niewatpliwie najwazniejszym jest logiczna struktura języka i sposób tworzenia programów w danym
języku.
Języki imperatywne wymagają od programisty wyspecyfikowania konkretnej
sekwencji kroków realizacji zadania, natomiast języki deklaratywne
- opisują relacje pomiędzy danymi w kategoriach funkcji (języki funkcyjne
) lub reguł (języki relacyjne, języki programowania logicznego
), a wynik działania programu uzyskiwany jest poprzez zastosowanie wobec
opisanych relacji określonych gotowych, wbudowanych "w język" algorytmów. Podejście obiektowe polega przede wszystkim na łącznym rozpatrywaniu
danych i możliwych operacji na nich, dając możliwość tworzenia i używania
w programie nowych typów danych, odzwierciedlających dziedzinę problemu, programowanie proceduralne (czasami kojarzone z imperatywnym) rozdziela
dane i funkcje i nie dostarcza sposobów prostego adekwatnego odzwierciedlenia
dziedziny rozwiązywanego problemu w strukturach danych, używanych w programie.
Przykładami języków proceduralnych są: ALGOL, FORTRAN, PL/I, C. Języki obiektowe
to np. SmallTalk, Java, C++, C#. Najbardziej znanym językiem funkcyjnym jest
Haskell, zaś językiem programowania logicznego - Prolog.
Inny podział dotyczy sposobu w jaki tekst programu przekształcany jest na
instrukcje dla procesora.
Mamy tu podział na języki kompilowane i interpretowane.
Kompilator tłumaczy program źródłowy na instrukcje, które mogą
być wykonane przez procesor i jednocześnie sprawdza składniową poprawność
programu, sygnalizując wszelkie błędy. Proces kompilacji jest więc nie tylko
porcesem tłumaczenia, ale również weryfikacji składniowej poprawności programu.
W językach kompilowanych tekst programu ( program źródłowy)
tłumaczony jest na kod binarny (pośredni) przez specjalny program
nazywany kompilatorem. Zazwyczaj inny program zwany linkerem
- generuje z kodu pośredniego gotowy do działania binarny kod wykonywalny
i zapisuje go na dysku w postaci pliku typu wykonywalnego (np. z rozszrzeniem
EXE lub z nadanym atrybutem "zdolny do wykonywania"). W ten sposób działają
takie języki jak C czy C++. Czasem kompilator produkuje symboliczny kod
binarny, który jest wykonywany za pomocą interpretacji przez program
zwany interpreterem. Tak właśnie dzieje się w przypadku języka Java.
Interpreter wykonuje bezpośrednio tekst programu. Zatem składniowa
poprawność jest sprawdzana zazwyczaj dopiero w trakcie działania programu,
aczkolwiek niektóre języki interpretowane udostępniają fazę symbolicznej
kompilacji do kodu pośredniego, podczas której sprawdzana jest poprawność
źródła.
W językach interpretowanych kod programu (źródłowy lub
pośredni) jest odczytywany przez specjalny program zwany interpreterem.
który na bieżąco - w zależności od przeczytanych fragmentów programu - przesyła
odpowiednie polecenia procesorowi i w ten sposób wykonuje program.
Przykładami języków interpretowanych są: REXX, ObjectREXX, Perl, PHP.
Reasumując, proces programowania można przedstawić na poniższym rysunku za pomocą następującego algorytmu.
|