Saltu al enhavo

Algoritmo

El Vikipedio, la libera enciklopedio
Sovetia poŝtmarko okaze de la 1200-jariĝo de Al-Ĥorezmi.

Algoritmo estas metodoprogramo por solvi komputajn aŭ aliajn problemojn, kiu ĝuste difinas, kiel kaj en kia (vic)ordo procedi por ricevi rezulton senambigue determinitan de originaj datumoj. Ekz. por la konataj reguloj de adicio, subtraho, multipliko kaj divido la eblaj rezultatoj estas naturaj nombroj prezentitaj ekzemple en dekuma sistemo, kaj eblaj originaj datumoj estas ordigitaj paroj de samspecaj nombroj. La vorto algoritmo estas ŝanĝita formo de la nomo de la persa matematikisto Al-Ĥorezmi.

Ĝenerale, oni ne supozas ke ia rezulto nepre devas esti ricevita: la algoritma procezo povas interrompiĝi aŭ ne finiĝi iam. Algoritma procezo estas la agoj por sinsekvaj transformoj de konstruktaj objektoj, okazantaj per diskretaj paŝoj. Ĉiu paŝo konsideras la ŝanĝon de unu konstruita objekto per la alia. Oni skribas ĉi tiujn paŝojn matematike per t. n. algoritma lingvo, kiu konsistas en komandoj, instrukcioj aŭ operatoroj plenumendaj sinsekve per elementaj operacioj. Laŭ la stirfluo de plenumado de algoritma aplikaĵo ĉiu paŝo estas plenumo de simpla instrukcio.

Kun tiu ĉi difino ne konsentus multaj informadikistoj, kiuj insistas, ke taŭge formulita algoritmo devas garantii iaman finon. Iusenca escepto estas ekzemple mastrumaj programoj (operaciumoj), kiuj normale ne finiĝas; por ili Donald Knuth proponis la nomon "komputika metodo", por distingi ilin de algoritmoj.

Mem la vorto devenas de Algorithmi, algorismus, kiu originas de latina transliterado de la nomo de mezazia matematikisto Al-Ĥorezmi. En mezepoka Eŭropo algoritmo nomiĝis la dekuma pozicia sistemo kaj la arto kalkuli per ĝi, ĉar danke al latina traduko de la traktato de Al-Ĥorezmi (en la 12-a jarcento) la eŭropa matematiko konatiĝis kun pozicia sistemo.

Algoritmo estas unu el ĉefaj nocioj de matematiko kaj cibernetiko. Ĝin pristudas unu el la matematikaj branĉoj: Teorio de Algoritmoj. En komputada teknologio por priskribi algoritmojn, oni uzas programlingvojn.

La termino "algoritmo" kutime implicas relative abstraktan matematikan prezenton, kontraste al komputopreta, sed ofte komputildependa "programo".

Etimologio

[redakti | redakti fonton]

La vorto 'algoritmo' havas sian devenon el latinigo de la prinoma "nisba", kiu indikas la geografian devenon, de la nomo de la persa matematikisto Muhammad ibn Musa al-Ĥorezmi al algorismus.[1][2] Al-Ĥorezmi (arabigite perse الخوارزمی ĉirkaŭ 780–850) estis matematikisto, astronomo, geografo, kaj saĝulo en la Hejmo de Saĝeco en Bagdado,[3] kies nomo signifas 'lokano de Ĥorezmo', regiono kiu estis parto de Granda Irano kaj estas nune en Uzbekio.[4][5] Ĉirkaŭ la jaro 825, Al-Ĥorezmi verkis arablingvan traktaĵon pri la Hind–araba nombrosistemo, kiu estis tradukita en Latinon dum la 12-a jarcento. La manuskripto elstartas per la frazo latine Dixit Algorizmi ('Tion diris Al-Ĥorezmi'), kie "Algorizmi" estis la latinigo de la nomo de Al-Ĥorezmi fare de la tradukisto.[6] Al-Ĥorezmi estis la plej amplekse legata matematikisto en Eŭropo fine de la Mezepoko, ĉefe tra alia el liaj libroj, nome Al-ĜabrAlgebro.[7] En malfrumezepoka Latino, algorismus, nome 'algorismo', korupto de lia nomo, simple signifis "dekuma nombrosistemo".[8] En la 15-a jarcento, sub la influo de la greka vorto ἀριθμός (arithmos), 'nombro' (cf. 'aritmetiko'), la latina vorto estis ŝanĝita al algorithmus, kaj la koresponda moderna termino 'algoritmo' estis por la unua fojo registrita en angla en la 17-a jarcento; la moderna senco estis enkondukita en la 19-a jarcento.[9]

