Lankide:Doraemon Katu Kosmikoa/Proba orria

Algoritmoen diseinua

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, 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 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 implementazioa: Algoritmoa kode bihurtu.
8. Programaren egiaztapena: Algoritmoak behar bezala funtzionatzen duela frogatu.
9. Dokumentazioaren prestaketa: Algoritmoaren ezaugarriak jasotzen dituen dokumentu bat egitea.

Algoritmoa diseinatzeko paradigma

Paradigma komun batzuk hauek dira:

Indar basatia

Hau da irtenbide guztiak probatzen duena, ea zein den onena aurkitzeko.

Zatitu eta konkistatu

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 konkastatu 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 binarioaren algoritmoa da.

Bilaketa eta zenbaketa

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

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

Konplexutasunaren murrizketa

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

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