template-browser-not-supported

Grado en Ingeniería Informática en Tecnologías de la Información

Back Back

Computabilidad

Código asignatura
GIITIN01-2-004
Curso
Segundo
Temporalidad
Primer Semestre
Materia
Fundamentos de Computación
Carácter
Obligatoria
Créditos
6
Pertenece al itinerario Bilingüe
Yes
Actividades
  • Prácticas de Aula/Semina (7 Hours)
  • Tutorías Grupales (2 Hours)
  • Clases Expositivas (28 Hours)
  • Prácticas de Laboratorio (21 Hours)
Guía docente

The course on Computability, together with the course on Automaton and Discrete Mathematics, conforms the block of Fundamentals of Computation (FC), which is a part of the module Fundamentals of Engineering (FE) together with Fundamentals of Physics and Fundamentals of Mathematics blocks. The course takes place in the first semester of the second year of the Degree. It states a natural continuation of the first year course on Automaton and Discrete Mathematics. During the study of the latter, the students learn about Formal Languages, especially about recursive languages and recursively enumerable languages. The course on computability extends this basis by introducing different models of computation. The union of both courses establishes the theoretical fundamentals of computing, and it aims to make the students ponder the origin and development of Computer Science and Computer Engineering. In addition, there are important connections between the course on Computability and the following courses in the degree:

Programming Methodology (First year): The way in which the different computational models are introduced in the computability course provides the students with a knowledge on, what can be considered as, theoretical programming languages. This gives the students a different point of view so they can have a deeper understanding of the coding paradigms they have learnt in this previous course.

Algorithmia (Second year): A significant part of the contents of the Computability course focuses on determining what is, and is not, computable. The design of algorithms for computable functions and the capacity to demonstrate the non-solvability of certain problems is of great relevance in Computer Science and of key importance for this course.

Linear Algebra (First year): The first part of the computability course focuses on the study of Logic, which will be further studied in later years. However, it is in the first year, in the course on linear algebra, where the students start learning about proof methods and the notation that is useful to learn Logic.

Furthermore, computability has also close ties with the course on Intelligent Systems (third year). In fact, Logic is an important part of Artificial Intelligence, since it can be used as an analysis tool, a knowledge-based system or as a programming language. Moreover, the identification of difficult-to-solve problems is key to determine when Artificial Intelligence techniques are required. It is in the course on Computability that the students start to acquire the ability to assess the hardness or easiness of different problems.

Based on the previous context description, it is essential for the students to have previously passed the course on Automaton and Discrete Mathematics. At the same time, it is advised to have passed the course on Programming Methodology. Finally, it is desirable that the student possesses some basic skills on the use of notation and mathematical language, as well being fluent in proof methods.

The target of this course is to provide the students with the following set of skills:

  1. Apply the acquired knowledge to construct and defend logical arguments that allow the students to spread information, ideas, problems and solutions to both a specialized and a non-specialized public.
  2. Have initiative to solve problems, taking informed decisions and being autonomous and creative.
  3. Reason in a critical and logical way.
  4. Have a deep knowledge on the fundamentals of computation and apply it to understand, select, estimate, model and create new concepts, theories and technological advances.

Achieving these goals will provide the students with many of the basic and general competencies, as well as some of the specific ones mentioned in the Verification Document (Memoria de Verificación). According to this document, the basic and general competencies that are cross-cutting, are based on the recommendations, among others, of the CODDII (Conferencia de Directores y Decanos de Ingeniería Informática) and the curriculums of ACM/IEEE. Even though these are cross-cutting competencies, and therefore are tackled in different courses, the course on Computability contributes significantly to the following ones:

Basic (CB) and General (CGR) Competencies:

CB2. Students will be able to apply the acquired knowledge on their working environment in a professional manner. They will be capable of having productive discussions by using strong and reasonable arguments, as well as knowing how to approach and solve problems in their field of study.

CB3. Students will have enough skills to collect and correctly interpret relevant data (especially in their field of study) in order to assess the relevance of a topic for society, science or ethics.

CB4. Students will be able to transmit ideas, information, problems and solutions, both to specialized and non-specialized audiences.

GTR2 Abstraction: Capacity of creating and using formal models of real situations

GTR3 Ability to work in an autonomous way.

GTR4 Ability to plan and organize their personal workload.

GTR5 Ability to quickly integrate and work efficiently in specialized teams, as well as to collaborate in multi-disciplinary teams.

