Guías Docentes Electrónicas
1. General information
Course:
TEORÍA DE AUTÓMATAS Y COMPUTACIÓN
Code:
42342
Type:
CORE COURSE
ECTS credits:
6
Degree:
346 - DEGREE IN COMPUTER SCIENCE AND ENGINEERING
Academic year:
2019-20
Center:
604 -
Group(s):
15 
Year:
3
Duration:
C2
Main language:
Spanish
Second language:
Use of additional languages:
English Friendly:
Y
Web site:
Bilingual:
N
Lecturer: FERNANDO LOPEZ PELAYO - Group(s): 15 
Building/Office
Department
Phone number
Email
Office hours
ESII / 1A3
SISTEMAS INFORMÁTICOS
2681
fernandol.pelayo@uclm.es
Consultar en https://www.esiiab.uclm.es/pers.php?codpers=126&curso=2018-19

2. Pre-Requisites

As this subject is taught in the third year of the degree it is expected that all the necessary requirements are met. Therefore, it is expected that there will be a basic background in:

- Mathematical formalisms: Set theory in Algebra. Basic mathematical background on proof techniques, especially Induction.

- Languages ¿¿and Programming Techniques: Mainly Imperative Style. It is expected that the student would be non-dependant on a specific programming language for final implementation (if required). The stunts are expected to know some programming languages in order to better illustrtate the usefulness of using grammars.

More specifically, the student should:

- Be able to work within a mathematical and formal framework.

- have abstraction capacity that allows they to identify the key ideas and concepts above the details and / or notation used.

3. Justification in the curriculum, relation to other subjects and to the profession

Automata theory and Computation is basic background for on both Science and Technique of Computing, in fact it has always been included in the Curriculum of these studies from its origins. At present, for the sake of a technification of the discipline, the study of this subject has remained part of the Computation itinerary, due to its more scientific nature.

In this subject, where both is justified and stablished  the basis of the studies, there can be found most of the basic concepts studied and used in almost all other subjects. What is a programming language, how and why is it defined in the way it is done? What is the mechanism in which it is translated into a formalism understandable by a machine, why is that specifically, and what are the limitations that can be found, among many others.

This subject is strongly linked with others, as are all having mathematical nature, since formerly the subject has this origin, as well as those with a certain theoretical component related to programming, such as Language Processors, Declarative Programming, and all those in which the Artificial Intelligence has a certain weight.


4. Degree competences achieved in this course
Course competences
Code Description
CM1 Ability to acquire thorough knowledge about fundamental principles and models in computation, and to apply them for the interpretation, selection, assessment, modelling, and creation of new concepts, theories, uses, and development of those technologies in the field of IT.
CM2 Ability to know the theoretical fundamentals of programming languages, and their associated techniques for lexical, syntactic, and semantic processes, along with their application in the creation, design, and language processing.
INS1 Analysis, synthesis, and assessment skills.
INS4 Problem solving skills by the application of engineering techniques.
INS5 Argumentative skills to logically justify and explain decisions and opinions.
SIS1 Critical thinking.
SIS3 Autonomous learning.
UCLM3 Accurate speaking and writing skills.
5. Objectives or Learning Outcomes
Course learning outcomes
Description
Understanding and skills in the definition of regular and context-free languages as well as the computers that recognize them.
Understanding of the theoretical foundations of computability and decidability.
Additional outcomes
Description
Knowing the formal languages theory concepts that can be applied to Informatics, e.g., formal language definition, skills and tools for formal language processing, goals for this processing, etc...
Connecting these previous concepts with some others that are widely used throughout the studies of the degree, among which sohuld be included those related to programming languages.
6. Units / Contents
  • Unit 1: Introduction
  • Unit 2: Formal Languages
  • Unit 3: Formal Grammars
  • Unit 4: Finite Automata / Finite State Machine
  • Unit 5: Regular expressions
  • Unit 6: Regular Languages properties
  • Unit 7: Context Free Grammars
  • Unit 8: PushDown Automata
  • Unit 9: Turing Machines
7. Activities, Units/Modules and Methodology
Training Activity Methodology Related Competences ECTS Hours As Com R Description
Class Attendance (theory) [ON-SITE] Combination of methods CM1 INS1 CM2 0.64 16 Y Y Y
Problem solving and/or case studies [ON-SITE] Problem solving and exercises INS5 CM1 UCLM3 SIS1 INS1 CM2 0.64 16 Y Y Y
Problem solving and/or case studies [ON-SITE] Problem solving and exercises SIS3 CM1 UCLM3 SIS1 INS1 CM2 0.96 24 Y Y Y
Progress test [ON-SITE] Assessment tests CM1 UCLM3 SIS1 INS1 CM2 0.24 6 Y Y Y
Project or Topic Presentations [ON-SITE] Group Work UCLM3 SIS1 INS1 0.64 16 Y Y Y
Study and Exam Preparation [OFF-SITE] Self-study CM1 SIS1 INS1 CM2 2.4 60 Y Y Y
In-class Debates and forums [ON-SITE] Debates PER2 UCLM3 SIS1 INS1 0.24 6 Y Y Y
Final test [ON-SITE] CM1 UCLM3 SIS1 INS1 CM2 0.24 6 Y N Y
Total: 6 150
Total credits of in-class work: 3.6 Total class time hours: 90
Total credits of out of class work: 2.4 Total hours of out of class work: 60
As: Assessable training activity
Com: Training activity of compulsory overcoming
R: Rescheduling training activity
8. Evaluation criteria and Grading System
  Grading System  
