Algoritmoen diseinu

Wikipedia, Entziklopedia askea

Algoritmoen diseinuak arazoen soluzioari eta ingeniaritza algoritmoetarako metodo edo prozesu matematiko bati erreferentzia egiten dio. Algoritmoen diseinua ebakuntza-ikerketarako soluzio teoria askoren zati da. Algoritmoen diseinuak diseinatzeko eta aplikatzeko teknikak algoritmoen diseinu-ereduak ere deitzen dira[1], adibidez, metodo berritzailea eta dekorazio-patroia. Algoritmoen diseinuaren alderdirik garrantzitsuenetako bat goi borne asintotiko bezala ere ezagutzen den lasterketa-denbora eraginkorra duen algoritmoa sortzea da.

Algoritmoen garapena[aldatu | aldatu iturburu kodea]

Algoritmoen garapenean urrats tipikoak honakoak dira:

  1. Arazoen zehazketa: Algoritmoa konponduko duen arazoa behar bezala zehaztu behar da.
  2. Eredu baten garapena: Algoritmoak jarraituko duen ereduari buruz pentsatu behar da.
  3. Algoritmoaren zehazpena: Algoritmoaren funtzionamendu osoa argitu behar da.
  4. Algoritmoaren diseinua: Aurreko urratsetan zehaztu den modua jarraituz, algoritmoaren egitura eta behar diren diagramak sortu behar dira.
  5. Algoritmoaren zuzentasunaren frogaketa: Algoritmoak behar bezala funtzionatzeko funtsezko metodoen proba egokiak egin behar dira.
  6. Algoritmoaren azterketa: Kalkulu teorikoak egin behar dira arazo konputazional jakin bat konpontzen duen edozein algoritmok behar dituen baliabideetarako.
  7. Algoritmoaren inplementazioa: Algoritmoa kode bihurtu behar da.
  8. Programaren egiaztapena: Algoritmoak behar bezala funtzionatzen duela frogatu behar da.
  9. Dokumentazioaren prestaketa: Algoritmoaren ezaugarriak jasotzen dituen dokumentu bat egin behar da.

Algoritmoa diseinatzeko paradigma[aldatu | aldatu iturburu kodea]

Paradigma komun batzuk hauek dira:

Indar basatia[aldatu | aldatu iturburu kodea]

Horrek irtenbide guztiak probatzen ditu, onena zein den aurkitzeko[2].

Zatitu eta konkistatu[aldatu | aldatu iturburu kodea]

Algoritmo zatitzaile eta konkistatzaile batek behin eta berriz murrizten du problema baten instantzia bat problema beraren instantzia txikiago batera (normalean errekurtsiboki), kasuak erraz konpontzeko bezain txikiak izan arte. Zatiketaren eta konkistatzailearen adibide bat sailkatzea da. Datu-segmentu bakoitzean, sailkapena egin daiteke, datuak segmentuetan banatu eta datu osoak sailkatu ondoren, eta konkistatzaile fasean lortzen diren segmentuak elkartuz. Zatitzaile eta konkistatzaile aldagai xumeari gutxitu eta konkistatu algoritmoa deritzo, azpiarazo berdin bat ebazten duena eta azpiarazo horren soluzioa erabiltzen duena problema handiagoa konpontzeko. Zatitu eta konkistatzaileak arazoa azpiarazoetan banatzen du. Horregatik, konkistatzeko etapa konplexuagoa da gutxitu eta konkistatu algoritmoa baino. Gutxitu eta konkistatu algoritmoaren adibide bat bilaketa bitarren algoritmoa da.

Bilaketa eta zenbaketa[aldatu | aldatu iturburu kodea]

Arazo asko (xakean jokatzea, adibidez) grafoen problema gisa modelatu daitezke. Grafoen esplorazio-algoritmoak grafiko baten inguruan mugitzeko arauak zehazten ditu eta arazo horietarako baliagarria da. Gainera, kategoria honetan, bilaketa-algoritmoak, adarrak eta limiteak eta atzerapenak daude.

Ausazko algoritmoa[aldatu | aldatu iturburu kodea]

Ausazko algoritmoek aukera batzuk ausaz egiten dituzte. Oso baliagarriak izan daitezke arazoentzako soluzio hurbilduak aurkitzeko, non konponbide zehatzak aurkitzea inpraktikoa izan daitekeen[3].

Konplexutasunaren murrizketa[aldatu | aldatu iturburu kodea]

Teknika honek arazo zail bat konpontzen du, algoritmo asimetrikoak asimetrikoki optimizatuak ditugun problema ezagun bat bihurtuz. Helburua da algoritmo murriztaile bat aurkitzea, zeinaren konplexutasuna ez den menderatzen ondorengo algoritmo murriztuaren bidez. Konplexutasunaren murrizketa transformadore eta konkistatzaile bezala ere ezagutzen da.

Atzerako bilaketa[aldatu | aldatu iturburu kodea]

Hurbilketa horretan, hainbat konponbide eraikitzen dira eta bertan behera uzten dira, ezin dutela baliozko konponbide batera eraman erabakitzen denean.

Erreferentziak[aldatu | aldatu iturburu kodea]

  1. «algorithmdesign.net» www1.algorithmdesign.net Noiz kontsultatua: 2020-12-18.
  2. (Ingelesez) Daughtrey, Taz; Carroll, Sue. (2007-01-01). Fundamental Concepts for the Software Quality Engineer. ASQ Quality Press ISBN 978-0-87389-720-4. Noiz kontsultatua: 2020-12-18.
  3. Dyer, M.; Frieze, A.; Kannan, R.. (1989). «A random polynomial-time algorithm for approximating the volume of convex bodies» JACM doi:10.1145/102782.102783. Noiz kontsultatua: 2020-12-18.

Kanpo estekak[aldatu | aldatu iturburu kodea]