This subject is an introduction to the Computation Speciality and its goal is to deepen fundamental principles and models of computation and programming languages, in order to apply them in new computer systems, in the assessment of the complexity of problems and in the design of algorithmic strategies to solve them, independently of the equipment or software it is used.



Algorithmic problem solving has been studied in previous subjects (Principles of Programming, Modular Programming and Object Orientation, and Data Structures and Algorithms), using several methodologies and concrete programming languages. In this subject we will instead address which problems can be solved algorithmically, regardless of the equipment or software.



We will cover topics ranging from basic contents of formal languages and automata to basic principles of computability and complexity, including steps towards Artificial Intelligence. These topics are further elaborated in other subjects of the speciality such as Abstract Models of Computation, Compilation, Design of Algorithms, Data Mining, and Artificial Intelligence. Some of the topics can be also studied in more detail in subjects offered in this degree, such as Advanced Tools in Artificial Intelligence, Machine Learning and Neural Networks, Natural Language Processing, Knowledge Based Systems, Search Heuristics, Logic Programming, and Functional Programming.



Applications of models studied in this subject can be found through all the computer engineering professional scope. Languages enable human-machine and machine-machine communication. Without them, current application such as network communication protocols, markup languages, etc. would never exist. For example:

- the design and implementation of modern programming languages is based on grammars;

- text processors and natural language processing base some of their techniques on the models seen in the subject;

- communication protocols, vending machines, and many games are described in terms of finite state automata.

Finally, the results of complexity are the basis of cryptography.

- Identifying and resolving problems that can be approached using restricted computational models (automata) or alternative computational models (intelligent systems).

- Designing automata, grammars, and regular expressions to define formal languages.

- Using pattern recognizing and processing software.

- Being aware of the existence of intrinsic limits in the computational processes and of their consequences.

- Analysing problems and their computational solutions using verbal, mathematical, and graphic languages.

1. Introduction. Strings and languages.

2. Computation without memory.

2.1 Finite automata and transducers. Equivalences and transformations.

2.2 Regular expressions. Equivalences and transformations.

2.3 Limits.

3. Computation with restricted memory.

3.1 Context-free grammars. Ambiguity.

3.2 Pushdown automata.

3.3 Limits.

4. General model of computers.

4.1 Turing automata.

4.2 Turing machines and diagrams.

4.3 The Church-Turing Thesis.

4.4 Limits. Uncomputability.

5. Intelligent Systems.

5.1 Introduction to computational complexity. Need for approaches.

5.2 Non-functional specifications.

5.3 Example: Decision trees.

The lessons will be presented in class, along with complementary reading material. In the class sessions the following activities will take place on a regular basis: the course concepts will be presented systematically, followed by exercises to assimilate the learnt techniques.



A large collection of problem statements will be made available, to get used to fluently and appropriately expressing oneself regarding problems according to each context: informal (usually natural language), text-based formal (logic and mathematics), and graphic-based formal (automata diagram, decision tree).



Collaborative study will be enhanced through the use of eGela forums to present organized solutions to the problems from the collections of proposed statements. To share those solutions quickly and comprehensively, graphic tools will be used, which will allow viewing the behaviour of the theoretical models and facilitate understanding how they function.

• Continuous Assessment System
• Final Assessment System
• Tools and qualification percentages:
  • The percentages and types of evaluation are specified in the following sections (%): 100

The subject has two assessment options: end-of-course (or overall) assessment and continuous assessment.



CONTINUOUS ASSESSMENT: This modality of assessment is opt-in, as students will be required to dedicate time during the semester to studying and solving exercises in order to pass the subject.



The various assessment activities will be weighted in the following way:

1) Written tests (80%)

2) Exercises/problems delivery assessment (20%)



There will be three written tests, with weights of 35%, 30% and 15%, which make up 80% of the final grade of the subject indicated above for the written tests. Each of the written tests will require a minimum grade of 30% for students to remain in continuous assessment mode. No minimum grade will be required for the delivery of exercises/problems.



Students will be considered for continuous assessment unless they explicitly renounce. Those students who meet the requirements of continuous assessment but decide to choose the end-of-course evaluation, will have to notify to the teachers in charge of the subject about that decision before the last week of classes via eGela. If a student does not renounce continuous evaluation by the aforementioned date, it will be assumed that this is confirmation of continuous assessment.



END-OF-COURSE ASSESSMENT: This option will be applied both to students who do not wish to choose the continuous assessment and to those who do not pass the requirements. The assessment method will be a written exam that will cover 100% of the subject content, which will take place as specified in the official schedule of exams of the Faculty.



During all written tests (continuous or overall) the use of books, notes, phones, computers, or other electronic devices is strictly prohibited.

The test will be a written exam that will cover 100% of the subject content, which will take place as specified in the official schedule of exams of the Faculty.



During the written exam, the use of books, notes, phones, computers, or other electronic devices is strictly prohibited.

The slides used by the lecturers to present the subject, as well as the problems and exercises, are considered compulsory material and will be made available in eGela.

The use of the following resources is also necessary to follow the subject:
- eGela
- Corporate email address
- JFLAP

Basic bibliography

- INTRODUCTION TO AUTOMATA THEORY, LANGUAGES AND COMPUTATION: J.E. Hopcroft, R. Motwani & J.D. Ullman. Addison-Wesley, 3rd edition, 2006.

- AUTÓMATAS Y LENGUAJES. UN ENFOQUE DE DISEÑO: R. Brena. Instituto Tecnológico de Monterrey, 2003. (https://lenguajesformalesyautomatas.files.wordpress.com/2017/11/automatas-y-lenguajes.pdf)

- JFLAP: AN INTERACTIVE FORMAL LANGUAGES AND AUTOMATA PACKAGE: S.H. Rodger eta T.W. Finley. Jones & Bartlett, 2006. (https://www.jflap.org/jflapbook/jflapbook2006.pdf)

- ARTIFICIAL INTELLIGENCE: A MODERN APPROACH: S. Russell and P. Norvig. Prentice Hall, 3rd edition, 2009

In-depth bibliography

- AUTOMATA, COMPUTABILITY AND COMPLEXITY: E. Rich. Pearson Education, 2008.
- INTRODUCCIÓN A LA TEORÍA DE AUTÓMATAS, GRAMÁTICAS Y LENGUAJES. E. Gaudioso & T. García. Editorial Universitaria Ramón Areces. 2017. (contains exercises and solutions)

Web addresses

- Visual and interactive tools (JFLAP): http://www.jflap.org
- Alan Turing: http://www.turing.org.uk