poniedziałek, 11 czerwca 2012


Instrukcja warunkowa


Instrukcja warunkowa jest elementem języka programowania, które pozwala na wykonanie różnych obliczeń w zależności od tego czy zdefiniowane przez programistę wyrażenie logiczne jest prawdziwe, czy fałszywe. Możliwość warunkowego decydowania o tym, jaki krok zostanie wykonany w dalszej kolejności jest jedną z podstawowych własności współczesnych komputerów – dowolny model obliczeń zdolny do wykonywania algorytmów (tj. równoważny maszynom Turinga) musi ją posiadać[1].
W imperatywnych językach programowania używa się terminu instrukcja warunkowa, podczas gdy w programowaniu funkcyjnym preferowane są nazwy wyrażenie warunkowe lubkonstrukcja warunkowa, gdyż posiadają one inną zasadę działania.

Warunki w maszynach Turinga

W teorii złożoności obliczeniowej maszyna Turinga jest wzorcowym, matematycznym modelem obliczeń komputerowych zdolnym do wykonywania algorytmów[2]. Składa się ona z nieskończonej taśmy podzielonej na komórki z symbolami oraz głowicy. W każdym kroku głowica może zmienić symbol nad aktualnie przeglądaną komórką, zmienić swój stan oraz przesunąć się w lewo lub w prawo. Program definiowany jest jako tablica stanów i dopuszczalnych przejść między nimi w zależności od widzianego symbolu[3]. Możemy ją rozpatrywać jako rodzaj warunku, a każdy krok obliczeń – jako jego ewaluację[4]. Przykładowo, element tablicy przejść \delta (2, a) \rightarrow (4, c, \leftarrow) może być rozumiany jako warunek "jeśli jesteśmy w stanie 2 i widzimy symbol a, przechodzimy do stanu 4, zapisujemy symbol c i przesuwamy się w lewo"

Rodzaje instrukcji warunkowych

We współczesnych językach programowania można spotkać wiele rodzajów instrukcji warunkowych.

If-Then

Podstawowym rodzajem instrukcji warunkowej jest If-Then. Jest spotykany w większości języków programowania i umożliwia warunkowe wykonanie określonego bloku kodu, a jeśli warunek nie jest spełniony – alternatywnego bloku. Pomiędzy językami występują nieznaczne różnice składniowe, ale ogólny schemat w pseudokodzie zawsze wygląda następująco:
if warunek then
    właściwy blok kodu
else
    alternatywny blok kodu
end if
Na początku wykonywana jest ewaluacja warunku podanego w postaci wyrażenia logicznego. Jeśli wynikiem jest true, wykonywany jest właściwy blok kodu, a jeśli false – alternatywny. Następnie program kontynuuje od pierwszej komendy po end if.
Wiele języków programowania umożliwia zdefiniowanie więcej niż jednego warunku do sprawdzenia przy pomocy opcjonalnego bloku else-if:
if warunek 1 then
    pierwszy blok kodu
else-if warunek 2 then
    drugi blok kodu
else-if warunek 3 then
    trzeci blok kodu
else
    alternatywny blok kodu
end if
W tym wypadku warunki ewaluowane są po kolei do momentu, gdy któryś z nich nie da wartości true – wykonywany jest wtedy przypisany mu blok kodu. Jeśli żaden z warunków nie będzie prawdziwy, wykonywany jest blok alternatywny. Bez względu na ilość prawdziwych warunków, zawsze wykona się tylko pierwszy z nich, a pozostałe zostaną pominięte.
W pewnych językach programowania dostępna jest konstrukcja analogiczna do opisanej wyżej instrukcji warunkowej, której działanie jest jednak odwrotne do powyższego, tzn.pierwszy blok kodu wykonywany jest, gdy warunek 1 nie jest spełniony, a inne warunki fraz else w przeciwnym razie. Jest to więc równoważnik konstrukcji if not(warunek)then instrukcja. Dla odróżnienia od konstrukcji pierwotnej stosuje się w tym przypadku inne słowo kluczowe, np. unless, w języku BCPL[5] i pochodnych (np. w język MCPL[6]), czy także w Perl[7]
.

Wyrażenia warunkowe

Wyrażenie warunkowe jest odmianą instrukcji warunkowej If-Then z tą różnicą, że wykonany blok kodu musi zwrócić jakąś wartość, która staje się jednocześnie wynikiem całego wyrażenia. Wyrażenia warunkowe są popularne w funkcyjnych językach programowania.

Operator trójargumentowy

