Algorytm Euklidesa

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Algorytm Euklidesaalgorytm wyznaczania największego wspólnego dzielnika dwóch liczb. Został opisany przez greckiego matematyka, Euklidesa w jego dziele „Elementy”, w księgach siódmej oraz dziesiątej.

Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.Rozkład na czynniki lub faktoryzacja – proces, w którym dla danego obiektu znajdują się obiekty, takie że ich iloczyn jest jemu równy, przez co są one w pewnym sensie od niego prostsze.

Pierwsze wzmianki na temat tego algorytmu pojawiły się w dziele Euklidesa zatytułowanym „Elementy”, około trzysetnego roku przed naszą erą, co sprawia, że jest jednym z najstarszych, wciąż używanych algorytmów numerycznych. Pierwsza wersja algorytmu została opisana tylko dla liczb naturalnych. W XIX wieku powstały odmiany algorytmu dla liczb całkowitych Gaussa oraz wielomianów z jedną niewiadomą. Doprowadziło to do powstania współczesnych pojęć algebry abstrakcyjnej, takich jak dziedzina Euklidesa. W późniejszych czasach opracowano odmiany algorytmu dla innych struktur matematycznych, jak węzły czy wielomiany z wieloma niewiadomymi.

Pętla repetycyjna (pętla warunkowa) w programowaniu, to rodzaj pętli, w której wykonanie kolejnej iteracji uzależnione jest od pewnego, zdefiniowanego przez programistę warunku. Warunek zawarty w definiowanej pętli jest pewnym wyrażeniem, które zwraca wartość typu logicznego (np. Pascal, Visual Basic, VBA). Istnieją języki programowania, w których składnia nie przewiduje takiego typu danych. W językach tych stosuje się wyrażenia zwracające pewną wartość innego typu, która następnie podlega odpowiedniej interpretacji, np. wartość zero może być utożsamiana z wartością false typu logicznego, a pozostałe wartości z wartością true, lub inne rozwiązania (np. PL/I, C, C++ i pochodne). W zależności do tego, czy wartość logiczna, uzyskana w wyniku ewaluacji wyrażenia reprezentującego warunek, jest równa wartości logicznej true (prawda), czy false (fałsz), wykonywanie pętli jest kontynuowane, bądź przerywane.Arytmetyka modularna, arytmetyka reszt – w matematyce system liczb całkowitych, w którym liczby „zawijają się” po osiągnięciu pewnej wartości nazywanej modułem, często określanej terminem modulo (skracane mod). Pierwszy pełny wykład arytmetyki reszt przedstawił Carl Friedrich Gauss w Disquisitiones Arithmeticae („Badania arytmetyczne”, 1801).

Istnieje wiele teoretycznych i praktycznych zastosowań algorytmu. Może on zostać wykorzystany do generowania rytmów muzycznych, stosowanych jako ostinato w muzyce. Jest wykorzystywany w algorytmie RSA. Algorytm Euklidesa używany jest też do rozwiązywania równań diofantycznych, na przykład do znajdowania liczb spełniających zadany układ kongruencji (chińskie twierdzenie o resztach) czy znajdowania liczb odwrotnych w ciele skończonym. Może być także stosowany do generowania ułamków łańcuchowych w metodzie Sturma do obliczania pierwiastków rzeczywistych wielomianu. Wykorzystywany jest również w kilku współczesnych algorytmach do faktoryzacji liczb całkowitych.

Wielomian – wyrażenie algebraiczne złożone ze zmiennych i stałych połączonych działaniami dodawania, odejmowania, mnożenia i podnoszenia do potęgi o stałym wykładniku naturalnym.RSA – jeden z pierwszych i obecnie najpopularniejszych asymetrycznych algorytmów kryptograficznych z kluczem publicznym, zaprojektowany w 1977 przez Rona Rivesta, Adi Shamira oraz Leonarda Adlemana. Pierwszy algorytm, który może być stosowany zarówno do szyfrowania jak i do podpisów cyfrowych. Bezpieczeństwo szyfrowania opiera się na trudności faktoryzacji dużych liczb złożonych. Jego nazwa pochodzi od pierwszych liter nazwisk jego twórców.

