Algorytm – w matematyce oraz informatyce to skończony, uporządkowany ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego zadania. Słowo "algorytm" pochodzi od nazwiska Muhammed ibn Musa Alchwarizmi matematyka perskiego z IX wieku i początkowo oznaczało w Europie sposób obliczeń oparty na dziesiętnym systemie liczbowym.
Algorytm ma przeprowadzić system z pewnego stanu początkowego do pożądanego stanu końcowego. Badaniem algorytmów zajmuje się algorytmika. Algorytm może zostać zaimplementowany w postaci programu komputerowego lub dla innego urządzenia. Kiedy podczas tego procesu programista popełni błąd (ang. bug), może to doprowadzić do poważnych konsekwencji np. błędy w implementacji algorytmów bezpieczeństwa mogą ułatwić popełnienie przestępstwa komputerowego.
Jako przykład stosowanego w życiu codziennym algorytmu podaje się często przepis kulinarny. Dla przykładu, aby ugotować bigos należy w określonej kolejności oraz odstępach czasowych (imperatyw czasowy) dodawać właściwe rodzaje kapusty i innych składników. Może istnieć kilka różnych przepisów dających na końcu bardzo podobną potrawę. Przykład ten ma wyłącznie charakter poglądowy, ponieważ język przepisów kulinarnych nie został jasno zdefiniowany. Algorytmy zwykle formułowane są w sposób ścisły w oparciu o język matematyki.
W niektórych krajach, jak USA, algorytmy mogą zostać opatentowane, jeżeli zostaną zaimplementowane w jakimś praktycznym celu. Niektórzy twierdzą, że patentowanie algorytmów spowalnia rozwój informatyki, bo jeden producent może uzyskać monopol, np. na pisanie oprogramowania tworzącego pewne typy plików (np. GIF). Wiele koncernów komputerowych prowadzi między sobą prawnicze spory dotyczące praw własności do niektórych patentów. Kontrargumentem jest tzw. prawo własności intelektualnej (jaką objęty jest np. utwór muzyczny, będący wytworem intelektu i pracy muzyka) zakładające, że program jest intelektualną własnością twórcy. Schemat Hornera – sposób obliczania wartości wielomianu dla danej wartości argumentu wykorzystujący minimalną liczbę mnożeń. Również algorytm dzielenia wielomianu W(x) przez dwumian x-c wiązany z nazwiskiem Hornera był jednak znany już Newtonowi, Ruffiniemu i matematykom chińskim w XII wieku.
Sortowanie to jeden z podstawowych problemów informatyki. Polega na uporządkowaniu zbioru danych względem pewnych cech charakterystycznych każdego elementu tego zbioru. Szczególnym przypadkiem jest sortowanie względem wartości każdego elementu, np. sortowanie liczb, słów itp.
Algorytmy sortowania są stosowane w celu uporządkowania danych, umożliwieniu stosowania wydajniejszych algorytmów (np. wyszukiwania) i prezentacji danych w sposób czytelniejszy dla człowieka.
Jeśli jest konieczne posortowanie zbioru większego niż wielkość dostępnej pamięci, stosuje się algorytmy sortowania zewnętrznego.
Do algorytmów numerycznych zaliczamy algorytmy, które mogą być stosowane do obliczeń nie tylko na liczbach całkowitych, ale również na danych typu real. Należy przy tym pamiętać, że pojawienie się liczb takiego typu w obliczeniach oznacza, że dane są reprezentowane w komputerze w sposób przybliżony. Ponadto, wiele algorytmów numerycznych rozwiązuje problemy w sposób przybliżony, generując rozwiązania bliskie dokładnych rozwiązań. Wynika to na ogół z charakteru problemów rozwiązywanych takimi algorytmami. Przykładami takich problemów są: znajdowanie wartości pierwiastka kwadratowego oraz liczb π i e, gdyż w skończonym czasie możemy jedynie zbliżyć się do wartości tych liczb (dowolnie blisko jednak), ponieważ mają one nieskończone rozwinięcie.
Dodajmy tutaj jeszcze, że są algorytmy, w których nie ma specjalnego znaczenia, jakie są dane: całkowite, rzeczywiste (typu rzeczywistego) czy mieszane. Takimi algorytmami są w większości algorytmy służące do porządkowania – nie ma znaczenia, jakie liczby porządkujemy, ważne są tylko relacje między nimi.
Reprezentacja binarna liczb a schemat Hornera
Niektóre algorytmy numeryczne, zaprojektowane do obliczeń na dowolnych liczbach, mogą być stosowane w obliczeniach dokładnych. Najlepszym przykładem jest tutaj algorytm znany jako schemat Hornera, służący do obliczania wartości wielomianu – jeśli współczynniki wielomianu i wartość argumentu są liczbami całkowitymi, to wartość wielomianu jest także liczbą całkowitą.
Przypomnij sobie i zapisz schemat Hornera w postaci listy kroków i procedury w języku programowania. Powinieneś być przekonany, że wykonuje on tyle mnożeń i dodawań, ile wynosi stopień wielomianu
Zauważ, że postać binarna dowolnej liczby naturalnej jest wielomianem – jakie liczby są współczynnikami i argumentem takiego wielomianu:
wybierz jakiś przykład takiej reprezentacji,
zapisz ją w postaci schematu Hornera (chodzi tutaj o odpowiednie rozstawienie nawiasów, wymuszające obliczenia według schematu Hornera),
oblicz na tej podstawie wartość dziesiętną liczby zapisanej w początkowej reprezentacji binarnej.
Przekonaj się na podstawie poprzedniego punktu, że wartość dziesiętna liczby danej w postaci reprezentacji binarnej może być obliczona na prostym kalkulatorze, bez korzystania z jakiejkolwiek komórki pamięci.
wiedza_na_chomikuj