Algorytm — definicja, cechy i przykłady
Algorytm to skończony, uporządkowany ciąg czynności prowadzący do rozwiązania określonego problemu. Musi mieć jasno określone dane wejściowe, wynik i kończyć się po skończonej liczbie kroków.
Algorytm kojarzy się z programowaniem, ale pojęcie jest szersze — przepis kulinarny czy instrukcja montażu też nim są. Poniżej definicja, cechy i sposoby zapisu.
Definicja
Algorytm to skończony, uporządkowany ciąg jasno określonych czynności, których wykonanie prowadzi do rozwiązania postawionego problemu.
Nazwa pochodzi od nazwiska perskiego matematyka al-Chwarizmiego, żyjącego w IX wieku. Od jego prac wywodzi się też słowo „algebra”.
Cechy poprawnego algorytmu
- Skończoność — musi zakończyć się po skończonej liczbie kroków
- Określoność — każdy krok jest jednoznaczny, bez miejsca na interpretację
- Dane wejściowe — jasno zdefiniowane, może ich być zero lub więcej
- Wynik — musi dawać co najmniej jeden rezultat
- Efektywność — każdy krok da się wykonać w rozsądnym czasie
Instrukcja „dodaj sól do smaku” nie spełnia warunku określoności — nie jest więc poprawnym algorytmem, choć bywa dobrym przepisem.
Sposoby zapisu
- Opis słowny — najprostszy, ale podatny na nieścisłości
- Lista kroków — ponumerowane czynności
- Schemat blokowy — zapis graficzny z symbolami: owal to początek i koniec, prostokąt operacja, romb warunek
- Pseudokod — zapis przypominający kod programu, ale bez składni konkretnego języka
- Kod programu — zapis w wybranym języku programowania
Trzy podstawowe konstrukcje
Każdy algorytm da się zbudować z trzech elementów:
- Sekwencja — czynności wykonywane po kolei
- Warunek — wybór jednej z dróg zależnie od sytuacji
- Pętla — powtarzanie kroków, dopóki warunek jest spełniony
To twierdzenie o strukturze programów, udowodnione w latach sześćdziesiątych, leży u podstaw programowania strukturalnego.
Przykład: największy z trzech
- Wczytaj liczby a, b, c
- Przyjmij max = a
- Jeśli b > max, to max = b
- Jeśli c > max, to max = c
- Wypisz max
Algorytm spełnia wszystkie warunki: ma dane wejściowe, jednoznaczne kroki, kończy się i daje wynik.
Algorytmy poza informatyką
Pojęcie jest starsze od komputerów o tysiąclecia. Algorytm Euklidesa, służący do znajdowania największego wspólnego dzielnika dwóch liczb, opisano około 300 roku przed naszą erą i stosuje się go do dziś w niezmienionej postaci.
Algorytmami są też: pisemne dodawanie i dzielenie, którego uczymy się w szkole, procedura postępowania przy resuscytacji, instrukcja składania mebla czy przepis kulinarny — o ile jest wystarczająco precyzyjny. Wspólną cechą jest to, że osoba wykonująca kroki nie musi rozumieć, dlaczego działają; wystarczy, że wykona je dokładnie.
Złożoność — dlaczego to ważne
Ten sam problem można rozwiązać na wiele sposobów, różniących się liczbą operacji. Przy wyszukiwaniu w uporządkowanej liście tysiąca elementów przeglądanie po kolei wymaga średnio 500 sprawdzeń, a wyszukiwanie połówkowe — około dziesięciu, bo za każdym razem odrzuca połowę pozostałych możliwości.
Przy milionie elementów różnica rośnie do 500 tysięcy kontra dwadzieścia. Dlatego wybór algorytmu bywa ważniejszy od szybkości komputera — lepszy algorytm na słabszym sprzęcie potrafi wygrać z gorszym na mocniejszym.