Jeżeli algorytm zostanie zaimplementowany poprzez obliczanie reszt z dzielenia, a nie odejmowanie, to jest wydajny dla dużych liczb: nigdy nie wymaga więcej dzieleń niż liczba cyfr (w systemie dziesiętnym) mniejszej liczby pomnożona przez 5. Zostało to udowodnione przez Gabriela Lamé w 1844 i uważane jest za pierwszy przypadek analizy złożoności obliczeniowej algorytmu. Sposoby zwiększenia wydajności algorytmów zostały opracowane w XX wieku.

Podprogram (inaczej funkcja lub procedura) - termin związany z programowaniem proceduralnym. Podprogram to wydzielona część programu wykonująca jakieś operacje. Podprogramy stosuje się, aby uprościć program główny i zwiększyć czytelność kodu.Instrukcja powrotu (wyjścia) to instrukcja w określonym języku programowania powodująca opuszczenie aktualnie wykonywanego bloku programu (modułu, podprogramu: procedury, funkcji, metody, lub innych segmentów - bloków programowych - występujących w określonym języku programowana, a także całego programu, procesu) i przejście do następnej instrukcji występującej po instrukcji wywołania danego podprogramu.

Największym wspólnym dzielnikiem dwóch liczb jest największa z liczb, która dzieli obie te liczby bez reszty. Algorytm Euklidesa opiera się na założeniu, że największy wspólny dzielnik dwóch liczb nie zmienia się, jeżeli od większej liczby odejmujemy mniejszą. Dla liczb całkowitych k, m oraz n załóżmy, że k jest wspólnym czynnikiem liczb A oraz B; załóżmy też, że oraz Możemy teraz dokonać działania wiemy więc, że k jest także wspólnym czynnikiem różnicy tych liczb.

Algebra ogólna – obiekt matematyczny będący przedmiotem badań algebry uniwersalnej. Czasami algebra uniwersalna nazywana jest algebrą ogólną, wówczas rozważane w niej obiekty nazywa się zwykle algebrami abstrakcyjnymi lub po prostu algebrami.MathWorld – encyklopedia matematyczna online, sponsorowana przez Wolfram Research, twórcę i producenta programu Mathematica; współsponsorem jest National Science Foundation (National Science Digital Library).

Opis algorytmu[ | edytuj kod]

Najprostsza wersja algorytmu rozpoczyna się od wybrania dwóch liczb naturalnych, dla których należy wyznaczyć największy wspólny dzielnik. Następnie z tych dwóch liczb tworzymy nową parę: pierwszą z liczb jest liczba mniejsza, natomiast drugą jest różnica liczby większej i mniejszej. Proces ten jest powtarzany aż obie liczby będą sobie równe – wartość tych liczb to największy wspólny dzielnik wszystkich par liczb wcześniej wyznaczonych. Wadą tej wersji algorytmu jest duża liczba operacji odejmowania, które należy wykonać w przypadku, gdy różnica pomiędzy liczbami z pary jest znacząca.

Liczby całkowite – liczby naturalne dodatnie N + = { 1 , 2 , 3 , … } {displaystyle mathbb {N} _{+}={1,2,3,dots }} oraz liczby przeciwne do nich { − 1 , − 2 , − 3 , … } {displaystyle {-1,-2,-3,dots }} , a także liczba zero. Uogólnieniem liczb całkowitych są liczby wymierne i tym samym liczby rzeczywiste, szczególnym przypadkiem liczb całkowitych są: liczby naturalne.Struktura matematyczna (także model, system semantyczny, model semantyczny, dziedzina, struktura pierwszego rzędu) - w matematyce zbiór obiektów matematycznych połączonych w pewien system.

