Algoritmoak

Algoritmo hitza, berez, IX. mendeko matematikari persiar baten izenetik eratortzen da: Al-Khwarizmi. Greziar tradizio matematikoak, nagusiki, geometriari buruz hitz egiten zuen, triangeluak, zirkuluak eta poligonoak bezalako formei buruz, eta azalera eta bolumena kalkulatzeko moduari buruz. Bestalde, Indiako matematikak kalkulua askoz sinpleagoa egiten zuen hamar sinboloko sistema hamartarrari esker. Al-Khwarizmiren ekarpena: Al-Khwarizmik greziar irudiak eta indiar sinboloak konbinatu zituen, gaur egun aljebra deitzen dugun pentsamendu matematikoari hasiera emanez.

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.

Abu Abdallah Muḥammad ibn Mūsā al-Jwārizmī (arabieraz: أبو عبد الله محمد بن موسى الخوارزمي ابو جعفر‎; c. 780 – c. 850), Al-Khwarizmi izenaz ezaguna. Al-Khwarizmi (Sobiet Batasuneko seilua, 1983)

Ada Lovelace, Augusta Ada Byron (Lovelaceko kondesa). Historiako lehen programatzailea izan zela esan ohi da, eta Charles Babbageren konputagailu mekanikoaren gaitasuna erakutsi zuen

Ada Lovelace eredutzat har daitekeen bezala, historian izan dira beste emakume zientzialari asko. Hona hemen, mosaiko txiki bat:

Guzti horien artetik pare bat aipatzearren, ondoko bi hauek nabarmenduko
genituzke: Hedy Lamarr ingeniaria eta Sofia Kovalevskaia matematikaria

Jarraian ondoko hauek ikusiko ditugu:

• Algoritmoaren kontzeptua
• Ezagutzen ditugun algoritmo batzuk
• Algoritmoen adierazpenak
• Algoritmo baten adibidea

Problema informatiko bati erantzuna emateko lau urrtas hauek bete behar dira:

1. Arazoaren definizioa
2. Algoritmoa asmatu
3. Algoritmoa programa bezala idatzi
4. Soluzioa ebaluatu

Beraz programa bat idatzi aurretik algoritmo bat asmatu beharra daukagu. Baina algoritmoa zer da? Intuitibori erraz definitzen da: lan bat exekutatzeko behar diren instrukzioen multzoa da algoritmoa.

Algoritmo kontzeptuaren definizioa: Problema baten ebazpena lortzen duen pauso-sekuentzia finitu, ordenatu eta anbiguotasun gabekoa [Knuth, 1968]. Edozein programak algoritmo bat dauka bere baitan, algoritmoak independenteak dira programa idaztean erabilitako programazio-lengoaiarekiko zein programa exekutatzen duen ordenagailuarekiko.

Algoritmoen ezaugarriak:

• Zehatza da (zalantzagarritasunik gabea)
• Pausoen kopurua finitua da
• Pausoen arteko ordena adierazi behar du
• Bukatu egin behar du
• Bi aldiz exekutatzean emaitza bera bueltatu behar du
• Programazio-lengoaiarekiko independentea da
• Dagokion programa exekutatzen duen ordenagailuarekiko independentea da

Dagoeneko programatzen ari garelako, konturatu ez garen arren, algoritmoak erabiltzen ari gara. Ikusitako algoritmo batzuei begirada bat bota diezaiegun:

• Gogoratu 3. astea | triangeluaren hirugarren erpina ariketaren algoritmoa
• Biderkatzeko taularik gabe, biderkadura bat lortzeko algoritmoa Errusiar Biderketaren Metodoa izeneko artikuluan jasota dago
• Funtzio baten erroak lortzeko 5. astea | Newton-Raphson hurbilketa-metodoa gogoratu ere
• Aukera askoren artean bat hautatzeko algoritmo desberdinak bildu dira 5. astea | menu bat artikuluan
• Itzuli kopuru jakin bat emateko algoritmoa 8. Ariketa: errepikapen kopuru ezaguna artikuluan ikasi genuen
• Muga batzuen arteko balio bat teklatuz irakurtzeko erabili genuen 9. Ariketa: errepikapen kopuru ezezaguna (I) artikuluko algoritmoa gogoratu ere

Laster ikusiko ditugu beste algoritmo bi hauek: 6. astea | zenbaki bat asmatzen eta 6. astea | letra bat asmatzen. 

Algoritmoak adierazteko funtsean bi modu daude:

• Lengoaia-naturala: sasikodea
• Modu grafikoa: fluxu-diagrama edo organigrama

Algoritmoen adibiderik klasikoenak errezetak dira, jarraian Pedro Subijana maisu famatuaren “Denok Sukaldari” liburutik hartutako algoritmoa ematen da:

Algoritmoak ideiak transmititzeko tresnak direnez grafikoak izan daitezke, jostailuak muntatzeko orrietan agertzen diren bezalakoak:

Algoritmoak adierazteko fluxu-diagramak erabiltzen dira, Esate baterako, Grezia zaharrean Euklides matematikariak gure egunetara iritsi den algoritmoa asmatu zuen bi zenbakien zatitzaile komunetako handiena z.k.h. lortzeko. Hauxe da Euklidesen algoritmoari dagokion fluxu-diagrama:

Adibide honetan zenbaki sorta baten maximoa zehaztuko dugu. Hemen algoritmoa:

Zehaztu zenbat zenbakik osatuko duten zenbakien sorta Sortaren lehen zenbakia irakurri Lehen zenbaki hori maximoa da Errepikatu zenbakien sorta amaitu arte: Zenbaki berria irakurri Zenbaki berria maximoa baino handiagoa bada maximoaren balioa berritu Maximoa erakutsi

Eta hemen algoritmo hori Pascal programazio-lengoaian ezarrita:

program ZenbakiSortaBatenMaximoa ;

uses
   crt ;
var
   iZenbakiKopurua, iZbk, iMaximoa, iKont : integer ;

begin
   clrscr ;
   writeln('Zenbaki positibo osoen sorta batean sartutako maximoa zehaztu') ;
   writeln('=============================================================') ;
   writeln ;
   
   (* --------------------------ALGORITMOAREN 1. URRATSA------------------ *)
   repeat
      write('Zenbaki osoen kopuru eman: ') ;
      readln(iZenbakiKopurua) ;
   until iZenbakiKopurua > 0 ;  
   writeln ;
   
   (* --------------------------ALGORITMOAREN 2. URRATSA------------------ *)
   repeat
      write('Lehen zenbaki positiboa eman: ') ;
      readln(iZbk) ;
   until iZbk > 0 ;
   
   (* --------------------------ALGORITMOAREN 3. URRATSA------------------ *)
   { lehen zenbakia iMaximoa da }
   iMaximoa := iZbk ;
   
   (* --------------------------ALGORITMOAREN 4. URRATSA------------------ *)
   for iKont:=2 to iZenbakiKopurua do
   begin
      repeat
         write(iKont, '. zenbaki positiboa eman: ') ;
         readln(iZbk) ;
      until iZbk > 0 ;
      
      if iZbk > iMaximoa then     { oraintxe sartutakoa handiagoa denean }
      begin
         iMaximoa := iZbk ;
      end ;
   end ;
   
   (* --------------------------ALGORITMOAREN 5. URRATSA------------------ *)
   writeln ;
   writeln('Maximoa = ', iMaximoa) ;
   
   repeat until keypressed ;
end.

Hauxe da programa horren balizko irteera bat:

Ikusi algoritmo honen programazio desberdinak:

• Zenbakien sorta baten MAXIMOA
• Letren sorta baten MINIMOA