Ալգորիթմ

Վիքիպեդիայից՝ ազատ հանրագիտարանից

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

Պատմությունը[խմբագրել]

Տերմինի (եզրի) ծագումը[խմբագրել]

Մեկ էջ Քիտաբ ալ֊ջեբր վալ֊մուկաբալա («Գիրք գումարման և հանման») գրքից

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

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

Զարգացումը[խմբագրել]

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

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

Հատկությունները[խմբագրել]

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

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

Ալգորիթմի օրինակներ[խմբագրել]

Էվկլիդեսի ալգորիթմի կատարման անիմացիոն տարբերակը 1599-ի և 650-ի ամենամեծ ընդհանուր բաժանարարը որոշելու համար։
Քայլ 1 1599 = 650×2 + 299
Քայլ 2 650 = 299×2 + 52
Քայլ 3 299 = 52×5 + 39
Քայլ 4 52 = 39×1 + 13
Քայլ 5 39 = 13×3 + 0
  • Որպես լավագույն օրինակ կարող է ծառայել արագ տեսակավորման ալգորիթմը։
  • Հաջորդ օրինակը Էվկլիդեսի ալգորիթմն է, որով որոշված վերջին ոչ զրոյական մնացորդը տրված a և b թվերի ամենամեծ ընդհանուր բաժանարարն է՝ (a, b)։[3]

Բերված օրինակում ամենավերջին առանց մնացորդ բաժանվող թիվը և, հետևաբար 1599-ի և 650-ի ամենամեծ ընդհանուր բաժանարարն է 13-ը։


Ծանոթագրություններ[խմբագրել]

  1. "Օրինակ, ցանկացած դասական մաթեմատիկական ալգորիթմ կարող է նկարագրվել վերջավոր թվով անգլերեն բառերով:" (Rogers 1987:2):
  2. "Մինչեւ իր սկսելը, ալգորիթմն ունենում է նախապես տրված զրո կամ ավելի հատ մուտքեր" (Knuth 1973:5).
  3. Գ.Ա.Ղարագեբակյան, Թվերի տեսության դասընթաց, Երեւան, Էդիթ պրինտ, 2008թ.