Algoritmo

Algoritmo bat problema bat ebazteko eman behar diren urratsen deskribapen formala. Programazio-lengoaia baten bidez, algoritmoa ordenagailu batek egikari dezakeen programa bihur daiteke. Matematikan, informatikan, hizkuntzalaritzan eta beste zenbait esparrutan, algoritmo bat ongi definitutako instrukzio sekuentzia finitu bat da, ordenagailuz martxan jar daitekeena, normalean problema bat urratsez urrats ebazteko edo konputazio bat kalkulatzeko. Algoritmoak beti dira zehatzak, ez dira anbiguoak, eta jarraibide gisa erabiltzen dira kalkuluak egiteko, datuak prozesatzeko, datuak prozesatzeko, arrazoitze automatizaturako eta beste zeregin batzuetarako. Metodo eraginkor gisa, algoritmo bat espazio- eta denbora-kantitate finitu baten barruan eta ongi definitutako hizkuntza formal batean adieraz daiteke, funtzio bat kalkulatzeko.

Fluxu-diagramak sarritan erabiltzen dira algoritmoak grafikoki adierazteko.

Hasierako egoera batetik eta hasierako datu batetik ("sarrera") abiatuta (agian hutsik egongo da), instrukioek konputazio bat deskribatzen dute, eta, exekutatzen direnean, ondo definitutako ondoz-ondoko egoera-kopuru finitu baten bidez egiten da, eta, aldi berean, "irteera" sortzen da, eta amaierako egoeran amaitzen da. Egoera batetik bestera igarotzeko bideak ez du beti eredu determinista jarraitzen, zenbait algoritmok zorizko balioak ere integratzen baitituzte.

Historia. Kontzeptuaren bilakaera

Al-Khwarizmi (Sobiet Batasuneko seilua, 1983)

Makina Analitikoarekin Bernoulliren zenbakiak konputatzeko algoritmo baten diagrama, Ada Lovelaceren oharrekin.

Algoritmo hitza, berez, IX. mendeko matematikari persiar baten izenetik eratortzen da: Al-Khwarizmi.

XIX. mendean Ada Lovelace-k makina analitikoaren bidez Bernouilliren zenbakiak kalkulatzeko algoritmo bat idatzi zuen: zer eragiketa egin behar ziren, zer ordenan, zer aldagairen gainean, begiztak, baldintzen menpeko jauziak... Hori guztia ordenagailu baterako programa gisa har daiteke. Horregatik, historiako lehen programatzailetzat hartu izan da Lovelace.

Geroago algoritmoaren kontzeptu moderno bihurtuko zena formalizatzeko lehen urratsak berak egin zituen, David Hilbertek 1928an planteatutako Entscheidungsproblema (erabakitze-problema) ebazteko saiakerak egin ziren. Ondoren formalizazio berriak asmatu ziren "kalkulagarritasun eraginkorra" edo "metodo eraginkorra" definitzeko saiakera gisa. Formalizazio horien artean sartu ziren 1930eko, 1934ko eta 1935eko Gödel–Herbrand–Kleeneren funtzio errekurtsiboak, 1936ko Alonzo Church-en lambda kalkulua, 1936ko Emil Post-en 1 formulazioa, eta 1936-37 eta 1939ko Alan Turing-en Turing makinak.

Algoritmo baten adierazpen-baliabideak

Algoritmoak modu askotara adieraz daitezke, besteak beste, hizkuntza naturala, pseudokodoa, fluxu-diagramak eta programazio-lengoaiak. Hizkuntza naturaleko deskribapenak anbiguoak eta zabalak izan ohi dira. Pseudokodoa eta fluxu-diagramak erabiltzeak hizkuntza naturalaren anbiguotasun asko saihesten ditu. Adierazpen horiek algoritmoak irudikatzeko forma egituratuagoak dira; hala ere, programazio-lengoaia espezifiko batetik aparte mantentzen dira.

Algoritmo baten deskribapena hiru mailatan egin ohi da:

1. Goi-mailako deskribapena. Problema ezartzen da, eredu matematiko bat aukeratzen da eta algoritmoa hitzez azaltzen da, segur aski ilustrazioekin eta xehetasunik gabe.
2. Deskribapen formala. Pseudokodo bat erabiltzen da soluzioa aurkitzen duten urratsen sekuentzia deskribatzeko.
3. Inplementazioa. Algoritmoa programazio-lengoaia espezifiko batean edo jarraibideak gauzatzeko gai den objekturen batean adierazten da.

