Pla docent

Academic year 2013-14

Formal Systems

Degree:	Code:	Type:
Bachelor's Degree in Computer Science	21424	Compulsory subject, 3rd year
Bachelor's Degree in Telematics Engineering	22607	Optional subject
Bachelor's Degree in Audiovisual Systems Engineering	22673	Optional subject

ECTS credits:

Workload:

100 hours

Trimester:

1st

Department:	Dept. of Information and Communication Technologies
Coordinator:	Víctor Dalmau
Teaching staff:	Victor Dalmau
Language:	Catalan
Timetable:
Building:	Communication campus - Poblenou

Introduction

This course introduces and studies the basic computational models. The course is divided in two blocks.

The first block deals with regular expressions and context-free grammars. The goal is to show the foundations of the technology underlying the design of compiler and text processors. Another application of these concepts is in the field of system's verification.

The second block studies the Turing Machine. The Turing Machine is a mathematical model that has the very same power than a computer. First, we shall investigate which computational tasks can be solved by a Turing Machine. This area of research is called "Decidabilty Theory". We will show surprising results. For example, we will see that there are some computational tasks that are not solvable by any computer. Secondly, we will introduce "Complexity Theory". The goal of Complexity Theory is to investigate which tasks can be solved efficiently by a Turing Machine. In particular, we shall discuss the so-called P=?NP question, considered as one of the 10 most important mathematical problems (in fact, the "Clay Institute" has set a million dollar award for it).

This course aims to improve the student's reasoning capabilities, strengthening his/her capacity of abstraction. The course has a theoretical and deductive focus.

Prerequisites

The course requires certain basic mathematical ground that the student should have acquired during secondary school or when studying the mathematical courses of the first year:

-Basic algebraic notions.

-Basic arithmetic.

-Capability to understand and write simple mathematical expressions.

-Familiarity with basic proof techniques: induction, contradiction.

-Basic graph theory notions.

The students that are not familiar with the mathematical requirements will be able to pass the course but will need to do and extra effort, as they will need to strengthen their mathematical background. The bibliography contains several references that can be used to this end.

It is also convenient to have some basic notions about algorithms and logic introduced previously in the courses "Foundations of programming" and "Computational Logic". Again, the students that have not taken those courses sill can pass this course by just devoting a little extra effort.

Associated competences

Competències transversals	Competències específiques
Instrumentals G1. Capacidad de análisis y síntesis G2. Capacidad de organización y planificación G3. Capacidad para aplicar los conocimientos al análisis de situaciones y la resolución de problemas G4. Habilidad en la búsqueda y la gestión de la información G5. Habilidad en la toma de decisiones G6. Capacidad de comunicarse con propiedad de forma oral y escrita en catalán y en castellano, tanto ante audiencias expertas como inexpertas Interpersonals G8. Capacidad de trabajo en equipo Sistèmiques G11. Capacidad de aplicar flexibilidad y creatividad los conocimientos adquiridos y de adaptarlos a contextos y situaciones nuevas G12. Capacidad para progresar en los procesos de formación y aprendizaje de manera autónoma y continua G14. Capacidad de motivación por la calidad y por el logro G15. Capacidad de generación de nuevas ideas	H1. Capacidad de concebir y llevar a cabo proyectos informáticos metodologías propios de la ingeniería. H3. Capacidad para la redacción y desarrollo de proyectos en el ámbito de su especialidad. H4. Aprender de manera autónoma nuevos conocimientos y técnicas adecuados para la concepción, el desarrollo o la explotación de sistemas informáticos. IN25. Conocer la teoría y práctica de autómatas de estados finitos, propiedades de las expresiones y lenguajes regulares, así como técnicas para determinar si un lenguaje es regular o no. IN26. Conocer los lenguajes libres de contexto y su relación con los autómatas con pila, gramáticas libres de contexto, árboles sintácticos, derivaciones y ambigüedad. IN27. Conocer la máquina de Turing y la relación con la noción de algoritmo o programa.

Competències transversals

Competències específiques

Instrumentals
G1. Capacidad de análisis y
síntesis

G2. Capacidad de organización
y planificación

