Algoritmo

Algoritmo estas metodo aŭ programo 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.

Sovetia poŝtmarko okaze de la 1200-jariĝo de 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

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. Al-Ĥorezmi (arabigite perse الخوارزمی ĉirkaŭ 780–850) estis matematikisto, astronomo, geografo, kaj saĝulo en la Hejmo de Saĝeco en Bagdado, kies nomo signifas 'lokano de Ĥorezmo', regiono kiu estis parto de Granda Irano kaj estas nune en Uzbekio. Ĉ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. Al-Ĥorezmi estis la plej amplekse legata matematikisto en Eŭropo fine de la Mezepoko, ĉefe tra alia el liaj libroj, nome Al-Ĝabr aŭ Algebro. En malfrumezepoka Latino, algorismus, nome 'algorismo', korupto de lia nomo, simple signifis "dekuma nombrosistemo". 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.

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.

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

	„ Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris. ”

tradukeble al:

	„ 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.

Historio: Disvolvigo de la nocio de "algoritmo"

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

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. Dum la Hamurabia dinastio ĉirkaŭ 1800-1600 a.n.e., la babilonaj argilaj tabuletoj priskribis algoritmojn por kalkulaj formuloj. 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.

Algoritmoj por aritmetiko troveblas ankaŭ en matematiko de Antikva Egipto, date el la Papiruso de Rhind ĉirkaŭ 1550 a.n.e. 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, kaj la Eŭklida algoritmo, kiu estis por la unua fojo priskribita en la Elementoj de Eŭklido (ĉirkaŭ 300 a.n.e.).

Apartaj kaj distingeblaj simboloj

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. 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

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. Tio finfine rezultis en la nocio de Leibniz pri calculus ratiocinator (ĉirkaŭ 1680):

	„ 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. ”

Kriptografiaj algoritmoj

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.

Flu-diagramo povas priskribi algoritmon

Tipoj

En komputiko, ordiga algoritmo aù algoritmo 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

• Algoritmo de Bresenham
• Algoritmo de Coppersmith-Winograd
• Algoritmo de Eŭklido
• Algoritmo de Karacuba
• Algoritmo de Luhn
• Algoritmo de multiplikado
• Algoritmo de Nagle
• Algoritmo de Strassen
• Algoritmo de Toom-Cook

Literaturo

• Axt, P (1959). "On a Subrecursive Hierarchy and Primitive Recursive Degrees". Transactions of the American Mathematical Society. 92 (1): 85–105. doi:10.2307/1993169. JSTOR 1993169.
• Bell, C. Gordon kaj Newell, Allen (1971), Computer Structures: Readings and Examples, McGraw–Hill Book Company, New York. ISBN 0-07-004357-4.
• Bellah, Robert Neelly (1985). Habits of the Heart: Individualism and Commitment in American Life. Berkeley: University of California Press. ISBN 978-0-520-25419-0.
• Berlinski, David (2001). The Advent of the Algorithm: The 300-Year Journey from an Idea to the Computer. Harvest Books. ISBN 978-0-15-601391-8.
• Blass, Andreas; Gurevich, Yuri (2003). "Algorithms: A Quest for Absolute Definitions" (PDF). Bulletin of European Association for Theoretical Computer Science. 81. Arkivita (PDF) el la originalo la 9an de Oktobro, 2022. Inkludas bibliografion de 56 referencoj.
• Bleakley, Chris (2020). Poems that Solve Puzzles: The History and Science of Algorithms. Oxford University Press. ISBN 978-0-19-885373-2.
• Bolter, David J. (1984). Turing's Man: Western Culture in the Computer Age (eldono de 1984). Chapel Hill, NC: The University of North Carolina Press. ISBN 978-0-8078-1564-9., ISBN 0-8078-4108-0
• Boolos, George; Jeffrey, Richard (1999) [1974]. Computability and Logic (4a eld.). Cambridge University Press, London. ISBN 978-0-521-20402-6.
• Burgin, Mark (2004). Super-Recursive Algorithms. Springer. ISBN 978-0-387-95569-8.
• Campagnolo, M.L., Moore, C., kaj Costa, J.F. (2000) An analog characterization of the subrecursive functions. En Proc. of the 4th Conference on Real Numbers and Computers, Odense University, pp. 91–109
• Chabert, Jean-Luc (1999). A History of Algorithms: From the Pebble to the Microchip. Springer Verlag. ISBN 978-3-540-63369-3.
• Church, Alonzo (1936). "An Unsolvable Problem of Elementary Number Theory". American Journal of Mathematics. 58 (2): 345–363. doi:10.2307/2371045. JSTOR 2371045. Represita en The Undecidable, p. 89ff. The first expression of "Church's Thesis". See in particular page 100 (The Undecidable) where he defines the notion of "effective calculability" in terms of "an algorithm", and he uses the word "terminates", etc.
• Church, Alonzo (1936). "A Note on the Entscheidungsproblem". The Journal of Symbolic Logic. 1 (1): 40–41. doi:10.2307/2269326. JSTOR 2269326. S2CID 42323521. Church, Alonzo (1936). "Correction to a Note on the Entscheidungsproblem". The Journal of Symbolic Logic. 1 (3): 101–102. doi:10.2307/2269030. JSTOR 2269030. S2CID 5557237. Represita en The Undecidable, p. 110ff. Church shows that the Entscheidungsproblem is unsolvable in about 3 pages of text and 3 pages of footnotes.
• Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction To Algorithms (Tria eldono). MIT Press. ISBN 978-0-262-03384-8.
• Daffa', Ali Abdullah al- (1977). The Muslim contribution to mathematics. London: Croom Helm. ISBN 978-0-85664-464-1.
• Davis, Martin. (1965) The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions. New York: Raven Press. ISBN 978-0-486-43228-1.

• 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. 

• Dennett, Daniel. (1995) Darwin's Dangerous Idea 2. New York: Touchstone/Simon & Schuster, p. [htt://archive.org/details/darwinsdangerous0000denn/e/32 32]–36. doi:<32::AID-CPLX8>3.0.CO;2-H 10.1002/(SICI)1099-0526(199609/10)2:1<32::AID-CPLX8>3.0.CO;2-H. ISBN 978-0-684-80290-9.

• 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). 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ŭ

• Al-Ĥorezmi
• Algorismo
• Alonzo Church
• Interreta serĉilo
• Stephen Kleene
• Donald Knuth
• Plenumebla dosiero
• Problemo de halto
• Pseŭdokodo
• Rapida ordigo

• Serĉilo-optimumigo

Eksteraj ligiloj

• Vortaro de algoritmoj kaj datenstrukturoj
• Manlibro de algoritmoj kaj datenstrukturoj
• Ekzemploj de algoritmoj en diversaj programlingvoj Arkivigite je 2019-05-28 per la retarkivo Wayback Machine
• "Nombraj receptoj", algoritmoj de la komputa matematiko Arkivigite je 2008-05-16 per la retarkivo Wayback Machine