Algoritmoa zuzena dela, konplexutasun-azterketa dela edo biak direla frogatzen duen teorema ere sar daiteke.

Zenbaki baten erro karratua kalkulatzeko algoritmo bat adierazten duen fluxu-diagrama

Fluxu-diagrama

Fluxu-diagramak algoritmoen deskribapen grafikoak dira; geziekin lotutako ikurrak erabiltzen dituzte jarraibideen sekuentzia adierazteko, eta ISO arauak dituzte.

Fluxu-diagramak algoritmo txikiak irudikatzeko erabiltzen dira, espazio handia hartzen baitute eta egitura neketsua baitute. Irakurtzeko erraza denez, algoritmoetarako sarrera gisa, hizkuntza baten deskribapena egiteko eta konputazioaz kanpoko pertsonei prozesuak deskribatzeko erabiltzen dira.

Sasikode

Sasikodea algoritmo baten goi-mailako deskribapena da. Algoritmo horrek lengoaia naturala eta programazio-lengoaien berezko konbentzio sintaktiko batzuk nahasten ditu, hala nola esleipenak, zikloak eta baldintzazkoak, nahiz eta ez duen inolako estandarrik erabiltzen.

Sasikodea pertsonei algoritmo bat ulertzen laguntzeko pentsatuta dago, eta, beraz, inplementazio batean beharrezkoak diren xehetasun garrantzigabeak ken ditzake. Programatzaile desberdinek konbentzio desberdinak erabiltzen dituzte, programazio-lengoaia zehatzen sintaxian oinarrituta egon daitezkeenak. Hala ere,sasikodea, oro har, ulergarria da berariazko programazio-ingurune bat ezagutu edo erabili beharrik gabe, eta, aldi berean, nahikoa egituratua da hura zuzenean inplementatu ahal izateko.

Hala, sasikodea arestian aipatutako funtzioak betetzen ditu zerbait abstraktua irudikatzeko; protokoloak programaziorako lengoaiak dira. Bilatu iturri zehatzagoak gaia hobeto ulertzeko.

Sistema formalak

Automaten teoriak eta funtzio errepikakorren teoriak algoritmo kontzeptua formalizatzen duten eredu matematikoak ematen dituzte. Eredu ohikoenak Turing makina, erregistro-makina eta μ-recursivas funtzioak dira. Eredu horiek makina-lengoaia bezain zehatzak dira, eta ez dute lagunarteko adierazpiderik edo anbiguotasunik; hala ere, edozein konputagailurekin eta edozein inplementaziorekin zerikusirik ez dute.

Inplementazioa

Algoritmo asko programa batean ezartzeko asmatu dira. Hala ere, algoritmoak beste ingurune batzuetan ezar daitezke, hala nola neurona-sare batean, zirkuitu elektriko batean edo aparatu mekaniko eta elektriko batean. Algoritmo batzuk bereziki diseinatzen dira arkatza eta papera erabiliz inplementatzeko. Biderketa tradizionaleko algoritmoa, Euklidesen algoritmoa, Eratostenesen bahetzea eta erro karratua ebazteko modu asko adibide batzuk besterik ez dira.

Aldagaiak

Datu-mota jakin baten balio espezifikoak hartzen dituzten elementuak dira. Aldagai baten deklarazioa egiteko, var-a erabil daiteke. Nagusiki, bi modu daude aldagaiei hasierako balioak emateko:

1. Esleipen-epai baten bidez.
2. Datuak sartzeko prozedura baten bidez (adibidez, 'read').

Adibidea:

     ...
    i:=1;
    read(n);
    while i < n do begin
       (* cuerpo del bucle *)
       i := i + 1
    end;
     ...

Egitura sekuentzialak

Egitura sekuentzialean, ekintza batek segidako beste ekintza bati jarraitzen dio. Eragiketak bata bestearen atzetik gertatzen dira, halako moldez non baten irteera hurrengoaren sarrera baita, eta horrela hurrenez hurren, prozesua amaitu arte. Hori esleitzeko, balioak edo emaitzak memoriaren eremu batera pasatu behar dira. Eremu horri balioa hartzen duen aldagaiaren izena jarriko zaio. Esleipena honela sailka daiteke:

