Euklidesen algoritmo

Wikipedia, Entziklopedia askea
Hona jauzi: nabigazioa, Bilatu

Euklidesen algoritmoa, matematikan, bi zenbakiren zatitzaile komunetako handiena () kalkulatzeko erabiltzen den metodo bat da. Euklidesek deskribatu zuen lehenengo aldiz bere Elementuak obran (K. a. 300). Euklidesen algoritmo hedatuarekin, gainera, zatitzaile komunetako handiena emandako bi zenbakien konbinazio lineal moduan adierazteko koefizienteak kalkula daitezke. Algoritmoa hainbat arlotan aplikatzen da; aljebran, zenbaki-teorian eta informatikan, esaterako.

Euklidesen jatorrizko algoritmoa[aldatu | aldatu iturburu kodea]

AB eta CD segmentu neurgarriak

Grekoek matematikari buruz zuten ikuspuntuaren arabera, zenbakiak magnitude geometrikoak dira. Geometria grekoak bi segmenturen neurgarritasuna aztertzen zuen: bi segmentu (zenbaki) AB eta CD neurgarriak dira hirugarren PQ segmentu bat existitzen bada zein aurreko bien barruan egokitzen den n zenbaki osoa adina aldiz, hau da, PQ-k AB eta CD segmentuak neurtzen baditu.

Edozein segmentu bikote ez da neurgarria; pitagorikoek aurkitu zuten moduan, karratuaren diagonala eta aldea ez dira neurgarriak. Bi segmentu neurgarriak direnean, haien arteko neurri komun handiena topatu nahi izaten da.

Euklidesek bere Elementuak lanaren VII liburuko 2. proposizioan bi segmenturen (zenbakiren) neurri komun handiena topatzeko metodo bat deskribatzen du, zenbakiak haien artean lehenak ez diren kasurako.

« Elkarren artean lehenak ez diren bi zenbakiren gehienezko neurri komuna aurkitzeko.
Euclides VII-2.svg

Izan bitez AB, CD emandako bi zenbaki elkarrekiko ez-lehenak. Bada, AB, CD zenbakien neurri komun handiena aurkitu behar da.

 »
Euklides. Elementuak VII.2

Metodoa termino geometrikoetan azaldu zen garai hartan. Gaur egungo hizkuntza modernoan algoritmoa horrela deskribatzen da:

Euklidesen jatorrizko algoritmoaren adibidea
  1. Izan bitez AB eta CD bi segmentu, non AB>CD betetzen den. AB-ri CD kentzen diogu behin eta berriz posiblea den bitartean. Amaieran hondarrik geratzen ez bada, orduan CD da neurri komun handiena.
  2. EA hondarra geratzen bada, CD baino txikiagoa izango da eta prozesua errepika daiteke; CD-ri EA kenduko zaio behin eta berriz posiblea den bitartean. Azkenean hondarrik gelditzen ez bada, EA izango da neurri komuna. Bestela, EA baino txikiagoa den FC hondar berria lortuko da.
  3. Prozesua errepikatu behar da hondarrik geratuko ez den arte. Lortutako azken hondarra da neurri komun handiena.

Euklidesen algoritmoa[aldatu | aldatu iturburu kodea]

Zatiketa Euklidearraren definizioaren arabera, bi zenbaki oso eta izanik, , beste bi zenbaki oso eta existitzen dira eta bakarrak dira non

betetzen den, izanik eta -ren balio absolutua den. Hau da, zenbaki osoa zenbaki osoaz zatitzean zatidura eta hondarra lortzen dira.

Euklidesen algoritmoa zatiketa euklidearrean oinarritzen da eta bi zenbaki osoren zatitzaile komunetako handiena kalkulatzeko balio du. eta bi zenbakiren zatitzaile komunetako handiena adierazteko erabiltzen den notazioa da.

Euklidesen algoritmoaren oinarrizko printzipioa da. Bertatik ondorioztatzen da dela. Hortaz, Euklidesen algoritmoa erabiliz eta bi zenbakiren zatitzaile komunetako handiena horrela kalkulatzen da:

  1. bada da.
  2. Bestela, da, izanik eta -ren arteko zatiketa euklidearraren hondarra.

Demagun eta notazioaz adierazten direla. kalkulatzeko prozedura orokorra honakoa da:

Urratsa a b Eragiketa q r Esanahia
1 zati
2 zati
3 zati
...
zati
zati

Hondarra txikituz doanez, azkenean 0 hondarra lortuko da eta prozedura amaituko da. eta zenbakien zatitzaile komunetako handiena ez den azken hondarra da: .

Adibidea.

eta izanik, horrela kalkulatzen da:

Urratsa a b Eragiketa q r Esanahia
1 zati
2 zati
3 zati

sekuentziaren bidez, honakoa ondorioztatzen da: eta denez, da.

Orokortasuna[aldatu | aldatu iturburu kodea]

