Eukleidův algoritmus: Porovnání verzí

Přidáno 24 bajtů ,  před 4 lety
m
Skloňování pojmu největší společný dělitel jako neživotného, úprava sazby (doplnění mezer do matematických vyjádření)
(→‎Ukázka činnosti algoritmu: v zaměněno za w, aby souhlasilo s popisem algoritmu výše)
m (Skloňování pojmu největší společný dělitel jako neživotného, úprava sazby (doplnění mezer do matematických vyjádření))
[[Soubor:Euclidean algorithm 1071 462.gif|alt=Animace Eukleidova algoritmu|thumb|309x309px|Animace Eukleidova algoritmu]]
'''Eukleidův algoritmus''' (též '''Euklidův''') je [[algoritmus]], kterým lze určit [[Největšínejvětší společný dělitel|největšího společného dělitele]] dvou [[Přirozené číslo|přirozených čísel]], tedy největší číslo takové, že beze zbytku dělí obě čísla. Jedná se o jeden z nejstarších známých netriviálních algoritmů a postupně vznikla řada jeho modifikací například pro příbuzné úlohy. Z nich nejdůležitější je [[rozšířený Eukleidův algoritmus]], kterým lze nalézt [[Bézoutova rovnost|Bézoutovu rovnost]], neboli vyjádření největšího společného dělitele dvou čísel jejich lineární kombinací.
 
Algoritmus lze také použít i v jiných [[algebraická struktura|algebraických strukturách]], než jsou přirozená čísla. Takové struktury se nazývají [[Eukleidovský obor|Eukleidovské obory]] a jedná se například o některé [[okruh mnohočlenů|okruhy mnohočlenů]] nebo o [[Eisensteinovo číslo|Eisensteinova čísla]].
== Popis činnosti ==
 
Opakovaně prováděné operace nemění hodnotu největšího společného dělitele
Opakovaně prováděné operace nemění hodnotu největšího společného dělitele (neboť NSD(''u'',''v'')=NSD(''v'',''u''-''qv'') pro libovolné celé číslo ''q''), ale v každém kroku se hodnota proměnné ''v'' sníží, takže je zřejmé, že v konečném počtu kroků se algoritmus ukončí s tím, že ''v'' je nulové. Tehdy obsahuje proměnná ''u'' největší společný dělitel, neboť NSD(''u'',0)=''u'', což musí být současně největší společný dělitel původních čísel, neboť, jak už bylo uvedeno, hlavní smyčka programu hodnotu největšího společného dělitele nemění.
 
Opakovaně prováděné operace nemění hodnotu největšího společného dělitele (neboť NSD(''u'', ''v'') = NSD(''v'', ''u'' - ''qv'') pro libovolné celé číslo ''q''), ale v každém kroku se hodnota proměnné ''v'' sníží, takže je zřejmé, že v konečném počtu kroků se algoritmus ukončí s tím, že ''v'' je nulové. Tehdy obsahuje proměnná ''u'' největší společný dělitel, neboť NSD(''u'', 0) = ''u'', což musí být současně největší společný dělitel původních čísel, neboť, jak už bylo uvedeno, hlavní smyčka programu hodnotu největšího společného dělitele nemění.
 
== Vlastnosti algoritmu ==
== Ukázka činnosti algoritmu ==
 
Mějme čísla ''u'' = 40902, ''w'' = 24140. Výpočet probíhá následujícím způsobem:
 
{| class="wikitable"
| 40902
| 24140
| 40902 = 24140×1 + 16762
|- align="right"
| 24140
| 16762
| 24140 = 16762×1 + 7378
|- align="right"
| 16762
| 7378
| 16762 = 7378×2 + 2006
|- align="right"
| 7378
| 2006
| 7378 = 2006×3 + 1360
|- align="right"
| 2006
| 1360
| 2006 = 1360×1 + 646
|- align="right"
| 1360
| 646
| 1360 = 646×2 + 68
|- align="right"
| 646
| 68
| 646 = 68×9 + 34
|- align="right"
| 68
| 34
| 68 = 34×2 + 0
|- align="right"
| 34
== Poznámky ==
{{upravit část}}
* Na základě tohoto algoritmu lze rychle spočítat [[inverzní prvek]] k násobení v [[modulární aritmetika|modulární aritmetice]]. Největší společný dělitel dvou čísel se dá vyjádřit [[Bézoutova rovnost|Bézoutovou rovností]] jako součet násobků těchto čísel. Pokud je tímto největším společným dělitelem 1, pak dostaneme součin prvku a jeho inverzního. Tedy pokud máme spočítat inverzní prvek ''x'' modulo ''n'' a vyjde nám vyjádření největšího společného dělitele Bézoutovou rovností ''ax'' + ''bn'' = 1, kde známe všechny proměnné. Máme tak vlastně přímo rovnost ''ax''=1 [[modulo]] ''n'' a nalezené ''a'' je hledaný inverzní prvek. Tento výpočet inverzního prvku je častý v aplikacích [[teorie čísel]], zejména v [[kryptografie|kryptografii]].
* Tento algoritmus lze použít nejen pro čísla, ale také pro [[polynom]]y. Polynom je s jeho využitím možno rozdělit na součin polynomů oddělených dle násobnosti kořenů. Derivace snižuje násobnost každého kořene o 1 a zavádí nové kořeny. Největší společný dělitel s původním polynomem odstraňuje nové kořeny. Například lze tak zjistit kořeny polynomu (x - a)(x - a)(x - a)(x - b)(x - b), přestože neexistuje algoritmus na výpočet kořenů polynomu stupně většího než 4.
* Tento algoritmus je jeden z těch, u nichž není znám způsob paralelního zpracování, který by podstatně zvýšil výpočetní rychlost.
 
94

editací