informatika-2022-23: 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

Algoritmoaren kontzeptua

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

Arazoaren definizioa

Algoritmoa asmatu

Algoritmoa programa bezala idatzi

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 (zalantzagaritasunik 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

Ezagutzen ditugun algoritmo batzuk

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.

Algoritmoen adierazpenak

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:

Algoritmo baten adibidea

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:

Zenbaki osoen multzo batean zein da zenbakirik handiena?

Hainbat zenbaki teklatuaren bitartez irakurri eta guztien artean maximoa zehaztu. Hona hemen algoritmoa:

Zenbakien sorta batekin lan egingo dugu, zenbakien kopurua zehaztu

Sortaren lehen zenbakia irakurri

Lehen zenbaki hori maximoa da

Errepikatu zenbakien sorta amaitu arte:

Zenbaki berria irakurri

Zenbaki berria orain arteko maximoa baino handiagoa bada maximoaren balioa berritu

Maximoa erakutsi

Demagun iZenbakienKopurua kopuru osoa eta positiboa teklatuaren bitartez irakurriko dela, adibidez 5. Prozesu errepikakor batean 5-1=4 itzuli eman eta itzuliak kontrolatzeko k kontagailua erabili, 5-1=4 itzuliak amaitzean maximoaren balioa pantailaratu. Hau da algoritmotik eratorren taula:

k	iZbk	iMaximoa
–	8	8
2	11	11
3	4	11
4	23	23
5	17	23
		23

Algoritmotik programara jauzi egitean programazio-lengoaiaren elementuak aintzat hartuko dira eta jarraian baliokidean diren bi programa eskaintzen ditugu. Baliokideak izan arren bigarrena hobea da, lehen programak ez baitu algoritmoa zehatz-mehatz jarraitzen.

ZenbakiSortaBatenMaximoa_1.pas

Programa honek ez du goiko algoritmoa jarraitzen, zenbakiaren irakurketa guztiak prozesu errepikakorraren barruan egiten direlako. Horregatik iMaximoa aldagaiak hasieraketa berezi bat behar du derrigorrez:

{ Maximoaren hasieraketa berezia prozesu errepikakorra baino lehen }

program ZenbakiSortaBatenMaximoa_1 ;

uses
   crt ;
var
   iZenbakiKopurua, iZbk, iZenbatgarrena, iMaximoa, k : integer ;

begin
   clrscr ;
   writeln('Zenbaki positibo osoen sorta batean sartutako maximoa zehaztu') ;
   writeln('-------------------------------------------------------------') ;
   writeln ;
   
   repeat
      write('Zenbaki osoen kopuru eman: ') ;
      readln(iZenbakiKopurua) ;
   until iZenbakiKopurua > 0 ;
   
   iMaximoa := 0 ;     { maximoa bilatzen digulako, hasieraketa baliorik txikiena izan dadila; }
                       { hori dela eta, iMaximoa 0 delako, lehen itzulian iMaximoa aldatuko da }
   for k:=1 to iZenbakiKopurua do
   begin
      repeat
         write(k, '. zenbaki positiboa eman: ') ;
         readln(iZbk) ;
      until iZbk > 0 ;
      
      if iZbk > iMaximoa then      { oraintxe sartutakoa handiagoa denean }
      begin
         iMaximoa := iZbk ;
         iZenbatgarrena := k ;
         writeln('Une honetan, iMaximoa=', iMaximoa, ' eta iZenbatgarrena=', iZenbatgarrena) ;
      end ;
   end ;
   
   writeln ;
   writeln('Maximoa ', iMaximoa, ' izan da eta sortako ', iZenbatgarrena, '. izan da') ;
   
   repeat until keypressed ;
end.

ZenbakiSortaBatenMaximoa_2.pas

Goiko algoritmoa jarraituz, zenbakiaren lehen irakurketa prozesu errepikakorra baino lehen egiten delako iMaximoa aldagaiak hasieraketa berezerik ez du behar, iMaximoa hasiera iZbk izango delako:

{ Prozesu errepikakorra baino lehen maximoaren hasieraketa: iMaximoa:=iZbk; }

program ZenbakiSortaBatenMaximoa_2 ;

uses
   crt ;
var
   iZenbakiKopurua, iZbk, iZenbatgarrena, iMaximoa, k : integer ;

begin
   clrscr ;
   writeln('Zenbaki positibo osoen sorta batean sartutako maximoa zehaztu') ;
   writeln('-------------------------------------------------------------') ;
   writeln ;
   
   repeat
      write('Zenbaki osoen kopuru eman: ') ;
      readln(iZenbakiKopurua) ;
   until iZenbakiKopurua > 0 ;
   
   repeat
      write('Lehen zenbaki positiboa eman: ') ;
      readln(iZbk) ;
   until iZbk > 0 ;
   
   iMaximoa := iZbk ;              { lehen zenbakia iMaximoa da }
   iZenbatgarrena := 1 ;           { maximoaren posizioa 1 da   }
   for k:=2 to iZenbakiKopurua do
   begin
      repeat
         write(k, '. zenbaki positiboa eman: ') ;
         readln(iZbk) ;
      until iZbk > 0 ;
      
      if iZbk > iMaximoa then      { oraintxe sartutakoa handiagoa denean }
      begin
         iMaximoa := iZbk ;
         iZenbatgarrena := k ;
         writeln('Une honetan, iMaximoa=', iMaximoa, ' eta iZenbatgarrena=', iZenbatgarrena) ;
      end ;
   end ;
   
   writeln ;
   writeln('Maximoa ', iMaximoa, ' izan da eta sortako ', iZenbatgarrena, '. izan da') ;
   
   repeat until keypressed ;
end.

LetraSortaBatenMinimoa.pas

Zenbakiekin lan egin ordez karakterekin lan egingo bagenu, goiko algoritmoak berdin-berdin balio du. Jarraian ematen den programan ikusi larrien alfabetoko minimoa nola lortzen den:

{ Prozesu errepikakorra baino lehen minimoaren hasieraketa: cMinimoa:=cLetra; }

program LetraSortaBatenMinimoa ;

uses
   crt ;
var
   iLetraKopurua, iZenbatgarrena, k : integer ;
   cLetra, cMinimoa : char ;

begin
   clrscr ;
   writeln('Larrien alfabetoko letra sorta batean sartutako minimoa zehaztu') ;
   writeln('---------------------------------------------------------------') ;
   writeln ;
   
   repeat
      write('Zenbat letra sartuko duzu? kopuru osoa eta positiboa eman: ') ;
      readln(iLetraKopurua) ;
   until iLetraKopurua > 0 ;   
   
   repeat
      write('Lehen letra eman: ') ;
      readln(cLetra) ;
      cLetra := upcase(cLetra) ;
   until (cLetra >= 'A') and (cLetra <= 'Z') ;
   
   cMinimoa := cLetra ;             { lehen letra cMinimoa da  }
   iZenbatgarrena := 1 ;            { minimoaren posizioa 1 da }
   for k:=2 to iLetraKopurua do
   begin
      repeat
         write(k, '. letra eman: ') ;
         readln(cLetra) ;
         cLetra := upcase(cLetra) ;
      until (cLetra >= 'A') and (cLetra <= 'Z') ;
      
      if cLetra < cMinimoa then     { oraintxe sartutakoa txikiagoa denean }
      begin
         cMinimoa := cLetra ;
         iZenbatgarrena := k ;
         writeln('Une honetan, cMinimoa=', cMinimoa, ' eta iZenbatgarrena=', iZenbatgarrena) ;
      end ;
   end ;
   
   writeln ;
   writeln('Minimoa ', cMinimoa, ' izan da eta sortako ', iZenbatgarrena, '. izan da') ;
   
   repeat until keypressed ;
end.