Էվկլիդեսի ալգորիթմ

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search
Էվկլիդեսի ալգորիթմ
Euclidean algorithm 252 105 animation flipped.gif
Տեսակ ալգորիթմ
Անվանված է Էվկլիդես

Էվկլիդեսի ալգորիթմ, երկու ամբողջ թվերի ամենամեծ ընդհանուր բաժանարարը գտնելու արդյունավետ ալգորիթմ։ Ալգորիթմը իր անունը ստացել է ի պատիվ հույն մաթեմատիկոս Էվկլիդեսի։ Էվկլիդեսի ալգորիթմի ամենապարզ դեպքը վերաբերվում է երկու ամբողջ դրական թվերի զույգին, որոնցից ձևավորվում է նոր թվերի զույգ, որը կազմված է այդ երկու թվերի փոքրագույնից և մեծագույնի ու փոքրագույնի տարբերությունից։ Գործընթացը շարունակվում է այնքան ժամանակ, քանի դեռ թվերը կդառնան հավասար։ Այդ ստացված թիվն էլ հանդիսանում է տրված երկու ամբողջ թվերի ամենամեծ ընդհանուր բաժանարարը։ Այս ալգորիթմի մասին առաջին անգամ նշվել է Էվկլիդես «Սկզբունքներ» գրքում (մոտավորապես մ.թ.ա. 300 թ.)։ Այդ իսկ պատճառով էլ այն համարվում է ամենահին թվային ալգորիթմներից մեկը, որը օգտագործվում է մեր ժամանակներում։ Բայց XIX դարում այն ընդհանրացվել է տարբեր տիպի թվերի համար, ինչպիսիք են՝ Գաուսի ամբողջ թվերը, բազմանդամները։ Որից հետո հանրահաշվում առաջացավ Էվկլիդեսյան օղակ եզրույթը։ Հետագայում Էվկլիդեսյան ալգորիթմը ընդլայնել է իր շրջանակները։ Այս ալգորիթմը ունի շատ տեսական և գործնակնան կիրառություններ։ Այն օգտագործվում է գծային հավասարումների լուծման ժամանակ։ էվկլիդեսյան ալգորիթմը մեծ դեր ունի Ժամանակակից թվերի տեսության թեորեմների ապացույցների ժամանակ։

Պատմական ակնարկ[խմբագրել | խմբագրել կոդը]

Հույն մաթեմատիկոսները այս ալգորիթմը անվանել են ἀνθυφαίρεσις կամ ἀνταναίρεσις — «փոխադարձ հանում»: Այս ալգորիթմը Էվկլիդեսի հայտնագործությունը չէ, քանի որ ալգորիթմի մասին նշել է Արիստոտելը իր «Տոպիկա» տրամաբանական տեսության մեջ։ Իր «Սկզբունքներ» գրքում Էվկլիդեսը այս ալգորիթմին անդրադարձել է երկու անգամ՝ ինչպես գտնել երկու ամբողջ թվերի ամենամեծ ընդհանուր բաժանարարը (VII գրքում) և ինչպես որոշել երկու նույն կարգի մեծությունների մեծագույնը (X գրքում)։ Երկու դեպքում էլ տրված է ալգորիթմի երկրաչափական իմաստը։ Պատմաբան մաթեմատիկների կողմից ենթադրվում է, որ հենց Էվկլիդեսի ալգորիթմի օգնությամբ է, որ հույն մաթեմատիկոսները առաջ քաշեցին անսահմանության գաղափարը։ Սակայն, այս ենթադրությունը չունի հստակ փաստաթղթային ապացույց:

Նկարագրություն[խմբագրել | խմբագրել կոդը]

Էվկլիդեսի ալգգորիթմը ամբողջ թվերի համար[խմբագրել | խմբագրել կոդը]

Դիցուք և — ամբողջ թվեր են, որոնք միաժամանակ հավասար չեն 0-ի, և այդ թվերի հաջորդականությունը

որոշվում է նրանով, որ յուրաքանչյուր — դա նախորդի և վերջինիս նախորդի բաժանումից ստացած մնացորդն է, իսկ նախավերջինը անմնացորդ բաժավում է վերջինի վրա, այսինքն.