W językach wywodzących się z C dostępny jest trójargumentowy operator zwany także operatorem wyrażenia warunkowego. Schemat składni jest następujący:
(warunek) ? (wyrażenie, gdy warunek jest prawdziwy) : (wyrażenie, gdy warunek jest fałszywy)
Efektem jego działania jest wartość drugiego lub trzeciego wyrażenia. Umożliwia on osadzanie warunków wewnątrz wyrażeń, np.
zmienna = (a > 5) ? (a * 7) : (a - 3);

Jako funkcja

W językach Visual Basic oraz SQL warunek jest funkcją trójargumentową. Działa ona trochę inaczej, niż klasyczne wyrażenie warunkowe, gdyż w trakcie wykonywania obliczana jest zawsze zarówno "prawdziwa", jak i "fałszywa gałąź", a funkcja zwraca po prostu wynik jednej z nich, drugi odrzucając.

Arytmetyczny If

Język Fortran do wersji Fortran 77 obsługiwał tzw. arytmetyczny If będący czymś pomiędzy klasycznym Ifem, a przypadkiem instrukcji wyboru bazującym na trychotomii x < 0,x = 0x > 0. Był to najwcześniejszy rodzaj instrukcji warunkowej spotykanej w tym języku[8].:
IF (e) label1, label2, label3
Gdzie e to dowolne wyrażenie numeryczne. Powyższy zapis jest równoważny następującemu:
IF (e .LT. 0) GOTO label1
IF (e .EQ. 0) GOTO label2
IF (e .GT. 0) GOTO label3

Opis stosowanych operatorów


Jeśli zmienne lub stałe poprawnie połączymy operatorami zgodnie z regułami 
matematycznymi, to otrzymamy wyrażenie. Zmienne i stałe występujące w wyrażeniu 
nazywamy operandami. Na przykład: a + 4 - b jest wyrażeniem składającym się z trzech 
operandów i dwóch operatorów. Liczba 4 jest operandem stałym, a, b to operandy zmienne. 
Operatory występujące w tym wyrażeniu to operatory arytmetyczne. Proponujemy ci 
zapoznanie się już teraz z zapisem operatorów, gdyż pomyłki w ich stosowaniu są przyczyną
wielu błędów popełnianych zwłaszcza przez początkujących programistów. 

Operatory relacji służą do tworzenia wyrażeń logicznych. Wyrażenia logiczne 
charakteryzują się tym, że możemy im przypisać wartość logiczną „prawda" lub „fałsz". Na 
przykład stwierdzamy: a < 4 lub b >= c + 1, albo badamy warunek prawdziwości relacji x < y. 
Wówczas dla zadanych wartości zmiennych moŜemy w sposób jednoznaczny odpowiedzieć: 
tak lub nie, co odpowiada wartościom logicznym: prawda lub fałsz. 
Zapis w notacji Pascala: „a = b" zinterpretujemy jako pytanie: Czy wartości 
argumentów a i b są sobie równe? Oczywiście, również tu odpowiedź jest jednoznaczna: albo 
a jest równe b, albo a nie jest równe b. 
Operator przypisania (podstawienia) opisuje operację nadania zmiennej 
umieszczonej po lewej stronie operatora wartości wyrażenia występującego po prawej stronie 
tego operatora -jest to instrukcja przypisania. Do oznaczania tej instrukcji przyjmiemy 
umownie oznaczenie operatora zgodnie ze składnią języka Pascal, czyli znak równości 
poprzedzony dwukropkiem. W składni C+ + ten sam operator jest reprezentowany przez znak 
równości


 Specyfikacja problemu algorytmicznego 

