Algorithm

 

Flow-chart of an algorithm Euclides algorithm's ) a wɔde bu akontaa wɔ akontaahyɛde abien a ne b mu mpaapaemu kɛse (gcd) a ɛwɔ mmeae a wɔato din A ne B. Algorithm no kɔ so denam twe a wɔtwe fi mu nnidiso nnidiso wɔ loop abien mu: SƐ sɔhwɛ B ≥ A no ma "yiw " anaa "nokware" (sɛ yɛbɛka no pɛpɛɛpɛ a, nɔma b a ɛwɔ beae B no sõ anaasɛ ɛne nɔma a a ɛwɔ beae A no yɛ pɛ) AFEI, algorithm no kyerɛ B ← B − A (a ɛkyerɛ sɛ nɔma b − a besi b dedaw no ananmu) . . Saa ara nso na SƐ A > B, AFEI A ← A − B. Adeyɛ no ba awiei bere a (nneɛma a ɛwɔ) B mu no yɛ 0, na ɛma gcd a ɛwɔ A. (Algorithm a wonya fii Scott 2009:13; nsɛnkyerɛnne ne mfoniniyɛ kwan a efi Tausworthe 1977) .

Ada Lovelace 's mfonini a efi "note G", kɔmputa so nhyehyɛe a edi kan a wotintimii

Wɔ nkontaabu ne kɔmputa ho nyansahu mu no, algorithm (/ˈælɡərɪðəm/ (tie)) yɛ akwankyerɛ a ɛyɛ katee a ɛtoatoa so a anohyeto wom, a wɔtaa de di ɔhaw pɔtee bi ho dwuma anaasɛ wɔde yɛ akontaabu.[1]Wɔde algorithms di dwuma sɛ nkyerɛkyerɛmu a wɔde yɛ akontaabu ne data ho dwumadie. Algorithm a ɛkɔ anim kɛse betumi de tebea mu nneɛma adi dwuma de adan mmara no a wɔde di dwuma no afa akwan horow so (a wɔfrɛ no gyinaesi a wɔde wɔn ankasa yɛ) na wɔasusuw nsusuwii a ɛfata (a wɔfrɛ no nsusuwii a wɔde wɔn ankasa yɛ ho), na awiei 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", "hwehwɛ" ne "nkanyan" de di dwuma dedaw.[2]

Nea ɛne eyi bɔ abira no, heuristic yɛ ɔkwan a wɔfa so siesie ɔhaw ahorow a ebia wɔankyerɛkyerɛ mu yiye anaasɛ ebia ɛnyɛ nea ɛbɛma wɔanya nea ɛteɛ anaa nea eye sen biara, titiriw wɔ ɔhaw ahorow mu a nea efi mu ba a ɛteɛ anaa nea eye 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 bere 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 akontaa.[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ɔ[8] mu, 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.),[11] Misrifo akontaabu (bɛyɛ afe 1550 A.Y.B.),[11] 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]