ALGORYTMY


spis treści

powrót do strony głównej

Wstęp

Podstawą do programowania jest znajomość algorytmów. Na tej stronce znajdziesz wprowadzenie do algorytmów, metody przedstawiania algorytmów.
Na początek co to jest algorytm?
Algorytm jest przepisem opisującym krok po kroku rozwiązanie problemu lub osiągnięcia jakiegoś celu.

powrót

Cechy algorytmu

  1. Skończoność
    realizowany ciąg operacji powinien mieć swój koniec
  2. Określoność
    operacje jak i porządek ich wykonywania powinien być ściśle określony, nie zostawiając miejsca na dowolne interpretowanie
  3. Ogólność
    algorytm nie ogranicza się do jednego przypadku, ale odnosi się do pewnej klasy zadań
  4. Efektywność
    powinien prowadzić do rozwiązania możliwie najprostrzą drogą

powrót

Sposoby przedstawiania algorytmów

Opis słowny

Pokaże to na przekładzie:
Obliczyć wartość funkcji f(x)=x/|x|. Przedstawić algorytm jako opis słowny.

wartość funkcji f(x):
f(x)=-1 dla x<0
f(x)=0 dla x=0
f(x)=1 dla x>0

Opis algorytmu:
Dane: dowolna liczba rzeczywista x
Wynik: wartość funkcji f(x)
Krok 0: wczytaj wartość danej x
Krok 1: jeśli x>0 to f(x)=1, zakończ
Krok2: jeśli x=0 to f(x)=0, zakończ
Krok 3: jeśli x<0 to f(x)=-1, zakończ

Drzewo algorytmu(drzewo obliczeń)

Narysuj drzewo algorytmu dla funkcji f(x)=x/|x|

Drzewo wyrażenia

Zbuduj drzewo wyrażenia (5+3) - (2+8)


Schemat blokowy algorytmu

Zasady budowy:
Kazda operacja, relacja lub informacja umieszczona jest w skrzynce
Kolejność wykonywania operacji wyznaczają połączenia między skrzynkami
Każde połączenie jest zaczepione początkiem do skrzynki a koniec do innej skrzynki lub innego połączenia
Skrzynki przybierają kształty: prostokąta, rombu, równoległoboku, okręgu

Rodzaje skrzynek:

skrzynka operacyjna
służy ona do m.in. deklaracji zmiennych, obliczeń
skrzynka warunkowa(decyzyjna)
ta skrzynka posiada dwa wyjścia nie, tak( prawda, fałsz), sprawdza czy dane wyrażenia jest prawdą czy nie
skrzynka wprowadzania i wyprowadzania informacji(we/wy)
jak sama nazwa wskazuje służy do wprowadzania lub wyprowadzania infoemacji
skrzynka graniczna(start, stop)
stosyje się ją gdy rozpoczynamy algorytm i w miejscu gdzie algorytm przestaje działać
skrzynka łącznikowa
gdy schemat blokowy znajduje sie na kilku kartkach, tą skrzynką zaznaczamy gdzie jest następny ciąg algorytmu
skrzynka komentarza
skrzynka komentarza służy do opisywania danego algorytmu np nazwy, co dana zmienna oznacza

powrót

Procedura

Procedurą nazywamy wyodrębnioną część algorytmu posiadającą jednoznaczną nazwę oraz ściśle określony sposób wymiany informacji z pozostałą częścią algorytmu.
Procedurę opisujemy za pomocą deklaracji zaś stosujemy przez wywołanie

Procedure <nazwa>(<lista parametrów formalnych>) - deklaracja
<nazwa>(<lista parametrów formalnych>) - wywołanie

Rozróżniamy procecdurę rekurencyjną i iteracyjną
Procedurą rekurencyjną nazywamy taką procedurę która w ciele wywołyje samą siebie
Procedurą iteracyjną nazywamy procedurę w której główną instrukcją jest instrukcja iteracji(pętla)

powrót

Poprawność algorytmów

Poprawność logiczna (semantyczna)
Mówimy że algorytm jest semantycznie poprawny wzgledem warunków wejściowych A i wyjściowych B wtedy i tylko wtedy gdy dla każdych danych wejściowych spełniające warunki wejściowe A obliczanie algorytmu dochodzi do punktu końcowego i jego wynik spełnia warunki wyjściowe B.
Aby udowodnić poprawność algorytmu należy:

  1. pokazać że dla każdych danych wejściowych spełniających warunki A jeśli obliczenia dochodzą do końca to jego wyniki spełnią warunki wyjściowe B(warunek częściowej poprawności)
  2. pokazać że wszystkie operacje opisane w algorytmie są dobrze określone dla danych spełniających warunek A(własność określoności)
  3. pokazać że dla każdej danej wejściowej A obliczanie algorytmu nie jest nieskończone (własność stopu)

powrót

Złożoność obliczeniowa algorytmów

powrót

Przykładowe schematy blokowe

algorytm obliczający pole koła (użytkownik podaje promień)

algorytm obliczający silnie z podanej liczby(wersja rekurencyjna)

powrót