Kahulugan at Kasaysayan ng Algorithm
– Ang mga algorithm ay isang may hangganang pagkakasunod-sunod ng mahigpit na mga tagubilin na ginagamit sa matematika at computer science.
– Ginagamit ang mga ito upang malutas ang mga partikular na problema o magsagawa ng mga pagkalkula.
– Ang mga algorithm ay nagsisilbing mga pagtutukoy para sa mga kalkulasyon at pagproseso ng data .
– Maaaring isama ng mas advanced na mga algorithm ang mga kondisyon at awtomatikong paggawa ng desisyon.
– Ang mga algorithm ay maaaring ipahayag sa isang mahusay na tinukoy na pormal na wika para sa pagkalkula ng isang function.
– Ang mga hakbang-hakbang na pamamaraan para sa paglutas ng mga problema sa matematika ay ginamit mula pa noong unang panahon.
– Ang mga sibilisasyong Babylonian, Egyptian, Indian, Greek, at Arabic ay nakabuo ng mga mathematical algorithm.
– Kasama sa mga algorithm na ito ang mga pamamaraan para sa paghahanap ng pinakakaraniwang divisor at cryptographic algorithm.
– Ang mga sinaunang algorithm ay nakabatay sa iba't ibang sistema ng numeral at mga diskarte sa aritmetika.
- Inilatag nila ang pundasyon para sa modernong algorithmic na pag-iisip.
– Si Muḥammad ibn Mūsā al-Khwārizmī ay nagsulat ng mga teksto sa Indian computation at arithmetic noong ika-9 na siglo.
– Ipinakilala ng mga pagsasalin sa Latin ng mga gawa ni al-Khwārizmī ang terminong 'algorismi' at 'algorithmus' noong ika-12 siglo.
– Ang terminong 'algorithm' ay nagmula sa pangalan ni al-Khwārizmī at tinutukoy ang sining ng pagtutuos sa pamamagitan ng mga numeral.
– Malaki ang naging papel ng mga teksto ni Al-Khwārizmī sa pagpapalaganap ng mga numero at aritmetika ng India sa Europa.
– Ang terminong 'algorithm' ay umunlad sa paglipas ng panahon sa iba't ibang wika.
– Ang salitang Ingles na 'algorism' ay pinatunayan noong 1230 at kalaunan ay pinagtibay ang terminong Pranses.
– Noong ika-15 siglo, ang salitang Latin ay binago sa 'algorithmus' sa ilalim ng impluwensya ng salitang Griyego na 'arithmos.'
– Tinukoy ng mga unang diksyunaryo ng Ingles ang 'algorism' bilang sining ng pagnunumero ng mga cypher at 'algorithmus' bilang kasanayan sa accounting o pagnunumero.
– Ang terminong 'algorithm' ay nagsimulang gamitin upang ipahiwatig ang isang hakbang-hakbang na pamamaraan sa Ingles mula noong hindi bababa sa 1811.
– Ang salitang 'algorithm' ay sumailalim sa iba't ibang interpretasyon at paggamit sa buong kasaysayan.
– Noong 1928, ang mga pagtatangka na lutasin ang Entscheidungsproblem ay humantong sa bahagyang pormalisasyon ng mga algorithm.
– Kasama sa mga pormalisasyon ang mga recursive function, lambda calculus, at Turing machine.
– Ang mga pormalisasyong ito ay naglalayong tukuyin ang epektibong kalkulasyon at epektibong pamamaraan.
– Ang mga Turing machine ni Alan Turing, na iminungkahi noong huling bahagi ng 1930s, ay itinuturing na pangunahing modelo ng pagtutuos.
– Ang pagbuo ng mga pormal na algorithm ay nagbigay daan para sa modernong computer science.
Pagpapahayag at Pagdidisenyo ng Algorithm
– Ang mga algorithm ay maaaring ipahayag sa mga natural na wika, pseudocode, flowchart, atbp.
– Ang mga natural na expression ng wika ng mga algorithm ay bihirang ginagamit para sa kumplikado o teknikal na mga algorithm.
– Ang pseudocode, mga flowchart, at control table ay nagbibigay ng mga structured na paraan upang ipahayag ang mga algorithm.
– Pangunahing ginagamit ang mga programming language upang magsagawa ng mga algorithm.
– Posible ang iba't ibang representasyon ng mga algorithm, tulad ng mga machine table, flowchart, at quadruples.
– Ang disenyo ng algorithm ay isang paraan para sa paglutas ng problema at mga algorithm ng engineering.
– Ang iba't ibang mga teorya ng solusyon, tulad ng divide-and-conquer o dynamic na programming, ay nag-aambag sa disenyo ng algorithm.
– Ang mga pattern ng disenyo ng algorithm, tulad ng pattern ng pamamaraan ng template at pattern ng dekorador, ay tumutulong sa pagdidisenyo at pagpapatupad ng mga algorithm.
– Ang kahusayan sa mapagkukunan, tulad ng run-time at paggamit ng memorya, ay isang mahalagang aspeto ng disenyo ng algorithm.
– Inilalarawan ng malaking O notation ang run-time na paglago ng isang algorithm habang tumataas ang laki ng input.
– Ang pagiging simple at kagandahan ay mga kanais-nais na katangian sa mga algorithm.
– Ang magagandang algorithm ay madaling ibagay, simple, at eleganteng.
– Ang haba ng oras na kinuha upang maisagawa ang isang algorithm ay isang pamantayan para sa pagsusuri ng kabutihan nito.
– Tinukoy ni Chaitin ang isang eleganteng programa bilang pinakamaliit na posibleng programa para sa paggawa ng isang partikular na output.
– Maaaring mangyari ang mga tradeoff sa pagitan ng bilis at pagiging compact sa mga eleganteng programa.
Mga Kompyuter at Mga Modelo ng Pagtutuos
– Ang computer ay isang discrete deterministic na mekanikal na aparato na sumusunod sa mga tagubilin.
– Ang mga modelo ng computation, tulad ng mga primitive na modelo ng Melzaks at Lambeks, ay may mga discrete na lokasyon, counter, ahente, at isang listahan ng mga epektibong tagubilin.
– Ang makina ni Minsky, isang variation ng Lambeks abacus model, ay sumusunod sa mga tagubilin nang sunud-sunod.
– Maaaring baguhin ng kondisyonal at walang kondisyong mga pahayag ng GOTO ang daloy ng programa.
– Maaaring makalkula ng iba't ibang mga algorithm ang parehong function.
Simulation at Pagpapatupad ng Algorithm
– Mahalaga ang mga algorithm sa paraan ng pagproseso ng mga computer ng data .
– Ang mga algorithm ay nagdedetalye ng mga tiyak na tagubilin para sa isang computer upang maisagawa ang isang gawain.
– Ang mga algorithm ay maaaring gayahin ng isang Turing-complete system.
– Hindi lahat ng proseso ng computational na tinukoy ng mga Turing machine ay nagwawakas.
– Kadalasang kinabibilangan ng mga algorithm ang pagbabasa, pagsusulat, at pag-iimbak ng data .
– Dapat isalin ng programmer ang algorithm sa isang wika na maaaring isagawa ng computer.
– Ang mabisang pagpili ng wika ay nakasalalay sa target na ahente sa pag-compute.
– Ang kaalaman sa mabisang wika ay kailangan para sa programmer.
– Ang pagpili ng modelo para sa simulation ay nagpapakilala sa ideya ng simulation.
– Ang bilis ng pagpapatupad ay depende sa set ng pagtuturo ng computer.
- Anumang algorithm ay maaaring kalkulahin ng isang kumpletong modelo ng Turing.
– Maaaring isulat ang mga structured na programa gamit ang mga may kondisyon at walang kondisyong GOTO, pagtatalaga, at mga tagubilin ng HALT.
– Ang walang disiplinang paggamit ng mga GOTO ay maaaring magresulta sa spaghetti code.
– Kasama sa mga karagdagang canonical na istruktura ang DO-WHILE at CASE.
– Ang mga istrukturang programa ay nagbibigay ng kanilang sarili sa mga patunay ng kawastuhan gamit ang mathematical induction.
– Ang Flowchart ay isang graphical na tulong upang ilarawan at idokumento ang isang algorithm.
– Ang Flowchart ay nagsisimula sa itaas at nagpapatuloy pababa.
– Kabilang sa mga pangunahing simbolo ang nakadirektang arrow, parihaba (SEQUENCE, GOTO), brilyante (IF-THEN-ELSE), at tuldok (OR-tie).
– Ang Böhm-Jacopini canonical structures ay maaaring itayo gamit ang mga simbolong ito.
– Maaaring pugad ang mga sub-structure sa mga parihaba na may iisang labasan.
Halimbawa ng Euclid's Algorithm at Algorithmic Analysis
– Ang algorithm ng Euclid ay isang paraan para sa paghahanap ng pinakamalaking karaniwang divisor (GCD) ng dalawang numero.
– Ang algorithm ay nagsasangkot ng isang serye ng mga hakbang na gumagamit ng pagbabawas upang mahanap ang natitira.
– Ito ay pinangalanan sa sinaunang Greek mathematician na si Euclid.
– Ang algorithm ay ginamit sa loob ng maraming siglo at malawak pa ring ginagamit ngayon.
– Ang algorithm ng Euclid ay mahusay at mahahanap ang GCD ng napakalaking numero.
– Ang Inelegant ay isang bersyon ng Euclid's
Sa matematika at computer science , isang algorithm ( / ˈæl ɡ ə r ɪ ð əm / ⓘ ) ay isang may hangganang pagkakasunod-sunod ng mahigpit na mga tagubilin, karaniwang ginagamit upang lutasin ang isang klase ng mga partikular na problema o upang magsagawa ng pagkalkula . Ginagamit ang mga algorithm bilang mga detalye para sa pagsasagawa ng mga kalkulasyon at pagproseso ng data . Ang mga mas advanced na algorithm ay maaaring gumamit ng mga kondisyon upang ilihis ang pagpapatupad ng code sa pamamagitan ng iba't ibang mga ruta (tinukoy bilang automated na paggawa ng desisyon ) at paghihinuha ang mga wastong inferences (tinukoy bilang automated na pangangatwiran ), pagkamit ng automation sa kalaunan. Ang paggamit ng mga katangian ng tao bilang mga deskriptor ng mga makina sa metaporikal na paraan ay isinagawa na ni Alan Turing na may mga terminong gaya ng "memorya", "search" at "stimulus".
Sa kabaligtaran, ang heuristic ay isang diskarte sa paglutas ng problema na maaaring hindi ganap na tinukoy o maaaring hindi ginagarantiyahan ang tama o pinakamainam na mga resulta, lalo na sa mga domain ng problema kung saan walang mahusay na tinukoy na tama o pinakamainam na resulta. Halimbawa, ang mga social media recommender system ay umaasa sa heuristics sa paraang, bagama't malawak na nailalarawan bilang "algorithm" sa 21st century popular na media, ay hindi makapaghatid ng mga tamang resulta dahil sa likas na katangian ng problema.
Bilang isang epektibong paraan , ang isang algorithm ay maaaring ipahayag sa loob ng isang tiyak na dami ng espasyo at oras at sa isang mahusay na tinukoy na pormal na wika para sa pagkalkula ng isang function . Simula sa paunang estado at paunang pag-input (marahil walang laman ), inilalarawan ng mga tagubilin ang isang pagtutuos na, kapag naisakatuparan , nagpapatuloy sa isang tiyak na bilang ng mga sunud-sunod na estado na mahusay na tinukoy, sa kalaunan ay gumagawa ng "output" at nagwawakas sa panghuling estado ng pagtatapos. Ang paglipat mula sa isang estado patungo sa susunod ay hindi kinakailangang deterministiko ; ang ilang mga algorithm, na kilala bilang randomized algorithm , ay nagsasama ng random na input.
