Algorytm

Algorytm to nic innego jak zbiór ściśle określonych reguł lub instrukcji, które prowadzą do rozwiązania konkretnego problemu lub wykonania danego zadania. Stanowi on sekwencję logicznych kroków, które należy podjąć w celu przekształcenia danych wejściowych w pożądany wynik końcowy. Algorytmy mogą być stosowane w różnych dziedzinach, od matematyki i informatyki po codzienne czynności, takie jak przepisy kulinarne.

Cechy dobrego algorytmu

Poprawnie skonstruowany algorytm powinien spełniać kilka kluczowych kryteriów:

1. Jednoznaczność – dla tych samych danych wejściowych, algorytm musi generować identyczne wyniki, niezależnie od kontekstu.
2. Skończoność – algorytm powinien zakończyć swoje działanie w skończonym czasie, wykorzystując dostępne zasoby obliczeniowe.
3. Efektywność – optymalne algorytmy prowadzą do rozwiązania problemu w jak najmniejszej liczbie kroków, minimalizując zużycie zasobów.
4. Poprawność – wyniki generowane przez algorytm muszą być zgodne z oczekiwaniami i spełniać określone warunki.

Reprezentacja algorytmów

Algorytmy można przedstawiać na różne sposoby, w zależności od stopnia złożoności i preferencji twórcy. Oto niektóre z popularnych metod reprezentacji:

Opis słowny

W opisie słownym operacje, które należy wykonać, są zapisywane za pomocą zwykłego tekstu. Ten sposób jest często stosowany we wstępnej fazie opisu problemu, gdy trzeba ogólnie przedstawić wymagane działania bez wchodzenia w szczegóły implementacji.

Lista kroków

Lista kroków to zbiór numerowanych instrukcji, z których każda reprezentuje pojedynczą operację do wykonania. Ta metoda pozwala na precyzyjne zdefiniowanie całego algorytmu.

Pseudokod

Pseudokod to opis słowny przypominający zapis kroków algorytmu, który może zawierać instrukcje z języka programowania. W pseudokodzie często wykorzystuje się słowa języka naturalnego do określenia kroków algorytmu (np. "wczytaj dane", "oblicz wartość"), ale mogą się w nim również pojawić elementy symbolicznego opisu działań (np. "a=5", "powtarzaj ... aż do ...").

Drzewo algorytmu

Drzewo algorytmu to reprezentacja graficzna algorytmu w formie drzewa. W schemacie tym wyróżnia się korzeń (wierzchołek początkowy), gałęzie (wierzchołki pośrednie reprezentujące operacje) oraz liście (wierzchołki końcowe reprezentujące wyniki).

Schemat blokowy

W schemacie blokowym operacje, które należy wykonać, są przedstawione w postaci graficznej z użyciem symboli. Schematy blokowe są powszechnie wykorzystywane do wizualizacji złożonych algorytmów, ułatwiając ich zrozumienie i analizę.

Klasyfikacja algorytmów

Algorytmy można klasyfikować na różne sposoby, w zależności od przyjętych kryteriów. Oto niektóre z popularnych podziałów:

Klasyfikacja ze względu na sposób konstruowania algorytmu

1. Dziel i zwyciężaj – problem jest dzielony na mniejsze części, które są następnie rozwiązywane niezależnie, a ich wyniki są łączone w celu uzyskania rozwiązania głównego problemu.
2. Programowanie dynamiczne – podobnie jak w przypadku metody "dziel i zwyciężaj", problem jest dzielony na mniejsze części, ale wyniki analizy cząstkowych problemów są wykorzystywane do rozwiązania głównego problemu.
3. Metoda zachłanna – nie jest przeprowadzana dokładna analiza problemu, tylko wybierane jest rozwiązanie, które w danym momencie wydaje się najkorzystniejsze.
4. Poszukiwanie i wyliczanie – przeszukiwany jest zbiór danych aż do znalezienia rozwiązania.
5. Heurystyka – na podstawie niepełnych danych tworzony jest algorytm, który działa w sposób najbardziej prawdopodobny, ale nie gwarantuje poprawnego rozwiązania.

Klasyfikacja ze względu na kolejność wykonywania działań

1. Liniowy – kolejne kroki w algorytmie są wykonywane w kolejności, w jakiej zostały zapisane, bez pominięcia lub powtórzenia któregokolwiek z nich.
2. Warunkowy (z rozgałęzieniem) – wykonanie określonych kroków zależy od spełnienia lub niespełnienia określonego warunku.
3. Z pętlą (cykliczny) – grupa poleceń jest powtarzana wielokrotnie, aż do spełnienia określonego warunku lub uprzednio zdefiniowanej liczby powtórzeń.

