Wprowadzenie do algorytmów

Strona z Algebry Al-Kwarizmiego

Najważniejszym pojęciem algorytmiki jest algorytm (ang. algorithm). Nazwa pochodzi od nazwiska perskiego astronoma, astrologa, matematyka i geografa Muhameda ibn Musa Al-Kwarizmiego (arab. محمد بن موسی خوارزمی) żyjącego w latach od około 780 do 850 n.e. Był on autorem dzieła pt. Algebra (zmora dzisiejszych uczniów, nieprawdaż?) opisującego sposoby rozwiązywania różnych problemów matematycznych, np. równań wielomianowych.

Do dnia dzisiejszego nie istnieje formalna definicja algorytmu. My podamy następującą:

 

Algorytm jest ściśle określonym, skończonym i uporządkowanym ciągiem operacji, których wykonanie nad dobrze zdefiniowanym zbiorem danych prowadzi do rozwiązania określonej klasy problemów.

 

Z podanej definicji wynika kilka istotnych własności algorytmów, które każdy uczeń klasy informatycznej musi znać (patrz - kryteria ocen):

  • Jednoznaczność - operacje wykonywane przez algorytm nie można dowolnie interpretować - musi być określony jeden sposób ich wykonania.

  • Wykonalność - operacje muszą być wykonalne, np. mamy algorytm łapania tygrysa w dżungli:
        Znajdź tygrysa, z łap go za ogon i przywiąż go do najbliższego drzewa.
    Tygrys może mieć zły dzień i być dodatkowo głodny - resztę znasz...

  • Skończoność - liczba operacji może być bardzo duża, ale skończona. Wykonanie każdej operacji zajmuje pewien czas. Nieskończona liczba operacji będzie się wykonywała w nieskończoność, to co nam po takim algorytmie?

  • Porządek - operacje muszą być wykonywane w ustalonej kolejności, aby było wiadome, którą operację wykonać jako następną.

  • Ogólność - algorytm powinien rozwiązywać klasę problemów, a nie jeden przypadek szczególny. Np. algorytm obliczania sumy 2 + 2 = 4 jest złym algorytmem - lepszym jest algorytm dodawania dowolnych liczb, którego uczyłeś się na lekcjach matematyki w szkole podstawowej.

  • Efektywność - algorytm powinien dochodzić do rozwiązania najkrótszą drogą - czasem jest to trudne do spełnienia, gdyż możemy nie znać najkrótszej drogi.

Dalej w podanej definicji czytamy, iż ciąg operacji wykonywany jest nad dobrze zdefiniowanym zbiorem danych. Zatem algorytm, oprócz definicji operacji, wymaga również definicji danych, nad którymi pracuje. Definicję danych nazywamy specyfikacją algorytmu lub specyfikacją problemu. Specyfikacja składa się zwykle z dwóch podstawowych części:

Algorytm można przedstawić graficznie w sposób następujący:

Sposoby reprezentacji algorytmów

Dobrze udokumentowany algorytm powinien składać się ze specyfikacji oraz opisu operacji, który spełnia podaną na początku rozdziału definicję. Istnieje kilka użytecznych sposobów opisywania operacji, poniżej podajemy te najbardziej popularne:

Opis słowny

Operacje do wykonania opisujemy zwykłym tekstem opisowym. Tę formę prezentacji algorytmu stosuje się najczęściej w fazie wstępnej, gdy chcemy w sposób ogólny opisać operacje bez wdawania się w szczegóły techniczne. Zwykle na podstawie opisu słownego tworzymy w następnym kroku bardziej ścisłą reprezentację.

Przykład:

Algorytm obliczania obwodu i pola prostokąta.

Dane wejściowe:
a,b - długości boków prostokąta

Dane wyjściowe:
pole, obwód

Oblicza pole jako iloczyn boku a przez bok b prostokąta. Oblicz obwód jako sumę boków a i b pomnożoną przez 2.

