« poprzedni punkt 

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

  1. Wybierz z cennika procesor, zapisz jego cenę
  2. Wybierz z cennika pamięć RAM, zapisz jej cenę
  3. Wybierz z cennika płytę główną, zapisz jej cenę
  4. Wybierz z cennika kartę graficzną, zapisz jej cenę
  5. Wybierz z cennika dysk twardy, zapisz jego cenę
  6. Wybierz z cennika CDROM lub DVD, zapisz jego cene
  7. Wybierz z cennika kartę dźwiękową, zapisz jej cenę
  8. Wybierz obudowę i potrzebne akcesoria, zapisz ich ceny
  9. 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.

Rysunek - alg 1 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.

Rysunek - algorytm 2

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.

Rysunek - jezyki

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.

Rysunek - programowanie


« poprzedni punkt