Algoritmoen Diseinua Konputazioa espezialitateko derrigorrezko irakasgaia da, Informatika Ingeniaritzako Graduko hirugarren mailan bigarren lauhilekoan ematen dena, eta, aldi berean, gradu bereko aukerakoa irakasgaia da Konputagailuen Ingeniaritza eta Softwarearen Ingeniaritza espezialitateetan.



Algoritmoen diseinua konputazio zientziaren giltzarrietako bat da. Algoritmoen eta datu-egituren ikasketek ezinbesteko garrantzia dute tamaina handiko problemei konputagailu bidezko soluzio eraginkorren garapenean. Honela, eremu horretan garatutako ezagutzak funtsezko garrantzia du zientzietako eta ingeniaritzetako problemei soluzio eraginkorrei aurre egiteko. Ezagutza horrek 2030eko Nazioarteko Agendako Garapen Iraunkorreko Helburu (GIH) batzuen asimilazioaren alde egiten du, hala nola Ekoizpen eta kontsumo arduratsua (12) eta Klima babesteko ekintza (13).



Irakasgai honetan algoritmo klasikoen bilduma bat aztertuko da, euren analisirako eta diseinurako teknikekin batera. Algoritmo hauek problema tipikoen soluzioen oinarri dira eta, aldi berean, aplikazio ugarien garapenean ere aplika litezke. Algoritmoen diseinua (AD) ikasgaia Datu egitura eta algoritmoak (DEA) ikasgaiaren jarraipen naturala da, eta DEAren ezagupen ona izatea guztiz komenigarria da ADri zailtasun gehiegirik gabe aurre egiteko. Gainera, Analisi matematikoa eta Matematika diskretua ikasgaietan eskuratutako oinarrizko ezagutzak freskatzea komeni da: multzoak, funtzioak, progresioak, limiteak eta logika formala. Alderantziz ere, AD ikasgaian ikasitakoak (diseinu teknikak, problemak ebazteko ahalmena eta euren eraginkortasuna) isla zuzena du beste zenbait ikasgaietan, hala nola eta bereziki Adimen artifiziala, Datu meatzaritza, Ikaskuntza automatikoa eta neurona sareak, Bilaketa heuristikoak eta Hizkuntzaren prozesamendua ikasgaietan.



Begiratu, ikasleentzat interesgarria izan daitekeela Algoritmoen diseinua irakasgaia parte den espezialitatearen webgunea: https://www.ehu.eus/documents/340468/3805395/Computacion.pdf/7f35158c-e98e-4033-96ad-e317377b604b . Bertan, espezialitateko jakintza-arloen aplikazio-eremuei buruzko informazioa dago, bai eta espezialitateko irakasgaiekin lotutako irteera profesional batzuei buruzkoa ere.

IKASKETA-EMAITZAK:

1. Algoritmo klasikoen eta datu-egitura aurreratuen katalogoa berrerabil daitekeen egoerak antzematen/ezagutzen ditu.



2. Algoritmoen diseinuaren eta eraginkortasunaren analisiaren oinarrizko teknikak irizpideekin aplikatzen ditu.



3. Kritikoki eta zehaztasun nahikoarekin aztertzen ditu hainbat soluzio algoritmiko, sailkatzeko eta egokiena aukeratzeko.



4. Maila akademiko honen berezko arazoen soluzio algoritmiko eraginkorrak diseinatzen ditu, behar bezala justifikatuta.

1. Algoritmoen eraginkortasunaren analisia

1.1 Algoritmoen analisirako oinarrizko kontzeptuak

1.2 Kostu algoritmikoaren analisia: kasu onena, txarrena eta batez bestekoa

1.3 Notazio asintotikoak eta horien erabilera funtzioen sailkapenetan

1.4 Errekurtsio-ekuazioen ebazpena

1.5 Adibideak: bilaketa, ordenazio eta errekurtsioa algoritmo klasikoak

1.6 Problemen ebazpenak



2. Datu-egitura aurreratuak

2.1 Grafoa

2.2 Meta

2.3 Partiketa



3. Grafo gaineko korritzeak

3.1 Sakonerako eta zabalerako korritzeak

