The main objective of "Abstract Computation Models" subject is to determine the computational difficulty of those problems that can be solved by a computer. This subject presents theoretical contents to distinguish whether a given problem is very difficult to compute or not. Morevover, we will see that there exist problems that cannot be solved by any computer. "Abstract computation models" subject complements the knowledge of the previous "Languages, Computation and Intelligent Systems" subject.

Competences:

1) Know basic Computability Theory concepts

2) Be able to formalize Computability Theory concepts

3) Realize that there are limits beyond which algorithmic methods do not work

5) Develop intuition about non computable and intratable problems

6) Know some Complexity classes and the relationship among them

7) Learn techniques for determining the computational difficulty of problems

1) Introduction. Turing machines. Church Thesis and Church Thesis extended. Asymptotic analysis. Big O Notation.



2) SAT problem. NP-complete problems. polynomial-time reductions. P versus NP question.



3) Techniques to deal with intractable problems. Aproximations. Randomness.



4) Limits of computation. More about undecidible problems.

Support material will be available in the eGela virtual classroom.



We will work with Python programming language in the laboratories.

• Continuous Assessment System
• Final Assessment System
• Tools and qualification percentages:
  • Véase la explicación en el apartado inferior (%): 100

The subject has two different kinds of assessments: final (or overall) assessment and continuous assessment.



Continuous assessment

---------------------



The student will voluntarily decide whether to take part or not in it, since it is offered exclusively for those students who can carry out continuous monitoring of the subject within the established dedication framework and can attend to presential activities.



Pre-enrolment in the continuous assessment mode will take place during the first week of the course. Pre-enrolment will become definitive after confirmation of the application by the student on established dates (around the 12th week of the course, with approximately 70% of the continuous assessment already completed) and after partial performance verification by the teaching staff. If the student does not confirm his or her definitive enrolment in the continuous assessment on the abovementioned dates, it will be understood that he or she dismisses the enrolment.



The course is mainly focused on continuous assessment.



Continuous assessment will be evaluated by means of three written exams, with a weight of 30, 40 and 20% of the overall grade of the subject. Besides, a 10% of the grade will be determined by laboratory work.



Additionally, a minimum of a 30% grade must be achieved in each written exam and a minimum of 5 over 10 is required to pass the subject.





Final Assessment

----------------



This kind of assessment will be applicable to students who do not wish to take part in continuous assessment or those who do not meet the criteria continuous assessment.



In this case, a single written exam about the 100% of the subject must be performed. It will be carried out according to the official examination schedule of the Faculty. The minimum grade required in the final exam will be 5 out of 10.

One single written exam about 100% of the subject in which the minimum grade is 5 out of 10.

Basic bibliography

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. “Introducción a la teoría de Autómatas, Lenguajes y Computación: 2ª edición”. Pearson educación, 2002



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.

In-depth bibliography

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. "LOS PROGRAMAS WHILE. Bases para una
teoría de la Computabilidad”. Informe interno. UPV/EHU / LSI / TR 5-96.

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

J. IBAÑEZ; A. IRASTORZA; A. SANCHEZ. "“Algunas demostraciones de incomputabilidad usando la técnica de diagonalización”. UPV/EHU / LSI / TR 8-2000.

Web addresses

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/