Operacja odejmowania mniejszej liczby od większej może zostać zastąpiona przez wyznaczanie reszty z dzielenia. W tej wersji nowa para liczb składa się z mniejszej liczby oraz reszty z dzielenia większej przez mniejszą. Algorytm kończy się w momencie, w którym jedna z liczb jest równa zero – druga jest wtedy największym wspólnym dzielnikiem.

Nationalencyklopedin – największa, szwedzka encyklopedia współczesna. Jej stworzenie było możliwe dzięki kredytowi w wysokości 17 mln koron, którego udzielił rząd szwedzki w 1980 roku i który został spłacony w 1990. Drukowana wersja składa się z 20 tomów i zawiera 172 tys. haseł. Wersja internetowa zawiera 260 tys. haseł (stan z czerwca 2005). Inicjatorem projektu był rząd szwedzki, który rozpoczął negocjacje z różnymi wydawcami. Negocjacje zakończyły się w 1985, kiedy na wydawcę został wybrany Bra Böcker z Höganäs. Encyklopedia miała uwzględniać kwestie genderowe i związane z ochroną środowiska. Pierwszy tom ukazał się w 1989 roku, ostatni w 1996. Dodatkowo w roku 2000 ukazały się trzy dodatkowe tomy. Encyklopedię zamówiło 54 tys. osób. W 1997 roku ukazało się wydanie elektroniczne na CD, a w 2000 pojawiło się wydanie internetowe, które jest uzupełniane na bieżąco.Liczby naturalne – liczby służące podawaniu liczności (trzy osoby, zob. liczebnik główny/kardynalny) i ustalania kolejności (trzecia osoba, zob. liczebnik porządkowy), poddane w matematyce dalszym uogólnieniom (odpowiednio: liczby kardynalne, liczby porządkowe). Badaniem własności liczb naturalnych zajmują się arytmetyka i teoria liczb. Według finitystów, zwolenników skrajnego nurtu filozofii matematyki, są to jedyne liczby, jakimi powinna zajmować się matematyka - słynne jest stwierdzenie propagatora arytmetyzacji wszystkich dziedzin matematyki Leopolda Kroneckera: Liczby całkowite stworzył dobry Bóg. Reszta jest dziełem człowieka.

Przykład – wersja z odejmowaniem[ | edytuj kod]

Załóżmy, że chcemy znaleźć największy wspólny dzielnik liczb 1989 oraz 867. Jeżeli od większej liczby odejmiemy liczbę mniejszą, wartość największego wspólnego dzielnika nie ulegnie zmianie. Ponieważ 1989 – 867 = 1122, nowa para liczb wygląda następująco: 1122, 867

Ponownie odejmujemy mniejszą liczbę od większej 1122 – 867 = 255, tworząc w ten sposób kolejną parę:

Encyklopedia Britannica (ang. Encyclopædia Britannica) – najstarsza wydawana do chwili obecnej i najbardziej prestiżowa encyklopedia angielskojęzyczna. Artykuły w niej zamieszczane uważane są powszechnie przez czytelników za obiektywne i wiarygodne.Równanie diofantyczne (od matematyka Diofantosa) to równanie, którego rozwiązania szuka się w zbiorze liczb całkowitych lub liczb naturalnych. Zwykle rozważa się równania diofantyczne o dwóch lub więcej niewiadomych – równania z jedną niewiadomą dają się rozwiązać metodami algebraicznymi.
255, 867

867 nie jest już mniejszą liczbą. Stosując ten sam sposób, ponownie zmniejszamy wartość większej liczby o wartość mniejszej: 867 – 255 = 612, nowa para liczb to: 255, 612

Pierwsza liczba, 255, jest wciąż mniejsza, ponownie więc odejmujemy 255 od liczby większej: 612 – 255 = 357, więc kolejna para liczb to: 255, 357

357 – 255 = 102, kolejna para to:

