Алгоритъм математика

Алгоритъм, систематична процедура, която дава - в краен брой стъпки - отговора на въпрос или решение на проблема. Името произлиза от латинския превод, Algoritmi de numero Indorum, от аритметичния трактат на мюсюлманския математик ал-Хваризми от 9 век „Al-Khwarizmi относно индуисткото изкуство на разчитане“.

компютърни науки: Алгоритми и сложност

Алгоритъмът е специфична процедура за решаване на добре дефиниран изчислителен проблем. Разработването и анализът на алгоритмите е от основно значение

За въпроси или проблеми само с ограничен набор от случаи или стойности алгоритъм винаги съществува (поне по принцип); тя се състои от таблица на стойностите на отговорите. По принцип не е толкова тривиална процедура да се отговори на въпроси или проблеми, които трябва да се разгледат безкрайно много случаи или стойности, като „Дали естественото число (1, 2, 3, …) е първостепенно?“ или „Кой е най-големият общ делител на естествените числа a и b?“ Първият от тези въпроси принадлежи към клас, наречен decidable; алгоритъм, който произвежда отговор да или не, се нарича процедура за вземане на решение. Вторият въпрос принадлежи към клас, наречен изчислим; алгоритъм, който води до отговор на конкретен номер, се нарича изчислителна процедура.

Алгоритми съществуват за много такива безкрайни класове въпроси; Elements на Евклид, публикувана около 300 bc, съдържаше един за намиране на най-големия общ делител на две естествени числа. Всеки ученик в началното училище се пробива в дълъг деление, което е алгоритъм на въпроса „При разделяне на естествено число а на друго естествено число b, какви са коефициентът и остатъкът?“ Използването на тази изчислителна процедура води до отговора на решаващия въпрос „Дали b раздели a?“ (отговорът е да, ако остатъкът е нула). Многократното приложение на тези алгоритми в крайна сметка дава отговор на решаващия въпрос „Дали е премиер?“ (отговорът е не, ако a се дели на всяко по-малко естествено число освен 1).

Понякога не може да съществува алгоритъм за решаване на безкраен клас проблеми, особено когато се прави някакво допълнително ограничение при приетия метод. Например два проблема от времето на Евклид, изискващи използването само на компас и изправен (немаркиран владетел) - описване на ъгъл и изграждане на квадрат с площ, равна на даден кръг - са преследвани от векове, преди да се окаже невъзможно, В края на 20-ти век влиятелният немски математик Дейвид Хилберт предложи 23 проблема, които математиците трябва да решат през следващия век. Вторият проблем в неговия списък поиска разследване на последователността на асиомите на аритметиката. Повечето математици не се съмняваха в евентуалното постигане на тази цел до 1931 г., когато роденият в Австрия логик Курт Гьодел демонстрира изненадващия резултат, че трябва да съществуват аритметични предложения (или въпроси), които не могат да бъдат доказани или опровергани. По същество всяко такова предложение води до процедура за определяне, която никога не приключва (състояние, известно като проблем със спирането). В неуспешно усилие да установи поне кои предположения са неразрешими, английският математик и логик Алън Тюринг строго дефинира слабо разбраната концепция на алгоритъм. Въпреки че Тюринг в крайна сметка доказа, че трябва да съществуват неопределими предложения, неговото описание на основните характеристики на всяка машина с алгоритъм с общо предназначение или машина на Тюринг стана основата на компютърните науки. Днес въпросите за разрешимостта и изчислимостта са централни за проектирането на компютърна програма - специален тип алгоритъм.