En la angla, ĝi estis por la unua fojo uzata ĉirkaŭ 1230 kaj poste fare de Chaucer en 1391. La angla fakte adoptis la franclingvan terminon, sed nur fine de la 19-a jarcento "algoritmo" ekhavis la signifon kiun ĝi havas nuntempe.[10]

Alia frua uzo de la vorto estis el 1240, en manlibro titolita Carmen de Algorismo komponita de Alexandre de Villedieu. Ĝi estis tia:

Citaĵo
 Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris. 

tradukeble al:

Citaĵo
 Algorismo estas arto per kiu nune ni uzas tiujn hindiajn ciferojn, kiuj nombras du fojojn kvin. 

La poemo enhavas kelkajn centojn da liniojn kaj resumas la arton kalkuli per la novstila hindia sistemo (Tali Indorum), aŭ Hinduaj numeraloj.[11]

Historio: Disvolvigo de la nocio de "algoritmo"

[redakti | redakti fonton]
Argila tabuleto, pri matematiko, geometrio kaj algebro, simila al la Pitagora teoremo. El Tell al-Dhabba, Irako. 2003-1595 a.n.e. Iraka Muzeo

Antikva Proksima Oriento

[redakti | redakti fonton]

La plej fruaj pruvoj de algoritmoj estis trovitaj en la babilona matematiko de antikva Mezopotamio (nuntempa Irako). Argila tabuleto el Sumero trovita en Ŝuruppak apud Bagdado kaj datita de ĉirkaŭ 2500 a.n.e. priskribas la plej fruan dividan algoritmon.[12] Dum la Hamurabia dinastio ĉirkaŭ 1800-1600 a.n.e., la babilonaj argilaj tabuletoj priskribis algoritmojn por kalkulaj formuloj.[13] Algoritmoj estis uzataj ankaŭ en la babilona astronomio. Babilonaj argilaj tabuletoj priskribis kaj uzis algoritmajn procedurojn por kalkuli la tempon kaj lokon de gravaj astronomiaj eventoj.[14]

Algoritmoj por aritmetiko troveblas ankaŭ en matematiko de Antikva Egipto, date el la Papiruso de Rhind ĉirkaŭ 1550 a.n.e.[12] Algoritmoj estis uzitaj poste en matematiko de Helenisma Epoko. Du ekzemploj estas la Kribrilo de Eratosteno, kiu estis priskribita en Arithmetike eisagoge (Enkonduko al aritmetiko) de Nikomaĥo de Gerasa,[15][16]:Ch 9.2 kaj la Eŭklida algoritmo, kiu estis por la unua fojo priskribita en la Elementoj de Eŭklido (ĉirkaŭ 300 a.n.e.).[16]:Ch 9.1

Apartaj kaj distingeblaj simboloj

[redakti | redakti fonton]

Kalkulmarkoj: Por kaluklregistri siajn brutarojn, siajn grensakojn kaj sian monon la antikvuloj uzis kalkulmarkojn: akumulado de ŝtonetoj aŭ markoj strekitaj sur bastonetoj aŭ farado de apartaj simboloj en argilo. Tra la babilona kaj la egipta uzado de markoj kaj simboloj, finfine la Romaj ciferoj kaj la abako evoluis.[17] Kalkulmarkoj aperis elstare en la aritmetiko de unuara nombrosistemo uzata en la Maŝino de Turing kaj en la komputado de Post–Maŝino de Turing.