Klasyfikacja ze względu na sposób wykonywania operacji

1. Sekwencyjne – operacje w algorytmie są wykonywane w kolejności, w jakiej zostały opisane.
2. Iteracyjne – niektóre kroki są powtarzane aż do spełnienia wymaganego warunku.
3. Rekurencyjne – tworzona jest formuła powtarzająca dane i odwołująca się do niej samej, a zakończenie wywoływania formuły następuje po spełnieniu warunku zakończenia rekurencji.

Klasyfikacja ze względu na obszar zastosowań

1. Matematyczne – wykonują obliczenia numeryczne.
2. Przeszukujące – przeszukują zbiór danych w celu znalezienia określonego elementu.
3. Porządkujące – ustawiają elementy zbioru w określonej kolejności.
4. Rekurencyjne – rozwiązują problemy, które po podzieleniu na mniejsze części stanowią kopię głównego problemu.
5. Szyfrujące – kodują dane w taki sposób, że ich odczyt jest niemożliwy bez znajomości klucza kodującego.

Złożoność obliczeniowa algorytmów

Złożoność obliczeniowa algorytmu określa ilość zasobów (pamięci, czasu) niezbędnych do rozwiązania danego problemu. Wyróżnia się dwa główne rodzaje złożoności:

Złożoność czasowa

Złożoność czasowa algorytmu jest rozpatrywana jako ilość czasu potrzebnego do rozwiązania problemu w zależności od liczby danych wejściowych. Ponieważ podawanie złożoności obliczeniowej w jednostkach czasu jest nieprecyzyjne (wynik zależy od szybkości działania komputera), zazwyczaj przedstawia się ją jako największą liczbę operacji dominujących wykonywanych w algorytmie dla dowolnego układu danych.

Złożoność pamięciowa

Złożoność pamięciowa algorytmu określa wielkość pamięci operacyjnej komputera, która jest potrzebna do przechowywania danych wejściowych, danych pośrednich oraz ostatecznych wyników obliczeń.

Złożoność czasowa i pamięciowa algorytmu często zależą od postaci przetwarzanych danych, dlatego można je przedstawiać jako:

1. Pesymistyczną: Określa zużycie zasobów dla najgorszego przypadku.
2. Oczekiwaną: Określa zużycie zasobów dla uśrednionych wszystkich możliwych przypadków lub dla typowych przypadków.
3. Optymistyczną: Określa zużycie zasobów dla najkorzystniejszego przypadku.

 Algorytmy komputerowe

Komputery przetwarzają informacje za pomocą algorytmów. Program jest algorytmem zapisanym w języku zrozumiałym dla maszyny (kodzie maszynowym). Każdy poprawny kod maszynowy da się przełożyć na zestaw instrukcji dla teoretycznego modelu komputera – maszyny Turinga.

Zwykle algorytmy pracują na danych wejściowych i uzyskują z nich dane wyjściowe. Informacje zapisane w pamięci maszyny traktuje się jako jej stan wewnętrzny. Niektóre algorytmy mają za zadanie wyłącznie przeprowadzanie komputera z jednego stanu wewnętrznego do innego.

Algorytmy poza komputerami

Implementacja algorytmu w ogólności oznacza występowanie pewnego podobieństwa algorytmu opisanego w ludzkim języku do fizycznego zjawiska lub procesu. Czasami algorytm może być podstawą budowanego przez ludzi urządzenia, jak np. komputer. Jednak o implementacji możemy mówić również wtedy, kiedy pewien system zachowuje się podobnie do algorytmu.

Przykładowo, mózg ptaka implementuje arytmetykę w postaci sieci neuronowej, dzięki czemu zwierzę jest w stanie porównywać pewne odstępy czasu. W przypadku maszyn algorytm może zostać zaimplementowany jako pewna sieć połączeń elektrycznych, pneumatycznych bądź mechanicznych.

Algorytm a opisujący go język

Należy zdawać sobie sprawę z różnicy między algorytmem, będącym niezależnym od jego implementacji przepisem, a programem, który może zostać zinterpretowany i wykonany przez komputer. Różne języki programowania, wykorzystujące różne poziomy abstrakcji, mogą implementować ten sam algorytm na różne sposoby.