Այսինքն՝ ԱԸԲ (a, b), ամենամեծ ընդհանուր բաժանարար a և b, հավասար է rn, այդ հաջորդականության վերջին ոչ զրոյական անդամին։[1].

Այսպիսի r1, r2, ..., rn, հաջորդականության գոյությամբ, կամայական ամբողջ m և n թվերի համար, որտեղ m-ը կամայական ամբողջ թիվ է և ամբողջ n ≠ 0 թվերի համար, ապացուցվում է ըստ ինդուկցիայի մեթոդի։ Այսպիսով, կարելի է առանձնացել հետևյալ հետևանքները[2]:

  • Դիցուք՝ a = bq + r, ապա ԱԸԲ (a, b) = ԱԸԲ (b, r).
  • ԱԸԲ (r, 0) = r յուրաքանչյուր r≠ 0 թվի համար (քանի որ 0 բաժանվում է յուրաքանչյուր ամբողջ թվի վրա, բացի 0).

Էվկլիդեսի ալգորիթմի երկրաչափական իմաստը[խմբագրել | խմբագրել կոդը]

Դիցսուք՝ տրված է a և b հատվածներ։ Հաշվենք այս երկու հատվածների տարբերությունը և մեծ հատվածի արժեքը փոխարինենք ստացված տարբերությամբ։ Կրկնում ենք այս գործողությունը այնքան ժամանակ, քանի դեռ հատվածները կդառնան հավասար։ Եթե ստանում ենք նույն թիվը, ապա հենց այս թիվն էլ հանդիսանում է ամենամեծ ընդհանուր մեծույթունը։ Եթե ընդհանուր մաս չունի, ապա այս գործընթացը անվերջ կարելի է կատարել։ Էվկլիդեսը դիտարկել է այս դեպքը ևս, [3], որը իրականացվում է կարկինի և քանոնի միջոցով։

Կիրառություն[խմբագրել | խմբագրել կոդը]

Էվկլիդեսի ալգորիթմի ընդհանրացումը Բեզուի նկատմամբ[խմբագրել | խմբագրել կոդը]

Բանաձևերը -ի համար կլինեն հետևյալ կերպ.

ԱԸԲ

Ընդ որում` s и t ամբողջ թվեր են: ԱԸԲ-ի այսպիսի ներկայացումը կոչվում է Բեզուի հարաբերակցութուն, իսկ s և t թվերը` Բեզուի գործակիցներ: Հանրահաշվի հիմնական թեորեմի և Էվլիդեսի լեմմայի ապացուցման մեջ էականորեն մեծ դեր ունի Բեզուի հարաբերակցութունը:

Շղթայական կոտորակներ[խմբագրել | խմբագրել կոդը]

Էվկլիդեսի ալգորիթմը սերտ կապակցված է շղթայական կոտորակների հետ[4]: a/b ներկայացվում է շղթայական կոտորակների տեսքով հետևյալ կերպ.

.

Ընդ որում՝ շղթայական կոտորակը առանց վերջին անդամի հավասար է Բեզուի գործակիցների հարաբերությանը՝ վերցված բացասական նշանով.

.

Հավասարումների հաջորդականությունը, որը ներկայացնում է Էվկլիդեսի ալգորիթմ, կարելի է ներկայացնել հետևյալ տեսքով.

Առաջին երկու հավասարումների միավորումից կունենանք.

Հաշվի առնելով երրորդ հավասարությունը, r1/r0 կոտորակի հայտարարաը փոխարինելով, կունենանք.

Այսպիսով, rk/rk−1 կոտորակը միշտ կարող է փոխարինել հավասարումների հաջորդականության հաջորդ հավասարումով: Այս գործընթացը կարելի է շարունակել մինչև վերջին հավասարումը: Արդյունքում կստացվի շղթայական կոտորակ.

  1. Վինոգրադով, 1952, էջ 9-10
  2. Կուրանտ, 2001, էջ 67-70
  3. Մորդուխայ-Բոլստովսկի, 1949, էջ 103—105
  4. Վինոգրադով, 1952, էջ 14-18