1. Sinpleak: Balio konstante bat aldagai batera pasatzea da (bidalitako15)
2. Kontagailua: Prozesu bat zenbat aldiz egiten den egiaztatzeko erabiltzen da (bidalketei a + 1)
3. Metagailua: Prozesuan batutzaile gisa erabiltzean datza (a bidali a + b)
4. Lanekoa: Aldagai asko (bidalketei c + b*1/2) eragiten dituen eragiketa matematiko baten emaitza jaso dezakezu.

Hamiltonen zikloaren problema bat konpontzen duen algoritmo baten eskematika

Algoritmoak funtzio gisa

Algoritmo bat problema baten datuak (sarrera) ebazpen baten datu (irteera) bihurtzen dituen funtzio gisa uler daiteke. Are gehiago, datuak bit-sekuentzia gisa adieraz daitezke, eta, oro har, edozein sinboloren sekuentzia gisa. Bit-sekuentzia bakoitzak zenbaki arrunt bat adierazten duenez (ikus Sistema bitarra), algoritmoak, funtsean, zenbaki arrunten funtzioak dira kalkula daitezkeen zenbaki arruntetan. Hau da, algoritmo orok funtzio bat kalkulatzen du, non zenbaki natural bakoitza problema edo ebazpen baten kodetzea baita.$f\colon \mathbb {N} \to \mathbb {N}$

Batzuetan, algoritmoak ezin dira inoiz amaitu, adibidez, begizta infinitu batera sartzen direnean. Hori gertatzen denean, algoritmoak ez du inoiz irteerako baliorik itzultzen, eta esan dezakegu funtzioa mugagabe geratzen dela sarrera-balio horretarako. Hori dela eta, jotzen da algoritmoak funtzio partzialak direla, hau da, ez dutela zertan definitu haien definizio-eremu osoan.

Funtzio bat baliabide algoritmikoen bidez kalkula daitekeenean, betetzen duen memoria kopurua edo berandututako denbora kontuan hartu gabe, funtzio hori konputagarria dela esaten da. Datu-sekuentzien arteko funtzio guztiak ez dira konputagarriak. Geldialdiaren arazoa adibide bat da.

Algoritmoen analisia

Algoritmo baten eraginkortasunaren neurri gisa, algoritmoak kontsumitzen dituen baliabideak (memoria eta denbora) aztertzen dira. Algoritmoen analisia egin da, sarrera-balioen tamainaren arabera denbora- eta memoria-gastuaren bilakaera nolabait adierazten (edo zehazten) duten balioak lortzeko.

Algoritmoen azterketa eta azterketa konputazio-zientzien diziplina bat da, eta, kasu gehienetan, haien azterketa guztiz abstraktua da inolako programazio-hizkuntzarik edo beste edozein inplementaziorik erabili gabe; horregatik, alde horretatik, bat dator matematika-diziplinen ezaugarriekin. Hala, algoritmoen analisia algoritmoaren oinarrizko printzipioetan oinarritzen da, ez ezarpen partikularrean. Algoritmo bat irudikatzeko (edo batzuetan "kodetzeko") modu bat da pseudokodoan idaztea edo Lexico bezalako hizkuntza sinple bat erabiltzea, zeinaren kodeak programatzailearen hizkuntzan egon baitaitezke.

Zenbait idazlek algoritmoaren definizioa mugatu egiten dute uneren batean amaitu behar diren prozeduretara; beste batzuek, berriz, betiko eten gabe exekuta daitezkeen prozeduratzat hartzen dituzte, betiko funtziona dezakeen gailu fisikoren bat balego bezala. Azken kasu horretan, algoritmoa arrakastaz amaitzea ezingo litzateke esan algoritmoaren amaiera gisa, irteera egoki batekin, baizik eta arrakasta algoritmoa exekutatzen den bitartean emandako irteera-sekuentzien arabera definituko litzateke. Adibidez, sekuentzia bitar infinitu batean bat baino zero gehiago daudela egiaztatzen duen algoritmo bat exekutatu egin behar da beti balio erabilgarri bat itzuli ahal izateko. Zuzen ezartzen bada, algoritmoak itzultzen duen balioa baliozkoa izango da hurrengo digitu bitarra ebaluatu arte. Horrela, hurrengo sekuentzia ebaluatzen den bitartean, bi seinale mota irakur daitezke: seinale positibo bat (bat baino zero gehiago bada) eta, bestela, seinale negatibo bat. Azkenik, algoritmo horren irteera balio positiboen itzulketa gisa definitzen da, baldin eta bat baino zero gehiago badaude sekuentzian, eta, beste edozein kasutan, seinale positiboen eta negatiboen nahasketa bat itzuliko du.