3.2 Teknika erabiltzen duten algoritmo klasikoen aurkezpena eta bestelako problemen ebazpena: konektibitatea, bide motzenak, etab.



4. Zatitu eta irabazi teknika

4.1 Algoritmo diseinu-teknikaren azalpena

4.2 Teknika erabiltzen duten algoritmo klasikoen aurkezpena eta bestelako problemen ebazpena: bateraketa bidezko ordenazioa, ordenazio azkarra, K.ren hautaketa etab.



5.Programazio dinamikoaren teknika

5.1 Algoritmo diseinu-teknikaren azalpena

5.2 Teknika erabiltzen duten algoritmo klasikoen aurkezpena eta bestelako problemen ebazpena: Txanpon kopuru minimoen itzulera, motxila 0/1, eta abar.



6. Backtrack teknika

6.1 Algoritmoen diseinu-teknikaren azalpena

6.2 Teknika erabiltzen duten algoritmo klasikoen aurkezpena eta bestelako problemen ebazpena: Motxila, mapen koloreztapena, txanponak, etab.



7. Teknika jalea

7.1 Algoritmoen diseinu-teknikaren azalpena

7.2 Teknika erabiltzen duten algoritmo klasikoen aurkezpena eta bestelako problemen ebazpena: ekintza hautaketa, motxila zatiekin, hedapen zuhaitz minimoak, etab.

Irakasgai honetan irakaskuntza metodologia bat baino gehiago erabiltzen dira. Lan autonomoa indartuko da, baliabide informatikoak eta bibliografikoak erabilita, eta ikasleei lagunduko die horrek gaiaren hainbat alderdi ulertzen.



Irakasgaiaren eduki kontzeptualak azaltzeko klaseak (M) emango dira, eta ikasleek parte hartuko dute eduki horiei buruz noizbehinka egingo diren eztabaidetan. Ikasgelan, ikasleek zalantza eta problemen ebazpenean parte hartuko dute. Problemak eta ariketak jarriko zaizkie, bakarka edo taldeka egin ditzaten (GL). Horri esker, gaiaren alderdi teorikoan sakonduko dute, eta irakasgaia lotuko dute antzekoak diren beste arlo batzuekin.



Ikasleek hainbat proba egingo dituzte eta ikasturtean zehar puntuatuko dira (ariketak garatzea eta aurkeztea eta partzialak ebaztea), eta hautatutako ikasle batzuek inplementazioak egin ahal izango dituzte aukerako osagarri gisa.



Ikasketa-emaitzak gauzatzeko, ikasleek hainbat ariketa garatu, idatzi eta aurkeztu beharko dituzte mintegietan (gelako eta laborategiko eskola praktikoak). Laugarren ikasketa-emaitza proba partzialen bidez ebaluatuko da nagusiki.



Tekniken aplikazioa behar bezala dokumentatzea oso garrantzitsua denez, nahitaez bete beharreko dokumentazio eredu bat emango da, irakasgaiaren eGela ikastaroan eskuragarri egongo dena. Inplementatzeko, ikasleek nahi duten programazio-lengoaia erabili ahal izango dute (C, Python, Java, ...).



Ikasturtean zehar, banaka egin beharreko hainbat proba egingo dira, elkarlanean eta partzialki.

• Ebaluazio Jarraituaren Sistema
• Azken Ebaluazioaren Sistema
• Kalifikazioko tresnak eta ehunekoak:
  • Garatu beharreko proba idatzia (%): 50
  • alde lanak (arazoen ebazpenak, proiektuen diseinuak) (%): 50

Bi bide daude ikasgaia gainditzeko: Etengabeko ebaluazioa (jarraitua) edo Amaierako ebaluazioa.



ETENGABEKO EBALUAZIOA borondatezkoa da, eta ikaslearen parte-hartze aktiboa eskatzen du; beraz, ikasleak eskola eta ariketa saioetara etorri beharko du, haietan parte hartu, eta proposatutako jarduerak (ariketak, lanak, praktikak, azalpenak...) egin beharko ditu.