Manipulado de simboloj kiel "lokomarkoj" por nombroj: algebro

[redakti | redakti fonton]

Muhammad ibn Musa Al-Ĥorezmi, nome persa matematikisto, verkis Al-ĝabr en la 9-a jarcento. La terminoj "algorismo" kaj "algoritmo" deriviĝis el la nomo de Al-Ĥorezmi, dum la termino "algebro" deriviĝis el la libro Al-ĝabr. En Eŭropo, la vorto "algoritmo" estis origine uzata por referenci al la serio de reguloj kaj teknikoj uzitaj de Al-Ĥorezmi por solvi algebrajn ekvaciojn, antaŭ posta ĝeneraligo por referenci al ajna serio de reguloj kaj teknikoj.[18] Tio finfine rezultis en la nocio de Leibniz pri calculus ratiocinator (ĉirkaŭ 1680):

Citaĵo
 Unu jarcenton kaj duonon post lia epoko, Leibniz proponis algebron de logiko, algebron kiu specifu la regulojn por manipuladi logikajn konceptojn en la maniero kiel ordinara algebro specifas la regulojn por manipuladi nombrojn.[19] 

Kriptografiaj algoritmoj

[redakti | redakti fonton]

La unua kriptografia algoritmo por deĉifri ĉifritan kodon estis disvolvigita de Al-Kindi, araba matematikisto de la 9-a jarcento en Manuskripto por deĉifri kriptografiajn mesaĝojn. Li faris la unuan priskribon de ĉifranalizo pere de analizo de frekvenco, nome la plej frua deĉifra algoritmo.[20]

Flu-diagramo povas priskribi algoritmon

En komputiko, ordiga algoritmoalgoritmo de ordigo, estas algoritmo kiu metas elementojn de listo en ordo. La plej ofte uzataj ordoj estas nombra ordo kaj leksikografia ordo, kaj aŭ ascenda aŭ malkreska. Efika ordigo estas grava por optimumigado de la efikeco de aliaj algoritmoj (kiel ekzemple serĉo kaj kunfandi algoritmoj) kiuj postulas enigdatenojn esti en ordigitaj listoj.


Pli detalaj informoj troveblas en artikolo Algoritmo de multiplikado.

En matematiko, multiplika algoritmo estas algoritmo (aŭ maniero) por multipliki du nombroj. Se pozicia cifereca sistemo estas uzata, natura vojo de multiplikado de nombroj estas instruata en lernejoj kiel longa multipliko: multipliki la unuan multiplikaton per ĉiu cifero de la alia multiplikanto kaj tiam adicii ĉiujn propre ŝovitajn rezultojn. Ĝi postulas memorigon de la multiplika tabelo por solaj ciferoj. Ĉi tiu estas la kutima algoritmo por multiplikante permane en bazo 10. Komputiloj normale uzas tre similan ŝovan kaj adician algoritmon en bazo 2. La algoritmo funkcias kun nenegativaj entjeroj. En la aliaj okazoj, la signumojn kaj la poziciojn de la dekumaj komoj estas konsideritaj aparte, kaj post la longa multipliko aplikiĝas al la rezulto.

Kelkaj algoritmoj

[redakti | redakti fonton]

Referencoj

