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

- Problema batzuentzat soluzioa aurkitzeko ezintasuna.

- 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 (gainera, tratagarritasun eta trataezintasun mailak bereiziz). Irakasgai honetan, konputagarritasunaren azterketarekin hasteko, espezifikazio funtzionala eta espezifikazio ez-funtzionala zer diren azalduko da. Espezifikazio funtzionalik onartzen ez duten kalkuluak egiteko gai diren sistemei sistema adimendunak deitu ohi zaie (smart systems). Gu espezifikazio funtzionala duten kalkuluetan zentratuko gara konputagarritasuna aztertzeko orduan. Espezifikazio funtzionala duten kalkuluen konputagarritasuna aztertzeko helburuarekin, lengoaia formalen kontzeptua aurkeztuko da. Lengoaia formalei buruzko teoriak konputaezinak diren funtzioen existentzia era matematikoan frogatzea ahalbidetzen du. Baina lengoaia formalei buruzko teoria horrek ez du balio konputezinak diren funtzio konkretuak aurkitzeko. Ondorioz, konputazioaren teoriaren arloan hainbat konputazio-eredu definitu dira (Turing-en makinak, Lambda-kalkulua, Errekurtsioaren teoria, Lehen mailako logikako predikatuen kalkulua, eta abar). Konputazio-eredu horietako bakoitzean, algoritmoak nola adierazi behar diren eta algoritmo horiek nola egikaritu behar diren zehaztuko da. Konputazio-eredu konkretuen bidez konputaezinak diren funtzio konkretuak aurkitu daitezke. Lambda-kalkulua erabiliko dugu konputagarritasuna lantzeko eta konputezinak diren funtzio konkretuak aurkezteko. Bestalde, Turing-en makinen (edo automata orokorren) eredua ere aurkeztuko da. Turing-en makinen eredua konputatzearen konplexutasuna aztertzeko erabili ohi da askotan, baina analisi lexikoa eta analisi sintaktikoa egiteko ere erabil daiteke (hau da, egiturak eta formatuak identifikatzeko). Lambda-kalkulua funtzio bidezko programazio-lengoaien oinarritzat hartu daiteke eta Turing-en makinen eredua agindu bidezko programazio-lengoaien oinarritzat hartu daiteke.

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 konputazionala 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: Arrazoibide automatikoa.

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



GAI-ZERRENDA:

1. gaia: Sarrera

2. gaia: Sistema Adimendunak

3. gaia: Lengoaiak

4. gaia: Konputagarritasuna

5. gaia: Automata Finituak: Lengoaia Erregularrak

6. gaia: Automata Piladunak: Kontesturik Gabeko Lengoaiak

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 (%): 90
  • Praktikak egitea (ariketak, kasuak edo buruketak) (%): 10

EBALUAZIO JARRAITUA:

Edukien zerrendako atal bakoitzean landutako gaitasunak ebaluatzeko, lau 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 puntu lortzea nahikoa izango da. 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. Gai bakoitzari dagokion puntuazioa honako hau izango da: 1. gaia 0,5 puntu; 2. gaia 0,6 puntu; 3. gaia 1,95 puntu; 4. gaia 1,8 puntu; 5. gaia 4,15 puntu; 6. gaia 1,0 puntu.



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