5. jarduera | Algoritmoak

ZER DAKIDAN: Programa bat zer den badakit eta programak garatu ditudanean urratsak eman behar izan ditut. ZER IKASIKO DUDAN: Programa baten aginduek algoritmoren bat jarraitzen dutela ikasiko dut.

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 Ariketa 16 | Triangeluaren azalera adibidearen programa inkrementalki garatu genuenean algoritmo bat jarraitu genuela
• Biderkatzeko taularik gabe, biderkadura bat lortzeko algoritmoa 3. jarduera (III) | Errusiar Biderketaren Metodoa programatzen izeneko artikuluan jasota dago
• Funtzio baten erroak lortzeko Ariketa 28 | Newton-en hurbilketa-metodoa gogoratu ere
• Aukera askoren artean bat hautatzeko algoritmo desberdinak bildu dira Ariketa 36 | Hainbat aukeren menu bat artikuluan
• Algoritmo bat barneratzen duen Ariketa 33 | Fibonacci-ren zenbakiak artikulua gogoratu ere

Laster ikusiko ditugu beste algoritmo bi hauek: 7. jarduera (I) | Zenbaki bat asmatzen eta 7. jarduera (II) | 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

Hona hemen algoritmo hori C programazio-lengoaian ezarrita:

/* ZenbakiSortaBatenMaximoa.c */

// Zenbaki osoekin lan eginez. Sortaren luzera eskatu ondoren balio positiboak
// eman prozesu errepikakor batean eta iterazio bakoitzean maximoarekin geratu.

#include <stdio.h>

int main()
{
    int iZenbakiKopurua, iZbk, iMaximoa, iKont;

    printf("Zenbaki positibo osoen sorta batean sartutako maximoa zehaztu\n");
    printf("=============================================================\n\n");

    // 1. URRATSA: Zenbaki kopurua eskatu eta baieztatu kopurua > 0 dela
    do
    {
        printf("Zenbaki osoen kopuru eman: ");
        scanf("%d", &iZenbakiKopurua);
    } while (iZenbakiKopurua <= 0);
    printf("\n");

    // 2. URRATSA: Lehen zenbakia eskatu eta baieztatu > 0 dela
    do
    {
        printf("Lehen zenbaki positiboa eman: ");
        scanf("%d", &iZbk);
    } while (iZbk <= 0);

    // 3. URRATSA: Lehen zenbakia iMaximoa bezala ezarri
    iMaximoa = iZbk;

    // 4. URRATSA: Gainerako zenbakiak eskatu eta maximoa eguneratu
    for (iKont = 2; iKont <= iZenbakiKopurua; iKont++)
    {
        do
        {
            printf("%d. zenbaki positiboa eman: ", iKont);
            scanf("%d", &iZbk);
        } while (iZbk <= 0);

        if (iZbk > iMaximoa)
        {  // Zenbaki berria handiagoa bada, maximoa eguneratu
            iMaximoa = iZbk;
        }
    }

    // 5. URRATSA: Maximoa inprimatu
    printf("\nMaximoa = %d\n", iMaximoa);

    return 0;
}

Eta hemen algoritmo bera 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.

Eta hemen algoritmo bera Java programazio-lengoaian ezarrita:

import java.util.Scanner;

public class ZenbakiSortaBatenMaximoa {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int iZenbakiKopurua, iZbk, iMaximoa, iKont;
        
        System.out.println("Zenbaki positibo osoen sorta batean sartutako maximoa zehaztu");
        System.out.println("=============================================================\n");
        
        // 1. URRATSA: Zenbaki kopurua eskatu eta baieztatu kopurua > 0 dela
        do {
            System.out.print("Zenbaki osoen kopuru eman: ");
            iZenbakiKopurua = sc.nextInt();
        } while (iZenbakiKopurua <= 0);
        System.out.println();
        
        // 2. URRATSA: Lehen zenbakia eskatu eta baieztatu > 0 dela
        do {
            System.out.print("Lehen zenbaki positiboa eman: ");
            iZbk = sc.nextInt();
        } while (iZbk <= 0);
        
        // 3. URRATSA: Lehen zenbakia iMaximoa bezala ezarri
        iMaximoa = iZbk;
        
        // 4. URRATSA: Gainerako zenbakiak eskatu eta maximoa eguneratu
        for (iKont = 2; iKont <= iZenbakiKopurua; iKont++) {
            do {
                System.out.print(iKont + ". zenbaki positiboa eman: ");
                iZbk = sc.nextInt();
            } while (iZbk <= 0);
            
            if (iZbk > iMaximoa) {  // Zenbaki berria handiagoa bada, maximoa eguneratu
                iMaximoa = iZbk;
            }
        }
        
        // 5. URRATSA: Maximoa inprimatu
        System.out.println("\nMaximoa = " + iMaximoa);
        
        sc.close();
    }
}

Hauxe da hiru programa horien balizko irteera bat:

Maximoaren algoritmoa Java lengoaian, Pascal lengoaian eta C lengoaian ezarri da aurreko programetan, baina ez ahaztu algoritmo berbera ezar daitekeela beste edozein programazio lengoaiatan.

---

Ikusi maximo (edo minimo) algoritmo honen programazio desberdinak C lengoaian:

5a-MaximoarenAlgoritmoa.cbp | main.c Zenbakien sorta baten MAXIMOA (hasieraketarekin) 5b-MaximoarenAlgoritmoa.cbp | main.c Zenbakien sorta baten MAXIMOA (lehen irakurketa kanpoan) 5c-MaximoarenAlgoritmoa.cbp | main.c Letren sorta baten MINIMOA (lehen irakurketa kanpoan)