| Property |
Value |
| dbo:abstract
|
- Az euklideszi algoritmus egy számelméleti algoritmus, amellyel két szám legnagyobb közös osztója határozható meg. Nevét az ókori görög matematikusról, Eukleidészről kapta, aki az Elemekben írta le (Kr. e. 300 körül). Az egyik legrégibb, gyakran használt algoritmus. Alapötlete az, hogy a legnagyobb közös osztó nem változik, ha a nagyobb számot a két szám különbségével helyettesítjük. Például 252 és 105 legnagyobb közös osztója 21, amely legnagyobb közös osztója a 105 és a 147 = 252 − 105 számoknak is. Ez a helyettesítés csökkenti a nagyobb számot, így a cserék ismétlésével egyre kisebb számokat kapunk, egészen addig, amíg a két szám egyenlővé nem válik. Ez az eddigi számpárok, így az eredeti számpár legnagyobb közös osztója. Az algoritmus lépésein visszafelé menve találunk két egész (akár negatív) tényezőt, amelyek felhasználásával a legnagyobb közös osztó kifejezhető a két kiindulási szám lineáris kombinációjaként. Ha feltesszük, hogy a kivonások és a maradékos osztások ideje körülbelül megegyezik, akkor az algoritmusnak van egy gyorsabb változata is, amely a kivonások helyett maradékos osztással működik. Ennek lényege, hogy ha a nagyobb szám sokkal nagyobb, mint a kisebb, akkor sok kivonást kell elvégezni addig, amíg a két szám szerepe felcserélődik. A maradékképzés művelete ezt a sok kivonást egy lépésben végzi el. Az algoritmus akkor ér véget, amikor a maradék nulla lesz. Ekkor a legnagyobb közös osztó éppen a kisebb szám. Ezzel az algoritmus lépésszáma a kisebb szám logaritmusával arányossá válik (sohasem nagyobb, mint a tízes számrendszerbeli jegyek számának ötszöröse). A 20. század folyamán további optimalizációt végeztek. Az algoritmusnak számos alkalmazása van. A törtek egyszerűsítése mellett a moduláris aritmetika osztás műveletének megvalósításában is szerepel. Ehhez az ax ≡ c mod b kongruenciát kell megoldani, ezt a Lineáris diofantoszi egyenletek szakasz írja le részletesebben. Használható diofantoszi egyenletek megoldására, mint amilyen például a kínai maradéktételben szereplő szimultán kongruenciarendszer. Alkalmas lánctörtbe fejtéshez és irracionális számok közelítéséhez. Végül, de nem utolsósorban számelméleti tételek bizonyításának is hasznos segédeszköze; felhasználja a négynégyzetszám-tétel és a számelmélet alaptétele. Eredetileg egész számokra és szakaszokra használták, de a 19. században általánosították Gauss-egészekre és egyváltozós polinomokra. (hu)
- Az euklideszi algoritmus egy számelméleti algoritmus, amellyel két szám legnagyobb közös osztója határozható meg. Nevét az ókori görög matematikusról, Eukleidészről kapta, aki az Elemekben írta le (Kr. e. 300 körül). Az egyik legrégibb, gyakran használt algoritmus. Alapötlete az, hogy a legnagyobb közös osztó nem változik, ha a nagyobb számot a két szám különbségével helyettesítjük. Például 252 és 105 legnagyobb közös osztója 21, amely legnagyobb közös osztója a 105 és a 147 = 252 − 105 számoknak is. Ez a helyettesítés csökkenti a nagyobb számot, így a cserék ismétlésével egyre kisebb számokat kapunk, egészen addig, amíg a két szám egyenlővé nem válik. Ez az eddigi számpárok, így az eredeti számpár legnagyobb közös osztója. Az algoritmus lépésein visszafelé menve találunk két egész (akár negatív) tényezőt, amelyek felhasználásával a legnagyobb közös osztó kifejezhető a két kiindulási szám lineáris kombinációjaként. Ha feltesszük, hogy a kivonások és a maradékos osztások ideje körülbelül megegyezik, akkor az algoritmusnak van egy gyorsabb változata is, amely a kivonások helyett maradékos osztással működik. Ennek lényege, hogy ha a nagyobb szám sokkal nagyobb, mint a kisebb, akkor sok kivonást kell elvégezni addig, amíg a két szám szerepe felcserélődik. A maradékképzés művelete ezt a sok kivonást egy lépésben végzi el. Az algoritmus akkor ér véget, amikor a maradék nulla lesz. Ekkor a legnagyobb közös osztó éppen a kisebb szám. Ezzel az algoritmus lépésszáma a kisebb szám logaritmusával arányossá válik (sohasem nagyobb, mint a tízes számrendszerbeli jegyek számának ötszöröse). A 20. század folyamán további optimalizációt végeztek. Az algoritmusnak számos alkalmazása van. A törtek egyszerűsítése mellett a moduláris aritmetika osztás műveletének megvalósításában is szerepel. Ehhez az ax ≡ c mod b kongruenciát kell megoldani, ezt a Lineáris diofantoszi egyenletek szakasz írja le részletesebben. Használható diofantoszi egyenletek megoldására, mint amilyen például a kínai maradéktételben szereplő szimultán kongruenciarendszer. Alkalmas lánctörtbe fejtéshez és irracionális számok közelítéséhez. Végül, de nem utolsósorban számelméleti tételek bizonyításának is hasznos segédeszköze; felhasználja a négynégyzetszám-tétel és a számelmélet alaptétele. Eredetileg egész számokra és szakaszokra használták, de a 19. században általánosították Gauss-egészekre és egyváltozós polinomokra. (hu)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 94565 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| prop-hu:author2Link
|
- Carl Pomerance (hu)
- Carl Pomerance (hu)
|
| prop-hu:authorLink
|
- Harold Stark (hu)
- Henri Cohen (hu)
- John Stillwell (hu)
- Manfred R. Schroeder (hu)
- Peter Gustav Lejeune Dirichlet (hu)
- William J. LeVeque (hu)
- Øystein Ore (hu)
- Harold Stark (hu)
- Henri Cohen (hu)
- John Stillwell (hu)
- Manfred R. Schroeder (hu)
- Peter Gustav Lejeune Dirichlet (hu)
- William J. LeVeque (hu)
- Øystein Ore (hu)
|
| prop-hu:authorlink
|
- Donald Knuth (hu)
- Donald Knuth (hu)
|
| prop-hu:edition
|
- 2 (xsd:integer)
- 4 (xsd:integer)
- 1.0
- 3.0
|
| prop-hu:editorFirst
|
- Richard (hu)
- Richard (hu)
|
| prop-hu:editorLast
|
- Dedekind (hu)
- Dedekind (hu)
|
| prop-hu:editorLink
|
- Richard Dedekind (hu)
- Richard Dedekind (hu)
|
| prop-hu:first
|
- H. (hu)
- M. (hu)
- C. (hu)
- J. (hu)
- D. (hu)
- P. G. (hu)
- R. (hu)
- O. (hu)
- R. A. (hu)
- W. J. (hu)
- D. E. (hu)
- J. J. (hu)
- K. H. (hu)
- H. (hu)
- M. (hu)
- C. (hu)
- J. (hu)
- D. (hu)
- P. G. (hu)
- R. (hu)
- O. (hu)
- R. A. (hu)
- W. J. (hu)
- D. E. (hu)
- J. J. (hu)
- K. H. (hu)
|
| prop-hu:isbn
|
- 0 (xsd:integer)
- 978 (xsd:integer)
|
| prop-hu:language
| |
| prop-hu:last
|
- Cohen (hu)
- O'Shea (hu)
- Stark (hu)
- Cox (hu)
- Little (hu)
- Pomerance (hu)
- Knuth (hu)
- Schroeder (hu)
- Stillwell (hu)
- Cohn (hu)
- Crandall (hu)
- LeVeque (hu)
- Lejeune Dirichlet (hu)
- Mollin (hu)
- Ore (hu)
- Rosen (hu)
- Tattersall (hu)
- Cohen (hu)
- O'Shea (hu)
- Stark (hu)
- Cox (hu)
- Little (hu)
- Pomerance (hu)
- Knuth (hu)
- Schroeder (hu)
- Stillwell (hu)
- Cohn (hu)
- Crandall (hu)
- LeVeque (hu)
- Lejeune Dirichlet (hu)
- Mollin (hu)
- Ore (hu)
- Rosen (hu)
- Tattersall (hu)
|
| prop-hu:lccn
| |
| prop-hu:location
|
- New York (hu)
- Cambridge (hu)
- Braunschweig (hu)
- Boca Raton (hu)
- Reading, MA (hu)
- New York (hu)
- Cambridge (hu)
- Braunschweig (hu)
- Boca Raton (hu)
- Reading, MA (hu)
|
| prop-hu:oclc
| |
| prop-hu:origyear
| |
| prop-hu:publisher
| |
| prop-hu:ref
| |
| prop-hu:title
|
- Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (hu)
- A Course in Computational Algebraic Number Theory (hu)
- Advanced Number Theory (hu)
- An Introduction to Number Theory (hu)
- Elementary Number Theory and its Applications (hu)
- Elementary Number Theory in Nine Chapters (hu)
- Elements of Number Theory (hu)
- Fundamental Number Theory with Applications (hu)
- Fundamentals of Number Theory (hu)
- Number Theory and Its History (hu)
- Number Theory in Science and Communication (hu)
- Numbers and Geometry (hu)
- Prime Numbers: A Computational Perspective (hu)
- Vorlesungen über Zahlentheorie (hu)
- The Art of Computer Programming, Volume 2: Seminumerical Algorithms (hu)
- Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (hu)
- A Course in Computational Algebraic Number Theory (hu)
- Advanced Number Theory (hu)
- An Introduction to Number Theory (hu)
- Elementary Number Theory and its Applications (hu)
- Elementary Number Theory in Nine Chapters (hu)
- Elements of Number Theory (hu)
- Fundamental Number Theory with Applications (hu)
- Fundamentals of Number Theory (hu)
- Number Theory and Its History (hu)
- Number Theory in Science and Communication (hu)
- Numbers and Geometry (hu)
- Prime Numbers: A Computational Perspective (hu)
- Vorlesungen über Zahlentheorie (hu)
- The Art of Computer Programming, Volume 2: Seminumerical Algorithms (hu)
|
| prop-hu:url
| |
| prop-hu:wikiPageUsesTemplate
| |
| prop-hu:year
|
- 1894 (xsd:integer)
- 1948 (xsd:integer)
- 1962 (xsd:integer)
- 1978 (xsd:integer)
- 1993 (xsd:integer)
- 1996 (xsd:integer)
- 1997 (xsd:integer)
- 2000 (xsd:integer)
- 2001 (xsd:integer)
- 2003 (xsd:integer)
- 2005 (xsd:integer)
- 2008 (xsd:integer)
|
| dct:subject
| |
| rdfs:label
|
- Euklideszi algoritmus (hu)
- Euklideszi algoritmus (hu)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is foaf:primaryTopic
of | |
