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