Sveu?ilište u Zagrebu

Fakultet organizacije i
informatike

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

 

 

 

 

 

Esej br. 1: Euklidov algoritam

 

 

 

 

 

 

 

 

 

 

 

 

U Varaždinu, 23.12.2017.                                                                               Mi?i?,
Mateo, G31

Sadržaj
 
Uvod. 3
Euklidov algoritam.. 3
Primjer upotrebe
algoritma. 7
Literatura. 10
 

 

Uvod

 

Euklid (gr?.
?????????, oko 330. pr. Kr. – oko
275. pr. Kr.) jedan je od najpoznatijih starogr?kih matemati?ara. Ro?en je u Ateni, a živio je u Aleksandriji
gdje je i osnovao matemati?ku školu. Tokom svog života, napisao je mnoga djela,
mnoga od kojih su bila predmet prou?avanja i gotovo neograni?en izvor znanja koje
su koristile generacijama matemati?ara sve do danas.

Mnoga od tih djela,
izgubljena su, a od onih koja su o?uvana, najvažnije je Elementi, kolekcija od 13 knjiga koje se bave teorijom geometrije. U
knjigama I–VI obra?ena je planimetrija,
VII–X aritmetika i teorija brojeva u
geometrijskom obliku, a XI–XIII stereometrija.

 

Euklidov algoritam

Euklidov algoritam
je jedan od najstarijih algoritama koji se još uvijek upotrebljava.1 
U VII knjizi, algoritam je formuliran za cijele brojeve, dok je u X knjizi dana
primjena na dužini, što pokazuje da je on geometrijske prirode.2 Najve?i
zajedni?ki djelitelj za dane dužine a i b odgovara
dužini g koja je najve?a mogu?a dužina kojom se mogu izmjeriti a i b podjednako.
Drugim rije?ima, dužine a i b se mogu dobiti
množenjem dužine g nekim cijelim brojem.

            U Europi,
Euklidov algoritam je prvi put opisao Claude
Gaspard Bachet de Méziriac u drugom izdanju svog
djela Problèmes plaisants et délectables (1624. god.),3 a
pretpostavlja se da je korišten u rješavanju diofantskih jednadžbi i pri
konstrukciji verižnih
razlomaka. Prošireni
Euklidov algoritam je,
kao metodu za efikasno izra?unavanje verižnih razlomaka, objavio engleski
matemati?ar Nikolas
Saunderson,
pripisavši ga Rogeru
Koutsu.4

            Euklidov algoritam je iterativne
prirode, što zna?i da se krajnji rezultat dobiva u nizu koraka, dok se
me?urezultat proizvoljnog koraka koristi u prvom sljede?em.5
Ukoliko je k cijeli broj kojim su ozna?eni koraci algoritma po?evši
od nule,
prvom koraku odgovara jednakost k = 0, drugom k = 1,
i tako dalje.

            Svaki korak po?inje sa dva
nenegativna ostatka rk?1 i rk?2.
Kako algoritam osigurava da se ostaci svakim korakom neprekidno smanjuju, rk?1 je
manje od svog prethodnika rk?2. Cilj k-tog
koraka je da se odrede koli?nik qk i ostatak rk takvi
da vrijedi jednakost:

rk?2 = qk rk?1 + rk

