algorytmach

Algorytm to jasno określony ciąg kroków, który przetwarza dane wejściowe i generuje dane wyjściowe. Każde wykonanie algorytmu zaczyna się od wejścia i kończy rezultatem, a poszczególne kroki muszą być wykonywane w skończonej liczbie iteracji. Algorytmy stanowią fundament informatyki i teoretycznie opisują, jak rozwiązywać problemy.

W odróżnieniu od programu, który jest konkretną implementacją algorytmu w języku programowania, algorytm to abstrakcyjny opis rozwiązania. Algorytmy mogą być deterministyczne lub probabilistyczne, a ich projektuje się z uwzględnieniem ograniczeń czasowych i pamięciowych. Ocena poprawności algorytmu polega na wykazaniu, że dla każdego dopuszczalnego wejścia daje poprawne wyjście.

Złożoność obliczeniowa opisuje zasoby potrzebne do wykonania algorytmu — czas i zużycie pamięci — w zależności od rozmiaru danych wejściowych. Notacje asymptotyczne (O, Ω, Θ) są powszechnie używane do klasyfikowania efektywności.

Typowe paradygmaty projektowania to podział i zwycięstwo (divide and conquer), dynamiczne programowanie, algorytmy zachłanne, backtracking, heurystyki i metaheurystyki oraz algorytmy probabilistyczne. W praktyce łączą one różne techniki w zależności od problemu.

Przykłady klasycznych algorytmów: Euklidesa do wyznaczania największego wspólnego dzielnika; sortowanie szybkie (quicksort) i scalanie (mergesort); Dijkstra i Bellman-Ford do najkrótszych ścieżek; algorytmy wyszukiwania i przeszukiwania grafów.

Zastosowania obejmują sortowanie i przetwarzanie danych, kompresję, kryptografię, sztuczną inteligencję, analitykę danych i inżynierię oprogramowania.

Historia algorytmów wiąże się z pracami nad arytmetyką i logiką, a w XX wieku rozwinęła się formalna teoria algorytmów wraz z pracą Turinga i koncepcjami maszyn Turinga oraz hipotezami Churcha–Turinga.