Wiesz już, co to jest algorytm, jakie wymogi powinien spełniać i jak go zapisać.
Brakuje jeszcze jednego czynnika, aby zadanie, które chcesz rozwiązać za pomocą algorytmu,
było przedstawione w pełni precyzyjnie. Jeśli bowiem zamierzasz napisać program, w którym
zastosujesz utworzony przez siebie algorytm, to musisz wiedzieć, jakiego typu są dane
wejściowe, wyniki, czyli dane wyjścia itp. Wszystkie te informacje powinny zostać
umieszczone w specyfikacji problemu algorytmicznego.
Definicja
Specyfikacją problemu algorytmicznego nazywamy dokładny opis problemu
algorytmicznego, który ma zostać rozwiązany, oraz podanie danych wejściowych i
danych wyjściowych wraz z ich typami.
Najczęściej specyfikacja składa się z opisu danych wejściowych wraz ze wszystkimi
warunkami, jakie mają one spełniać, oraz danych wyjściowych (wyników) z uwzględnieniem
warunków, jakie mają spełniać i ich związku z danymi wejściowymi. Pokażmy to na
przykładzie.
Specyfikacja problemu algorytmicznego 
Problem algorytmiczny: Obliczanie potęgi liczby naturalnej o wykładniku
naturalnym
Dane wejściowe:   a ∈ N - podstawa potęgi,  b∈ N - wykładnik potęgi
Dane wyjściowe:   w∈ N - wartość a
b
Dane w algorytmie są najczęściej przedstawiane za pomocą liter lub dłuŜszych nazw,
które nazywamy zmiennymi.
Definicja
Zmienną nazywamy obiekt występujący w algorytmie, określony przez nazwę i
służący do zapamiętywania pewnych danych.
Typy zmiennych
Jeśli używamy w algorytmie zmiennej, musimy dokładnie określić, jakiego rodzaju
wartości może ona przechowywać - mówimy, że określamy tak zwany typ zmiennej. Mogą
to być liczby całkowite, liczby rzeczywiste, litery, znaki klawiaturowe. Różne typy będziemy
omawiać w kolejnych rozdziałach naszych rozważań.
W czasie działania algorytmu można swobodnie zmieniać wartość przypisaną
zmiennej w zakresie jej typu.
Zmienna pomocnicza jest zmienną wprowadzoną do zapisu algorytmu w celu
umożliwienia jego realizacji. Zmienne pomocnicze służą w algorytmie do pamiętania danych
przejściowych, czyli danych potrzebnych do działania algorytmu, ale niebędących danymi
wejściowymi ani wynikami. Na przykład w algorytmie obliczającym średnią arytmetyczną
wielu liczb potrzebujemy dwóch zmiennych pomocniczych - jednej do zapamiętywania ilości
podanych liczb, drugiej zaś do zapamiętywania sumy podanych liczb.
Stałe w algorytmie
Prócz zmiennych w algorytmie możemy używać stałych. Mogą to być wartości
podane wprost, na przykład liczba 35, albo wartości reprezentowane przez nazwy - podobnie
jak zmienne. Wartość stałej w algorytmie nie może ulec zmianie, na przykład: używamy stałej
JT mającej wartość 3,14 i oczywiście zależy nam, aby ta wartość nie została przypadkowo
zmieniona.
Bezpośrednio po specyfikacji należy umieścić zapis algorytmu - wybór metody zapisu
należy do ciebie. My preferujemy zapis za pomocą schematu blokowego, jako najbardziej 2
czytelny dla odbiorcy. Jeśli więc do powyższej specyfikacji dodasz zapis algorytmu
sporządzony w postaci na przykład schematu blokowego, to dokumentacja słuŜąca
rozwiązaniu problemu byłaby niemal pełna. Należy bowiem jeszcze przeprowadzić ocenę
poprawności algorytmu, o czym będzie mowa w dalszej części tego rozdziału.

Wyróżnia się następujące rodzaje bloków:
Graficzne przedstawienie bloków w kolejności opisywania.
  • a) Blok graniczny − oznacza on początek, koniec, przerwanie lub wstrzymanie wykonywania działania, np. blok startu programu.
  • b) Blok wejścia-wyjścia − przedstawia czynność wprowadzania danych do programu i przyporządkowania ich zmiennym dla późniejszego wykorzystania, jak i wyprowadzenia wyników obliczeń, np. czytaj z, pisz z+10.
  • c) Blok obliczeniowy − oznacza wykonanie operacji, w efekcie której zmienią się wartości, postać lub miejsce zapisu danych, np. z := z + 1.
  • d) Blok decyzyjny, warunkowy − przedstawia wybór jednego z dwóch wariantów wykonywania programu na podstawie sprawdzenia warunku wpisanego w ów blok, np. a = b.
  • e) Blok wywołania podprogramu − oznacza zmianę wykonywanej czynności na skutek wywołania podprogramu, np. MAX(x,y,z).
  • f) Blok fragmentu − przedstawia część programu zdefiniowanego odrębnie, np. sortowanie.
  • g) Blok komentarza − pozwala wprowadzać komentarze wyjaśniające poszczególne części schematu, co ułatwia zrozumienie go czytającemu, np. wprowadzenie danych.
  • h) Łącznik wewnętrzny − służy do łączenia odrębnych części schematu znajdujących się na tej samej stronie, powiązane ze sobą łączniki oznaczone są tym samym napisem, np. A1, 7.
  • i) Łącznik zewnętrzny − służy do łączenia odrębnych części schematu znajdujących się na odrębnych stronach, powinien być opisany jak łącznik wewnętrzny, poza tym powinien zawierać numer strony, do której się odwołuje, np. 4.3, 2,B2.