gdje je rk < rk?1.             Drugim rje?ima, umnošci manjeg broja rk?1 se oduzimaju od ve?eg broja rk?2 sve dok je dobiveni ostatak manji od rk?1.             U prvom koraku (k = 0), ostatci r?2 ir?1 su jednaki a i b respektivno, a to su upravo brojevi za koje se traži najve?i zajedni?ki djelitelj. U sljede?em koraku (k = 1), ostatci postaju jednaki b i ostaku po?etnog koraka r0...             Ispravnost Euklidovog algoritma se može dokazati u dva koraka.6 U prvom koraku pokazuje se da posljednji ostatak rN?1 razli?it od nule dijeli istovremeno i a i b. Kako je u pitanju zajedni?ki djelitelj, on mora biti manji ili jednak najve?em zajedni?kom djelitelju g. U drugom koraku se pokazuje da proizvoljan zajedni?ki djelitelj brojeva a i b, uklju?uju?i i g, mora da dijeli i rN?1; gdje dalje slijedi da g mora biti manji ili jednak rN?1. Dobivena dva zaklju?ka su konzistentna samo u slu?aju da je rN?1 = g.             Da bi se pokazao prvi korak, odnosno da rN?1 djeli istovremeno i a i b, najprije treba primjetiti da rN?1 dijeli svog prethodnika rN?2: rN?2 = qN rN?1 kako je posljednji ostatak rN jednak nuli. rN?1 djeli i rN?3: rN?3 = qN?1 rN?2 + rN?1 zato što istovremeno dijeli oba pribrojnika s desne strane jednakosti. Razmatraju?i redom ostale prethodnike, dobiva se da ih rN?1 dijeli sve, uklju?uju?i a i b. S druge strane, nijedan od preostalih ostataka rN?2, rN?3, itd. ne dijeli istovremeno i a i b, pošto se u jednakostima uvijek javlja ostatak. Kako je rN?1 zajedni?ki djelitelj brojeva a i b, mora biti rN?1 ? g.             U drugom koraku treba dobiti da proizvoljan prirodan broj c koji istovremeno dijeli i a i b (proizvoljan zajedni?ki djelitelj brojeva a i b) mora dijeliti i ostatak rk. Po definiciji, a i b mogu biti zapisani kao umnošci broja c:  a = mc i b = nc, pri ?emu su m i n prirodni brojevi. Dalje slijedi da c dijeli prvi ostatak r0, jer vrijedi sljede?i niz jednakosti: r0 = a ? q0b = mc ? q0nc = (m ? q0n)c.             Analogno se može dobiti da c djeli i ostatke r1, r2, itd. Zaklju?ak je da najve?i zajedni?ki djelitelj g mora dijeliti rN?1, odakle je g ? rN?1. Kako je prema prvom koraku dan uvjet za: rN?1 ? g, slijedi da mora biti: g = rN?1. Zato je g najve?i zajedni?ki djelitelj svih sljede?ih parova:78 g = najve?i zajedni?ki djelitelj (a, b) = i zajedni?ki djelitelj (b, r0) = i zajedni?ki djelitelj (r0, r1) = … = i zajedni?ki djelitelj (rN?2, rN?1) = rN?1.   Primjer upotrebe algoritma   1.      Primjer Tražimo najve?i zajedni?ki djelitelj brojeva: a = 1071 i b = 462 U prvom koraku od broja a oduzimamo broj b, sve dok se kao rezultat ne dobije broj manji od 462, te se vidi da se taj postupak može ponoviti 2 puta, jer vrijedi sljede?a jednakost: 1071 = 2 × 462 + 147. Sada ponavljamo analogno postupak za brojeve 462 i 147 sve dok kao rezultat ne dobijemo broj manji od 147, što se postiže kroz 3 ponavljanja: 462 = 3 × 147 + 21. Tre?i korak je pak postpuak oduzimanja broja 21 od 147 sve dok ne dobijemo ostatak manji od 21, što se postigne u 7 ponavljanja, a ostatak je jednak nuli: 147 = 7 × 21 + 0.   Kako je ostatak jednak nuli, algoritam se završava, a 21 je najve?i zajedni?ki djelitelj brojeva 1071 i 462. Dobiveni rezultat se podudara s najve?im zajedni?kim djeliteljem tih brojeva odre?enim pomo?u faktorizacije na proste brojeve. Još ?emo pokazati navedeno na 3 para brojeva. 2.      Primjer a= 2056, b= 569 a-b=2056-569=1487-569=918-569=349 a=3x569 + 349 569-349=220 569=1x349+220 349-220=129 349=1x220+129 220-129=91 220=1x129+91 129-91=38 129=1x91+38 91-38=53-38=15 91=2x38+15 38-15=23-15=8 38=2x15+8 15-8=7 15=1x8+7 8-7=1 8=1x7+1 7-1=6-1=5-1=4-1=3-1=2-1=1-1=0 7=7*1+0 Najve?i zajedni?ki djeljitelj brojeva a= 2056, b= 569 je broj 1. 3.      Primjer a= 1925, b= 775   1925-775=1150-775=375 14925=2x775+375 775-375=400-375=25 775=375x2+25 375-25=350-25=325-25=300-25=175-25=150-25=125-25=100-25=75-25=50-25=25-25=0 375=15x25+0 Najve?i zajedni?ki djelitelj brojeva a= 1925, b= 775 je broj 25.   4.      Primjer   a= 1248, b= 728 1248-728=520 1248=728x1+520 728-520=208 728=520x1+208 520-208=312-208=104 520=208x2+104 208-104=104-104=0 208=104*2+0   Najve?i zajedni?ki djelitelj brojeva a= 1248, b= 728 je broj 104.     Literatura          I.            http://www.enciklopedija.hr/natuknica.aspx?ID=18596 (Preuzeto 17.12.2017.)     II.            Knuth, The Art of Computer Programming, Volume 2, str. 318.  III.            Jones A (1994). "Greek mathematics to AD 300". Companion encyclopedia of the history and philosophy of the mathematical sciences. New York: Routledge. str. 46-48. ISBN 978-0-415-09238-8.  IV.            Tattersall, Elementary number theory in nine chapters, str. 70.     V.            Tattersall, Elementary number theory in nine chapters, str. 72–76.  VI.            Stark, An Introduction to Number Theory, str. 16–20. VII.            Knuth, The Art of Computer Programming, Volume 2, str. 320. VIII.            Lovasz, Laszlo; Jozsef Pelikan, Katalin L. Vesztergombi (2003). Discrete Mathematics: Elementary and Beyond. New York: Springer-Verlag. str. 100-101. ISBN 978-0-387-95584-1.  IX.            https://web.math.pmf.unizg.hr/nastava/metodika/sem1617/7as-stariGrci.pdf (Preuzeto 19.12.2017.)             1 Knuth, The Art of Computer Programming, Volume 2, str. 318. 2 Jones A (1994). "Greek mathematics to AD 300". Companion encyclopedia of the history and philosophy of the mathematical sciences. New York: Routledge. str. 46-48. ISBN 978-0-415-09238-8. 3 Tattersall, Elementary number theory in nine chapters, str. 70. 4 Tattersall, Elementary number theory in nine chapters, str. 72–76. 5 Stark, An Introduction to Number Theory, str. 16–20. 6 Stark, An Introduction to Number Theory, str. 16–20. 7 Knuth, The Art of Computer Programming, Volume 2, str. 320. 8 Lovasz, Laszlo; Jozsef Pelikan, Katalin L. Vesztergombi (2003). Discrete Mathematics: Elementary and Beyond. New York: Springer-Verlag. str. 100-101. ISBN 978-0-387-95584-1.