Евклид алгоритмы

Википедия — ирекле энциклопедия мәғлүмәте

Евкли́д алгори́тмы — ике бөтөн һандың иң ҙур уртаҡ бүлеүсеһен (йәки ике киҫектең уртаҡ үлсәмен) табыу өсөн эффектив алгоритм. Алгоритм уны беренсе башлап «Башланғыстар»ҙың VII[1] һәм X[2] китаптарында һүрәтләгән грек математигы Евклид хөрмәтенә шулай аталған. Иң ябай осраҡта Евклид алгоритмы ыңғай бөтөн һандар парына ҡулланыла һәм, бәләкәй һандан һәм ҙур һан менән бәләкәй һандың айырмаһынан торған яңы пар барлыҡҡа килтерә. Ошо процесс һандар тигеҙ булғанға тиклем дауам итә. Табылған һан бирелгән парҙың иң ҙур уртаҡ бүлеүсеһе була ла инде.

Алгоритмдың беренсе тасуирламаһы Евклидтың «Башланғыстар» китабында (б.э.т. яҡынса300 йыл) бирелгән, ул бөгөнгө көндә лә ҡулланылған иң боронғо һанлы алгоритм[3]. Алгоритмдың оригиналы тик натураль һандар һәм геометрик оҙонлоҡтар (ысын һандар) өсөн тәҡдим ителгән була. Ләкин XIX быуатта ул Гаусстың бөтөн һандары кеүек башҡа типтағы һандарға һәм бер үҙгәреүсәнле полиномдарға дөйөмләштерелә. Был хәҙергә дөйөм алгебрала евклид балдағы тигән төшөнсә барлыҡҡа килтерҙе. Һуңғараҡ Евклид алгоритмы төйөндәр һәм күп үлсәмле полиномдар кеүек башҡа математик структуралар өсөн дә дөйөмләштерелә. Был алгоритм өсөн күп теоретик һәм практик ҡулланылыш бар. Айырып әйткәндә, ул электрон коммерцияла киң таралған асыҡ асҡыслы RSA[4] криптографик алгоритм өсөн нигеҙ булып тора. Алгоритмдар шулай уҡ һыҙыҡлы диофант тигеҙләмәләрен сығарғанда[5], өҙлөкһөҙ кәсерҙәр төҙөгәндә[6], Штурм методында[7] ҡулланылалар. Евклид алгоритмы дүрт квадраттың суммаһы тураһында Лагранж теоремаһы[8], арифметиканың төп теоремаһы[9] һ.б. кеүек хәҙергә һандар теорияһы теоремаларын иҫбат итеү өсөн төп инструмент булып тора.

Тарих[үҙгәртергә | сығанаҡты үҙгәртеү]

Боронғо грек математиктары был алгоритмды ἀνθυφαίρεσις йәки ἀνταναίρεσις — «үҙ-ара алыу» тип атайҙар. Был алгоритм Евклид тарафынан асылмаған, сөнки ул Аристотель Топигында[3] телгә алына. Евклид «Башланғыстарында» ул ике тапҡыр — VII китапта ике натураль һандың иң ҙур уртаҡ бүлеүсеһен[1] табыу өсөн һәм X китапта ике бер төрлө дәүмәлдең[1] иң ҙур уртаҡ үлсәмен табыу өсөн телгә алына. Ике осраҡта ла, ике киҫектең «дөйөм үлсәмен» табыу өсөн, алгоритмдың геометрик тасуирламаһы бирелә.

Математика тарихсылары фаразлауынса, тап Евклид алгоритмы (эҙмә-эҙ үҙ-ара алыу процедураһы) ярҙамында сағыштырғыһыҙ булған дәүмәлдәрҙең (квадраттың яғы һәм диагонале, төҙөк бишмөйөштөң яҡтары һәм диагоналдәре)[10] булыуы асыҡланған. Әйтергә кәрәк, был фараздың етерлек документаль раҫламаһы юҡ. Ике натураль һандың иң ҙур уртаҡ бүлеүсеһен эҙләү алгоритмы боронғо ҡытайҙың туғыҙ китаптан торған Математика трактатының I китабында ла тасуирланған.

Тасуирлама[үҙгәртергә | сығанаҡты үҙгәртеү]

Бөтөн һандар өсөн Евклид алгоритмы[үҙгәртергә | сығанаҡты үҙгәртеү]

и — бер үк ваҡытта нулгә тигеҙ булмаған бөтөн һандар булһын, ти, һәм

һандар эҙмә-эҙлелеге

шулай билдәләнгән, һәр — алдағынан алдағы һанды алдағы һанға бүлеүҙән ҡалдыҡ, әһуңғыһынан алдағы һуңғыһына ҡалдыҡһыҙ бүленә, йәғни:

Ул саҡта ИҘУБ(a, b), a һәм b-ның иң ҙур уртаҡ бүлеүсеһе, rn-ға, был эҙмә-эҙлелектең[11] һуңғы нулдән айырмалы быуынына, тигеҙ.

