Algorithm, sistematikong pamamaraan na gumagawa-sa isang tiyak na bilang ng mga hakbang - ang sagot sa isang katanungan o ang solusyon ng isang problema. Ang pangalang ito ay nagmula sa salin na Latin, Algoritmi de numero Indorum, ng ika-9 na siglo na matematiko na si al-Khwarizmi ng aritmetika na "Al-Khwarizmi Pag-aalala sa Hindu Art of Reckoning."
computer science: Algorithms at pagiging kumplikado
Ang isang algorithm ay isang tiyak na pamamaraan para sa paglutas ng isang maayos na tinukoy na problema sa computational. Ang pag-unlad at pagtatasa ng mga algorithm ay pangunahing
Para sa mga katanungan o problema na may isang tiyak na hanay ng mga kaso o halaga ng isang algorithm palaging umiiral (hindi bababa sa prinsipyo); binubuo ito ng isang talahanayan ng mga halaga ng mga sagot. Sa pangkalahatan, hindi tulad ng isang walang kuwentang pamamaraan upang sagutin ang mga katanungan o mga problema na may isang walang hanggan bilang ng mga kaso o mga halaga na dapat isaalang-alang, tulad ng "Ang natural na numero (1, 2, 3,.) Isang kalakasan?" o "Ano ang pinakadakilang pangkaraniwang naghahati ng mga likas na numero a at b?" Ang una sa mga tanong na ito ay kabilang sa isang klase na tinatawag na decidable; isang algorithm na gumagawa ng isang oo o walang sagot ay tinatawag na isang pamamaraan ng pagpapasya. Ang pangalawang tanong ay kabilang sa isang klase na tinatawag na computable; isang algorithm na humahantong sa isang tiyak na sagot na numero ay tinatawag na isang pamamaraan sa pag-compute.
Ang mga algorithm ay umiiral para sa maraming mga walang hanggan na klase ng mga katanungan; Mga Element ng Euclid, na inilathala tungkol sa 300 bc, ay naglalaman ng isa para sa paghahanap ng pinakadakilang pangkaraniwang tagapaghati ng dalawang likas na numero. Ang bawat mag-aaral sa elementarya ay drill sa mahabang dibisyon, na kung saan ay isang algorithm para sa tanong na "Sa paghati ng isang likas na numero sa pamamagitan ng isa pang likas na numero b, ano ang malinaw at ang nalalabi?" Ang paggamit ng computational na pamamaraan na ito ay humahantong sa sagot sa napapasyang tanong na "Nagbabahagi ba ang isang?" (ang sagot ay oo kung ang natira ay zero). Ang paulit-ulit na aplikasyon ng mga algorithm na ito ay kalaunan ay gumagawa ng sagot sa napapasyang tanong na "Ay isang kalakasan?" (ang sagot ay hindi kung ang isang ay nahahati sa anumang mas maliit na likas na bilang maliban sa 1).
Minsan ang isang algorithm ay hindi maaaring umiiral para sa paglutas ng isang walang hanggan na klase ng mga problema, lalo na kung ang ilang karagdagang paghihigpit ay ginawa sa tinanggap na pamamaraan. Halimbawa, dalawang mga problema mula sa panahon ni Euclid na nangangailangan ng paggamit ng isang kompas lamang at isang tuwid (walang marka na tagapamahala) - ang pag-alis ng isang anggulo at pagbubuo ng isang parisukat na may isang lugar na katumbas ng isang naibigay na bilog - ay hinabol ng maraming siglo bago sila ipinakita na imposible. Sa pagliko ng ika-20 siglo, ang maimpluwensiyang Aleman matematiko na si David Hilbert ay nagmungkahi ng 23 mga problema para malutas ng mga matematiko sa darating na siglo. Ang pangalawang problema sa kanyang listahan ay nagtanong para sa isang pagsisiyasat ng pagkakapareho ng mga axioms ng aritmetika. Karamihan sa mga matematiko ay walang pag-aalinlangan sa pagkakamit ng hangaring ito hanggang sa 1931, nang ipinakita ng ipinanganak na taga-Austrian na si Kurt Gödel ang nakakagulat na resulta na dapat mayroong umiiral na mga panukala sa aritmetika (o mga katanungan) na hindi mapapatunayan o hindi naaprubahan. Mahalaga, ang anumang naturang panukala ay humahantong sa isang pamamaraan ng pagpapasiya na hindi kailanman magtatapos (isang kondisyon na kilala bilang ang paghinto sa problema). Sa isang hindi matagumpay na pagsisikap upang matukoy ang hindi bababa sa kung anong mga panukala ay hindi malulutas, ang matematiko ng matematika at lohista na si Alan Turing ay mahigpit na tinukoy ang maluwag na naunawaan na konsepto ng isang algorithm. Bagaman natapos na si Turing na nagpapatunay na dapat mayroong umiiral na mga hindi maisasang-ayon na mga panukala, ang kanyang paglalarawan sa mga mahahalagang katangian ng anumang makina ng pangkalahatang layunin na algorithm, o Turing machine, ay naging pundasyon ng agham ng computer. Ngayon ang mga isyu ng desidability at computability ay sentro sa disenyo ng isang computer program - isang espesyal na uri ng algorithm.
