Irakasgai honetako edukiak ordenagailu modernoen aurreko informatika teorikoaren adar klasiko batekoak dira. Automaten eta hizkuntza formalen teoriatik abiatzen da, programazio-lengoaien definizioan eta konpiladoreen eraikuntzan zuzenean aplikatzen dena.



Landutako formalismoei esker, konputagailu/konputazio kontzeptua abstraktu daiteke, algoritmoen konputagarritasuna, konplexutasuna eta tratagarritasuna aztertzeko; algoritmoen optimizazioan eta kriptografian erabiltzen dira algoritmoak.



Multzoen aljebra eta hizkuntzen zehaztapen/deskribapen formala erabiltzen dira; beraz, interesgarria da Gradu honetako lehen mailako Programazioaren Metodologia irakasgaia egin izana, eta bereziki zehaztapena.

- Konputazio-eredu murriztuen (automatak) edo alternatiboen (sistema adimendunak) bidez landu daitezkeen problemak identifikatzea eta ebaztea.

- Gramatikak eta adierazpen erregularrak erabiltzea hizkuntza formalak definitzeko

- Patroiak ezagutu eta prozesatzeko softwarea erabiltzea

- Prozesu konputazionalen berezko mugak eta haien ondorioak ulertzea

- Programazio-paradigmak eta konputazio-eredu alternatiboak ezagutu eta erabiltzea

- Problemak eta haien soluzio konputazionalak landu eta aztertzea, ahozko hizkuntza, hizkuntza matematikoa eta grafikoa erabiliz.

- Memoriarik gabeko konputazioa Automatak eta itzultzaile finituak. Hizkuntza eta adierazpen erregularrak. Aplikazioak: analisi lexikoa.

- Piladun automaten murriztapenak dituen memoria. Gramatikak eta testuinguruz kanpoko hizkuntzak. Automata lineal akotatuak. Aplikazioak: analisi sintaktikoa.

- Konputagailuaren eredu orokorra eta bere mugak Turing makinak. Unibertsaltasun konputazionala eta Church-Turing-en tesia. Konputaezintasuna. Konplexutasun konputazionalaren hastapenak. Aplikazioak: gako publikoko kriptografia.

- Konputazio-ereduaren alternatibak Makina-ereduak eta programazio-paradigmak. Zirkuitu eta makina errealak. Aginduzko programak, programa funtzionalak eta logikoak. Aplikazioak: arrazoitze automatikoa

- Arazo-ereduaren alternatibak Zehaztapen ez-funtzionalak. Erabaki-zuhaitzak. Sailkatzaileak. Probabilitate-programazioa. Aplikazioak: ikasten duten sistemak.

Eskola magistraletan (M) irakasgaiaren oinarri teorikoak deskribatzen dira, eta algoritmoak sartzen dira ikasgelan ebatzitako ariketa gisa. Laborategietan (PL) binaka ebazteko ariketa berriak proposatzen dira. Automaten simulagailuen bidez (JFLAP) egiaztatuko dira.

• Azken Ebaluazioaren Sistema
• Kalifikazioko tresnak eta ehunekoak:
  • Garatu beharreko proba idatzia (%): 75
  • Praktikak egitea (ariketak, kasuak edo buruketak) (%): 25

Irakasgaiaren notaren %25eko 3 azterketa partzial eginen dira. Deialdi arrunterako, lehenengo bi blokeetako bakoitzaren aukerako berrarrantza eginen da, nota hobetzeko.

Laborategiei notaren% 25 emanen zaie, eta bukatutakoan banakako probak eginen dira.

Etengabeko ebaluazioari uko eginez gero, notaren %100eko azken azterketa eginen da. Uko egite hori 9. astea baino lehen jakinarazi beharko zaio irakasleari, dagoen araudiaren arabera.

Azken probara agertzen ez bada, ez dela aurkeztu ulertuko da.

Aparteko deialdirako, notaren %100eko azken azterketa eginen da. Ez da aurreko ebaluazioen oharrik gorde.

- Irakasgaiaren aurkezpenak
- Ikasgaiaren adibide ebatziak
- Ikasgaiaren ariketak
- Emandako JFLAP simulagailua

Oinarrizko bibliografia

- Ramón F. BRENA; "Autómatas y Lenguajes. Un enfoque de diseño", Tec de Monterrey, 2003.

- Jean Gallier, "Introduction to the Theory of Computation", University of Pennsylvania, 2018.

- Elaine RICH, "Automata, Computability and Complexity. Theory and Applications", Pearson/Prentice Hall, 2008

- V. MATHIVET, "Inteligencia Artificial para desarrolladores. Conceptos e implementación en Java", ENI Ediciones, 2017

- J.E. HOPCROFT, R. MOTWANI, J.D. ULLMAN: "Teoría de Autommatas, Lenguaje y Computación" 3. arg. Pearson hezkuntza, 2007

- S. RUSSELL, P. NORVIG: "Artificial Intelligence: A Modern Approach", 2. arg. Prentice Hall, 2003

- S.H. RODGER, T.W. FINLEY; "JFLAP: An Interactive Formal Languages and Automata Package". Jones and Bartlett, 2006

Gehiago sakontzeko bibliografia

- S. ARORA, B. BARAK: "Computational Complexity: A Modern Approach" Cambridge University, 2009.
- D. WOOD; "Theory of computation". John Wiley & Sons, 1987.
- 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.

Web helbideak

- Visual and interctive tools (JFLAP): https://www.jflap.org/
- Machine Learning theory and examples: https://www.cs.cmu.edu/~avrim/ML07/
- Javan AA algoritmoak inplementatzea: https://github.com/aimacode/aima-java