Ordenagailu-programa baten bitartez ebazgarriak diren problemen zailtasun graduak identifikatzeko beharrezkoa den ezagutza barneratzea da "Konputazioaren Eredu Abstraktuak" ikasgaiaren helburua. Ikasgaiak "Konputazioa" espezialitatearen oinarrizko ikasgai bat da eta informatika teorikoaren arloan kokatzen da. Bigarren mailako "Lengoaiak; Konputazioa eta Sistema Adimendunak" ikasgaia du aurrekari.



Irakasgai honetan, kalkulu osoa duen eredu teoriko batetik abiatuta, programa informatikoen bidez soluzio zaila edo ezinezkoa dituzten arazoak daudela frogatuko da. Arazoen zailtasun gradu konputazionala frogatzea ahalbidetzen duten teknikak ere aztertuko dira.

IRAKASKUNTZAREN EMAITZAK:



1- Konputazio eredu abstraktu nagusiak ezagutu



2- Problema NP-Osoak eta laburketa polinomikoak ezagutu



3- Problema zailei aurre egiteko teknika ezberdinak ezagutu eta erabili



4- Problema erabakiezinak eta konputazioaren limiteak ezagutu

1. GAIA: Sarrera. Turing-en makinak. Church-en tesi hedatua. Algoritmoen analisia. O notazioa.



2. GAIA: SAT arazoa. NP-osoak. Laburketa polinomikoak. P ≠ NP galdera.



3. GAIA: Arazo zailak ekiteko teknikak. Hurbildutako ebazpenak. Ausazko ebazpenak.



4. GAIA: Konputazioaren mugak. Arazo erabakiezinak.

Gaitegiaren zati handi bat eskola orduetan aditzera emango zaie ikasleei ordu presentzial deitzen direnetan. Hala ere, ikasleek gaitegia lantzeko ardura izango dute eskola-ordu horietatik kanpo, emango zaizkien lan gehigarriak eginez.



Eskola orduetan eta sistematikoki, talde-lanak, eztabaida uneak eta ariketa praktikoen aurkezpenak garatuko dira, ikasleok ikasgaian duten partaidetza eta motibazioa bultzatzeko asmoz.

• Ebaluazio Jarraituaren Sistema
• Azken Ebaluazioaren Sistema
• Kalifikazioko tresnak eta ehunekoak:
  • Ehunekoak eta ebaluazio motak hurrengo ataletan zehazten dira (%): 100

Bi bide daude irakasgaia gainditzeko: ebaluazio globala (bukaeran), eta ebaluazio jarraitua.





EBALUAZIO JARRAITUA:



Ebaluazio jarraitua ikasleek beren borondatez baliatu ahal izango dute, irakasgaiaren jarraipen jarraitua egin dezaketen ikasleentzat eskaintzen da, aktibitate presentzialetarako ezarritako dedikazio eta asistentziak betez. Ikasleek uko egin diezaiokete ebaluazio jarraituari, baldin eta uko egite hori esplizitua egiten bada irakasgaiaren % 80 igaro baino lehen. Ikasleak ezingo dira ebaluazio jarraituaren bidez ebaluatu baldin eta ez badira ebaluagarriak diren jarduera guztietara aurkezten, eta ez badituzte ebaluazio-modalitate horretarako ezarritako gutxienekoak betetzen, jarraian zehazten direnak. Azken kasu horretan, ebaluazio globala egingo da.



Ebaluazio jarraituari dagozkion hiru proba idatzietan nota minimoa (% 30) lortu beharko da.



Probek balio hauek izango dituzte: % 25 + % 35 + % 20



Notaren gainerako % 20a ikasgelan proposaturiko beste jarduera batzuekin ebaluatuko da.



Ebaluazio jarraituan irakasgaia gainditzeko baldintzak:



- Froga idatzi bakoitzean gutxienez % 30eko nota lortzea

- Lan praktiko guztiak entregatzea

- Horiekin guztiekin, esandako haztapena aplikatu ondoren 5 edo nota altuagoa batzea





EBALUAZIO GLOBALA:



Ohiko deialdian idatzizko azterketa bakar bat, non irakasgaian landutako guztia sartzen den. Azterketa hori gainditu beharra dago (gutxienez 5 puntu 10etik atera behar da) irakasgaia gainditzeko.

Ez ohiko deialdian idatzizko azterketa bakar bat, non irakasgaian landutako guztia sartzen den. Azterketa hori gainditu beharra dago (gutxienez 5 puntu 10etik atera behar da) irakasgaia gainditzeko.

Oinarrizko bibliografia

Michael Sipser. “Introduction to the Theory of Computation: second edition”. PWS Publishing Company, Boston, 2006.



Michael Sipser. “Introduction to the Theory of Computation: third edition”. CENGAGE, 2013.



Susan.H. Rodger and Thomas.W. Finley. “JFLAP: an interactive formal languages ans automata package”. Jones & Bartlett Publishers, 2006.

Gehiago sakontzeko bibliografia

Sanjeev Arora and Boaz Barak. "Computational Complexity: A Modern Approach", Cambridge University Press, 2009

Efim Kinber and Carl Smith. "Theory of Computing: a gentle introduction", Prentice Hall, 2001

J. IBAÑEZ; A. IRASTORZA; A. SANCHEZ. "While programak. Konputagarritasun Teoria oinarritzeko tresna." Barne-txostena. UPV/EHU / LSI / TR 3-98.

J. IBAÑEZ; A. IRASTORZA; A. SANCHEZ. "Técnicas básicas de computabilidad". Barne-txostena. UPV/EHU / LSI / TR 3-2003.

J. IBAÑEZ; A. IRASTORZA; A. SANCHEZ. "Konputaezintasun frogapen batzuk diagonalizazio teknika erabiliz". Barne-txostena. UPV/EHU / LSI / TR 11-2000.

Web helbideak

http://www.jflap.org/

https://eu.udacity.com/course/intro-to-theoretical-computer-science--cs313

http://en.wikipedia.org/wiki/Theory_of_computation/

http://computational.complexity.googlepages.com/