Алгоритъм - онлайн пъзели

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

Неформална дефиниция

При все, че няма общоприета формална дефиниция на алгоритъм, неформално понятието може да се определи като „набор от правила, които точно дефинират някаква поредица от операции“. Това определение обхваща всички компютърни програми, включително тези, които не извършват числени изчисления, стига те да прекратяват работа след краен брой операции.Класически пример за „алгоритъм“ е алгоритъмът на Евклид чрез изваждане за намиране на най-големия общ делител (НОД) на две цели числа, по-големи от 1. При него се изпълнява следната поредица от стъпки: На стъпка i, се дели X на Y и остатъкът се означава с R. Ако R = 0, резултатът на задачата е Y. В противен случай, резултатът съвпада с НОД на числата R и Y. Такъв алгоритъм, при който за намирането на решение е необходимо да бъде решена аналогична, но „по-малка“ задача, се нарича рекурсивен.

Американските учени Джордж Булос и Ричард Джефри дават следното неформално определение за алгоритъм в своя класически учебник по математическа логика:

Никое човешко същество не може да пише достатъчно бързо или достатъчно дълго, или достатъчно дребно, за да изброи всички елементи на дадено изброимо безкрайно множество, изписвайки техните имена, едно след друго, с една и съща нотация.