Մասնակից:Արմինե Չատինյան/Ավազարկղ 2

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

Էվկլիդեսի ալգորիթմ — երկու ամբողջ թվերի ամենամեծ ընդհանուր բաժանարարը գտնելու արդյունավետ ալգորիթմ: Ալգորիթմը իր անունը ստացել է ի պատիվ հույն մաթեմատիկոս Էվկլիդեսի: Էվկլիդեսի ալգորիթմի ամենապարզ դեպքը վերաբերվում է երկու ամբողջ դրական թվերի զույգին, որոնցից ձևավորվում է նոր թվերի զույգ, որը կազմված է այդ երկու թվերի փոքրագույնից և մեծագույնի ու փոքրագույնի տարբերությունից: Գործընթացը շարունակվում է այնքան ժամանկ, քանի դեռ թվերը կդառնան հավասար: Այդ ստացված թիվն էլ հանդիսանում է տրված երկու ամբողջ թվերի ամենամեծ ընդհանուր բաժանարարը: Այս ալգորիթմի մասին առաջին անգամ նշվել է Էվկլիդեսի «Սկզբունքներ» գրքում (մոտավորապես Ք.ա. 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