G3. Capacidad para aplicar los
conocimientos al análisis de
situaciones y la resolución de
problemas

G4. Habilidad en la búsqueda y
la gestión de la información

G5. Habilidad en la toma de decisiones

G6. Capacidad de comunicarse
con propiedad de forma oral y
escrita en catalán y en
castellano, tanto ante audiencias
expertas como inexpertas

Interpersonals

G8. Capacidad de trabajo en equipo

Sistèmiques

G11. Capacidad de aplicar
flexibilidad y creatividad los
conocimientos adquiridos y de
adaptarlos a contextos y
situaciones nuevas

G12. Capacidad para progresar
en los procesos de formación y
aprendizaje de manera
autónoma y continua

G14. Capacidad de motivación
por la calidad y por el logro

G15. Capacidad de generación
de nuevas ideas

H1. Capacidad de concebir y llevar a
cabo proyectos informáticos
metodologías propios de la
ingeniería.

H3. Capacidad para la redacción y
desarrollo de proyectos en el ámbito
de su especialidad.

H4. Aprender de manera autónoma
nuevos conocimientos y técnicas
adecuados para la concepción, el
desarrollo o la explotación de
sistemas informáticos.

IN25. Conocer la teoría y práctica de
autómatas de estados finitos,
propiedades de las expresiones y
lenguajes regulares, así como
técnicas para determinar si un
lenguaje es regular o no.

IN26. Conocer los lenguajes libres de
contexto y su relación con los
autómatas con pila, gramáticas libres
de contexto, árboles sintácticos,
derivaciones y ambigüedad.

IN27. Conocer la máquina de Turing
y la relación con la noción de
algoritmo o programa.

Assessment

The evaluation is as follows

1.-Continuous evaluation. Before class, students will prepare exercises that will be solved on the blackboard and/or delivered. A part of these exercises will be evaluated. The result will be a grade, L, in the range 0-10.

2.-Partial exam. It consists of a compulsory exam containing theory questions and problems that will be done in the middle of the trimester. The result will be a grade, EP, in the range 0-10.

3.-Final exam (december). It consists of a compulsory exam containing theory questions and problems that will be done during the exams period at the end of the trimester. The result will be a grade, EF1, in the range 0-10.

4.-Final exam (july). It consists of a compulsory exam containing theory questions and problems that will be done during the exams period in July.
The result will be a grade, EF1, in the range 0-10.

The final grade is computed as follows:

-December. In order to pass it is necessary that the grade of december's exam, EF1, is at least 5. In this case, the final grade will be
0.20*L+0.15*EP+0.65*EF1.

-July.-December. In order to pass it is necessary that the grade of july's exam, EF2, is at least 5. In this case, the final grade will be
0.20*L+0.15*EP+0.65*EF1.

The course is divided in four units:

1.-Regular languages.

Finite deterministic and non deterministic automaton. Regular expressions. Equivalence between regular expression and DFAs (Kleene Theorem). Regular languages and their basic properties.

2.-Context-free languages.
Context-free grammars. Context-free languages and their basic properties.

3.-Decidability Theory.
Turing Machines (TMs). Equivalence between TMs and computer programs. Recursively enumerable and recursive languages. Diagonal, Universal, and Halting Problems.

4.-Complexity Theory.
Temporal complexity of a Turing Machine. The classes P and NP. NP-completeness and Cook's theorem.

Methodology

Before class.

The student will prepare, before each class, some material that will be provided previously by the professor. In general (although not necessarily always) this material will consists of several sections of the course notes. The student will need to read this sections carefully and solve the exercises in them.

During class.

During class, the students will be asked to solve exercises on the blackboard. The professor participation during the class will be minimal, merely asking questions.

In addition, the professor might require other tasks such as delivering exercises or presenting some material.

Resources

Resources.

-Course Notes. Available online at Moodle.

Basic bibliography.

-J. Hopcroft, R. Motwani i J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2007.

- M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.

Auxiliary bibiography

- D. Kelley. Teoría de autómatas y lenguajes formales. Prentice-Hall, 1995.

- D. Kozen. Automata and Computability. Springer-Verlag, 1997.