Algoritmi

Diagrami i rrjedhës së përdorimit të zbritjeve të njëpasnjëshme për të gjetur pjesëtuesin më të madh të përbashkët të numrit r dhe s

Në matematikë dhe shkenca kompjuterike, një algoritëm (/'ælɡərɪðəm/ⓘ) është një sekuencë e kufizuar udhëzimesh matematikisht rigoroze, që përdoren zakonisht për të zgjidhur një klasë problemesh specifike ose për të kryer një llogaritje. Algoritmet përdoren si specifikime për kryerjen e llogaritjeve dhe përpunimin e të dhënave. Algoritmet më të përparuara mund të përdorin kushte për të devijuar ekzekutimin e kodit përmes rrugëve të ndryshme (të referuara si vendimmarrje e automatizuar) dhe për të nxjerrë përfundime të vlefshme (të referuara si arsyetim i automatizuar).

Në të kundërt, një heuristikë është një qasje për zgjidhjen e problemeve pa rezultate të sakta ose optimale të përcaktuara mirë. Për shembull, megjithëse sistemet e rekomandimit të mediave sociale zakonisht quhen "algoritme", ato në fakt mbështeten në heuristikë pasi nuk ka një rekomandim vërtet "të saktë".

Si një metodë efektive, një algoritëm mund të shprehet brenda një sasie të kufizuar hapësire dhe kohe dhe në një gjuhë formale të përcaktuar mirë për llogaritjen e një funksioni. Duke filluar nga një gjendje fillestare dhe një hyrje fillestare (ndoshta bosh), udhëzimet përshkruajnë një llogaritje që, kur ekzekutohet, vazhdon përmes një numri të kufizuar gjendjesh të njëpasnjëshme të përcaktuara mirë, duke prodhuar përfundimisht "dalje" dhe duke përfunduar në një gjendje përfundimtare. Kalimi nga një gjendje në tjetrën nuk është domosdoshmërisht determinist; disa algoritme, të njohura si algoritme të rastësishme, përfshijnë hyrje të rastësishme.

Etimologjia

Rreth vitit 825 të erës sonë, shkencëtari dhe polimati persian Muhamed ibn Mūsā al-Khwarizmi shkroi kitāb al-ḥisāb al-hindī ("Libri i llogaritjes indiane") dhe kitab al-jam' wa'l-tafriq al-ḥisāb al-hindī ("Mbledhja dhe zbritja në aritmetikën indiane"). Në fillim të shekullit të 12-të, u shfaqën përkthime latine të këtyre teksteve që përfshinin sistemin numerik hindu-arab dhe aritmetikën, për shembull Liber Alghoarismi de practica arismetrice, që i atribuohet Gjonit të Seviljes, dhe Liber Algorismi de numero Indorum, që i atribuohet Adelardit të Bathit. Këtu, alghoarismi ose algorismi është latinizimi i emrit të Al-Khwarizmit; teksti fillon me frazën Dixit Algorismi, ose "Kështu foli Al-Khwarizmi".

Fjala algorizëm në anglisht filloi të nënkuptonte përdorimin me vlerë pozicionale në llogaritje; ajo shfaqet në Ancrene Wisse nga rreth vitit 1225. Në kohën kur Geoffrey Chaucer shkroi The Canterbury Tales në fund të shekullit të 14-të, ai përdori një variant të së njëjtës fjalë në përshkrimin e gurëve augrym, gurë të përdorur për llogaritjen e vlerës së vendit. Në shekullin e 15-të, nën ndikimin e fjalës greke ἀριθμός ( arithmos, "numër"; krahaso "aritmetik"), fjala latine u ndryshua në algoritmus. Deri në vitin 1596, kjo formë e fjalës u përdor në anglisht, si algorithm, nga Thomas Hood.

Përkufizim

Një përkufizim joformal është "një grup rregullash që përcakton saktësisht një sekuencë operacionesh", që do të përfshinte të gjitha programet kompjuterike (duke përfshirë programet që nuk kryejnë llogaritje numerike) dhe çdo procedurë burokratike të përcaktuar ose recetë nga libri i gatimit. Në përgjithësi, një program është një algoritëm vetëm nëse ndalet përfundimisht – edhe pse ciklet e pafundme ndonjëherë mund të jenë të dëshirueshme. Boolos, Jeffrey & 1974, 1999 e përcaktojnë një algoritëm si një grup udhëzimesh të qarta për përcaktimin e një rezultati, që mund të ndiqet nga një makinë llogaritëse ose një njeri që mund të kryejë vetëm operacione specifike elementare mbi simbolet.

Pasi ta mbarosh fshije kete tekst

Shumica e algoritmeve synojnë të zbatohen si programe kompjuterike. Megjithatë, algoritmet zbatohen edhe me mjete të tjera, si në një rrjet nervor biologjik (për shembull, truri i njeriut që kryen veprime aritmetike ose një insekt që kërkon ushqim), në një qark elektrik ose në një pajisje mekanike.

Histori

 Algoritmet e lashta

Procedurat hap pas hapi për zgjidhjen e problemeve matematikore janë regjistruar që nga lashtësia. Kjo përfshin matematikën babilonase (rreth vitit 2500 p.e.s.), matematikën egjiptiane (rreth vitit 1550 p.e.s.),.matematikën indiane (rreth vitit 800 p.e.s. dhe më vonë), Orakullin e Ifës (rreth vitit 500 p.e.s.), matematikën greke (rreth vitit 240 p.e.s.) matematikën kineze (rreth vitit 200 p.e.s. dhe më vonë) dhe matematikën arabe (rreth vitit 800 p.e.s.).

Provat më të hershme të algoritmeve gjenden në matematikën e lashtë të Mesopotamisë. Një pllakë argjile sumeriane e gjetur në Shuruppak pranë Bagdadit dhe e datuar rr. 2500 BC përshkruan algoritmin më të hershëm të pjesëtimit. Gjatë dinastisë Hamurabi rr. 1800 – rr. 1600 BC, pllakat prej balte babilonase përshkruan algoritme për llogaritjen e formulave. Algoritmet u përdorën gjithashtu në astronominë babilonase. Pllakat prej balte babilonase përshkruajnë dhe përdorin procedura algoritmike për të llogaritur kohën dhe vendin e ngjarjeve të rëndësishme astronomike.

Algoritmet për aritmetikë gjenden gjithashtu në matematikën e lashtë egjiptiane, që datojnë që nga Papirusi Matematikor i Rhind-it rr. 1550 BC. Algoritmet u përdorën më vonë në matematikën e lashtë helenistike. Dy shembuj janë Sita e Eratostenit, e cila u përshkrua në Hyrje në Aritmetikë nga Nikomaku,dhe algoritmi Euklidian, i cili u përshkrua për herë të parë në Elementet e Euklidit ( rr. 300 BC ).Shembuj të matematikës së lashtë indiane përfshinin Shulba Sutrat, Shkollën Kerala dhe Brāhmasphuṭasiddhānta- n.

Algoritmi i parë kriptografik për deshifrimin e kodeve të koduara u zhvillua nga Al-Kindi, një matematikan arab i shekullit të 9-të, në dorëshkrimin "Një dorëshkrim mbi deshifrimin e mesazheve kriptografike". Ai dha përshkrimin e parë të kriptanalizës me anë të analizës së frekuencës, algoritmi më i hershëm i zbërthimit të kodit.

Kompjuterë

Orë të drejtuara nga pesha

Bolter e konsideron shpikjen e orës së drejtuar nga pesha si "shpikjen kryesore [të Evropës në Mesjetë]", konkretisht mekanizmin e arratisjes nga kufijtë që prodhonte tik-tak-un e një ore mekanike. "Makina automatike e saktë" çoi menjëherë në "automatet mekanike" në shekullin e 13-të dhe "makinat llogaritëse"- motorët analitikë dhe diferencialë të Charles Babbage dhe Ada Lovelace në mesin e shekullit të 19-të. Lovelace projektoi algoritmin e parë të destinuar për përpunim në një kompjuter, në motorin analitik të Babbage-it, i cili konsiderohet paisja e parë që është vlerësuar si një kompjuter i vërtetë i plotë sipas modelit të Turingut, e jo vetem kalkulator. Megjithëse zbatimi i plotë i pajisjes së dytë të Babbage-it nuk u realizua për dekada pas jetës së saj, Lovelace është quajtur "programuesja e parë e historisë".

Rele elektromekanike

Bell dhe Newell (1971) shkruajnë se tezgjahu Jacquard, një pararendës i kartave Hollerith (kartave shpuese) dhe "teknologjive të ndërrimit të telefonave" çoi në zhvillimin e kompjuterëve të parë. Nga mesi i shekullit të 19-të, telegrafi, pararendësi i telefonit, ishte në përdorim në të gjithë botën. Nga fundi i shekullit të 19-të, shiriti me tik-takë (rr. 1870s) ishte në përdorim, ashtu si edhe kartat Hollerith (rreth vitit 1890). Pastaj doli teleprinteri (rr. 1910) me përdorimin e kodit Baudot në shirit si letër e shpuar.

Rrjetet telefonike me ndërrues elektromekanikë u shpikën në vitin 1835. Këto çuan në shpikjen e pajisjes dixhitale për mbledhje nga George Stibitz në vitin 1937. Ndërsa punonte në Laboratorët Bell, ai vëzhgoi përdorimin "të lodhshëm" të kalkulatorëve mekanikë me ingranazhe. "Ai shkoi në shtëpi një mbrëmje në vitin 1937 me qëllim që të testonte idenë e tij... Kur mbaroi puna, Stibitz kishte ndërtuar një pajisje binare për mbledhje".

Formalizimi

Diagrami i Ada Lovelace nga "Shënimi G", algoritmi i parë kompjuterik i botuar

Në vitin 1928, filloi një formalizim i pjesshëm i konceptit modern të algoritmeve me përpjekjet për të zgjidhur problemin Entscheidungsproblem (problemin e vendimmarrjes) të paraqitur nga David Hilbert. Formalizimet e mëvonshme u formuluan si përpjekje për të përcaktuar "llogaritshmërinë efektive" ose "metodën efektive". Këto formalizime përfshinin funksionet rekursive Gödel – Herbrand – Kleene të viteve 1930, 1934 dhe 1935, llogaritjen lambda të Alonzo Church të vitit 1936, Formulimin 1 të Emil Post të vitit 1936, dhe makinat Turing të Alan Turing të viteve 1936–37 dhe 1939.

Algoritmet Moderne

Algoritmet kanë përmirsuar dhe evoluar në shumë mënyra me kalimin e kohës. Përdorimet e zakonshme të algoritmeve sot përfshijnë aplikacionet e mediave sociale si Instagram dhe YouTube. Algoritmet përdoren si një mënyrë për të analizuar atë që u pëlqen njerëzve dhe për t'i ofruar më shumë nga këto gjëra njerëzve që bashkëveprojnë me to. Informatika kuantike përdor procedurat e algoritmit kuantik për të zgjidhur problemet më shpejt. Kohët e fundit, në vitin 2024, NIST përditësoi standardet e tyre të enkriptimit post-kuantik, të cilat përfshijnë algoritme të reja të enkriptimit për të përmirësuar mbrojtjen kundër sulmeve duke përdorur informatikën kuantike.

Përfaqësime

Algoritmet mund të shprehen në shumë lloje shënimesh, duke përfshirë gjuhët natyrore, pseudokodin, diagramet e rrjedhës, diagramet drakon, gjuhët e programimit ose tabelat e kontrollit (të përpunuara nga interpretuesit). Shprehjet në gjuhën natyrore të algoritmeve kanë tendencë të jenë të gjata dhe të paqarta dhe rrallë përdoren për algoritme komplekse ose teknike. Pseudokodi, diagramet e rrjedhës, diagramet drakon dhe tabelat e kontrollit janë shprehje të strukturuara të algoritmeve që shmangin paqartësitë e zakonshme të gjuhës natyrore. Gjuhët programuese përdoren kryesisht për të shprehur algoritmet në një formë të ekzekutueshme nga kompjuteri, por përdoren gjithashtu për të përcaktuar ose dokumentuar algoritmet.

Makinat Turing

Ekzistojnë shumë përfaqësime të mundshme, dhe programet e makinës Turing mund të shprehen si një sekuencë tabelash makinash (shih makinën me gjendje të kufizuar, tabelën e tranzicionit të gjendjes dhe tabelën e kontrollit për më shumë), si diagrame rrjedhëse dhe diagrame drakon (shih diagramin e gjendjes për më shumë), si një formë e kodit rudimentar të makinës ose kodit të montimit të quajtur "grupe katërfishësh" dhe më shumë. Përfaqësimet e algoritmeve gjithashtu mund të klasifikohen në tre nivele të pranuara të përshkrimit të makinës Turing: përshkrim i nivelit të lartë, përshkrim i zbatimit dhe përshkrim formal. Një përshkrim i nivelit të lartë përshkruan vetë cilësitë e algoritmit, duke injoruar se si zbatohet në makinën Turing. Një përshkrim zbatimi përshkruan mënyrën e përgjithshme në të cilën makina lëviz kokën e saj dhe ruan të dhënat për të kryer algoritmin, por nuk jep gjendje të sakta. Në detajet më të hollësishme, një përshkrim formal jep tabelën e saktë të gjendjes dhe listën e tranzicioneve të makinës Turing.

Përfaqësimi i diagramit të rrjedhës

Ndihma grafike e quajtur si diagram rrjedhës ofron një mënyrë për të përshkruar dhe dokumentuar një algoritëm (dhe një program kompjuterik që i korrespondon atij). Ai ka katër simbole kryesore: shigjeta, që tregojnë rrjedhën e programit, drejtkëndësha (SEKUENCA, GOTO), diamante (NËSE-ATËHERË-GJITHÇKA) dhe pika (OSE-lidhje). Nënstrukturat mund të "vendosen" në drejtkëndësha, por vetëm nëse ndodh një dalje e vetme nga superstruktura.

Shpesh është e rëndësishme të dihet se sa kohë, hapësirë ruajtjeje ose kosto të tjera mund të kërkojë një algoritëm. Janë zhvilluar metoda për analizën e algoritmeve për të marrë përgjigje (vlerësime) sasiore të tilla; për shembull, një algoritëm që mbledh elementët e një liste prej n numrash do të kishte një kërkesë kohore prej O(n), duke përdorur simbolin e madh O. Algoritmi duhet të mbajë mend vetëm dy vlera: shumën e të gjithë elementëve deri më tani dhe pozicionin e tij aktual në listën e të dhënave hyrëse. Nëse hapësira e nevojshme për të ruajtur numrat e të dhënave hyrëse nuk llogaritet, ai ka një hapësirë të kërkuar prej O(1), ndryshe O(n) është e detyrueshme .

Algoritme të ndryshme mund ta përfundojnë të njëjtën detyrë me një grup udhëzimesh të ndryshme, duke përdorur më pak ose më shumë kohë, hapësirë ose 'përpjekje' sesa të tjerët. Për shembull, një algoritëm kërkimi binar (me kosto O(log n)) performonë më mirë se një kërkim i sekuencës (me kosto O(n)) kur përdoret për kërkime në tabela në lista ose vargje të renditura.

Formale kundrejt empirike

 Analiza dhe studimi i algoritmeve është një disiplinë e shkencës kompjuterike. Shpesh algoritmet studiohen në mënyrë abstrakte, pa iu referuar ndonjë gjuhe programimi ose zbatimi specifik. Analiza e algoritmeve i ngjan disiplinave të tjera matematikore pasi përqendrohet në vetitë e algoritmit, jo në zbatimin e tij. Pseudokodi është tipik për analizën pasi është një përfaqësim i thjeshtë dhe i përgjithshëm. Shumica e algoritmeve zbatohen në platforma të veçanta hardueri/softueri dhe efikasiteti i tyre algoritmik testohet duke përdorur kod real. Efikasiteti i një algoritmi të caktuar mund të jetë i parëndësishëm për shumë probleme "të njëhershme", por mund të jetë kritik për algoritmet e dizajnuara për përdorim të shpejtë ndërveprues, komercial ose shkencor jetëgjatë. Shkallëzimi nga n i vogël në n të madh shpesh ekspozon algoritme joefikase që përndryshe janë të mira.

Testimi empirik është i dobishëm për zbulimin e ndërveprimeve të papritura që ndikojnë në performancë. Pikat e referencës mund të përdoren për të krahasuar përmirësimet e mundshme para/pas një algoritmi pas optimizimit të programit. Megjithatë, testet empirike nuk mund të zëvendësojnë analizën formale dhe nuk janë të parëndësishme për të kryer në mënyrë të drejtë.

Efikasiteti i ekzekutimit

Për të ilustruar përmirësimet e mundshme edhe në algoritmet e mirë-vendosura, një risi e rëndësishme e kohëve të fundit, që lidhet me algoritmet FFT (të përdorura gjerësisht në fushën e përpunimit të imazheve), mund ta ulë kohën e përpunimit deri në 1,000 herë për aplikime si imazheria mjekësore. Në përgjithësi, përmirësimet e shpejtësisë varen nga vetitë e veçanta të problemit, të cilat janë shumë të zakonshme në aplikimet praktike. Shpejtësitë e kësaj madhësie u mundësojnë pajisjeve kompjuterike që përdorin gjerësisht përpunimin e imazheve (si kamerat dixhitale dhe pajisjet mjekësore) të konsumojnë më pak energji.

Rasti më i mirë dhe rasti më i keq

Rasti më i mirë i një algoritmi i referohet skenarit ose të dhënave hyrëse për të cilat algoritmi ose struktura e të dhënave kërkon më pak kohë dhe burime për të përfunduar detyrat e tij. Rasti më i keq i një algoritmi është rasti që bën që algoritmi ose struktura e të dhënave të konsumojë periudhën maksimale të kohës dhe burimeve llogaritëse.

Dizajn

Dizajnimi i i algoritmeve është një metodë ose proces matematikor për zgjidhjen e problemeve dhe inxhinierinë e algoritmeve. Dizajnimi i algoritmeve është pjesë e shumë teorive të zgjidhjes, të tilla si programimi përçaj-dhe-sundo ose programimi dinamik brenda kërkimit të operacioneve . Teknikat për dizajnimin dhe zbatimin e algoritmeve quhen edhe modele dizajnimi algoritmesh, me shembuj që përfshijnë modelin e metodës shabllon dhe modelin dekorues. Një nga aspektet më të rëndësishme të dizajnimit të algoritmeve është efikasiteti i burimeve (koha e ekzekutimit, përdorimi i memories); notacioni i madh O përdoret për të përshkruar, p.sh., rritjen e kohës së ekzekutimit të një algoritmi ndërsa rritet madhësia e të dhënave hyrëse të tij.

Programim i strukturuar

Sipas tezës Church-Turing, çdo algoritëm mund të llogaritet nga çdo model i plotë Turing. Plotësia e Turing-ut kërkon vetëm katër lloje udhëzimesh – GOTO të kushtëzuar, GOTO të pakushtëzuar, caktim, HALT. Megjithatë, Kemeny dhe Kurtz vërejnë se, ndërsa përdorimi "i padisiplinuar" i GOTO-ve të pakushtëzuara dhe GOTO-ve të kushtëzuara IF-THEN mund të rezultojë në "kod spageti", një programues mund të shkruajë programe të strukturuara duke përdorur vetëm këto udhëzime; nga ana tjetër "është gjithashtu e mundur, dhe jo shumë e vështirë, të shkruash programe të strukturuara keq në një gjuhë të strukturuar". Tausworthe plotëson tre strukturat kanonike Böhm-Jacopini: SEKUENCA, IF-THEN-ELSE dhe WHILE-DO, me dy të tjera: DO-WHILE dhe CASE. Një përfitim shtesë i një programi të strukturuar është se ai i jep vetes prova të saktësisë duke përdorur induksionin matematik .

Statusi ligjor

Në vetvete, algoritmet zakonisht nuk janë të patentueshme. Në Shtetet e Bashkuara, një pretendim që përbëhet vetëm nga manipulime të thjeshta të koncepteve, numrave ose sinjaleve abstrakte nuk përbën "procese" (USPTO 2006), kështu që algoritmet nuk janë të patentueshme (si në Gottschalk kundër Benson). Megjithatë, zbatimet praktike të algoritmeve ndonjëherë janë të patentueshme. Për shembull, në Diamond kundër Diehr, zbatimi i një algoritmi të thjeshtë reagimi për të ndihmuar në kurimin e gomës sintetike u konsiderua i patentueshëm. Patentimi i softuerit është i diskutueshëm, dhe ka patenta të kritikuara që përfshijnë algoritme, veçanërisht algoritme të kompresimit të të dhënave, siç është patenta LZW e Unisys. Përveç kësaj, disa algoritme kriptografike kanë kufizime eksporti (shih eksporti i kriptografisë ).

Klasifikimi

Me anë të zbatimit

Rekursioni

Një algoritëm rekursiv e thërret veten në mënyrë të përsëritur derisa të përmbushë një kusht përfundimi dhe është një metodë e zakonshme e programimit funksional. Algoritmet iterative përdorin përsëritje të tilla si cikle ose struktura të dhënash si pirgje për të zgjidhur problemet. Disa probleme mund të jenë të përshtatshme për një implementim ose tjetrin. Kulla e Hanoit është një enigmë që zgjidhet zakonisht duke përdorur implementim rekursiv. Çdo version rekursiv ka një version iterativ ekuivalent (por ndoshta më shumë ose më pak kompleks) dhe anasjelltas.

Serial, paralele ose i shpërndarë

Algoritmet zakonisht diskutohen me supozimin se kompjuterët ekzekutojnë një udhëzim të një algoritmi në të njëjtën kohë në kompjuterë serialë. Algoritmet seriale janë projektuar për këto mjedise, ndryshe nga algoritmet paralele ose të shpërndara. Algoritmet paralele përfitojnë nga arkitekturat kompjuterike ku procesorë të shumtë mund të punojnë në një problem në të njëjtën kohë. Algoritmet e shpërndara përdorin makina të shumta të lidhura nëpërmjet një rrjeti kompjuterik. Algoritmet paralele dhe të shpërndara e ndajnë problemin në nënprobleme dhe i mbledhin rezultatet së bashku. Konsumi i burimeve në këto algoritme nuk është vetëm ciklet e procesorit në secilin procesor, por edhe mbingarkesa e komunikimit midis procesorëve. Disa algoritme renditjeje mund të paralelizohen në mënyrë efikase, por mbingarkesa e tyre e komunikimit është e kushtueshme. Algoritmet iterative janë përgjithësisht të paralelizueshme, por disa probleme nuk kanë algoritme paralele dhe quhen probleme seriale në thelb.

Determinist ose jo-determinist

Algoritmet deterministike e zgjidhin problemin me vendime të sakta në çdo hap; ndërsa algoritmet jo-deterministike i zgjidhin problemet nëpërmjet hamendësimit. Hamendësimet zakonisht bëhen më të sakta nëpërmjet përdorimit të heuristikës.

I saktë ose i përafërt

Ndërsa shumë algoritme arrijnë në një zgjidhje të saktë, algoritmet e përafrimit kërkojnë një përafrim që është afër zgjidhjes së vërtetë. Algoritme të tilla kanë vlerë praktike për shumë probleme të vështira. Për shembull, problemi i çantës së shpinës, ku ekziston një bashkësi sendesh, dhe qëllimi është të paketohet çanta e shpinës për të marrë vlerën maksimale totale. Çdo send ka një peshë dhe një vlerë të caktuar. Pesha totale që mund të mbahet nuk është më shumë se një numër i caktuar X. Pra, zgjidhja duhet të marrë në konsideratë peshat e sendeve, si dhe vlerën e tyre.

Algoritmi kuantike

Algoritmet kuantike funksionojnë në një model realist të llogaritjes kuantike. Termi zakonisht përdoret për ato algoritme që duken në thelb kuantike ose përdorin ndonjë veçori thelbësore të llogaritjes kuantike, siç është mbivendosja kuantike ose ngatërresa kuantike.

Sipas paradigmës së dizajnit

Për klasifikimin e algoritmeve një tjetër mënyrë është sipas metodologjisë ose paradigmës së tyre të projektimit. Disa paradigma të zakonshme janë:

Kërkim me forcë brutale ose i plotë

Forca brutale është një metodë zgjidhjeje problemesh që provon sistematikisht çdo opsion të mundshëm derisa të gjendet zgjidhja optimale. Kjo qasje mund të jetë shumë kohë-konsumuese, duke testuar çdo kombinim të mundshëm të variablave. Shpesh përdoret kur metodat e tjera nuk janë të disponueshme ose janë shumë komplekse. Forca brutale mund të zgjidhë një sërë problemesh, duke përfshirë gjetjen e rrugës më të shkurtër midis dy pikave dhe thyerjen e fjalëkalimeve.

Përça dhe sundo

Një algoritëm përçaj-dhe-sundo e redukton në mënyrë të përsëritur një problem në një ose më shumë raste më të vogla të vetes (zakonisht në mënyrë rekursive) derisa rastet të jenë mjaftueshëm të vogla për t'u zgjidhur lehtë. Renditja me bashkim është një shembull i përçaj-dhe-sundo, ku një listë e parenditur ndahet në mënyrë të përsëritur në lista më të vogla, të cilat renditen në të njëjtën mënyrë dhe më pas bashkohen. Në një variant më të thjeshtë të algoritmit përçaj-dhe-sundo të quajtur krasit dhe kërko ose algoritmi zvogël-dhe-sundo, i cili zgjidh një rast më të vogël të vetes dhe nuk kërkon një hap bashkimi. Një shembull i një algoritmi krasit dhe kërkimi është algoritmi i kërkimit binar .

Kërkim dhe numërim

Shumë probleme (si p.sh. loja e shahut) mund të modelohen si probleme në grafikë. Një algoritëm eksplorimi i grafikëve specifikon rregulla për lëvizjen rreth një grafiku dhe është i dobishëm për probleme të tilla. Kjo kategori përfshin gjithashtu algoritmet e kërkimit, numërimin e degëve dhe të kufizuara, dhe kthimin prapa.

Algoritmi i rastësishëme

Algoritme të tilla bëjnë disa zgjedhje rastësisht (ose pseudo-rastësisht). Ata gjejnë zgjidhje të përafërta kur gjetja e zgjidhjeve të sakta mund të jetë e pa mundur (shih metodën heuristike më poshtë). Për disa probleme, përafrimet më të shpejta duhet të përfshijnë njëfarë rastësie. Nëse algoritmet e rastësishme me kompleksitet kohor polinomial mund të jenë algoritmi më i shpejtë për disa probleme është një pyetje e hapur e njohur si problemi P kundrejt NP. Ekzistojnë dy klasa të mëdha të algoritmeve të tilla:

1. Algoritmet Monte Karlo kthejnë një përgjigje të saktë me probabilitet të lartë. P.sh. RP është nënklasa e këtyre që ekzekutohen në kohë polinomiale.
2. Algoritmet e Las Vegasit gjithmonë kthejnë përgjigjen e saktë, por koha e tyre e ekzekutimit është e kufizuar vetëm probabilistikisht, p.sh. ZPP.

Reduktimi i kompleksitetit

Kjo teknikë i transformon problemet e vështira në probleme më të njohura, të zgjidhshme me algoritme (shpresojmë) asimptotikisht optimale. Qëllimi është të gjendet një algoritëm reduktues, kompleksiteti i të cilit nuk dominohet nga algoritmet e reduktuara që rezultojnë. Për shembull, një algoritëm përzgjedhjeje gjen medianën e një liste të pa penditur duke e renditur së pari listën (pjesa e shtrenjtë) dhe pastaj duke nxjerrë elementin e mesëm në listën e renditur (pjesa e lirë). Kjo teknikë njihet edhe si transformo dhe pushto .

Gjurmimi prapa

Në këtë qasje, zgjidhje të shumëfishta ndërtohen në mënyrë graduale dhe braktisen kur përcaktohet se ato nuk mund të çojnë në një zgjidhje të plotë të vlefshme.

Probleme optimizimi

Për problemet e optimizimit egziton një klasifikim me specifik i algoritmeve; për probleme të tilla një algoritem mund të bjerë në një ose më shumë nga kategoritë e përgjithshme të përshkruara më sipër, si dhe në njërën nga kategoritë e mëposhtme:

Programimi linear

Kur kërkohen zgjidhje optimale për një funksion linear të lidhur nga kufizime lineare të barazisë dhe pabarazisë, kufizimet mund të përdoren drejtpërdrejt për të prodhuar zgjidhje optimale. Ekzistojnë algoritme që mund të zgjidhin çdo problem në këtë kategori, siç është algoritmi i njohur simpleks. Problemet që mund të zgjidhen me programim linear përfshijnë problemin e rrjedhës maksimale për grafet e drejtuara. Nëse një problem kërkon gjithashtu që ndonjë nga të panjohurat të jetë numër i plotë, atëherë ai klasifikohet në programim numër i plotë. Një algoritëm programimi linear mund ta zgjidhë një problem të tillë nëse mund të provohet se të gjitha kufizimet për vlerat e plota janë sipërfaqësore, d.m.th., zgjidhjet i plotësojnë këto kufizime gjithsesi. Në rastin e përgjithshëm, përdoret një algoritëm i specializuar ose një algoritëm që gjen zgjidhje të përafërta, varësisht nga vështirësia e problemit.

Programimi dinamik

Kur një problem tregon nënstruktura optimale – që do të thotë se zgjidhja optimale mund të ndërtohet nga zgjidhjet optimale të nënprobleve – dhe nënprobleme mbivendosëse, që do të thotë se të njëjtat nënprobleme përdoren për të zgjidhur shumë raste të ndryshme problemesh, një qasje më e shpejtë e quajtur programim dinamik shmang rishikimin e zgjidhjeve. Për shembull, algoritmi Floyd-Warshall, rruga më e shkurtër midis një kulmi fillestar dhe qëllimi në një graf të ponderuar mund të gjendet duke përdorur rrugën më të shkurtër drejt qëllimit nga të gjitha kulmet ngjitur. Programimi dinamik dhe memorizimi shkojnë së bashku. Ndryshe nga përçaj dhe sundo, nënproblemet e programimit dinamik shpesh mbivendosen. Dallimi midis programimit dinamik dhe rekursionit të thjeshtë është ruajtja në memorien e përkohshme ose memorizimi i thirrjeve rekursive. Kur nënproblemet janë të pavarura dhe nuk përsëriten, memorizimi nuk ndihmon; prandaj programimi dinamik nuk është i zbatueshëm për të gjitha problemet komplekse. Përdorimi i memorizimit, programimi dinamik, zvogëlon kompleksitetin e shumë problemeve nga eksponenciale në polinomiale.

Metoda e pangopur

Algoritmet lakmitare, ngjashëm me një programim dinamik, funksionojnë duke shqyrtuar nënstrukturat, në këtë rast jo të problemit, por të një zgjidhjeje të caktuar. Algoritme të tilla fillojnë me një zgjidhje dhe e përmirësojnë atë duke bërë modifikime të vogla. Për disa probleme, ata gjithmonë gjejnë zgjidhjen optimale, por për të tjerat mund të ndalen në optimumet lokale . Përdorimi më i popullarizuar i algoritmeve lakmitare është gjetja e pemëve minimale që përfshijnë grafe pa cikle negative. Pema Huffman, Kruskal, Prim, Sollin janë algoritme lakmitare që mund ta zgjidhin këtë problem optimizimi.

Metoda heuristike

Në problemet e optimizimit, algoritmet heuristike gjejnë zgjidhje afër zgjidhjes optimale kur gjetja e zgjidhjes optimale është jopraktike. Këto algoritme i afrohen gjithnjë e më shumë zgjidhjes optimale ndërsa përparojnë. Në parim, nëse ekzekutohen për një kohë të pafundme, ato do të gjejnë zgjidhjen optimale. Idealisht, ato mund të gjejnë një zgjidhje shumë afër zgjidhjes optimale në një kohë relativisht të shkurtër. Këto algoritme përfshijnë kërkimin lokal, kërkimin tabu, kalitjen e simuluar dhe algoritmet gjenetike . Disa, si kalitja e simuluar, janë algoritme jo-deterministike, ndërsa të tjerët, si kërkimi tabu, janë deterministikë. Kur dihet një kufi mbi gabimin e zgjidhjes jo-optimale, algoritmi kategorizohet më tej si një algoritëm përafrimi.

Shembuj

Input: A list of numbers L.
Output: The largest number in the list L.

if L.size = 0 return null
largest ← L[0]
for each item in L, do
    if item > largest, then
        largest ← item
return largest

Një nga algoritmet më të thjeshta gjen numrin më të madh në një listë numrash të renditur rastësisht. Gjetja e zgjidhjes kërkon qe te shikohet çdo numi në listë. Nga kjo rrjedh një algoritëm i thjeshtë, i cili mund të përshkruhet në anglisht të thjeshtë si:

Përshkrim i nivelit të lartë:

1. Nëse një bashkësi numrash është bosh, atëherë nuk ka numër më të madh.
2. Supozoni se numri i parë në bashkësi është më i madhi.
3. Për çdo numër të mbetur në bashkësi: nëse ky numër është më i madh se më i madhi aktual, ai bëhet më i madhi i ri.
4. Kur nuk kanë mbetur numra të pakontrolluar në bashkësi, konsiderojeni numrin më të madh aktual si më të madhin në bashkësi.

Përshkrim (kuazi-)formal: I shkruar në prozë, por shumë më afër gjuhës së nivelit të lartë të një programi kompjuterik, më poshtë është kodimi më formal i algoritmit në pseudokod ose kod pidgin:

Input: A list of numbers L.
Output: The largest number in the list L.

if L.size = 0 return null
largest ← L[0]
for each item in L, do
    if item > largest, then
        largest ← item
return largest

Kompleksiteti i algoritmeve

Analiza e algoritmeve

Analiza e algoritmit është një pjesë e rëndësishme e teorisë së kompleksitetit llogaritës, e cila siguron vlerësimin teorik për burimet e nevojshme të një algoritmi për të zgjidhur një problem specifik llogaritës. Analiza e algoritmeve është përcaktimi i sasisë së burimeve të kohës dhe hapësirës që nevojiten për ta ekzekutuar atë. Korrekësia dhe Efikasiteti janë dy elementet kryesore për tu analizuar gjatë ndërtimit të një algoritmi.

Kuptimi i “𝚶 – së madhe”

Kuptimi “Ο- e madhe” shërben për të vlerësuar rritjen e një funksioni pa u shqetësuar për shumëzuesit konstant apo terma të një rendi më të ulët se vetë funksioni. Në rastet kur inputi i një algoritmi shkon duke u rritur, përdoret kuptimi “Ο- e madhe” për të vlerësuar numrin e veprimeve që ai algoritëm përdorë.

Kuptimi matematikor “𝛰- e madhe” njihet si kuptim i limituar pasi që nuk ofron kufij të poshtëm.

Kuptimi “Ο- e madhe”  fillimisht u prezantua nga matematikani gjerman i njohur Paul Bachmann më 1892. Ky simbol përdoret në shkenca kompjuterike gjatë analizimit të algoritmeve dhe shpesh herë njihet si simboli Landau sipas matematicientit gjerman Edmund Landau, i cili përdori këtë nocion përgjatë punës së tij. Disa nga elementet kryesore janë “n” që ndryshe njihet si njësia hyrëse e një programi, T(n) – funksioni që e tregon kohën e ekzekutimit, dhe f(n) – funksion i thjeshtë.

Definicioni 1.

$T(n)=O(f(n))$ nëse ekzistojnë konstantet C dhe n₀ të tilla që $T(n)\leq c\cdot f(n)$ kur n ≥ n₀

Definicioni 2.

T(n) = Ω(f(n)) nëse ekzistojnë konstantet C dhe n₀ të tilla që $T(n)\geq c\cdot f(n)$ kur n ≥ n₀

Definicioni 3.

T(n) = Θ(h(n)) nëse ekzistojnë konstantet C dhe n₀ ashtu që T(n) = O(h(n)) dhe T(n) = Ω(h(n))

Definicioni 4.

T(n) = o(p(n)) nëse ekzistojnë T(n) = O(p(n)) dhe T(n) < p(n)

Disa rregulla:   Nëse T₁(n) = O(f(n)) dhe T₂(n) = O(g(n)) atëherë

                       T₁(n) + T₂(n) = max (O(f(n)), O(g(n)))

                       T₁(n) * T₂(n) = O(f(n) * g(n))

Përkufizim: Le të jenë dhënë dy funksione f dhe g me bashkësi fillimi 𝑍 (ose 𝑅) dhe bashkësi mbarimi 𝑅.

Themi se 𝑓(𝑥) është 𝛰 (𝑔(𝑥)) nëse ekzistojnë konstantet 𝐶 dhe 𝑘 të tilla që

|𝑓(𝑥)| ≤ 𝐶|𝑔(𝑥)|,                    ku 𝑥 > 𝑘.

Me rritjen e përmasave të inputit, rritet edhe koha që i duhet një algoritmi për të shkuar deri te zgjidhja e problemit. Vlerësimi “O“ i kompleksitetit në kohë tregon këtë rritje.

Vlerësimet “𝚶 – e madhe” për disa funksione të rëndësishme

Teorema 1 jep një rezultat të përgjithshëm për rritjen e polinomeve.

Le të jetë 𝑓(𝑥) = 𝑎_𝑛𝑥_𝑛 + 𝑎_𝑛−1𝑥_𝑛−1 + ⋯ + 𝑎₁𝑥 + 𝑎₀, ku 𝑎₀, 𝑎₁, . . . , 𝑎_𝑛 janë numra real konstant. Atëherë, 𝑓(𝑥) është Ο(x_n).

Vërtetim: Për 𝑥 > 1, përdorim mosbarazimin e trekëndëshit.

|𝑓(𝑥)| = |𝑎_𝑛𝑥_𝑛 + 𝑎_𝑛−1𝑥_𝑛−1 + ⋯ + 𝑎₁𝑥 + 𝑎₀ | ≤ |𝑎_𝑛 |𝑥 _𝑛 + |𝑎_𝑛−1 |𝑥 _𝑛−1 + ⋯ + |𝑎₁ |𝑥 + |𝑎₀ | = 𝑥_𝑛 (|𝑎_𝑛 | + |𝑎_𝑛−1 | 𝑥 + ⋯ + |𝑎₁ | 𝑥 _𝑛−1 + |𝑎₀ | 𝑥_𝑛 ) ≤ 𝑥_𝑛(|𝑎_𝑛 | + |𝑎_𝑛−1 | + ⋯ + |𝑎₁ | + |𝑎₀ |)

Gjatë këtyre kalimeve matematikore u përdor fakti që 𝑥_𝑛 > 1 duke qënë se 𝑥 > 1, e për rrjedhojë mund të shmanget vlera absolute. Gjithashtu, 1 𝑥_𝑖 , për 𝑖 = 1, . . . , 𝑛 është më e vogël se 1, duke qënë se 𝑥 > 1. Nëse shënojmë me 𝐶 = |𝑎_𝑛 | + |𝑎_𝑛−1 | + ⋯ + |𝑎₁ | + |𝑎₀ |, kemi që për 𝑘 = 1, |𝑓(𝑥)| ≤ 𝐶𝑥_𝑛 .

Pra, 𝑓(𝑥) është 𝛰(𝑥_𝑛 ).

Teoremë: Le të jenë dhënë dy numra real 𝑎 dhe 𝑏 më të mëdhenj se 1, dhe le të jetë 𝑥 një numër real pozitiv.

Atëherë, log_𝑎 𝑥 = log_𝑏 𝑥 log_𝑏 𝑎 ⟺ log_𝑏 𝑥 = log_𝑎 𝑥 ∙ log_𝑏 𝑎

Vërtetim: Për të treguar rezultatin e mësipërm, mjafton të tregojmë që 𝑥 = 𝑏 log_𝑏 𝑥 = 𝑏 log_𝑎 𝑥∙log_𝑏 𝑎 = (𝑏 log_𝑏 𝑎 ) log_𝑎 𝑥 = 𝑎 log_𝑎 𝑥 = 𝑥 .

Teoremë: Supozojmë që 𝑓₁(𝑥) është 𝛰(𝑔₁ (𝑥)) dhe 𝑓₂(𝑥) është 𝛰(𝑔₂ (𝑥)).

Atëherë, (𝑓₁ + 𝑓₂ )(𝑥) është 𝛰(max(|𝑔₁ (𝑥)|,|𝑔₂ (𝑥)|)).

Vërtetim: Meqënëse 𝑓₁(𝑥) është 𝛰(𝑔₁ (𝑥)) dhe 𝑓₂(𝑥) është 𝛰(𝑔₂ (𝑥)) , ekzistojnë konstantet 𝐶₁, 𝑘₁ dhe 𝐶₂, 𝑘₂ të tilla që |𝑓₁(𝑥)| ≤ 𝐶₁ |𝑔₁ (𝑥)|, për çdo 𝑥 > 𝑘₁ dhe |𝑓₂ (𝑥)| ≤ 𝐶₂ |𝑔₂ (𝑥)|, për çdo 𝑥 > 𝑘₂. Nëse 𝑥 > 𝑘₁ dhe 𝑥 > 𝑘₂, rrjedh se për 𝑥 ≥ max(𝑘₁, 𝑘₂ ) kemi të vërtetë |(𝑓₁ + 𝑓₂ )(𝑥) | = |𝑓₁ (𝑥) + 𝑓₂(𝑥)| ≤ |𝑓₁ (𝑥)| + |𝑓₂ (𝑥)| ≤ 𝐶₁ |𝑔₁ (𝑥)| + 𝐶₂ |𝑔₂ (𝑥)| ≤ (𝐶₁ + 𝐶₂ )|𝑔(𝑥)|

ku |𝑔(𝑥)| = max(|𝑔₁ (𝑥)|,|𝑔₂ (𝑥)|).

Kompleksiteti

Çdo objekt fizik përcaktohet nga hapësira dhe koha. Për të gjetur efektivitetin e programit, njohja e vlerësimit të tyre duke përdorur kompleksitetin e hapësirës dhe kohës, mund ta bëjë programin të sillet në kushtet optimale të kërkuara dhe duke e bërë këtë, bëhemi programues efikas.

Problemi i cili është i zgjidhshëm me anë të një algoritmi me kompleksitet polinomial, themi se edhe në rastin më të keq quhet i lehtë, sepse pritshmëria është që algoritmi do të ofroj zgjidhjen për problemin në një kohë relativisht të shkurtër. Nëse polinomi në vlerësimin “O- e madhe” ka shkallë të lartë (për shembull 100) ose në rastin kur koeficientët e tij janë ekstremisht të mëdhenj, algoritmit mund ti duhet një kohë shumë më gjatë për të zgjidhur problemin. Problemet të cilat nuk mund të zgjidhen nga algoritmet me kompleksitet polinomial, në rastin më të keq, quhen të vështirë. Problemet e ndryshme për të cilat nuk ekzistojnë algoritme që ofrojnë zgjidhjen e tyre quhen të pazgjidhshme. Vërtetimin e parë për ekzistencën e këtyre problemeve e ka dhënë matematikani dhe shkencëtari anglez Alan Turing.

Rasti më i keq

Me performancë më të keqe të një algoritmi kuptojmë numrin më të madh të veprimeve të nevojshme për të zgjidhur përmes algoritmit një problem të dhënë, me një input me një përmasë të caktuar. Në analizën e rastit më të keq, ne llogarisim kufirin e sipërm në kohën e funksionimit të një algoritmi. Analiza e performancës më të keqe na tregon se sa është numri i veprimeve që kërkon një algoritëm për të siguruar që të ofroj një zgjidhje.

Rasti mesatar

Analiza e rastit mesatar merret me gjetjen e numrit mesatar të veprimeve që nevojiten për të zgjidhur një problem, duke marrë parasysh të gjitha inputet e mundshme me një përmasë të dhënë. Pra, në analizën mesatare të rasteve, ne marrim të gjitha inputet e mundshme dhe llogarisim kohën e llogaritjes për të gjitha inputet. Analiza e rastit mesatar, zakonisht është më shumë e komplikuar se sa analiza e rastit më të keq.

Rasti më i mirë

Në analizën më të mirë të rastit, ne llogarisim kufirin e poshtëm në kohën e ekzekutimit të një algoritmi. Ne duhet të dimë rastin që shkakton një numër minimal operacionesh për t'u ekzekutuar. Analiza e rastit më të mirë është jo e vërtetë. Garantimi i një kufiri më të ulët në një algoritëm nuk jep ndonjë informacion, pasi që në rastin më të keq, një algoritmi mund të marrë vite për t'u ekzekutuar.

Kompleksiteti kohor

Kompleksiteti kohor është sasia e kohës që i duhet një algoritmi për tu ekzekutuar, në funksion të gjatësisë së hyrjes. Ai e mat kohën për të ekzekutuar çdo deklaratë të kodit në një algoritëm.

Ekziston një lidhje midis madhësisë së të dhënave hyrëse (n) dhe një numri operacionesh të kryera (N) në lidhje me kohën. Kjo lidhje njihet si rendi i rritjes në kompleksitetin kohor dhe jepet me O[n] ku O është rendi i rritjes dhe n është gjatësia e hyrjes.

Ekzistojnë lloje të ndryshme të kompleksiteteve kohore, si:

1. Koha konstante – O(1)

2. Koha lineare – O(n)

3. Koha logaritmike – O(log n)

4. Koha kuadratike – O(n²)

5. Koha kubike – O(n³)

Disa nga funksionet shumë më komplekse janë: koha eksponenciale, koha kuazilineare, koha faktoriale, etj. Të cilat përdoren varësisht nga lloji i funksioneve të përcaktuara.

Algoritmi Brute Force është një teknikë tipike e zgjidhjes së problemit ku zgjidhja e mundshme për një problem zbulohet duke kontrolluar secilën përgjigje një nga një, duke përcaktuar nëse rezultati plotëson deklaratën e një problemi apo jo. Algoritmi i forcës brutale zgjidhet në mënyrën më të drejtpërdrejtë, pa përfituar nga ndonjë ide që mund ta bëjë algoritmin më efikas. Kompleksiteti kohor i forcës brutale është O(m*n).

Kompleksiteti hapësinor

Kompleksiteti i hapësirës së një algoritmi paraqet hapësirën e marrë nga algoritmi në lidhje me madhësinë e hyrjes. Kompleksiteti hapësinor përfshin dy hapësira: ndihmëse dhe hapësirën e përdorur nga inputi.

Kompleksiteti hapësinor është një koncept paralel me kompleksitetin kohor. Nëse krijojmë një grup me madhësi n, ky grup do të kërkojë hapësirë O(n). Nëse krijojmë një grup dy-dimensional me madhësi n*n, kjo kërkon hapësirë O(n²).

Është më se e nevojshme të përmendet se kompleksiteti i hapësirës varet nga një një numër faktorësh si: gjuha programuese, përpiluesi, apo edhe makina që drejton algoritmin.

Shënimi	Tipi i KOMPLEKSITETIT
$O(1)$	Kompleksiteti konstant (i pavarur nga madhësia e të dhënave)
$O(log(n))$	Kompleksiteti logaritmik
$O(n)$	Kompleksiteti linear
$O(nlog(n))$	Kompleksiteti gati-linear
$O(n^{2})$	Kompleksiteti kuadratik
$O(n^{3})$	Kompleksiteti kubik
$O(n^{p})$	Kompleksiteti polinomial
$O(n^{\log(n)})$	Kompleksiteti gati-polinomial
$O(2^{n})$	Kompleksiteti ekspononcial
$O(n!)$	Kompleksiteti faktorial

Bibliografia

• Zaslavsky, C. (1970). Matematika e Popullit Joruba dhe e Fqinjëve të Tyre në Nigerinë Jugore. Revista Dyvjeçare e Matematikës së Kolegjit, 1(2), 76–99. https://doi.org/10.2307/3027363
• NIST Publikon 3 Standardet e Para të Finalizuara të Enkriptimit Post-Kuantum. https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards

Lidhje të jashtme

• Weisstein, Eric W. "Algorithm". MathWorld.
• Dictionary of Algorithms and Data Structures – National Institute of Standards and Technology
• Depozita e Algoritmit Stony Brook – Universiteti Shtetëror i Nju Jorkut në Stony Brook
• Algoritmet e Mbledhura të ACM – Shoqatat për Makineritë Kompjuterike
• Stanford GraphBase Arkivuar dhjetor 6, 2015, tek Wayback Machine – Universiteti i Stanfordit