Алгоритам

Алгоритам , систематски поступак који даје - у коначном броју корака - одговор на питање или решење проблема. Назив потиче из латинског превода, Алгоритми бројеви Индијанаца , муслиманског математичара из 9. века ал-Хваризми Аритметика расправа Ал-Кхваризми у вези са хиндуистичком уметношћу обрачуна.

За питања или проблеме са само коначним скупом случајева или вредности ан алгоритам увек постоји (бар у принципу); састоји се од табеле вредности одговора. Генерално, није тако тривијалан поступак да се одговоре на питања или проблеме који имају бесконачно број случајева или вредности које треба узети у обзир, као што је Да ли је природни број (1, 2, 3, ...) до главни ? или Који је највећи заједнички делилац природних бројева до и б ? Прво од ових питања припада класи која се назива прихватљивом; алгоритам који даје одговор са да или не назива се поступак одлуке. Друго питање припада класи која се назива израчунати; алгоритам који доводи до одређеног броја одговора назива се поступак израчунавања.

Алгоритми постоје за многе такве бесконачне класе питања; Еуклидова Елементи , објављено око 300бце, садржао је један за проналажење највећег заједничког делитеља два природна броја. Сваки ученик основне школе буши се у дугој подели, што је алгоритам за питање Након дељења природног броја до другим природним бројем б , колики је количник и остатак? Коришћење овог рачунарског поступка доводи до одговора на одговорно питање Да ли б подела до ? (одговор је да ако је остатак нула). Поновљена примена ових алгоритама на крају даје одговор на питање које је могуће решити до главни? (одговор је не ако до је дељив са било којим мањим природним бројем осим 1).

Понекад алгоритам не може постојати за решавање бесконачне класе проблема, посебно када се извесна даља ограничења прихватају. На пример, два проблема из Еуклидовог времена која су захтевала употребу само компаса и исправљача (необележени лењир) - пресецање угла и конструкција квадрата површине једнаке датој кружници - бавила су се вековима пре него што се показало да су немогући . На прелому 20. века, утицајни немачки математичар Давид Хилберт предложио је 23 задатка која ће математичари решити у наредном веку. Други проблем са његове листе тражио је истрагу доследности аксиома аритметике. Већина математичара је мало сумњала у коначно постизање овог циља све до 1931. године, када је аустријски логичар Курт Годел показао изненађујући резултат да морају постојати аритметички предлози (или питања) који се не могу доказати или оповргнути. У основи, сваки такав предлог доводи до поступка утврђивања који се никад не завршава (услов познат као проблем заустављања). У неуспелом напору да утврдити бар који су предлози нерешиви, енглески математичар и логичар Алан Туринг ригорозно је дефинисао слабо схваћен концепт алгоритма. Иако је Туринг на крају доказао да морају постојати неодлучне тврдње, његов опис основних карактеристика било које машине алгоритма опште намене или Турингове машине постао је темељ информатика . Данас су питања читљивости и израчунљивости најважнија за дизајн рачунарског програма - посебне врсте алгоритма.