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");