[redakti | redakti fonton]
  1. Al-Khwarizmi biography. Arkivita el la originalo je 2a de Aŭgusto, 2019. Alirita 3a de Majo, 2017 .
  2. Etymology of algorithm. Arkivita el la originalo je 31a de Marto, 2019. Alirita December 13, 2016 .
  3. "Hellenistic Mathematics". The Story of Mathematics. Arkivita el la originalo la 11an de Septembro, 2019. Alirita la 14an de Novembro, 2019.
  4. (1998) “al-Khwarzimi”, Pythagoras 38 (2), p. 4–5.  Arkivigite je 2008-03-19 per la retarkivo Wayback Machine
  5. . Was al-Khwarizmi an applied algebraist?. University of Indianapolis. Arkivita el la originalo je 18a de Julio, 2011. Alirita 30a de Majo, 2008 . Arkivita kopio. Arkivita el la originalo je 2011-07-18. Alirita 2021-08-08 .
  6. Brezina, Corona. (2006) Al-Khwarizmi: The Inventor Of Algebra. The Rosen Publishing Group. ISBN 978-1-4042-0513-0.
  7. Foremost mathematical texts in history Arkivigite je 2019-10-31 per la retarkivo Wayback Machine, laŭ Carl B. Boyer.
  8. "algorismic", The Free Dictionary, https://www.thefreedictionary.com/algorismic, retrieved 2019-11-14 
  9. Oxford English Dictionary, Tria Eldono, 2012 s.v.
  10. (2017) “From Al-Khwarizmi to Algorithm”, Olympiads in Informatics 11 (2), p. 71–74. doi:10.15388/ioi.2017.special.11. 
  11. Abu Jafar Muhammad ibn Musa al-Khwarizmi. Arkivita el la originalo je 21a de Aŭgusto, 2019. Alirita 2019-11-14 .
  12. 12,0 12,1 Chabert, Jean-Luc. (2012) A History of Algorithms: From the Pebble to the Microchip. Springer Science & Business Media, p. 7–8. ISBN 9783642181924.
  13. (1972) “Ancient Babylonian Algorithms”, Commun. ACM 15 (7), p. 671–677. doi:10.1145/361454.361514. 7829945.  Arkivigite je 2016-12-20 per la retarkivo Wayback Machine Arkivita kopio. Arkivita el la originalo je 2016-12-20. Alirita 2021-08-08 .
  14. Aaboe, Asger (2001), Episodes from the Early History of Astronomy, New York: Springer, pp. 40–62, (ISBN 978-0-387-95136-2) 
  15. . Eratosthenes. Wichita State University: Department of Mathematics and Statistics. Arkivita el la originalo je 27a de Februaro, 2015. Alirita 27a de Februaro, 2015 .
  16. 16,0 16,1 Cooke, Roger L. (2005). The History of Mathematics: A Brief Course. John Wiley & Sons. ISBN 978-1-118-46029-0.
  17. (Dilson, p. 16–41).
  18. Chabert, Jean-Luc. (2012) A History of Algorithms: From the Pebble to the Microchip. Springer Science & Business Media. ISBN 9783642181924.
  19. Davis 2000:18
  20. Dooley, John F.. (2013) A Brief History of Cryptology and Cryptographic Algorithms. Springer Science & Business Media, p. 12–3. ISBN 9783319016283.

Literaturo