Euklidesen algoritmoak ez du zenbaki arruntetarako soilik balio; hondarra uzten duen zatiketa bat dagoen beste kasuetara ere orokor daiteke. Koefiziente arrazionalak dituzten polinomioen arteko zatiketa euklidearra ere definitu daitekeenez, haien arteko zatitzaile komunetako handiena kalkula daiteke.

Adibidea.

Euklidesen algoritmoaren bidez eta polinomioen arteko zatitzaile komunetako handiena horrela kalkulatzen da:

Urratsa Eragiketa Esanahia
1 zati ; hondarra:
2 zati ; hondarra:
3 zati ; hondarra:

Hortaz, eta polinomioen zatitzaile komunetako handiena dela ondorioztatzen da.

Deskribapen formala[aldatu | aldatu iturburu kodea]

Algoritmoa modu formalagoan adierazteko sasikodea erabil daiteke. Kasu honetan, "" adierazpenaren esanahia " zati eragiketarekin lortutako hondarra" da (ikus Aritmetika modular).

Euklides algoritmoa


Algoritmo hau ez da eraginkorra konputagailuan inplementatua izateko, balio guztiak gordetzea eskatzen duelako.

Euklidesen algoritmo hedatua[aldatu | aldatu iturburu kodea]

Bi zenbaki osoren zatitzaile komunetako handiena haien konbinazio lineal moduan idatz daiteke. Formalki, eta bi zenbaki oso izanik, betetzen duten eta koefiziente osoak existitzen dira, edo izanik. Gainera, da eta zenbakien konbinazio lineal moduan idatz daitekeen zenbaki oso positiborik txikiena. eta koefizienteak ez dira bakarrak.

Euklidesen algoritmo hedatuari esker, kalkulatzeaz gain eta koefiziente osoak kalkula daitezke.

Oinarrizko printzipioak[aldatu | aldatu iturburu kodea]

Euklidesen algoritmo hedatua azaltzeko, hainbat modu daude. Erabilienetako bat honako hau da:

  1. Euklidesen algoritmoa erabiltzea. Urrats bakoitzean, zenbakia zenbakiaz zatitzean, zatidura eta hondarra lortzen dira. ekuazioaren bidez adierazten da.
  2. Ekuazio bakoitzean hondarra askatzen da ().
  3. Azken ekuazioaren hondarra azken-aurrekoan ordezkatzen da, eta azken-aurrekoa azken-aurrekoaren aurrekoan eta horrela lehenengo ekuaziora iritsi arte. Urrats bakoitzean hondarra zenbakien konbinazional lineal moduan adierazita agertuko da.

Aplikazioak[aldatu | aldatu iturburu kodea]

Zatikien sinplikazioa[aldatu | aldatu iturburu kodea]

Zatikiekin eragitean, sinplifikazioak egitea oso garrantzitsua gertatzen da. Esaterako, eta zatikiak baliokideak dira (ikus Zenbaki arrazional). Izan ere, bada, zatikiak baliokideak dira. Oro har, zatikia sinplifikatzeko, eta zenbakiak haien zatitzaile komunetako handienaz zatitu behar dira.

Adibidea.

zatikia sinplifikatzeko, denez, eta zatiketak egiten dira, eta = baliokideak direla ondorioztatzen da.

Zatiki jarraituak[aldatu | aldatu iturburu kodea]

Euklidesen algoritmoa aplikatzean egiten den zatiketa euklidear sorta zatikia zatiki jarraitu moduan adierazteko erabil daiteke. Izan ere, eta badira, zera betetzen da:

Adibidea.

zatikia izanik, Euklidesen algoritmoa erabiliz kalkulatzean, honako zatiketa euklidear sorta egiten da:

Urratsa Eragiketa q r Esanahia
1 zati
2 zati
3 zati
4 zati

Ekuazio horiek guztiak era honetan ere idatz daitezke:

Bigarren ekuazioa lehenengoan ordezkatuz gero, honakoa lortzen da:

Gainerakoak ere ordenatuz, honako adierazpena lortzen da:

Oro har, zera baiezta daiteke:

Alderantzizko modularrak[aldatu | aldatu iturburu kodea]

Bi zenbaki oso moduluko kongruenteak direla esaten da, zati m egitean hondar bera lortzen bada. Adibidez, 7 kongruentea da 12 modulu 5-ekin 7 zati 12 eta 5 egitean, bietan hondar bera lortzen delako (hau da, 2). kongruentea denean modulu -rekin, honela idazten da: . Aurreko adibidea, beraz, honela idatziko litzateke: . Suposatuz eta baloreak ezagunak direla eta ezezaguna ondorengo ekuazioan:

Nahikoa da balorea aurkitzea, zeinek ezaugarria duen. Horrela, aurreko ekuazioa -ekin biderkatuz, nahi den soluzioa lortuko da:

