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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
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