GTR7 Enough learning skills for pursuing more advanced studies and improve their education in a more autonomous way.

GTR8 Motivation for keeping high quality standards and continuous improvement, as well as acting in a professional manner.

The Verification Document also contains the specific competencies and learning outcomes that are recommended by the Counsel of Universities (CU) for the Computer Science profession. Specifically, the course on Computability shall contribute to the achievement of the following basic education competencies:

Specific Competencies on Basic Education (EFB):

EFB3.2 Ability to understand and dominate basic concepts of Logic and their application on solving engineering problems.

EFB3.3 Ability to understand and dominate basic concepts of Algorithmia and their application on solving engineering problems.

EFB3.4 Ability to understand and dominate basic concepts of Computational complexity and their application on solving engineering problems.

The course also contributes to the pursuit of the first learning outcome of the module on specific knowledge on Computation that is part of the recommendations of the CU:


  • Ability to acquire a deep knowledge on the fundamental principles and models of computation, as well as to apply them to interpret, select, asses, model and create new concepts, theories and technological developments that are relevant to Computer Science.
  • Learning outcomes

    The expected learning outcomes of this course are the following:

    1. To handle fluently the languages of Propositional and Predicate Logic. (FC15)
    2. To use different methods to prove the validity of propositional and predicate logic formulas. (FC16)
    3. To translate simple statements from natural language to the most suitable logic language. (FC17)
    4. To assess the correctness of a reasoning process. (FC18)
    5. To understand the concept of axiomatic system and its relation with semantics in logic. (FC19)
    6. To translate a sentence to its Clausal Form. (FC20)
    7. To handle the general resolution procedure. (FC21)
    8. To understand the idea of algorithm and distinguish what is, and what is not, algorithmic. (FC22)
    9. To handle at least one computational model as framework for building different computable functions.
    10. To make adequate use of the basic principles of Computability: Universality, Parametrization and Recursion. (FC23)
    11. To understand the idea of irresoluble problems and apply different techniques on the study of the resolvability of problems, knowing what is, and what is not, computable. (FC24)

    5. Table of contents.

    Part 1 Fundamentals of Logic

    Lecture 1. Propositional Logic

    1. Syntax and Semantics

    2. Semantic Proof Methods

    3. Conjunctive and Disjunctive Normal Forms, and Propositional Resolution

    4. Natural Deduction

    Lecture 2. Predicate Logic

    5. Syntax and Semantics

    6. Clausal Form, Unification and General Resolution

    7. Natural Deduction in Predicate Logic

    Part 2 Computability

    Lecture 3. Computation Models and Computable Functions

    1. Introduction: The Concept of Algorithm

    2. While Programs

    3. Turing Machines

    4. Church-Turing thesis

    Lecture 4. Fundamental Results and Unsolvability

    5. Program Enumerations

    6. Basic Theorems: Universality, Parametrization and Recursion.

    7. Solvability and Unsolvability

    8. Introduction to Computational Complexity

    According to EEES guidelines, the course consists of both contact hours and autonomous work from the students.

    The contact hours will always count with the presence of the professor and are divided into the following types:

     Lectures: The conceptual and theoretical parts of the course will be mainly delivered during the lectures. All students receive the lectures in the same classroom, which will be supported by audiovisuals and classical means such as boards. The most difficult concepts are introduced here, therefore the professor shall encourage the participation of students. The latter are also responsible of asking any question whenever there is something unclear.

     Seminars: These sessions target at a higher participation from the students. The goal is to strengthen the knowledge acquired during the lectures by having smaller groups of students and solving different examples and exercises.

     Lab Sessions: Mainly focused on solving exercises related to the ideas introduced during the lectures and seminars. Students groups are very small in order to tackle learning difficulties.

     Group mentoring: During the course, there are different moments for group mentoring. The goal of these sessions is to answer all questions or address difficulties that the students may have during the course. As in lab sessions, the groups of students are small to ensure a more personalized attention.

     Evaluation Session: Dedicated to the exams, which can be either paper-based or PC-based. These exams are designed to evaluate the knowledge and skills acquired by students.

    In addition, following the guidelines of “Real Decreto 1393/2007”, the student is expected to invest in additional time beyond the scheduled class times. During this time, the student should review the lecture notes, attend office hours if needed, get hands-on practice applying the concepts discussed in class and work on assignments

    The working methodology relies on the participation of the students, especially during the seminars, lab sessions and group mentoring. Various problems are given to the students to encourage their participation, either by solving the problems together in class or by guiding them via asking some questions about the way to solve them.

    Besides, there might be mid-term exams after finishing each part of the course if the professor sees it fit. Regarding the lab sessions, at the end of each one of them, the student could be required to present a report, solve a practical exercise or answer some questions.

    The working methodology shall be adapted to the size of different student groups.

    The following tables depict the distribution of the different activities in the course:

    On-site Work

    Lectures

    28

    18.6%

    Seminars

    7

    4.6%

    Lab Sessions

    21

    14.0%

    Group mentoring

    2

    1.33%

    Evaluation Sessions

    2

    1.33%

    Total

    60

    40%

    Off-site work

    Study of theoretical concepts

    30

    20%

    Problem solving

    20

    13.3%

    Study and preparation for lab sessions

    40

    26.6%

    Total

    90

    60%

    Total

    150

    100%

    Workload distribution by lectures

    ON-SITE WORK

    OFF-SITE WORK

    Topics

    Total amount of hours

    Lectures

    Se minars

    Lab sessions

    Group mentoring

    Intermships

    Evaluation sessions

    Total

    Group work

    Individual work

    Total

    Propositional Logic

    38

    8

    2

    7

    17

    21

    38

    Predicate Logic

    37

    6

    1

    6

    1

    14

    3

    20

    37

    Computation Models and Computable Functions

    37

    6

    1

    4

    11

    6

    20

    37

    Fundamental results and Resolvability

    36

    8

    3

    4

    1

    16

    0

    20

    36

    Evaluation

    2

    2

    2

    2

    Total

    150

    28

    7

    21

    2

    2

    60

    9

    81

    150

    7.1 Scheduled Evaluation

    There are different evaluation procedures to assess the level of knowledge and competencies acquired by the student:

    1. Midterm evaluations after each of the main parts of the course, as well as different activities proposed during the lectures. The students may have to defend some exercises or assignments during the lectures and seminars, either individually or as part of a group. The midterm evaluations take place during these hours as well.
    2. Proposed exercises and questions during the lab sessions: the students will have to solve different problems and answer different questions, which will be evaluated at the end of the class.
    3. Examination: It can be one or more exams and it has the biggest impact on the final grade

    Points 1 and 2 constitute the “continuous evaluation”, which represents 50% of the final grade: 10% comes from the lab sessions and active participation during lectures and seminars, and the remaining 40% from the midterm evaluations. The examination represents the 50% of the final grade.

    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 scheduled evaluation, 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 grades obtained in each part between the midterm evaluations and the final exam.
    • The final grade of the course will be computed by adding 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 methods

    Weight in %

     
     

    Exam

    50

    Midterm evaluations after each of the main parts of the course.

    40

    Active participation and problem solving during lectures, seminars and lab sessions

    10

    7.2 Extraordinary exams

    In the extraordinary evaluations, students must take an exam that will represent 100% of the final grade, which will include the evaluation of both theoretical and practical sessions with the same weights as the written exam of the scheduled exam.

    The final grade of the course in the extraordinary evaluations will be computed by adding the weighted marks 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.

    7.3 Differentiated evaluation

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

    The following tables include the basic and complementary bibliographical references used during the course. However, the students will be provided with extra resources such as lecture notes, slides, problem bulletins, exam samples, quiz tests, etc. These resources will be available at the Virtual Campus.

    Basic Bibliography

    Title

    Author

    Editorial

    Mathematical Logic for Computer Science

    M. Ben-Ari

    Prentice-Hall

    Computability: An introduction to recursive function theory .

    Cutland, N.J.

    Cambridge University Press

    A Programming Approach to Computability

    Kfoury, A. J.; Moll, R. N.; Arbib, M. A.

    Springer-Verlag

    Logic in Computer Science. Modelling and reasoning about systems

    Huth, M.R.A; Ryan, M.D.

    Cambridge University Press

    Logic and Its Applications

    E. Burke and E. Foxley

    Prentice Hall International

    Elementary Computability, Formal Languages, and Automata

    McNaughton, R.

    Prentice-Hall

    Automata and Computability

    Kozen, D. C.

    Springer

    Computers and Intractability. A Guide to the Theory of NP-Completeness

    Garey, M.R.; Johnson,D.S.

    Freeman & Company