faktoreari modulu -ren alderantzizko modular deritzo. Zoritxarrez, balore hau ez da beti existitzen. Esaterako, eta direnean, ez da existitzen zenbaki osorik -entzat, non . Balore hau baldin eta soilik baldin izanik existitzen da. Euklidesen algortimo hedatua erabiltzean ( orain ) , lortzen da. Ondorioz, modulu -ren alderantzizko modularra da. Adibidez, honako ekuazio hau burutu nahi bada:

Orduan, Euklidesen algoritmo hedatuarekin kalkulatzen da. denez, 5-ak alderantzizko modularra du. Gainera,denez, alderantzizko hori 2 da. Orduan:

, hau da, -ren balioa da.

Algoritmoaren konplexutasuna[aldatu | aldatu iturburu kodea]

Lamé-ren teoremak baieztatzen du Euklidesen algoritmoa aplikatzean kasurik okerrena Fibonacci-ren segidako ondoz ondoko bi zenbakiren zatitzaile komunetako handiena kalkulatzean ematen dela.

Adibidea.

eta zenbakien zatitzaile komunetako handiena kalkulatzeko honako eragiketak egin behar dira:

Euklidesen algoritmoa aplikatzean egiten den zatiketa kopuruaren grafikoa. Gorriak eragiketa gutxi adierazten du; kolore urdinagoek, aldiz, eragiketa kopuru handiagoa adierazten dute.
Urratsa Eragiketa q r Esanahia
1 zati
2 zati
3 zati
4 zati
5 zati
6 zati
7 zati
8 zati
9 zati

Ikusten denez, bi digituko bi zenbaki horietarako 9 zatiketa egin behar izan dira. Oro har, egindako zatiketa kopurua zenbakiek duten digito kopurua bider 5 baino altuagoa ez da inoiz izango.

Konplexutasun konputazionalari dagokionez, eta -ren kalkulatzeko zatiketa egin beharko dira, izanik.

Brigitte Valleek frogatu zuen bi zenbakiak bitetan adieraz badaitezke, orduan bataz bestean egin beharreko zatiketa kopurua dela.

Hala ere, ez da nahikoa zatiketa kopurua ezagutzea. Aurretik aipatu den moduan, Euklidesen algoritmoak polinomioetan eta zenbaki osoetan funtzionatzen du eta, oro har, edozein eremu euklidearretan. Kasu bakoitzean, algoritmoaren konplexutasuna egin behar den zatiketa kopuruaren eta zatiketa bakoitza egitearen kostuaren mende dago. Polinomioen kasuan, egin beharreko zatiketa kopurua da, polinomioen gradua izanik.

Bibliografia[aldatu | aldatu iturburu kodea]

  • von zur Gathen, Joachim; Gerhard, Jürgen (2003). «The Euclidean Algorithm». Modern Computer Algebra
  • Cambridge University Press. ISBN 0-521-82646-2.
  • Shoup, Victor (2008). «Euclid’s algorithm». A Computational Introduction to Number Theory and Algebra
  • Cambridge University Press. ISBN 978-0-521-85154-1.
  • Johnsonbaugh, Richard (2005). «Introducción a la teoría de números». Matemáticas Discretas. México: PEARSON EDUCACIÓN. ISBN 970-26-0637-3.
  • Ralph P. Grimaldi (1998). «Propiedades de los números enteros: Inducción matemática». Matemáticas Discreta y Combinatoria. México: Addison Wesley Longman de México. ISBN 968-444-324-2.
  • Lipschutz, Seymour; Lipson, Marc (2009). «Propiedades de los enteros». Matemáticas Discretas. McGraw-Hill. ISBN 978-970-10-7236-3.
  • Brassard, Gilles; Bratley, Paul (1997). «Análisis de algoritmos». Fundamentos de Algoritmia. Madrid: PRENTICE HALL. ISBN 84-89660-00-X.
  • Vallée, Brigitte (2002). «Dynamical Analysis of α-Euclidean Algorithms»
  • Journal of Algorithms 44 (1). ISSN 0196-6774 , pp. 246-285.
  • Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2009). «Number-Theoretic Algorithms». Introduction to Algorithms. The MIT Press. ISBN 978-0-262-53305-8.
  • Barrera Mora, Fernando (2005). «Definiciones y resultados generales». Introducción a la Teoría de Grupos
  • Publicaciones Electrónicas de la Sociedad Matemática Mexicana. ISBN 968-9161-02-4.
  • Cárdenas, Humberto; Lluis, Emilio; Raggi, Francisco; Tomás, Francisco (2004). «Divisibilidad». Álgebra Superior. México: Trillas. ISBN 968-24-3783-0.
  • Pérez Seguí, María Luisa (2006). «Divisibilidad». Teoría de Números. Instituto de Matemáticas, UNAM. ISBN 970-32-1170-0.
  • Sánchez Velázquez, Jesús (1998). «Algoritmos para números grandes». Introducción al análisis de algoritmos. México: Trillas. ISBN 968-24-4341-5.
  • Baldor, Aurelio (2008). «Máximo común divisor». Álgebra. México: Grupo Editorial Patria. ISBN 978-970-817-000-0.