Academic management

The Computability course is included in the module of the subjects Common to Computer Science, and within the subject-matter of the degree called Computer Basics. Its teaching takes place in the first semester of the second year of the degree. This course is a natural continuation of another one included in the first year, called Automata and Discrete Mathematics, since through the different computation models progress is made in the study of Formal Languages, specifically Recursive and Recursively Enumerable Languages, and also in responding to the question of what problems can and cannot be solved computationally. The set of the two subjects constitutes the theoretical justification of important aspects of Computer Science and should make the student reflect on how it originated and developed. In addition, there are important relationships between Computability and the following courses in the degree:

Programming Methodology (First Year)

The way of presenting the computation models studied represents a way of introducing programming languages that we could call "theoretical". For the student this constitutes a different way of seeing different programming paradigms already covered in the first year.

Algorithmics (Second Year)

Much of Computability is dedicated to the study of what is and what is not computable. The design of algorithms for computable functions and the proof of the algorithmic unsolvability of problems is something that is very present.

Linear Algebra (First Year)

The first part of the Computability course includes all the Logic that the students will study during their stay in the degree. However, in the first year there are subjects of a mathematical nature, such as Linear Algebra, in which the proof methods and the notation used are related to simple aspects of Logic.

Other courses related to Computability are Design of Programming Languages (Third Year) and Intelligent Systems (Fourth Year).

Taking into account the previous section, it is essential that the student has previously taken the Automata and Discrete Mathematics course. It is also advisable that the student is familiar with the aspects covered in Programming Methodology, although this is not crucial. Finally, it is convenient for the student to have notions of notation and mathematical language, in addition to possessing some skill in proof methods.

The main competences and learning outcomes of this course are described below:

General competences

CG3:   Abstraction.

CG11: Team work.

CG25: Critical reasoning.

Basic training specific competences

Bas.3: Ability to understand and master the basic concepts of Automata and Discrete Mathematics, Logic, Algorithmics and Computational Complexity and their applications for solving engineering problems.

Computer Science branch specific competences

Com 6: Knowledge and application of the basic algorithmic procedures of computer technologies to design solutions to problems, analyzing the suitability and complexity of the proposed algorithms.

Learning outcomes

The expected learning outcomes related to the course are the following:

1. Know and handle the languages of Propositional Logic and Predicate Logic.
2. Represent domain information in formal languages of Logic.
3. Understand the concept of algorithm and know some computation model as a context for the construction of codes of computable functions.
4. Understand and assume the Church Thesis as a crucial aspect of Computing.
5. Know how to properly use the fundamental results of Computability.
6. Understand the concept of non-computable function and know techniques to try to differentiate what is and what is not computable.

Part 1. Logic Foundations

Topic 1. Propositional Logic

1. Syntax and semantics
2. Semantic proof methods
3. Conjunctive and Disjunctive Normal Forms and Propositional Resolution
4. Natural Deduction

Topic 2. Predicate Logic

1. Syntax and semantics
2. Clausal Form, Unification and General Resolution
3. Natural Deduction in Predicate Logic

Part 2. Computability Theory

Topic 3. Computation Models and Computable Functions

1. Introduction: Intuitive concept of algorithm
2. The model of While Programs
3. The model of Turing Machines
4. Church-Turing Thesis

Topic 4. Fundamental Results and Solvability of Problems

1. Enumeration of algorithms
2. Fundamental Theorems: Universality, Parametrization and Recursion
3. Algorithmic solvability and unsolvability
4. Introduction to Computational Complexity

According to EEES guidelines, the course consists of both in-class activities and autonomous work from the students.

The in-class activities will always count with the presence of the professor. These are divided into lectures, seminars, lab sessions, group mentoring sessions and evaluation sessions.

• Lectures: Taught to the entire group, not necessarily as a master lesson, but seeking an active participation of the student in their dynamics. In these classes the theoretical contents of the course will be developed, combined with the resolution of small exercises. The blackboard and different audiovisual media will be used.

• Seminars: Taught to smaller groups, approximately half of a complete group. These sessions will try to consolidate the knowledge presented in the lectures, describing examples and doing exercises. Student participation will be of greater intensity.

• Lab Sessions: Dedicated to solving exercises and practical problems using the PC whenever possible. They will be developed in several groups, in an eminently participatory way.

• Group Mentoring Sessions: Dedicated to clarifying doubts about theory, problems or work in progress. These activities may be used to check the degree of acquisition of competences and skills by the student. They will be developed in various groups, thus providing the students with a more personalized attention from the professor.

• Evaluation Sessions: They will be dedicated to the realization of written tests or with a PC, with which the level reached by the students in the acquisition of some of the foreseen competences can be evaluated objectively.

