Ալգորիթմ

Մաթեմատիկայում և ինֆորմատիկայում, ալգորիթմը (ստեղծվել է հռչակավոր մաթեմատիկոս Ալ-Խորեզմիի կողմից) քայլ առ քայլ հաշվարկային գործընթաց է։ Ալգորիթմը կիրառվում է հաշվարկներում, տվյալների մշակման և մտահանգումների ավտոմատացման ժամանակ։
Ավելի ճշգրիտ, ալգորիթմը ֆունկցիայի հաշվարկման որոշակի լավ սահմանված արդյունավետ մեթոդ է։
Սկսելով նախնական վիճակից և արված մուտքային տվյալներից (հնարավոր է՝ լինի դատարկություն) և ունենալով գործողությունները բացատրող հրահանգավորում, դրանք կատարելով ստացվում է վերջնական արդյունք։ Մի վիճակից մյուսին անցումը պարտադիր չէ, որ լինի դետերմինացված` որոշ ալգորիթմներ միավորում են պատահական մուտքեր։
Յուրաքանչյուր խնդիր լուծելու համար կարող են գոյություն ունենալ նպատակին հասցնող բազմաթիվ ալգորիթմներ։ Ալգորիթմների արդյունավետության մեծացումը ժամանակակից ինֆորմատիկայի խնդիրներից մեկն է։
Ալգորիթմ իրականացնողը հիմնականում համակարգիչներն ու այլ սարքավորումներն են, սակայն ալգորիթմը պարտադիր չէ, որ կապված լինի ծրագրավորման հետ։ Ուտեստի բաղադրատոմսը նույնպես կարելի է համարել ալգորիթմ։

Պատմություն

Տերմինի (եզրի) ծագումը 

Ալգորիթմ հասկացությունը մարդկությանը հայտնի է շատ վաղուց, սակայն այնպես, ինչպես մենք հիմա հասկանում ենք, հայտնվել է միայն 20-րդ դարի սկզբերին։ Եզրի ժամանակակից սահմանումը տրված է Ա․ Թյուրինգի, Է․ Պոստի, Ա․Չորչի, Ն․Վինների և Ա․ Մարկովի աշխատանքներում։

Ալգորիթմ տերմինը գալիս է Պարսկաստանից՝ ալ-Խորեզմիի անունից։ Ալ Խորեզմին գիտնական էր, ով մոտ 825 թ. գրեց մի գիրք, որտեղ ներկայացրեց Հնդկաստանում ստեղծված հաշվարկման տասական համակարգը և հավանաբար առաջինը ներկայացրեց Հնդկաստանում ստեղծված 0 թիվը։ Գրքի սկզբնական տարբերակը չի պահպանվել, սակայն 12-րդ դարում Եվրոպա մտած լատիներեն թարգմանությունը մինչև օրս էլ կա։ Անհայտ թարգմանիչի թարգմանությունը հայտնի է որպես Algoritmi de numero Indorum («Հնդկական հաշվի մասին ալգորիթմներ»), սակայն արաբները այն ավանաում էին Քիտաբ ալ֊ջեբր վալ֊մուկաբալա («Գիրք գումարման և հանման»)։ Գրքի օրիգինալ անվանումից է առաջացել algebra (հանրահաշիվ) բառը։

Ոչ ֆորմալ սահմանում 
Որպես ոչ ֆորմալ սահմանում կարող է լինել "կանոնների հավաքածուն, որը ճշգրիտ սահմանում է գործողությունների հաջորդականությունը", որը կարող է ներառել բոլոր համակարգչային ծրագրերը (ներառյալ ծրագրերը, որոնք թվային հաշվարկներ չեն իրականացնում) և (օրինակ) ցանկացած բյուրակրատական ընթացակարգ
կամ բաղադրատոմս խոհանոցային գրքից։

Ընդհանուր առմամբ ծրագիրը ալգորիթմ է միայն այն դեպքում, եթե այն ի վերջո ավարտվում է՝ չնայած երբեմն անվերջ ցիկլերը երբեմն կարող են ցանկալի լինել։

Ալգորիթմի նախատիպ է Էվկլիդյան ալգորիթմը, որն օգտագործվում է երկու ամբողջ թվերի ամենամեծ ընդհանուր բաժանարարը գտնելու համար։

Հետևյալ մեջբերումը ներկայացնում է ալգորիթմի իմաստի մեկնաբանությունը ըստ -ի․ 

Ոչ ոք չի կարող գրել բավական արագ, կամ բավական երկար, կամ բավական փոքր ( †"փոքր և ավելի փոքր առանց սահմանափակման ․․․ դուք կփորձեիք գրել մոլեկուլներով, ատոմներով, էլեկտրոններով") թվարկելու անվերջ բազմության անդամներին, որոշակի նշագրմամբ նրանց անունները հաջորդաբար գրառելով։ Բայց որոշակի անսահման բազմությունների դեպքում, մարդիկ կարող են նույնքան օգտակար բան անել․ նրանք կարող են կամայական վերջավոր n-ի համար,   բազմության nրդ անդամի սահմանման հստակ հրահանգներ տալ։ Այդ հրահանգները պետք է բավականաչափ հստակ լինեն, այնպես, որ դրանք համակարգչով իրականացնելի լինի, կամ մարդու կողմից, որ ունակ է սիմվոլների նկատմամբ տարրական գործողություններ կատարել։

Անվերջ հաշվելի բազմությունն այն բազմությունն է, որի տարրերը կարելի է մեկը մեկին համապատասխանության մեջ դնել դրական ամբողջ թվերի հետ։ Այսպիսով Բուլոսը և Ջեֆրին ասում են, որ ալգորիթմն իրենից ներկայացնում է գործընթացի հրահանգներ, որը «ստեղծում» է ելքային ամբողջ թվեր կամայական «մուտքային» ամբողջ թվից կամ թվերից, որոնք տեսականորեն կարող են շատ մեծ լինել։ Օրինակ, ալգորիթմը կարող է լինել հանրահաշվական հավասարում y = m + n (այսինքն, ցանկացած երկու m և n մուտքային փոփոխականների համար որ y ելք են տալիս), բայց տարբեր հեղինակների հասկացությունը սահմանելու փորձերը ցույց են տալիս, որ բառը շատ ավելի ընդգրկուն է , քան սա։
Համակարգչի շարժումը որոշող արագ, արդյունավետ և լավ գործընթացի համար Ճշգրիտ հրահանգներ ("համակարգչին հասկանալի լեզվով") (անհրաժեշտ ներքին տեղեկությամբ և ունակություններով օժտված մարդ կամ մեքենա) գտնելու, ապակոդավորելու և այնուհետ մշակելու կամայական մուտքային ամբողջ թվեր/m և n, + և =նշանները … և "արդյունավետ" "ողջամիտ" ժամանակում դուրս բերել  y ելքային ամբողջ թիվը նշված տեղում և նշված ֆորմատով։

Ալգորիթմ հասկացությունը օգտագործվում է որոշելիության հասկացությունը սահմանելու համար, բացատրելու համար թե ինչպես են ֆորմալ համակարգերը դուրս բերվում աքսիոմների և կանոննների փոքր բազմությունից։ Տրամաբանության մեջ ալգորիթմն իրականացնելու համար պահանջվող ժամանակը հնարավոր չէ չափել, քաանի որ ակնհայտ է, որ այն կապված չէ սովորական ֆիզիկական չափման հետ։ Ընթացիկ աշխատանքը բնութագրող նման անորոշություններից է բխում ալգորիթմի այնպիսի սահմանման անհնարինությունը, որը համապատասխանի տերմինի օգտագործման երկու՝ կոնկրետ (ինչ որ իմաստով) և աբստրակտ տարբերակներին։

Ֆորմալացում

Ալգորիթմները էական են համակարգիչների կողմից տվյալների մշակման ընթացքում։ Շատ համակարգչային ծրագրեր պարունակում են ալգորիթմներ, որոնք մանրամասն նկարագրում են որոշակի առաջադրանք կատարելու համար անհրաժեշտ հատուկ հրահանգները, որոնք համակարգիչը պետք է կատարի որոշակի կարգով։ Այդպիսի առաջադրանքներից են աշխատողների աշխատավարձերը հաշվարկելը կամ ուսանողների հաշվետվությունները տպելը։ Այսպիսով, ալգորիթմ կարելի է համարել գործողությունների ցանկացած հաջորդականություն, որը կարող է մոդելավորվել Թյուրինգի ամբողջական համակարգի միջոցով։ Այս թեզը պնդող հեղինակների թվում են Մինսկին (1967), Սավաջը (1987) և Գուրեվիչը (2000)։
 Մինսկի. «Թյուրինգի հետ միասին, մենք նաև պնդելու ենք, ... որ ցանկացած պրոցեդուրա, որը« բնականաբար »կարելի է անվանել արդյունավետ, փաստացի կարող է իրականացվել (պարզ) մեքենայի միջոցով։ Չնայած դա կարող է ծայրահեղ թվալ, սակայն դրա օգտին փաստարկները… դժվար է հերքել »։

 Գուրեվիչ. «… Իր թեզի օգտին Թյուրինգի ոչ ֆորմալ փաստարկը արդարացնում է ավելի ուժեղ թեզ. Յուրաքանչյուր ալգորիթմ կարող է մոդելավորվել Թյուրինգի մեքենայի միջոցով… ըստ Սավաջի [1987], ալգորիթմը Թյուրինգի մեքենայի միջոցով սահմանված հաշվարկային գործընթաց է»։

Թյուրինգի մեքենաները կարող են սահմանել գործընթացներ, որոնք չեն ավարտվում։ Ալգորիթմների ոչ ֆորմալ սահմանումները ընդհանուր առմամբ մշտապես պահանջում են ալգորիթմի ավարտ։ Այս պահանջը խնդիր է առաջացնում որոշելու արդյոք ֆորմալ գործընթացը ալգորիթմ է, ընդհանուր առամբ հաշվարկելիության տեսության պատճառով, որը հայտնի է որպես կանգ առնելու պրոբլեմ։ 

Սովորաբար, երբ ալգորիթմը կապված է տեղեկատվության մշակման հետ, տվյալները կարող են ընթերցվել մուտքային աղբյուրից, գրվել ելքային սարքի վրա և պահպանվել հետագա մշակման համար։ Պահված տվյալները դիտվում են որպես ալգորիթմ իրականացնող օբյեկտի ներքին վիճակի մի մաս։ Գործնականում իրավիճակը պահվում է տվյալների մեկ կամ մի քանի կառուցվածքներով։ 

Այս գործընթացներից որոշների համար, ալգորիթմը պետք է խիստ որոշակի լինի․ թե ինչպես է այն կիրառվում առաջ եկած բոլոր հնարավոր իրավիճակներում։ Սա նշանակում է, որ կամայական պայմանական քայլեր պետք է համակարգված լուծվի՝ ըստ առանձին դեպքերի, յուրաքանչյուր դեպքի չափորոշիչները պետք է լինեն պարզ (և հաշվարկելի)։

Քանի որ ալգորիթմն իրենից ներկայացնում է հստակ քայլերի ճշգրիտ ցանկ, ուստի ալգորիթմի գործունեության համար հաշվարկների հերթականությունը մշտապես վճռորոշ է։ Ենթադրվում է, որ հրահանգների ցանկը հստակ հերթականությամբ է և նկարագրված  է "վերևից" դեպի "վար, մինչև հատակ" հերթականությամբ։

Մինչ այժմ ալգորիթմի ֆորմալացման քննարկումները հիմնվում էին հրամայական ծրագրավորման վրա։ Սա ամենատարածված ընկալումն է. այն փորձում է խնդիրը նկարագրել դիսկրետ, «մեխանիկական» միջոցներով։ Ալգորիթմների ֆորմալացման այս կոնցեպցիայի յուրահատկությունը վերագրման գործողությունն է, որը փոփոխականներին արժեքներ է տալիս։ Սա բխում է հիշողությանը որպես բլոկնոտ դիտարկելուց։ Այսպիսի մոտեցման օրինակ բերված ներքևում։ 

Ալգորիթմի սահմանման ալտերնատիվ պատկերացումներ կարող եք գտնել Ֆունկցիոնալ ծրագրավորման և տրամաբանական ծրագրավորման հոդվածներում։

Ալգորիթմների ներկայացումը
Ալգորիթմներըը կարող են արտահայտված լինել տարբեր տեսակի նշումներով․ բնական լեզուներով, փսևդոկոդով, բլոկ սխեմաներով, DRAKON լեզվով կամ ծրագրավորման լեզուներով։ Ալգորիթմների արտահայտությունները բնական լեզվով սովորաբար երկար են և երկիմաստ, հազվադեպ են օգտագործվում բարդ կամ տեխնիկական ալգորիթմների համար։  Փսևդոկոդով, բլոկ սխեմաներով, DRAKON սխեմաները և ղեկավարող աղյուսակները ալգորիթմների արտահայտման կառուցվածքային եղանակներ են, որոնք հնարավորություն են տալիս խուսափել բնական լեզվին հատուկ երկիմաստություններից։ Ծրագրավորման լեզուները նախատեսված են ալգորիթմները ներկայացնելու այնպես, որպեսզի համակարգիչները կարողանան դրանք կատարել, սակայն հաճախ օգտագործվում են ալգորիթմները սահմանելու և փաստաթղթավորելու համար։ 

Ներկայացման մեծ բազմազանություն գոյություն ունի և Թյուրինգի մեքենայի տված ծրագիրը կարելի է ներկայացնել որպես մեքենայական աղյուսակների հաջորդականություն։

Ալգորիթմների ներկայացումները կարելի է դասակարգել Թյուրինգի մեքենայի նկարագրության երեք ընդունված մակարդակների, հետևյալ կերպ․
 1 Բարձր մակարդակի նկարագրություն
 “…ալգորիթմ նկարագրող արձակ, անտեսելով իրականացման մանրամասները։ Այս մակարդակում կրիք չկա նշել թե մեքենան ինչպես է կառավարում իր ժապավենը կամ գլխիկը։"
 2 Իրականացման նկարագրություն
 “…շարադրանքն օգտագործվում է սահմանելու, թե Թյուրինգի մեքենան ինչպես է օգտագործում իր գլխիկը և ինչպես է հիշում տվյալները իր ժապավենի վրա։ Այս մակարդակում մենք մանրամասներ չենք տալիս վիճակների կամ անցման ֆունկցիայի վերաբերյալ։"
 3 Ֆորմալ նկարագրություն
 Առավել մանրամասն, "ամենացածր մակարդակ", տալիս է Թյուրինգի մեքենայի վիճակների աղյուսակը։

Որպես պարզ ալգորիթմի օրինակF "Գումար m+n" նկարագրված է բոլոր երեք մակարդակներում, տես Algorithm#Examples.

Նախագծում
Ալգորիթմի նախագծումը վերաբերում է խնդրի լուծման և ալգորիթմների կառուցման մեթոդին կամ մաթեմատիկական գործընթացին։ Ալգորիթմների նախագծումը գործողությունների հետազոտության շատ լուծումների տեսությունների մաս է կազմում, ինչպիսիք են դինամիկ ծրագրավորումը և բաժանիր, որ տիրես ալգորիթմը։ Ալգորիթմների մշակման և իրականացման մեթոդները նաև կոչվում են ալգորիթմների նախագծման շաբլոններ,։

Ալգորիթմների մշակման կարևորագույն ասպեկտներից է ռեսուրսների (կատարման ժամանակը, հիշողության օգտագործման ծավալը) արդյունավետությունն է։

Ալգորիթմների մշակման բնորոշ քայլերն են․ 
 Խնդրի սահմանումը
 Մոդելի մշակումը
 Ալգորիթմի հստակեցում
 Ալգորիթմի մշակում
 Ալգորիթմի ճշգրտության ստուգում
 Ալգորիթմի վերլուծություն
 Ալգորիթմի գործարկում
 Ծրագրի ստուգում
 Փաստաթղթերի պատրաստում

Կատարում

Ալգորիթմների մեծ մասը նախատեսված է գործարկել որպես համակարգչային ծրագրեր։ Այնուամենայնիվ, ալգորիթմներն իրականացվում են նաև այլ միջոցներով, ինչպիսիք են կենսաբանական նյարդային ցանցը (օրինակ, մարդու ուղեղը թվաբանական գործողություն կատարելիս, կամ միջատը սնունդ փնտրելիս), էլեկտրական շղթայում կամ մեխանիկական սարքում։

Համակարգչային ալգորիթմներ

Համակարգչային համակարգերում ալգորիթմը հիմնականում մաթեմատիկական ապահովման մեջ ծրագրավորողների կողմից գրված տրամաբանության օրինակ է։ Նույնիսկ հին սարքի վրա աշխատող օպտիմալ ալգորիթմը ավելի արագ արդյունքներ կտա, քան ոչ օպտիմալը ավելի արագընթաց և արդյունավետ սարքավորման վրա։ Սա է պատճառը, որ ալգորիթմները համակարգիչների նման համարվում են տեխնոլոգիա։ 

«Էլեգանտ» (կոմպակտ) ծրագրեր, «լավ» (արագ) ծրագրեր. «Պարզություն և էլեգանտություն» հասկացությունը ոչ ֆորմալ կերպով հայտնվում է Կնուտի, և հատկապես Չայտինի մոտ.
Կնուտ « … մեզ անհրաժեշտ են լավ ալգորիթմներ որոշ թույլ սահմանված գեղագիտական իմաստով։ Մեկ չափանիշ՝ ալգորիթմի իրականացման տևողությունն է …։ Մեկ այլը` ալգորիթմի հարմարվողականությունը համակարգչին, նրա պարզությունն ու էլեգանտությունը և այլն»

