Algorytmy

1. Definicja algorytmu

• 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.

 2. Rodzaje algorytmów

- algorytm liniowy

Algorytm liniowy to taki, w którym nie określono żadnych warunków. Jest też nazywany sekwencyjnym, gdyż każdy z kroków w tym algorytmie następuje sekwencyjnie, czyli wykonanie jednej sekwencji powoduje przejście bezpośrednio do następnej.

- algorytm warunkowy

Algorytm warunkowy to taki, w którym wykonanie instrukcji uzależnione jest od spełnienia lub niespełnienia warunku.

- algorytm iteracyjny

Algorytm z iteracją to taki, w którym trzeba wielokrotnie powtarzać instrukcję, aby warunek został spełniony.

- algorytm rekurencyjny

 Algorytm rekurencyjny, algorytm, który wywołuje sam siebie do rozwiązania tego samego problemu.

3. Sposoby reprezentowania algorytmu

- lista kroków

Przykład:

Algorytm warunkowy w postaci listy kroków – obliczanie obwodu prostokąta

Dane: bok a i b

Lista kroków:

1. Początek algorytmu

2. Podaj bok a

3. Podaj bok b

4. Czy bok a>0?
    jeśli tak idź do kroku 5,
    jeśli nie podaj komunikat wyjściowy: "nie można obliczyć obwodu" i zakończ algorytm.

5. Czy bok b>0?
    jeśli tak idź do kroku 6
    jeśli nie podaj komunikat wyjściowy: "nie można obliczyć obwodu" i zakończ algorytm.

6. Oblicz obwód Ob:=2*a+2*b

7. Wyprowadź wartość Ob

6. Koniec algorytmu

- schemat blokowy

Przykład:

Algorytm liniowy w postaci schematu blokowego – obliczanie obwodu prostokąta

- drzewa

 - pseudokod

Pseudokodem nazywany jest taki sposób zapisu algorytmu, który, zachowując strukturę charakterystyczną dla kodu zapisanego w języku programowania, rezygnuje ze ścisłych reguł składniowych na rzecz prostoty i czytelności. Pseudokod nie zawiera szczegółów implementacyjnych (jak np. inicjalizacja zmiennych, alokacja pamięci), często też opuszcza się w nim opis działania podprocedur (jeśli powinien być on oczywisty dla czytelnika), zaś nietrywialne kroki algorytmu opisywane są z pomocą formuł matematycznych lub zdań w języku naturalnym.

Przykład pseudokodu algorytmu Euklidesa:

NWD(liczba całkowita a, liczba całkowita b)
        dopóki b != 0
                c := reszta z dzielenia a przez b
                a := b
                b := c
        zwróć a 

 - kod właściwy

 Przykład kodu właściwego algorytmu Floyda-Warshalla:


this.path = path;
next = new int[len, len];
for (int i = 0; i < len; i++)
    for (int j = 0; j < len; j++)
        if (path[i, j] == INF)
            next[i, j] = INF;
        else
            next[i, j] = i;
for (int k = 0; k < len; k++)
    for (int i = 0; i < len; i++)
        for (int j = 0; j < len; j++)
            if (path[i, k] != INF && path[k, j] != INF &&
                path[i, k] + path[k, j] < path[i, j])
            {
                path[i, j] = path[i, k] + path[k, j];
                next[i, j] = k;
            }
for (int i = 0; i < len; i++)
    if (path[i, i] < 0)
        throw new ArgumentException("Negative cycles");