The teaching methodology to be used will be based on the active participation of the student, especially in the seminars, lab sessions and group mentoring sessions. If the size of the group allows it, activities and exercises will be proposed that involve the students and encourage their participation, either by solving the tasks privately or publicly in the classroom.

In addition, at the end of each of the topics, if the teachers deem it appropriate, a small exam may be carried out in order to know the degree of acquisition of the cognitive competences most related to the contents of the course.

With regard to the lab sessions, at the end of each of the scheduled sessions, the student may have to prepare a report to later submit it to the professor. Exercises could also be proposed to submit at the end of each lab session or small quizzes about the concepts worked, which the student must solve.

If the size of the group allows it, teaching methodologies will be used according to the size of the group.

Exceptionally, online evaluation methods might be established if the general health situation requires so. In that case, students will be informed in due course.

Below, series of tables are presented that specify the temporality of both in-class and off-class activities:

Estimated volume of work for the student

Distribution by blocks

Homework

In the ordinary evaluation, various procedures will be used that will allow the monitoring of the student's learning process.

The different evaluation procedures will be the following:

1. Evaluation of the midterm exams carried out at the end of each of the topics, as well as other activities proposed in the classroom.
2. Evaluation of the proposed quizzes and practical exercises.
3. Final evaluation: Written exam and practical evaluation.

• Lab practices: In the lab practices, exercises and quizzes will be proposed to be carried out in the session and the proposed solutions may be evaluated at the end of it.

• Midterm exams and activities in the classroom: The students may have to defend in the classroom some small exercises or tasks proposed periodically by the professors, either individually or in groups. The different midterm exams will also be carried out in the classroom after the contents have been taught.

The two previous points constitute the continuous assessment process and have a weight of 50% in the final grade of the course. Such weight is obtained considering 10% for the activities in the lab sessions and 40% for the midterm exams and the rest of the programmed evaluation activities.

• Final exam: It will consist of one or more tests of different character, with a weight of 50% in the final grade.

Exceptionally, online evaluation methods might be established if the general health situation requires so. In that case, students will be informed in due course.

Important remarks:

• Those students having obtained a grade greater than or equal to 5 points out of 10 in some of the parts of the program (Logic and Computability Theory) with the proposed midterm evaluations and activities, will have the possibility, if they decide so, of saving that part and not taking it in the final exam of the ordinary call, considering the obtained grade as the corresponding grade for that part in the final exam.

• The weight of each item in the evaluation of each of the two parts of the program will be proportional to the number of hours devoted in class to such part.

• The final grade for each of the parts of the course will be the maximum of the marks obtained in each part between the midterm evaluations and the final exam.

• The final grade of the course will be computed by summing the weighted grades obtained in the two parts, provided a minimum of 5 points out of 10 have been obtained in both of them. Otherwise, the final grade will be the minimum between 4 and that weighted average.

Summary of evaluation

Evaluation in the extraordinary calls

In the extraordinary calls students must take a written exam, that will represent 100% of the final grade and that will include the evaluation of both theoretical and practical sessions with the same weights as in the written exam of the ordinary call.

The final grade of the course in the extraordinary call will be computed by summing the weighted grades of the two parts obtained in the exam, subject to having reached a minimum of 5 points out of 10 in both of them. Otherwise, the final grade will be the minimum between 4 and such weighted average.

Exceptionally, online evaluation methods might be established if the general health situation requires so. In that case, students will be informed in due course.

Differentiated evaluation

Those students with the right of differentiated evaluation will be evaluated in the same way as in the extraordinary calls.

Resources, bibliography and complementary documentation

The basic and complementary bibliographic references that will be used in the course are included below. In addition, students will have other resources in the form of notes, slides, problem bulletins, standard exams, etc. that will be available to them on the Virtual Campus, which will also include notices, applets, other interesting links, etc.

Basic bibliography

1. L. Arenas, Lógica Formal para Informáticos, Díaz de Santos, ISBN: 84-7978-240-4 (1996)
2. J. Cuena, Lógica Informática, Alianza Editorial
3. Cutland, N. J, Computability: An Introduction to Recursive Function Theory. Cambridge University Press.
4. Garey, M.R.; Johnson, D.S. Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman & Company.
5. Kfoury, A. J., Moll, R. N., Arbib, M. A., A Programming Approach to Computability. Springer-Verlag, 1982.

Complementary bibliography

1. M. Ben-Ari, Mathematical Logic for Computer Science. Prentice-Hall
2. Huth, M.R.A., Ryan, M.D., Logic in Computer Science. Modelling and reasoning about systems. Cambridge University Press.
3. Kozen, D. C., Automata and Computability. Springer, 1997.
4. McNaughton, R. Elementary Computability, Formal Languages and Automata. Prentice-Hall
5. E. Burke and E. Foxley, Logic and Its Applications, Prentice Hall International, ISBN: 0130302635 (1996)