Bi zenbakien arteko zatitzaile komunetako handiena kalkulatzeko algoritmoa.

Algoritmoaren adibidea

Problema zenbaki-multzo baten maximoa aurkitzea da. Adibide konplexuago baterako, ikus Euklidesen algoritmoa.

Goi-mailako deskribapena

Zenbaki-multzo finitu bat emanda, zenbakirik handiena aurkitzeko arazoa dago.$C$ Orokortasunik galdu gabe, onar daiteke multzo hori ez dela hutsa eta bere elementuak honela zenbakituta daudela:$c_{0},c_{1},\dots ,c_{n}$

Hau da, multzo bat emanda, multzoari dagokion elementu ororentzat aurkitzea eskatzen da.$C=\{c_{0},c_{1},\dots ,c_{n}\}$$m$$x\leq m$$x$$C$

Elementu maximoa aurkitzeko, lehenengo elementua () maximoa dela jotzen da; gero, multzoa zeharkatu eta balio bakoitza ordura arte aurkitutako zenbaki maximoaren balioarekin alderatzen da.$c_{0}$ Elementu bat maximoa baino handiagoa bada, haren balioa maximoari esleitzen zaio. Zerrenda amaitzen denean, multzo osoaren maximoa aurkitu da.

Deskribapen formala

Algoritmoa modu formalagoan idatz daiteke sasikodigo batekin.

Notazioari buruz:

• "Esleipen bat adierazten du": “Aldagaiak honako honen balioa hartzen duela adierazten du:$m$$x$$m$$x$
• "devolver"-ek algoritmoa amaitzen du eta balioa eskuinean itzultzen du (kasu honetan, -ren maximoa).$C$

Inplementazioa

C++ lengoaian:

int max(int c[], int n)
{
   int i, m = c[0];
   for (i = 1; i < n; i++)
      if (c[i] > m) m = c[i];
   return m;
}

Algoritmoak diseinatzeko teknikak

• Algoritmo bortitzak (greedy): hautagaien multzoan etorkizun handiena duten elementuak hautatzen dituzte irtenbide bat aurkitu arte. Kasu gehienetan, emaitza ez da optimoa.
• Algoritmo paraleloak: problema bat azpiproblemetan zatitzeko aukera ematen dute, zenbait prozesadoretan aldi berean exekutatu ahal izateko.
• Probabilitate-algoritmoak: horrelako algoritmoen urratsetako batzuk balio pseudoaleatorioen arabera daude.
• Algoritmo deterministikoak: algoritmoaren portaera lineala da: algoritmoaren urrats bakoitzak ondorengo urrats bat eta aurrekari bat besterik ez ditu.
• Algoritmo ez-deterministikoak: algoritmoaren portaerak zuhaitz-forma du, eta, algoritmoaren urrats bakoitzean, ondo-ondoko edozein urratsetara adarkatu daiteke; gainera, adar guztiak batera exekutatzen dira.
• Zatitu eta irabazi egingo duzu: arazoa disjuntoen azpimultzoetan zatitzen dute, eta azpimultzo bakoitzak emaitza bat ematen du, ondoren batu eta, hala, problema osoari konponbidea ematen zaio.
• Metaheuristikoak: problemen gutxi gorabeherako konponbideak aurkitzen dituzte (ez optimoak), haien aurreko ezagutzan oinarrituta (batzuetan esperientzia deitua).
• Programazio dinamikoa: problemak ebazten saiatzen da, kostu konputazionala gutxituz, kostu espaziala handituz.
• Adarkatzea eta akotazioa: arazoari irtenbideak ematean oinarritzen da, zuhaitz inplizitu baten bidez. Zuhaitz hori modu kontrolatuan zeharkatzen da eta soluziorik onenak aurkitzen ditu.
• Atzerako itzulera (backtracking): arazoari irtenbidea emateko espazioa eraikitzen da zuhaitz batean. Zuhaitz hori erabat aztertzen da, eta ahalik eta konponbide merkeenak biltzen dira.

Ikus, gainera

• Nagle algoritmoa

Kanpo estekak

• Algoritmoak, Gizapedian.
• (Ingelesez)Munduan gehien erabiltzen diren 10 algoritmoak

• Datuak: Q8366
• Multimedia: Algorithms