Шундай r1, r2, ..., rn-ҙың булыуы, йәғни теләһә ниндәй бөтөн m һәм бөтөн n ≠ 0 өсөн m-ды n-ға ҡалдыҡлы бүлеү мөмкин икәнлеге, m буйынса индукция ярҙамында иҫбатлана.

Был алгоритмдың урынлы булыуы түбәндәге ике раҫлауҙан[12] килеп сыға:

  • a = bq + r булһын, ул саҡта ИҘУБ(a, b) = ИҘУБ(b, r).
  • Нулдән айырмалы теләһә ниндәй r өсөн ИҘУБ(r, 0) = r (сөнки 0 нулдән башҡа теләһә ниндәй бөтөн һанға бүленә).

Геометрик Евклид алгоритмы[үҙгәртергә | сығанаҡты үҙгәртеү]

Оҙонлоҡтары a һәм b булған ике киҫек бирелһен, ти.Ҙур киҫектән бәләкәйен алабыҙ һәм ҙур киҫекте килеп сыҡҡан айырма менән алмаштырабыҙ. Был операцияны, киҫектәр тигеҙ булғанға тиклем, ҡабатлайбыҙ. Әгәр был хәл тыуһа, бирелгән киҫектәр үлсәнмәле, һуңғы табылған киҫек уларҙың иң ҙур уртаҡ үлсәме була. Әгәр уртаҡ үлсәм булмаһа, процесс сикһеҙ дауам итә. Ошондай күренештә алгоритм Евклид тарафынан тасуирланған[2] һәм циркуль һәм линейка ярҙамында башҡарыла.

Миҫал[үҙгәртергә | сығанаҡты үҙгәртеү]

Евклид алгоритмын һүрәтләү өсөн a = 1071 һәм b = 462 һандарының ИҘУБ табыуҙы ҡарайбыҙ. Тәүҙә 1071-ҙән 462-нең тапҡырлы ҡиммәтен, айырма 462-нән кәм булғанға тиклем, алабыҙ. Беҙ ике тапҡыр 462-не алабыҙ (q0 = 2), 147 ҡалдығы килеп сыға:

1071 = 2 × 462 + 147.

Бынан һуң 462-нән 147-нең тапҡырлы ҡиммәтен, ҡалдыҡ 147-нән кәмерәк булғансы, алабыҙ. Беҙ 147-не өс тапҡыр (q1 = 3)) алырға тейешбеҙ, ҡалдыҡ 21 килеп сыға:

462 = 3 × 147 + 21.