Liczby całkowite Gaussa (liczby całkowite zespolone) to liczby zespolone, których części rzeczywiste i części urojone są liczbami całkowitymi. Formalnie, zbiór liczb całkowitych Gaussa definiuje się jako { a + b i : a , b ∈ Z ∧ i 2 = − 1 } {displaystyle {a+bi:a,bin mathbb {Z} wedge i^{2}=-1}} .Twierdzenie Sturma - twierdzenie pozwalające ustalić liczbę miejsc zerowych dowolnego wielomianu rzeczywistego w ustalonym przedziale.
255, 102

Teraz widać, że 255 jest większą liczbą, odejmujemy więc od niej 102, co daje nam parę: 153, 102

Odjęcie 102 od 153 tworzy nam kolejną parę: 51, 102.

Teraz odejmujemy 51 od 102, co daje nam: 51, 51

Ponieważ obie liczby są sobie równe, kolejne odejmowanie da nam zero. Oznacza to, że największym wspólnym dzielnikiem liczb 1989 i 867 jest liczba 51.

Euklides z Aleksandrii (gr. Εὐκλείδης, Eukleides, ur. ok. 365 r. p.n.e., zm. ok. 300 r. p.n.e.) – matematyk grecki pochodzący z Aten, przez większość życia działający w Aleksandrii.W matematyce, termin indukcja matematyczna używany jest na określenie szczególnej metody dowodzenia twierdzeń (w najbardziej typowych przypadkach o liczbach naturalnych), ale także jest on używany na oznaczenie konstrukcji pewnych obiektów.


Podstrony: 1 [2] [3] [4]




Warto wiedzieć że... beta

Ostinato (wł.) – termin muzyczny, oznaczający wielokrotne powtarzanie struktury melodycznej (także harmonicznej lub rytmicznej), najczęściej w głosie najniższym (basso ostinato).
Dziedzina Euklidesa (albo pierścień Euklidesa, pierścień euklidesowy) – w teorii pierścieni najbardziej ogólny typ pierścieni, w którym możliwe jest wyznaczenie największego wspólnego dzielnika za pomocą algorytmu Euklidesa.
Store Norske leksikon (Wielka encyklopedia norweska) - norweska encyklopedia w języku bokmål. Powstała po fuzji dwóch dużych, tworzących encyklopedie i słowniki wydawnictw norweskich Aschehoug i Gyldendal w 1978 roku, które utworzyły wydawnictwo Kunnskapsforlaget. Były cztery wydania papierowe: pierwsza w latach 1978-1981 w 12 tomach, druga w latach 1986-1989 w 15 tomach, trzecia w latach 1995-1999 w 16 tomach i czwarta w latach 2005-2007 w 16 tomach. Ostatnie wydanie zawierało 150 tys. haseł i 16 tys. ilustracji i zostało opublikowana przy wsparciu finansowym stowarzyszenia Fritt Ord. W 2010 roku ogłoszono, że nie będzie już wydań papierowych encyklopedii. Encyklopedia dostępna jest on-line od 2000 roku, a od 2009 roku może być edytowane przez użytkowników. Kunnskapsforlaget korzysta jednak z pomocy ekspertów przy sprawdzaniu treści zamieszczonych przez czytelników.
Liczba odwrotna do danej liczby x {displaystyle x;} , to taka liczba y {displaystyle y;} , że x y = 1. {displaystyle xy=1.;}
Wielka Encyklopedia Rosyjska (ros. Большая российская энциклопедия, БРЭ) – jedna z największych encyklopedii uniwersalnych w języku rosyjskim, wydana w 36 tomach w latach 2004–2017. Wydana przez spółkę wydawniczą o tej samej nazwie, pod auspicjami Rosyjskiej Akademii Nauk, na mocy dekretu prezydenckiego Władimira Putina nr 1156 z 2002 roku
Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.
Kontrola autorytatywna – w terminologii bibliotekoznawczej określenie procedur zapewniających utrzymanie w sposób konsekwentny haseł (nazw, ujednoliconych tytułów, tytułów serii i haseł przedmiotowych) w katalogach bibliotecznych przez zastosowanie wykazu autorytatywnego zwanego kartoteką wzorcową.

Reklama