Evaluation System Face-to-Face Self-Study Student Description
Test 60.00% 0.00% Partial Test and if required Final Test
Other methods of assessment 20.00% 0.00% Writing and oral exposing and defending reports over general issues related to this subject
Self Evaluation and Co-evaluation 10.00% 0.00% LAB work
Oral presentations assessment 10.00% 0.00%
Total: 100.00% 0.00%  

Evaluation criteria for the final exam:
Written test: 60%.
Practical work: 20%.
The delivery of the internship work will be mandatory: 10%.
Oral presentations of topics, including work and memory of practices: 10%
Specifications for the resit/retake exam:
Written test to assess theoretical and practical knowledge.
The delivery of the internship is compulsory.
Specifications for the second resit / retake exam:
Written test to assess theoretical and practical knowledge.
The delivery of the internship is compulsory.
9. Assignments, course calendar and important dates
Not related to the syllabus/contents
Hours hours
In-class Debates and forums [PRESENCIAL][Debates] 4
Final test [PRESENCIAL][] 6

Unit 1 (de 9): Introduction
Activities Hours
Class Attendance (theory) [PRESENCIAL][Combination of methods] 1
Study and Exam Preparation [AUTÓNOMA][Self-study] 2
In-class Debates and forums [PRESENCIAL][Debates] 1

Unit 2 (de 9): Formal Languages
Activities Hours
Class Attendance (theory) [PRESENCIAL][Combination of methods] 1
Study and Exam Preparation [AUTÓNOMA][Self-study] 2
In-class Debates and forums [PRESENCIAL][Debates] 1

Unit 3 (de 9): Formal Grammars
Activities Hours
Class Attendance (theory) [PRESENCIAL][Combination of methods] 1
Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] 2
Progress test [PRESENCIAL][Assessment tests] 1
Study and Exam Preparation [AUTÓNOMA][Self-study] 2

Unit 4 (de 9): Finite Automata / Finite State Machine
Activities Hours
Class Attendance (theory) [PRESENCIAL][Combination of methods] 3
Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] 2
Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] 4
Progress test [PRESENCIAL][Assessment tests] 1
Project or Topic Presentations [PRESENCIAL][Group Work] 3
Study and Exam Preparation [AUTÓNOMA][Self-study] 10

Unit 5 (de 9): Regular expressions
Activities Hours
Class Attendance (theory) [PRESENCIAL][Combination of methods] 3
Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] 2
Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] 4
Progress test [PRESENCIAL][Assessment tests] 1
Project or Topic Presentations [PRESENCIAL][Group Work] 3
Study and Exam Preparation [AUTÓNOMA][Self-study] 10

Unit 6 (de 9): Regular Languages properties
Activities Hours
Class Attendance (theory) [PRESENCIAL][Combination of methods] 2
Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] 3
Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] 4
Progress test [PRESENCIAL][Assessment tests] 1
Project or Topic Presentations [PRESENCIAL][Group Work] 3
Study and Exam Preparation [AUTÓNOMA][Self-study] 10

Unit 7 (de 9): Context Free Grammars
Activities Hours
Class Attendance (theory) [PRESENCIAL][Combination of methods] 2
Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] 3
Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] 4
Progress test [PRESENCIAL][Assessment tests] 1
Project or Topic Presentations [PRESENCIAL][Group Work] 3
Study and Exam Preparation [AUTÓNOMA][Self-study] 10

Unit 8 (de 9): PushDown Automata
Activities Hours
Class Attendance (theory) [PRESENCIAL][Combination of methods] 2
Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] 2
Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] 4
Progress test [PRESENCIAL][Assessment tests] 1
Project or Topic Presentations [PRESENCIAL][Group Work] 4
Study and Exam Preparation [AUTÓNOMA][Self-study] 10

Unit 9 (de 9): Turing Machines
Activities Hours
Class Attendance (theory) [PRESENCIAL][Combination of methods] 1
Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] 2
Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] 4
Study and Exam Preparation [AUTÓNOMA][Self-study] 4

Global activity
Activities hours
10. Bibliography and Sources
Author(s) Title Book/Journal Citv Publishing house ISBN Year Description Link Catálogo biblioteca
 
F. Sande González Prácticas de teoría de autómatas y lenguajes formales Tenerife Gobierno de Canarias 2001 Texto para prácticas de la asignatura http://www.gobiernodecanarias.org/educacion/dgoie/publicace/scripts/detalle.asp?p=477  
Hopcroft, J.E.; Motwani R.;Ullman, J.D.: Introducción a la teoría de Autómatas, Lenguajes y Computación. Prentice-Hall 2002 Libro básico de referencia http://www.casadellibro.com/libro-introduccion-a-la-teoria-de-automataslenguajes-y-computacion/9789682612220/484262  
Isasi P., Martínez P., Borrajo D Lenguajes, Gramáticas y Autómatas. Un enfoque práctico Addison Wesley 9788478290147 1997 Ejemplos interesantes http://www.casadellibro.com/libro-lenguajes-gramaticas-y-automatas-un-enfoque-practico/9788478290147/792972  
J Glenn Brookshear Teoria de la Computación: Lenguajes Formales, Autómatas y Complejidad Alhambra Mexicana 9789684443846 2000 Muy ameno y didáctico https://www.casadellibro.com/libro-teoria-de-la-computacion-lenguajes-formales-automatas-y-complej-idad/9789684443846/730597  



Web mantenido y actualizado por el Servicio de informática