Schemat blokowy


Schemat blokowy (ang. block diagram, flowchart) jest narzędziem nakierowanym na prezentację kolejnych czynności w projektowanym algorytmie. Realizowane jako diagram, na którym procedurasystem albo program komputerowy są reprezentowane przez opisane figury geometryczne, połączone liniami zgodnie z kolejnością wykonywania czynności wynikających z przyjętegoalgorytmu rozwiązania zadania.
Cechuje je:
  • zasada budowy,
  • elastyczność zapisów,
  • możliwość zapisu z użyciem składu wybranego języka programowania,
  • łatwa kontrola poprawności algorytmu.
Schematy blokowe pozwalają na prostą zamianę instrukcji na instrukcje programu komputerowego.

Elementy budowy

  • strzałka − wskazuje jednoznacznie powiązania i ich kierunek,
  • operand − prostokąt, do którego wpisywane są wszystkie operacje z wyjątkiem instrukcji wyboru,
  • predykat − romb, do którego wpisywane są wyłącznie instrukcje wyboru,
  • etykieta − owal służący do oznaczania początku bądź końca sekwencji schematu (kończą, zaczynają lub przerywają/przenoszą schemat).
Schemat blokowy pozwala dostrzec istotne etapy algorytmu i logiczne zależności między nimi.
Zależnie od przedstawianego algorytmu stosowane są różne zestawy figur geometrycznych zwanych blokami, których kształty reprezentują umownie rodzaje elementów składowych.

PRZYKŁADY ALGORYTMÓW





poniedziałek, 4 czerwca 2012


Algorytm


Algorytm – w matematyce oraz informatyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism - przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosiłMuhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku[1]. 


Definicja klasyczna


  • Algorytm to jednoznaczny przepis obliczenia w skończonym czasie pewnych danych wejściowych do pewnych danych wynikowych.
Zazwyczaj przy analizowaniu bądź projektowaniu algorytmu zakłada się, że dostarczane dane wejściowe są poprawne, czasem istotną częścią algorytmu jest nie tylko przetworzenie, ale i weryfikacja danych.
Zgodnie z założeniem o jednoznaczności dla identycznego zestawu danych początkowych, algorytm zdefiniowany klasycznie zawsze zwróci identyczny wynik.

Przykład[edytuj]

Znalezienie największej wśród niepustej, nieposortowanej listy przypadkowych liczb można przeprowadzić na wiele sposobów, jednym z najszybszych jest przedstawiony niżej. Niech \scriptstyle \mathrm{indeks} oznacza wskazuje aktualnie badany element listy (jeśli jest ona numerowana, może on oznaczać np. jej numer), a \scriptstyle \mathrm{maksimum} oznacza największą dotychczas znalezioną wartość.
  1. Niech \scriptstyle \mathrm{indeks} wskazuje na pierwszy element (początek) listy.
  2. Niech \scriptstyle \mathrm{maksimum} zawiera wartość elementu listy wskazywanego przez \scriptstyle \mathrm{indeks} (tzn. pierwszego).
  3. Jeżeli zawartość elementu listy wskazywanego przez \scriptstyle \mathrm{indeks} jest większa od zawartości \scriptstyle \mathrm{maksimum}, to przypisz \scriptstyle \mathrm{maksimum} wartość elementu wskazywanego przez \scriptstyle \mathrm{indeks}.
  4. Niech \scriptstyle \mathrm{indeks} wskazuje kolejny element listy; jeśli to niemożliwe (tzn. \scriptstyle \mathrm{indeks} wskazuje ostatni element listy, czyli jej koniec), przejdź do punktu 6.
  5. Wróć do punktu 3.
  6. Koniec.
Wykonanie tego algorytmu spowoduje, że największa liczba na wspomnianej liście będzie wartością \scriptstyle \mathrm{maksimum}; ciekawostką jest fakt, iż algorytm ten działa dla list dowolnej długości (nie wykorzystuje on liczby elementów listy, lecz tylko tzw. operację następnika danej listy, tzn. przejścia do następnego jej elementu; niemożność wskazania kolejnego elementu jest wtedy równoważna temu, iż dany element jest ostatni na liście).