Չայտին. «... ծրագիրը« էլեգանտ է ասելով, ես նկատի ունեմ, որ այն արդյունքի իրականացման համար դա հնարավորինս փոքր ծրագիրն է»

Իր սահմանման նախաբանում Չայտինը գրում է․ «Ես ցույց կտամ, որ դուք չեք կարող ապացուցել, որ ծրագիրը էլեգանտ է »։

Ցավոք, լավ հնարավոր է փոխհամաձայնություն լավի (արագ) և էլեգանտության (կոմպակտություն) միջև— էլեգանտ ծրագիրը հաշվարկն ամբողջացնելու համար կարող է ավելի շատ քայլեր պահանջել, քան պակաս էլեգանտը։ Ստորև Էվկլիդեսի ալգորիթմն օգտագործող օրինակ։

Զարգացումը 
Ֆիզիկայի և մաթեմատիկայի արագ զարգացումը պահանջում էր ալգորիթմի կոնկրետ բնորոշում։ Առաջին նման փորձերը կատարեցին Ալան Թյուրինգը, Էմիլ Պրոստը, Ժակ Բերնանը, Կուրտ Գեդելը, Ա. Ա. Մարկովը և Ալոնզո Չորզը։ Նրանք տվեցին տարբեր սահմանումներ, սակայն ի վերջո պարզվեց, որ դրանք գրեթե նույնն են։
Թյուրինգի մեքենայի հիմնական գաղափարը պարզ է։ Յուրաքանչյուր քայլի ժամանակ մեքենան վերցնում է սլաքի ցույց տված նշանը և այդպես շարունակ, այնուհետև կարող է դրանք փոխել՝ մեկ քայլ աջ կամ ձախ գնալով։

