IRAKASGAIAREN AZALPENA: Konputazio-zientzien arloan, informazioaren era guztietako tratamendua burutzeko gai diren sistemak garatzearen helburuak bi oztopo nagusi aurkitu ditu:

- Problema batzuentzat soluzioa aurkitzeko ezintasuna (problemak zailak direlako edo berez soluziorik ez dutelako).

- Beste problema batzuentzat, soluzio eraginkorra aurkitzeko ezintasuna (problema hauek trataezinak direla esan ohi da; izan ere, soluzioa lortzeko metodoak aurkitu arren, metodo horiek ez dira bideragarriak denbora edo memoria gehiegi behar dutelako).

Hori guztia dela eta, alde batetik, "konputazioa" ikuspuntu teorikotik aztertzera jo da, problema bakoitza konputagarria edo konputaezina bezala sailkatzeko asmoarekin eta, beste aldetik, konputagarriak diren problemen konplexutasuna ikuspuntu teorikotik aztertzeari ekin zaio, problema hauetako bakoitza tratagarria edo trataezina bezala sailkatzeko helburuarekin. Konputagarritasuna eta konputazioaren konplexutasuna aztertu ahal izateko, hainbat konputazio-eredu definitu dira (Turing-en Makinak, Lambda-kalkulua, Errekurtsioaren teoria, Lehen mailako logikako predikatuen kalkulua, eta abar). Irakasgai honetan, konputagarritasunaren azterketa aurrera eramateko, lengoaia formalen kontzeptua aurkeztuko da lehenik. Konputatzea, lengoaia formalek izan ditzaketen propietateak identifikatzeko balio duten estrategiak edo algoritmoak formulatzea izango da. Algoritmo horiek formulatzeko balio duten bi sistema matematiko edo konputazio-eredu aurkeztuko ditugu: lambda-kalkulua eta Turing-en makinak. Lambda-kalkulua konputagarritasuna lantzeko erabiliko dugu eta Turing-en makinak konputatzearen konplexutasuna aztertzeko erabiliko ditugu.

TESTUINGURUA: Irakasgai honetara iritsi aurretik (bigarren mailako lehenengo lauhilekoa) konputazio-problemak ebazteko balio duten prozeduren diseinua landu da beste irakasgai batzuetan. Konputazio-lanak burutzeko gai diren prozedurak garatzeko behar den oinarrizko ezagutza eta trebetasuna eskuratu ondoren, konputazioaren mugak ezagutzeko une egokiaren aurrean gaude (konputagarritasuna oro har eta, batez ere, konputagarriak diren problemen tratagarritasuna). Konputagarritasunaren funtsezko mugak ezagutu ondoren eta konputagarritasuna era egokiagoan ulertu ondoren, informazioaren tratamendu automatikorako prozeduren diseinuari buruzko ezagutza hobetuz eta sakonduz jarraitu daiteke (bigarren mailako eta ondorengo mailetako beste irakasgaien bidez).

IRAKASGAIARI DAGOZKION BEREZKO GAITASUNAK:



M02CM06: Teknologia informatikoen oinarrizko prozedura algoritmikoak jakitea eta aplikatzea arazoentzat soluzioak diseinatzeko, proposatutako algoritmoen egokitasuna eta konplexutasuna analizatuta.



M02CM015: Sistema adimendunen funtsezko printzipioak eta oinarrizko teknikak eta haien aplikazio praktikoa jakitea eta aplikatzea.

EDUKIEN ZERRENDA LABURRA:

Automatak, gramatikak, lengoaia formalak, konputabilitatea, konplexutasuna,

programazio paradigmak, adimendun sistemak.



EDUKIEN ZERRENDA:

Menoriarik gabeko konputazioa. Automatak eta itzultzaile finitoak. Lengoaia eta espresio erregularrak. Aplikazioak: analisi lexikoa.

Mugatutako Memoria. Piladun automatak. Kontesturik gabeko gramatikak eta lengoaiak. Mugatutako automata linealak. Aplikazioak: analisi sintaktikoa.

Konputagailuaren eredu orokorra eta bere mugak. Turing-en makina. Unibertsaltasun konputazional eta Church-Turing-en Tesia. Konputaezintasuna. Konplexutasun konputazionalera sarrera. Aplikazioak: gako publikoko kriptografia.

Konputazio eredu ezberdinak. Makina ereduak eta programazio paradigmak. Zirkuituak eta makina errealak. Programa agintzaileak, funtzionalak eta logikoak. Aplikazioak: Arrazonamendu automatikoa.

Problema-eredu ezberdinak. Espezifikazio ez-funtzionalak. Zuhaitz bidezko erabakitze metodoak. Sailkatzaileak. Probabilitate bidezko Programazioa. Aplikazioak: ikasten duten sistemak.

Ikastaroaren garapenean ikaslearen parte-hartze zuzena eta ikasteko era kooperatiboa eta dinamikoa bultzatzeko eta ikaslearen motibazioa indartzeko, talde-lana, eztabaida eta ariketen emaitzen aurkezpena hartuko dira klaseak antolatzeko oinarri gisa.

• Ebaluazio Jarraituaren Sistema
• Azken Ebaluazioaren Sistema
• Kalifikazioko tresnak eta ehunekoak:
  • Garatu beharreko proba idatzia (%): 60
  • Praktikak egitea (ariketak, kasuak edo buruketak) (%): 40

EBALUAZIO JARRAITUA:

Edukien zerrendako atal bakoitzean landutako gaitasunak ebaluatzeko, bost azterketa partzial egingo dira lauhilekoan zehar. azterketa partzial bakoitza hainbat ariketez osatuta egongo da. Azterketa partzial hauen bidez 10 puntu lortu ahal izango dira. Irakasgaiak guztira 10 puntu balioko ditu. Beraz, azterketa partzialen bidez irakasgaiaren 10 puntuak eskuratu daitezke. Irakasgaia gainditzeko 5 puntura iritsi beharko da 10 puntu horietatik. Ariketa bat gainditzeak ariketari dagokion atala liberatzea eta bere nota gordetzea dakar ikasturte osorako. Ariketa bat gainditzeko, ariketari dagokion puntuazioaren erdira iristea nahikoa izango da. Bukaerako notarako, gainditutako ariketei dagozkien puntuazioak bakarrik hartuko dira kontuan.



Ohiko eta ezohiko deialdietako probetan, lauhilekoan zehar gainditu gabe edo ebaluatu gabe gelditu diren atalak ebaluatuko dira.



BUKAERAKO EBALUAZIOA:

Ebaluazio jarraitua ez aukeratuz gero, lauhilekoaren bukaeran 10 puntu balioko dituen azterketa baten bidezko ebaluazioa egingo da. Hor ere, 5 puntu lortzea nahikoa izango da irakasgaia gainditzeko. Puntuazioa kalkulatzeko, gainditutako ariketak bakarrik hartuko dira kontuan (hau da, ariketa batean lortutako puntuazioa bakarrik ariketari dagokion puntuazioaren erdira iritsi bada hartuko da kontuan).



EZ AURKEZTUA:

"Ez aurkeztua" kalifikazioa ipintzeko honako irizpidea jarraituko da:

Ebaluazio jarraitua aukeratu duten ikasleen kasuan, lauhilekoan zehar egindako frogen bidez irakasgaia gainditzea ez bada lortu, ohiko deialdiari dagokion frogara ez aurkeztea nahikoa izango da "Ez aurkeztua" ipintzeko. Bukaerako ebaluazioa aukeratu duten ikasleen kasuan, ohiko deialdiari dagokion frogara ez aurkeztea nahikoa izango da "Ez aurkeztua" ipintzeko. Ezohiko deialdian ere era berean jokatuko da.



EBALUAZIO ERAREN ALDAKETA: EBALUAZIO JARRAITUTIK BUKAERAKO EBALUAZIORA

Hasieran "ebaluazio jarraitua" aukeratu duten ikasleek "bukaerako ebaluazioa" erara bukaerako azterketa baino lehenagoko edozein unetan aldatzeko aukera izango dute (bai ohiko deialdian eta bai ezohiko deialdian ere).



Goian zehaztutako ebaluazio-metodoa "Ikasleen Ebaluaziorako Arautegia" kontuan hartuta planteatu da:

https://www.ehu.eus/eu/web/estudiosdegrado-gradukoikasketak/ebaluaziorako-arautegia

Ohiko deialdirako zehaztu diren irizpide eta baldintzei eutsiko zaie.

eGela-n eskuragarri dagoen materiala (apunteak, ariketak eta abar).

Oinarrizko bibliografia

- J.E. Hopcroft, R. Motwani, J.D. Ullman: "Teoría de Autómatas, Lenguajes y Computación" 3ª ed. Pearson educación, 2007

- R. Brena; "Autómatas y Lenguajes. Un enfoque de diseño" Tec de Monterrey, 2003. [on line] Disponible en http://lizt.mty.itesm.mx/~rbrena/AyL.html

- S. Russell, P. Norvig: "Artificial Intelligence: A Modern Approach" 2ª ed. Prentice Hall, 2003

- Blas C. Ruiz, Francisco Gutiérrez, Pablo Guerrero, José E. Gallardo: "Razonando con Haskell. Curso sobre Programación Funcional". Thomson - Paraninfo, 2004

- Simon Thompson: "Haskell. The Craft of Functional Programming" Third Edition. Adison-Wesley, 2011

- Richard Bird; Itzulpena, Ricardo Peña Marí; berrikuspen teknikoa, María Alpuente Frasnedo, Salvador Lucas Alba: "Introducción a la programación funcional con Haskell" 2ª ed. Prentice Hall, 2000

Gehiago sakontzeko bibliografia

- E. Rich; "Automata, Computability and Complexity". Pearson Education, 2008
- S.H. Rodger, T.W. Finley; "JFLAP: An Interactive Formal Languages and Automata Package". Jones and Bartlett, 2006.
- D. Wood; "Theory of computation". John Wiley & Sons, 1987.
- S. Arora, B. Barak: "Computational Complexity: A Modern Approach" Cambridge University, 2009.
- T. Mitchell: "Machine Learning" McGraw Hill, 1997.
- G.F. Luger, W.A. Stubblefield: "Artificial Intelligence. Structures and Strategies for Complex Problem Solving." Benjamin/Cummings Publishing Company, Inc, 1998.

Aldizkariak

(Ezer ez)

Web helbideak

- Java Computability Tool kit (JCT): http://humboldt.sunyit.edu/jct/
- Visual and interctive tools (JFLAP): http://www.jflap.org/
- Machine Learning theory and examples: http://www.cs.cmu.edu/~avrim/ML07/index.html
- Implementación de algoritmos de IA en Java: http://code.google.com/p/aima-java/
- Haskell ikastaroa gaztelaniaz: http://aprendehaskell.es
- Haskell ikastaroa ingelesez: http://learnyouahaskell.com/chapters