Etengabeko ebaluazioaren moduaren aurreinskripzioa automatikoa izango da, eta ebaluatutako jardueraren bat egin izanaren ondorioz gertatuko da. Etengabeko ebaluazioari uko egin nahi dioten ikasleek esplizituki idatziz adierazi beharko dute bigarren partzialaren aurretik.





Etengabeko ebaluazio hezitzailean, honako jarduerak burutuko dira azaldutako pisuekin:

(1) modu kolaboratiboan garatutako jarduerak: %50. (problemen garapena, test moduko galderen sortzea, inplementazioak, etab.)

(2) azterketa partzialak: %50. Ikasleen ezagutzak eta trebetasunak ebaluatzeko bi azterketa partzial egongo dira aste trinkoetan, bakoitzaren pisua irakasgaiaren azken notaren %25a delarik. Irakasgaia gainditu ahal izateko, azterketa partzial bakoitzean 10etik 2,5eko gutxieneko nota lortu beharko da. Bi partzialetara aurkeztuta, horietako batean gutxieneko nota lortu ez bada, azken notari ez zaizkio gehituko gainerako jarduera ebaluagarriak. Bi partzialetakoren batera aurkezten ez bada, edo lehenengoan gutxieneko nota lortu ez bada, ebaluazio jarraitua utzi eta azken ebaluaziora pasako da.



Gai eta diseinu-teknika bidezko problemen garapenen errubrikak irakasgaiaren eGelan daude, bai eta jarduera guztien data aipagarriak.



AMAIERAKO EBALUAZIOAn irakasgaiko edukien %100a neurtzeko idatzizko proba bat izango da, eta ikasleek ezagutzak eta trebetasunak erakutsi beharko dituzte. Proben data zehatzak irakasgaiari lotutako eGelan eta fakultateko web-atarian daude eskuragarri. Amaierako ebaluazioko proba idatzira aurkezten ez bada, ebaluazioari uko egiten zaiola ulertuko da.

EBALUAZIOAn irakasgaiko edukien %100a neurtzeko idatzizko proba bat izango da, eta ikasleek ezagutzak eta trebetasunak erakutsi beharko dituzte. Proben data zehatzak irakasgaiari lotutako eGelan eta fakultateko web-atarian daude eskuragarri. Amaierako ebaluazioko proba idatzira aurkezten ez bada, ebaluazioari uko egiten zaiola ulertuko da.

Irakasgaiaren ikasgela birtualean (eGelan) eskura dagoen materiala.

Oinarrizko bibliografia

- Cormen T.H, Leiserson C.E,, Rivest R.L. y Stein C: "Introduction to Algorithms", (4th edition), The MIT Press, (2022), Isbn: 978-0-262-04630-5



- Arruabarrena, R.: "Algoritmika". Ed. Udako Euskal Unibertsitatea, (1997). Isbn: 84-86967-82-1

(online eskura: https://ocw.ehu.eus/file.php/44/Bestelakoak/Algoritmika-RArruabarrena-UEU97.pdf)



- Arruabarrena, R., and Bermúdez, J.: "66 problemas resueltos de Análisis y Diseño de Algoritmos", (1999), http://hdl.handle.net/10810/42192

Gehiago sakontzeko bibliografia

- Kleinberg, J. and Tardos, E.: "Algorithm Design", 1st Edition, Pearson New International Edition, (2013), Isbn: 978-1292023946

- Dasgupta, S., Papadimitriou, C. H., and Vazirani, U. V.: "Algorithms", McGraw-Hill Education, (2006), Isbn: 978-0-07-352340-8

- Levitin, A.: "Introduction to The Design and Analysis of Algorithms". 3rd edition. Pearson International Edition, (2012), Isbn: 978-0-13-231681-1

- Brassard, G. and Bratley; P.: "Fundamentals of algorithmics". Prentice Hall, (1996), Isbn: 978-0-13-335068-5

Web helbideak

https://www.coursera.org/learn/algorithm-design-analysis
https://ocw.ehu.eus/course/view.php?id=44
http://ocw.ehu.es/file.php/107/diseno_alg/Course_listing.html
http://www3.cs.stonybrook.edu/~algorith/video-lectures/
https://xlinux.nist.gov/dads/