Аҙаҡ 147-нән 21-ҙең тапҡырлы ҡиммәтен, ҡалдыҡ 21-ҙән кәмерәк булғанға тиклем, алабыҙ. Беҙ 21-ҙе ете тапҡыр (q2 = 7 алырға тейешбеҙ, ҡалдыҡ ҡалмай:

147 = 7 × 21 + 0.

Шулай итеп a > b > r1 > r2 > r3 > … > rn эҙмә-эҙлелеге был конкрет осраҡта ошолай булып күренә:

1071 > 462 > 147 > 21.

Һуңғы ҡалдыҡ нулгә тигеҙ булғас, алгоритм 21 һаны менән тамамлана һәм ИҘУБ(1071, 462) = 21.

Аҙымдар таблица формаһында түбәндәгесә:

Аҙым k Тигеҙлек Бүлендек һәм ҡалдыҡ
0 1071 = q0 462 + r0 q0 = 2 и r0 = 147
1 462 = q1 147 + r1 q1 = 3 и r1 = 21
2 147 = q2 21 + r2 q2 = 7 и r2 = 0; алгоритм тамам

Ҡулланылышы[үҙгәртергә | сығанаҡты үҙгәртеү]

Евклидтың киңәйтелгән алгоритмы һәм Безу нисбәте[үҙгәртергә | сығанаҡты үҙгәртеү]

 өсөн формулаларҙы ошолай итеп күсереп яҙырға була:
ИҘУБ

Бында s һәм t бөтөн һандар. Иң ҙур уртаҡ бүлеүсене күрһәтеү Безу нисбәте тип атала, ә s һәм t һандары — Безу коэффициенттары [13]. Безу нисбәте Евклид леммаһын һәм арифметиканың төп теоремаһын иҫбатлағанда төп урынды алып тора..

Сылбырлы кәсерҙәр[үҙгәртергә | сығанаҡты үҙгәртеү]

Евклид алгоритмы сылбырлы кәсерҙәр менән тығыҙ бәйләнгән[14]. a/b сағыштырмаһын сылбырлы кәсер рәүешендә күрһәтергә мөмкин:

.

Бында һуңғы быуынынан башҡа сылбырлы кәсер минус тамғаһы менән алынған Безу коэффициентына t/s тигеҙ:

.

Евклид алгоритмын биргән һуңғы тигеҙлекте ошо формала яҙырға мөмкин:

Тигеҙлектең уң яғындағы һуңғы ҡушылыусы һәр ваҡыт артабанғы тигеҙләмәнең һул яғының кире ҡиммәтенә тигеҙ. Шуға күрә тәүге ике тигеҙләмәне ошолай берләштерергә мөмкин:

Өсөнсө тигеҙлек r1/r0 аңлатмаһының знаменателен алмаштырыу өсөн ҡулланылырға мөмкин. Табабыҙ:

Һуңғы ҡалдыҡтар сағыштырмаһы rk/rk−1 һәр ваҡыт эҙмә-эҙлелектәге артабанғы тигеҙлекте ҡулланып алмаштырылырға мөмкин, һәм шулай һуңғы тигеҙләмәгә тиклем.Һөҙөмтәлә сылбырлы кәсер килеп сыға:

Юғарыла килтерелгән #миҫалда миҫалда ИҘУБ(1071, 462) иҫәпләнде һәм ярашлы рәүештә 2, 3 һәм 7-гә тигеҙ булған qk бүлендектәр табылды. Шуға күрә 1071/462 бүлендеге ошолай яҙылырға мөмкин:

Һыҙыҡлы диофант тигеҙләмәләр[үҙгәртергә | сығанаҡты үҙгәртеү]

Диофант тигеҙләмәһе — ул бөтөн һанлы коэффициентлы һәм бер йәки бер нисә үҙгәреүсәнле тигеҙләмә, шуның менән бергә уның тик бөтөн тамырҙарын ғына табыу маҡсаты ҡуйыла. Ундай тигеҙләмәнең сикһеҙ күп сығарылышы булырға, сикле һанда сығарылышы булырға йәки бөтөнләй сығарылышы булмаҫҡа мөмкин. Иң ябай диофант тигеҙләмәһе - ике үҙгәреүсәнле һыҙыҡлы тигеҙләмә:

бында a, b, c — бөтөн һандар. Евклид алгоритмы ярҙамында бындай типтағы тигеҙләмәнең тулы сығарылышын табырға мөмкин[12]. Иң тәүҙә был алгоритм ярҙамында d = ИҘУБ(a, b) табырға була. Аҙаҡ, Евклидтың киңәйтелгән алгоритмын ҡулланып, шундай k һәм l табыла:

Йәғни x = k һәм y = l - тигеҙләмәнең c = d булғандағы сығарылышы. Әгәр c = q⋅d, ул саҡта x = q⋅k, y = q⋅l - бирелгән тигеҙләмәнең сығарылышы булыуы килеп сыға, сөнки:

Киреһенсә, әгәр тигеҙләмәнең бер генә булһа ла сығарылышы булһа, ул саҡта c d-ға бүленә. Был шунан килеп сыға, d a-ны ла, һәм b-ны ла бүлә (тимәк бөтә һул яғын), шуға күрә c-ны ла (уң яғын) бүлергә тейеш. Шулай итеп, һыҙыҡлы диофант тигеҙләмәһенең бер генә булһа ла сығарылышы шул саҡта һәм тик шул саҡта була, әгәр c ИҘУБ(a, b)-нә бүленһә.

Вариациялар һәм дөйөмләштереү[үҙгәртергә | сығанаҡты үҙгәртеү]

Евклид балдағы[үҙгәртергә | сығанаҡты үҙгәртеү]

Евклид алгоритмын ҡулланып булған балдаҡтар евклид балдаҡтары[15] тип атала. Уларға бөтөн һандар балдаҡтары һәм күпбыуындар балдаҡтары инә.

Күпбыуындар өсөн дөйөмләштерелгән Евклид алгоритмы[үҙгәртергә | сығанаҡты үҙгәртеү]

Евклид алгоритмы һәм киңәйтелгән Евклид алгоритмы тәбиғи рәүештә ирекле k яланында бер үҙгәреүсәнле k[x] күпбыуындар балдағында дөйөмләштерелә, сөнки ундай күпбыуындар өсөн ҡалдыҡлы бүлеү ғәмәле билдәләнгән. Күпбыуындар өсөн Евклид алгоритмын башҡарғанда, бөтөн һандарға Евклид алгоритмын ҡулланғандағыға оҡшаш рәүештә, полиномиаль ҡалдыҡтар (PRS)[16] эҙмә-эҙлелеге килеп сыға.

Алгоритмдың тиҙләтелгән версиялары[үҙгәртергә | сығанаҡты үҙгәртеү]

  • Бөтөн һанлы Евклид алгоритмын тиҙләтеү ысулдарының береһе булып симметрик ҡалдыҡ[17] ҡулланыу тора:
бында

кәметергә мөмкинлек бирә.

Иҫкәрмәләр[үҙгәртергә | сығанаҡты үҙгәртеү]

Әҙәбиәт[үҙгәртергә | сығанаҡты үҙгәртеү]


Һылтанмалар[үҙгәртергә | сығанаҡты үҙгәртеү]

Ҡалып:Добротная статья