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.
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:
- Arazoaren definizioa
- Algoritmoa asmatu
- Algoritmoa programa bezala idatzi
- Soluzioa ebaluatu
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
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:
|
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: