Алгоритъм
From Wikipedia, the free encyclopedia
Алгоритъм (от името на учения ал–Хорезми) е термин от математиката, информатиката, лингвистиката и други области, с който се описва сложно действие чрез редица от елементарни (достатъчно прости) действия, които изпълняващият може да извърши в последователни стъпки без допълнителни обяснения. Обикновено изпълнението на алгоритъма включва изчисление или обработка на данни.[1]
По-строго дефинирано, алгоритъмът е ефективен метод за изчисляване на функция, който може да бъде изразен в рамките на крайно време и пространство и чрез добре дефиниран формален език.[2] Започвайки от начално състояние и входни данни (понякога празни), инструкциите описват пресмятания, чието изпълнение преминава през краен брой добре дефинирани последователни състояния и завършва с крайно състояние, като в процеса се получават крайни резултати.[3] Не е задължително преходът между състоянията да е детерминиран (еднозначно определен): някои алгоритми, известни като вероятностни алгоритми, съдържат елемент на случайност.[4]
Концепцията за алгоритмите съществува от векове, но частичното формулиране на понятието започва с опитите да се реши 10-ия проблем на Хилберт – „Задача за разрешимост на диофантово уравнение“, поставен от Давид Хилберт през 1900 година на Втория световен конгрес по математика в Париж.[5] Последващите формулировки, при които се цели дефинирането на „ефективна изчислимост“[6] или „ефективен метод“[7], включват рекурсивните функции на Ербран-Гьодел-Клини от 1930, 1934 и 1935 година, ламбда смятането на Алонсо Чърч от 1936 година, „Формулировка 1“ на Емил Пост от 1936 година и машината на Тюринг от 1936 – 1937 и 1939 година. Създаването на формална дефиниция на алгоритъм, съответстваща на интуитивното понятие, остава отворен въпрос и в наши дни.[8]