Algorithm
Wɔ nkontaabu ne kɔmputa ho nyansahu mu no, algorithm (/ˈælɡərɪðəm/ (tie)) yɛ akwankyerɛ a ɛyɛ katewa a ɛtoatoa so a anohyeto wom, a wɔtaa de di ɔhaw pɔtee bi ho dwuma anaasɛ wɔde yɛ nkontaabu.[1] Wɔde algorithms di dwuma sɛ nkyerɛkyerɛmu a wɔde yɛ akontaabu ne data ho dwumadie. Algorithm a akɔ anim kɛseɛ betumi de tebea mu nneɛma adi dwuma de adan mmara no a wɔde di dwuma no afa akwan hodoɔ so (a wɔfrɛ no gyinaesi a wɔde wɔn ankasa yɛ) na wɔasusuw nsusuiiɛ a ɛfata (a wɔfrɛ no nsusuiiɛ a wɔde wɔn ankasa yɛ ho), na awieɛ koraa no wɔanya afiri a wɔde di dwuma. Nnipa su a wɔde bedi dwuma sɛ mfiri ho nkyerɛkyerɛmufoɔ wɔ kasakoa akwan so no, Alan Turing de nsɛmfua te sɛ "nkaeɛ", "nhwehwɛeɛ" ne "nkanyan" de di dwuma dedaw.[2]
Nea ɛne yi ɛbɔ abira no, 'heuristic' yɛ ɔkwan a wɔfa so siesie ɔhaw ahodoɔ a ebia wɔankyerɛkyerɛ mu yiye anaasɛ ebia ɛnyɛ nea ɛbɛma wɔanya nea ɛteɛ anaa nea ɛyɛ sen bibibiara, titiriw wɔ ɔhaw ahodoɔ mu a nea efi mu ba a ɛteɛ anaa nea ɛyɛ sen biara nni hɔ a wɔakyerɛkyerɛ mu yiye.[3]
Sɛ ɔkwan a etu mpɔn no, wobetumi ada algorithm adi wɔ ahunmu ne berɛ a anohyeto wom mu,[4] ne kasa a wɔakyerɛkyerɛ mu yiye a wɔde di dwuma wɔ ɔkwan a ɛfata so[5] a wɔde bu dwumadie bi ho nkontaa.[6] Sɛ yɛfiri aseɛ firi mfitiaseɛ tebea ne mfitiaseɛ nsɛm a wɔde hyɛ mu (ebia ɛda mpan),[7] akwankyerɛ no kyerɛkyerɛ akontabuo bi a, sɛ wɔyɛ a, ɛkɔ so fa tebea a ɛtoatoa soɔ a wɔakyerɛkyerɛ mu yie dodoɔ a ɛwɔ anohyetoɔ mu[8], na awieeɛ koraa no ɛde "afiri mu"[9] ne a ɛba awiei wɔ tebea a etwa to a ɛba awiei mu. Nsakrae a efi tebea biako mu kɔ foforo mu no nyɛ nea wɔahyɛ da ahyɛ da; algorithms bi a wɔfrɛ no randomized algorithms de random input ka ho.[10]
Abakwasɛm
Tete nhyehyɛe ahorow
Efi tete no, wɔadi akwan horow a wɔfa so di akontaabu mu haw ahorow ho dwuma anammɔn biara ho adanse. Eyi ka Babilon akontaabu (bɛyɛ afe 2500 A.Y.B.),[9] Misrifo akontaabu (bɛyɛ afe 1550 A.Y.B.), Indiafo akontaabu (bɛyɛ afe 800 A.Y.B. ne akyiri yi; s.e. Shulba Sutras, Kerala Sukuu, ne Brāhmasphuṭasiddhānta),[12][13] Ifa Oracle (bɛyɛ afe 500 A.Y.B.), Helafo akontabuo (bɛyɛ afe 240 A.Y.B., s.e. sieve of Eratosthenes and Euclidean algorithm),[14] ne Arabic akontabuo (afeha a ɛtɔ so nkron, s.e. cryptographic algorithms ama mmara a wobu so a egyina mpɛn dodow nhwehwɛmu so).[15 ] .
Al-khwarizmi ne asɛmfua algorithm
Bɛyɛ afe 825 no, Muhammad ibn Musa al-Khwarizmi kyerɛw kitāb al-ḥisāb al-hindī ("Indiafo akontabuo Nhoma") ne kitab al-jam' wa'l-tafriq al-ḥisāb al-hindī ("Nka a wɔde ka ho na wɔyi fi mu wɔ India akontabuo mu."). Saa nkyerɛwee abien yi nyinaa ayera wɔ mfitiase Arabic kasa mu wɔ saa bere yi mu. (Nanso, ne nhoma foforo a ɛfa algebra ho no da so ara wɔ hɔ.)[16]
Wɔ afe ɔha a ɛto so 12 mfiase no, Latin nkyerɛase ahorow a ɛfa al-Khwarizmi nkyerɛwee ahorow a wɔaka ho asɛm a ɛfa Hindufo–Arabic akontaabu nhyehyɛe ne akontaabu ho no puei:Liber Alghoarsmi de practica arismetrice (wɔkyerɛ sɛ John a ofi Seville na ɔkyerɛwee) ne Liber Algorismi de numero Indorum (wɔkyerɛ sɛ Adelard a ofi Bath na ɔkyerɛwee).[17] Ɛdenam eyi so no, alghoarismi anaa algorismi yɛ Al-Khwarizmi din a wɔde Latin kasa; nkyerɛwee no de kasasin Dixit Algorismi ("Saa na Al-Khwarizmi kasae") na efi ase.[18]
Borɔfo kasa mu adannandi a ɛfa asɛmfua no ho
Bɛyɛ afe 1230 no, Borɔfo asɛmfua algorism dii ho adanse na afei Chaucer dii ho adanse wɔ afe 1391. Engiresifo gyee Franse asɛmfua no toom.[20][21]
Wɔ afeha a ɛto so 15 mu no, wɔ Hela asɛmfua ἀριθμός (arithmos, "dodow"; fa toto "akontaabu") nkɛntɛnso ase no, wɔsesaa Latin asɛmfua no yɛɛ no algorithmus. Wɔ 1656 mu no, wɔ Engiresi kasa asekyerɛ nhoma Glossographia mu no, ɛka sɛ:[22]
Mfiri a wɔde yɛ dwuma
Wɔ 1928 mu no, wɔde nnɛyi adwene a ɛfa algorithm ho no fã bi hyɛɛ mmara kwan so denam mmɔden a wɔbɔe sɛ wobedi Entscheidungsproblem (gyinaesi ho haw) a David Hilbert de bae no ho dwuma so. Wɔhyehyɛɛ akyiri yi formalizations sɛ mmɔden a wɔbɔ sɛ wɔbɛkyerɛkyerɛ "effective calculability"[29] anaa "effective method".[30] Saa nhyehyɛe ahorow no bi ne Gödel–Herbrand–Kleene recursive functions a ɛbaa 1930, 1934 ne 1935, Alonzo Church lambda calculus a ɔyɛe wɔ 1936 mu, Emil Post Formulation 1 a ɔyɛe wɔ 1936 mu, ne Alan Turing Turing mfiri ahorow a ɔyɛe wɔ 1936–37 ne 1939 mu.
Nkyerɛase a wɔmfa nhyehyɛe mu
Nkyerɛaseɛ a ɛnyɛ ɔkwan pa so betumi ayɛ "mmara ahodoɔ a ɛkyerɛkyerɛ dwumadie ahodoɔ a ɛtoatoa soɔ mu pɛpɛɛpɛ",[31][hia sɛ wɔfa nsɛm ka de hwɛ sɛ ɛyɛ nokware] a ɛbɛka kɔmputa so dwumadie nyinaa ho (a dwumadie a ɛnyɛ akontabuo akontabuo ka ho), ne (sɛ nhwɛsoɔ no) adwumayɛfo kwan biara a wɔahyɛ ato hɔ[32] anaasɛ aduannoa ho nyansahyɛ.[33]
Mpɛn pii no, sɛ dwumadi bi yɛ algorithm nkutoo sɛ awiei koraa no egyae[34]—ɛwom mpo sɛ ɛtɔ mmere bi a ebia loop a enni ano betumi ayɛ nea wɔpɛ de.
Nhwɛsoɔ a ɛyɛ nhwɛsoɔ a ɛfa algorithm ho ne Euclidean algorithm, a wɔde kyerɛ dodoɔ a ɛkyɛn so a ɛyɛ integer mmienu; nhwɛsoɔ bi (afoforo wɔ hɔ) no, wɔde flowchart a ɛwɔ atifi hɔ no akyerɛkyerɛ mu na sɛ nhwɛsoɔ wɔ ɔfa bi a ɛbɛba akyiri yi mu.
Boolos, Jeffrey & 1974, 1999 de asɛmfua "algorithm" no nteaseɛ a ɛnyɛ ɔkwan pa so ma wɔ asɛm a wɔafa aka a ɛdidi soɔ yi mu:
Onipa biara nni hɔ a obetumi akyerɛw ntɛmntɛm, anaasɛ tenten, anaasɛ ketewaa† ( †"ketewa ne nketewa a anohyeto nni mu ... anka wobɛbɔ mmɔden sɛ wobɛkyerɛw wɔ molecule ahorow so, atɔm so, ɛlɛtrɔnik so") de akyerɛw an mufo nyinaa din a wɔkan wɔn a enni ano a wɔahyehyɛ denam wɔn din a wɔkyerɛw, mmiako mmiako, wɔ nkyerɛwde bi mu so. Nanso nnipa betumi ayɛ biribi a mfaso wɔ so saa ara, wɔ akuw bi a wontumi nkan a enni ano fam no: hey betumi ama akwankyerɛ a ɛda adi pefee de akyerɛ nth member a ɛwɔ set no mu, ama arbitrary finite n. Ɛsɛ sɛ wɔde akwankyerɛ a ɛte saa ma pefee, wɔ ɔkwan bi so a wobetumi de kɔmputa afiri adi akyi, anaasɛ onipa a otumi yɛ mfitiase adwuma nkutoo wɔ sɛnkyerɛnnede ahorow so.[35]
Wɔde algorithm ho adwene nso di dwuma de kyerɛkyerɛ adwene a ɛne sɛ wotumi si gyinae no mu —adwene a ɛyɛ ade titiriw a wɔde kyerɛkyerɛ sɛnea nhyehyɛe ahorow a wɔde di dwuma wɔ ɔkwan a ɛfata so ba a wofi ase fi axioms ne mmara kakraa bi so. Wɔ ntease mu no, wontumi nsusuw bere a algorithm bi hwehwɛ sɛ wɔde wie, efisɛ ɛda adi sɛ ɛne amanne kwan so honam fam afã no nni abusuabɔ. Efi adwenem naayɛ a ɛte saa, a ɛkyerɛ adwuma a ɛkɔ so no, fi nkyerɛase a enni hɔ a ɛfa algorithm ho a ɛfata asɛmfua no a wɔde di dwuma wɔ ɔkwan a ɛyɛ nokware (wɔ ntease bi mu) ne nea enni adwene mu.
Wɔayɛ nhyehyɛe sɛ wɔde algorithms dodow no ara bedi dwuma sɛ kɔmputa so dwumadi ahorow. Nanso, wɔfa akwan foforo so nso de algorithms di dwuma, te sɛ wɔ abɔde a nkwa wom ntini mu (sɛ nhwɛso no, onipa amemene a ɛde akontaabu di dwuma anaa nkoekoemmoa bi a ɔrehwehwɛ aduan), anyinam ahoɔden kwan so, anaa mfiri bi mu.
Beaeɛ a menyaa mmoa firiiɛ
- ↑ "Definition of ALGORITHM". Merriam-Webster Online Dictionary. Archived from the original on February 14, 2020. Retrieved November 14, 2019.
- ↑ Blair, Ann, Duguid, Paul, Goeing, Anja-Silvia and Grafton, Anthony. Information: A Historical Companion, Princeton: Princeton University Press, 2021. p. 247
- ↑ David A. Grossman, Ophir Frieder, Information Retrieval: Algorithms and Heuristics, 2nd edition, 2004, ISBN 1402030045
- ↑ "Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).
- ↑ "Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).
- ↑ "an algorithm is a procedure for computing a function (with respect to some chosen notation for integers) ... this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1).
- ↑ "An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973:5).
- ↑ "A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'" (Knuth 1973:5).
- ↑ Chabert, Jean-Luc (2012). A History of Algorithms: From the Pebble to the Microchip. Springer Science & Business Media. pp. 7–8. ISBN 9783642181924.