Ալգորիթմ

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

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

  • Համարվում է, որ ալգորիթմ բառը ծագել է միջնադարի նշանավոր գիտնական Մուհամեդ իբն Մուսա Խորեզմիի (783-850) (Ալ-Խորեզմի) անվան լատիներենացված գրությունից:

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

Ալգորիթմին ներկայացվող ընդհանուր պահանջները հետեւյալներն են`

Դիսկրետություն`
Խնդրի լուծման պրոցեսը ալգորիթմը պետք է ներկայացնի որպես որոշակի պարզ քայլերի կատարման հաջորդականություն: Ընդ որում, ալգորիթմի յուրաքանչյուր քայլի կատարման համար պահանջվում է սահմանափակ ժամանակահատված:
Որոշելիություն`
Ժամանակի յուրաքանչյուր պահի աշխատանքի հաջորդ քայլը միանշանակ որոշվում է ըստ համակարգի վիճակի։ Այսպիսով, մուտքի միևնույն տվյալների համար ալգորիթմը տալիս է միևնույն արդյունքը (պատասխանը)։
Հասանելիություն`
Ալգորիթմը պետք է պարունակի միայն այն հրահանգները, որոնք հասկանալի են կատարողի համար եւ մտնում են նրա հրահանգների համակարգի մեջ:
Ավարտվածություն`
Ճիշտ առաջադրված մուտքի տվյալների դեպքում ալգորիթմը պետք է ավարտի աշխատանքը և արդյունքը մատուցի քայլերի վերջավոր քանակով։ Զանգվածայնություն`
Ալգորիթմը պետք է հնարավորություն ունենա կիրառելու մուտքի տվյալների տարբեր խմբերի համար:
Արդյունավետություն`
Ալգորիթմը պետք է ավարտվի որոշակի արդյունքներով։

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

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

Էվկլիդեսի ալգորիթմի կատարման անիմացիոն տարբերակը 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թ.