Այս հետազոտությունների հիման վրա Թյուրինգը ձևակերպեց ալգորիթմների հիմնական հիպոթեզը։
Որևէ ֆունկցիայի արժեքներ գտնելու համար նախատեսված ալգորիթմ գոյություն ունի այն և միայն այն դեպքում, երբ այն կարելի է հաշվարկել Թյուրինգի մեթոդով՝ Թյուրինգի մեքենայի վրա։ Այս թեզը համարվում է աքսիոմ, և չի կարող խիստ ապացուցվել մաթեմատիկորեն, քանի որ ալգորիթմը հստակ մաթեմատիկական հասկացություն չէ։

Հատկություններ 
Ալգորիթմների տարբեր սահմանումներ պարունակում են հետևյալ պահանջները։

 Դիսկրետություն – ալգորիթմը պետք է իրենից ներկայացնի պարզ քայլերի հաջորդականություն, որոնք կբերեն որևէ խնդրի լուծմանը։ Միևնույն ժամանակ, ալգորիթմի յուրաքանչյուր քայլի կատարման ժամանակը սահմանափակ է։
 Որոշվածություն – ցանկացած պահի հաջորդ քայլը հստակ որոշվում է կախված համակարգի իրավիճակից։ Այսպիսով, ալգորիթմը տալիս է նույն պատասխանը նույն սկզբնական տվյալների համար։ Հնարավոր է նաև, որ հաջորդ քայլը կախված լինի այդ պահին ընտրված պատահական թվից։
 Հասկանալի լինել – ալգորիթմը պետք է ներառի միայն կատարողին հասկանալի և նրա տվյալների մեջ առկա գործողույթուններ։
 Վերջավորություն – ճիշտ տրված սկզբնական տվյալների դեպքում, ալգորիթմը պետք է վերջավոր քանակի քայլերից հետո տա ճիշտ պատասխանը։
 Ունիվերսալություն – ալգորիոմը պետք է կատարի իր ֆունկցիան ցանկացած թույլատրելի սկզբնական տվյալներ տալու դեպքում։
 Արդյունավետություն – որոշակի արդյունքների ստացում։
 Ալգորիթմը պարունակում է սխալներ, եթե արդյունքը սխալ է, կամ արդյունք չկա ընդհանրապես։
 Ալգորիթմը չի պարունակում սխալներ, եթե տալիս է ճշմարիտ արդյունք։

Ալգորիթմի օրինակներ 

 Որպես լավագույն օրինակ կարող է ծառայել արագ տեսակավորման ալգորիթմը։
 Հաջորդ օրինակը Էվկլիդեսի ալգորիթմն է, որով որոշված վերջին ոչ զրոյական մնացորդը տրված a և b թվերի ամենամեծ ընդհանուր բաժանարարն է՝ (a, b)։
Բերված օրինակում ամենավերջին առանց մնացորդ բաժանվող թիվը և, հետևաբար 1599-ի և 650-ի ամենամեծ ընդհանուր բաժանարարն է 13-ը։

Ծանոթագրություններ 

Մաթեմատիկական տրամաբանություն
Արաբական բառեր և արտահայտություններ
Տեղեկատվական տեխնոլոգիաներ
Տեսական ինֆորմատիկա