[redakti | redakti fonton]
  • Davis, Martin. (2000) Engines of Logic: Mathematicians and the Origin of the Computer. Nov-Jorko: W.W. Nortion. ISBN 978-0-393-32229-3.
  • Dean, Tim (2012). “Evolution and moral diversity”, Baltic International Yearbook of Cognition, Logic and Communication 7. doi:10.4148/biyclc.v7i0.1775. 
  • Dilson, Jesse. (2007) The Abacus, 19681994‑a eldono, St. Martin's Press, NY. ISBN 978-0-312-10409-2., (ISBN 0-312-10409-X)
  • Yuri Gurevich, Sequential Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, Vol 1, no 1 (Julio 2000), pp. 77–111. Inkludas bibliografion de 33 fontoj.
  • Harel, David; Feldman, Yishai (2004). Algorithmics: The Spirit of Computing. Addison-Wesley. ISBN 978-0-321-11784-7.
  • van Heijenoort, Jean (2001). From Frege to Gödel, A Source Book in Mathematical Logic, 1879–1931 ((1967) ed.). Harvard University Press, Cambridge. ISBN 978-0-674-32449-7., Tria eldono 1976[?], ISBN 0-674-32449-8 (pbk.)
  • Hertzke, Allen D.; McRorie, Chris (1998). "The Concept of Moral Ecology". En Lawler, Peter Augustine; McConkey, Dale (eld.). Community and Political Thought Today. Westport, CT: Praeger.
  • Hodges, Andrew (1983). Alan Turing: The Enigma. New York: Simon and Schuster. ISBN 978-0-671-49207-6., ISBN 0-671-49207-1. Cf. Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
  • Kleene, Stephen C. (1936). "General Recursive Functions of Natural Numbers". Mathematische Annalen. 112 (5): 727–742. doi:10.1007/BF01565439. S2CID 120517999. Arkivita el la originalo la 3an de Septembro, 2014. Alirita la 30an de Septembro, 2013. Prezentita al la American Mathematical Society, Septembre 1935. Represita en The Undecidable, p. 237ff. Kleene's definition of "general recursion" (known now as mu-recursion) was used by Church in his 1935 paper An Unsolvable Problem of Elementary Number Theory that proved the "decision problem" to be "undecidable" (i.e., a negative result).
  • Kleene, Stephen C. (1943). "Recursive Predicates and Quantifiers". Transactions of the American Mathematical Society. 53 (1): 41–73. doi:10.2307/1990131. JSTOR 1990131. Represita en The Undecidable, p. 255ff. Kleene refined his definition of "general recursion" and proceeded in his chapter "12. Algorithmic theories" to posit "Thesis I" (p. 274); he would later repeat this thesis (in Kleene 1952:300) and name it "Church's Thesis"(Kleene 1952:317) (i.e., the Church thesis).
  • Kleene, Stephen C. (1991) [1952]. Introduction to Metamathematics (Deka eldono). North-Holland Publishing Company. ISBN 978-0-7204-2103-3.
  • Knuth, Donald (1997). Fundamental Algorithms, Tria eldono. Reading, Massachusetts: Addison–Wesley. ISBN 978-0-201-89683-1.
  • Knuth, Donald (1969). Volume 2/Seminumerical Algorithms, The Art of Computer Programming, Unua eldono. Reading, Massachusetts: Addison–Wesley.
  • Knuth, Donald E. (2000). Selected Papers on Analysis of Algorithms, Arkivita la 1an de Julio, 2017, en Wayback Machine. Stanford, California: Center for the Study of Language and Information.
  • Knuth, Donald E. (2010). Selected Papers on Design of Algorithms, Arkivita la 16an de Julio, 2017, en Wayback Machine. Stanford, California: Center for the Study of Language and Information.
  • Kosovsky, N.K. Elements of Mathematical Logic and its Application to the theory of Subrecursive Algorithms, LSU Publ., Leningrad, 1981
  • Kowalski, Robert (1979). "Algorithm=Logic+Control". Communications of the ACM. 22 (7): 424–436. doi:10.1145/359131.359136. S2CID 2509896.
  • A.A. Markov (1954) Theory of algorithms. [Tradukita de Jacques J. Schorr-Kon kaj PST staff] Presita en Moskvo, Akademio de Sciencoj de Sovetunio, 1954 [t.e., Jerusalemo, Israela Programo por Sciencaj Tradukoj, 1961; disponebla el la Oficejo de Teknikaj Servoj, U.S. Dept. of Commerce, Washington] Priskribo 444 p. 28 cm. Aldonita en la rusa traduko de Works of the Mathematical Institute, Akademio de Sciencoj de Sovetunio, v. 42. Originala titolo: Teoriya algerifmov. [QA248.M2943 Dartmouth College library. U.S. Dept. of Commerce, Office of Technical Services, number OTS 60-51085.]
  • Minsky, Marvin (1967). Computation: Finite and Infinite Machines (Unua eldono). Prentice-Hall, Englewood Cliffs, NJ. ISBN 978-0-13-165449-5. Minsky expands his "...idea of an algorithm – an effective procedure..." en la ĉapitro 5.1 Computability, Effective Procedures and Algorithms. Infinite machines.
  • Post, Emil (1936). "Finite Combinatory Processes, Formulation I". The Journal of Symbolic Logic. 1 (3): 103–105. doi:10.2307/2269031. JSTOR 2269031. S2CID 40284503. Represita en The Undecidable, pp. 289ff. Post defines a simple algorithmic-like process of a man writing marks or erasing marks and going from box to box and eventually halting, as he follows a list of simple instructions. This is cited by Kleene as one source of his "Thesis I", the so-called Church–Turing thesis.
  • Rogers, Hartley Jr. (1987). Theory of Recursive Functions and Effective Computability. The MIT Press. ISBN 978-0-262-68052-3.
  • Rosser, J.B. (1939). "An Informal Exposition of Proofs of Godel's Theorem and Church's Theorem". Journal of Symbolic Logic. 4 (2): 53–60. doi:10.2307/2269059. JSTOR 2269059. S2CID 39499392. Represita en The Undecidable, p. 223ff.Tie estas la fama difino de Rosser pri "effective method": "...a method each step of which is precisely predetermined and which is certain to produce the answer in a finite number of steps... a machine which will then solve any problem of the set with no human intervention beyond inserting the question and (later) reading the answer" (pp. 225–226, The Undecidable)
  • Santos-Lang, Christopher (2015). "Moral Ecology Approaches to Machine Ethics" (PDF). Arkivigite je 2015-02-08 per la retarkivo Wayback Machine En van Rysewyk, Simon; Pontier, Matthijs (eld.). Machine Medical Ethics. Intelligent Systems, Control and Automation: Science and Engineering. Vol. 74. Switzerland: Springer. pp. 111–127. doi:10.1007/978-3-319-08108-3_8. ISBN 978-3-319-08107-6. Arkivita (PDF) el la originalo la 9an de Oktobro, 2022.
  • Scott, Michael L. (2009). Programming Language Pragmatics (Tria eldono). Morgan Kaufmann Publishers/Elsevier. ISBN 978-0-12-374514-9.
  • Sipser, Michael (2006). [1] Introduction to the Theory of Computation. PWS Publishing Company. ISBN 978-0-534-94728-6.
  • Sober, Elliott; Wilson, David Sloan (1998). Unto Others: The Evolution and Psychology of Unselfish Behavior. Cambridge: Harvard University Press. ISBN 9780674930469.
  • Stone, Harold S. (1972). Introduction to Computer Organization and Data Structures (1972 ed.). McGraw-Hill, New York. ISBN 978-0-07-061726-1. Cf. aparte la unua ĉapitro titolita: Algorithms, Turing Machines, and Programs. Lia mallonga neformala difino estas jena: "...any sequence of instructions that can be obeyed by a robot, is called an algorithm" (p. 4).
  • Tausworthe, Robert C (1977). Standardized Development of Computer Software, Parto 1a Methods. Englewood Cliffs NJ: Prentice–Hall, Inc. ISBN 978-0-13-842195-3.
  • Turing, Alan M. (1936–37). "On Computable Numbers, With An Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. Series 2. 42: 230–265. doi:10.1112/plms/s2-42.1.230. S2CID 73712.. Corrections, ibid, vol. 43(1937) pp. 544–546. Represita en The Undecidable, p. 116ff. Turing's famous paper completed as a Master's dissertation while at King's College Cambridge UK.
  • Turing, Alan M. (1939). "Systems of Logic Based on Ordinals". Proceedings of the London Mathematical Society. 45: 161–228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3. Represita en The Undecidable, pp. 155ff. La artikolo de Turing kiu difinis "the oracle" estis sia doktoriga disertacio estante en Princeton.
  • United States Patent and Trademark Office (2006), 2106.02 **>Mathematical Algorithms: 2100 Patentability, Manual of Patent Examining Procedure (MPEP). Lasta revizio en Aŭgusto 2006
  • Wallach, Wendell; Allen, Colin (Novembro 2008). Moral Machines: Teaching Robots Right from Wrong. US: Oxford University Press. ISBN 978-0-19-537404-9.
  • Zaslavsky, C. (1970). Mathematics of the Yoruba People and of Their Neighbors in Southern Nigeria. The Two-Year College Mathematics Journal, 1(2), 76–99. https://doi.org/10.2307/3027363

Vidu ankaŭ

[redakti | redakti fonton]

Eksteraj ligiloj

[redakti | redakti fonton]