Lista kroków

Każdą operację zapisujemy w osobnym, numerowanym kroku algorytmicznym. Stosuje się ograniczoną liczbę operacji elementarnych, które znajdziesz tutaj.. Lista kroków pozwala precyzyjnie zdefiniować cały algorytm.

Przykład:

Algorytm obliczania obwodu i pola prostokąta.

Dane wejściowe:
a,b - długości boków prostokąta

Dane wyjściowe:
pole, obwód

K01: Czytaj a,b
K02: pole ← a × b
K03: obwód ← 2 × (a + b)
K04: Pisz pole, obwód
K05: Zakończ

Schemat blokowy

Operacje przedstawiamy w sposób graficzny za pomocą następujących symboli:

oznacza początek algorytmu, czyli punkt startowy, od którego rozpoczynamy wykonywanie operacji.
oznacza koniec algorytmu.
określa następną operację do wykonania
wewnątrz tego symbolu umieszczamy operację do wykonania nad danymi
operacja wprowadzania danych do algorytmu - określa dane wejściowe, które algorytm musi odczytać.
operacja wyprowadzania wyników - określa dane wyjściowe, które produkuje algorytm.
test umożliwiający tworzenie rozgałęzień w algorytmie. Jeśli test jest spełniony, to z symbolu wychodzimy drogą oznaczoną strzałką TAK. W przeciwnym wypadku idziemy po strzałce oznaczonej NIE. Często umieszcza się przy symbolu testu tylko jeden napis TAK lub NIE. Drugi jest oczywisty.

Przykład:

Algorytm obliczania obwodu i pola prostokąta.

Dane wejściowe:
a,b - długości boków prostokąta

Dane wyjściowe:
pole, obwód

Program komputerowy

Tak, nie pomyliliśmy się. Program komputerowy jest niczym innym, jak jednym ze sposobów zapisu algorytmu przy pomocy środków dostarczanych przez język programowania. Dlatego Algorytmika jest tak ważna przy nauce programowania. Poprzednie sposoby reprezentacji algorytmów są ogólne, nie wymagają znajomości konkretnego języka programowania. Jest to zaletą, gdyż zwykle algorytm jest niezależny od konkretnego języka programowania i zapis algorytmu w postaci ogólnej pozwala później zaimplementować go w dowolnym, wybranym przez programistę języku programowania. Dlatego autorzy opracowań często wybierają jedną z poprzednich form przedstawiania algorytmów, aby uniezależnić się od zmian popularności tego, czy innego narzędzia programistycznego - np. znany autorytet w dziedzinie informatyki, profesor Donald Knuth, stworzył na potrzeby swojego dzieła "Sztuka programowania komputerów" fikcyjną maszynę cyfrową o dobrze zdefiniowanej liście poleceń i wszystkie prezentowane algorytmy przedstawiał w asemblerze tej maszyny. W ten sposób uniezależnił się od zmian stosowania języków programowania, a było ich trochę - Fortran, C, Pascal, C++, Java, PHP, Python, Ruby i tysiące innych.

Znane jest słynne powiedzenie Knutha:

"Languages come and go, but algorithms stand the test of time."
"Języki programowania przychodzą i odchodzą, lecz algorytmy opierają się próbie czasu"
 

// Pole i obwód prostokąta
// (C) I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
  unsigned int a,b,pole,obwod;

  cout << "Obliczanie pola i obwodu prostokata\n"
          "-----------------------------------\n\n";

// odczytujemy długości boków a i b

  cout << "Bok a = "; cin >> a;
  cout << "Bok b = "; cin >> b;
  cout << endl;

// wykonujemy obliczenia obwodu i pola

  obwod = 2 * (a + b);
  pole  = a * b;

// wyświetlamy wyniki obliczeń

  cout << "Obwod = " << obwod << endl
       << "Pole  = " << pole << endl << endl;

  system("pause");
  return 0;
}

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.