template-browser-not-supported

Doble Grado en Ingeniería Informática del Software / Grado en Matemáticas

Back Back

Autómatas y Matemáticas Discretas

Código asignatura
2GIISMAT-1-009
Curso
Primero
Temporalidad
Segundo Semestre
Carácter
Formación Básica
Créditos
6
Pertenece al itinerario Bilingüe
Yes
Actividades
  • Clases Expositivas (28 Hours)
  • Prácticas de Aula/Semina (14 Hours)
  • Prácticas de Laboratorio (14 Hours)
  • Tutorías Grupales (2 Hours)
Guía docente

Automata and Discrete Mathematics is framed in the Basic Training module. The concepts and methods presented therein are helpful to understanding issues included in other subjects.

Some aspects of graph theory are used in subjects as Data Structures (2nd year) when studying some search strategies, or in Algorithms (2nd year) when presenting some of the algorithm design techniques.

The study of formal languages, as well as their generator or recognizer devices, is very helpful to understand the process of compiling a program and, more specifically, the lexical and syntactic analysis of a program. These issues are covered in depth in the subject Programming Languages Design (3rd year) and, to a lesser extent, Intelligent Systems (4th year).

Automata and Discrete Mathematics is related to Linear Algebra, taken in the same year but in the 1st semester. Basic concepts about functions, such as domain, range or properties are very helpful for our subject. Also, demonstration techniques or test methods are very important in order to understand some theoretical demonstrations.

Finally, the subject Computability, in the 2nd year, can be considered as the second part of Automata and Discrete Mathematics. Both together, they offer important theoretical aspects of Computer Science. 

The training provided by technical subjects in high-school is enough to understanding the concepts presented in this subject. Anyway, as this is a 2nd semester subject, the student should have already completed the course on Computing Basics and Introduction to Programming, so he has enough computer and programming skills to successfully solve the assignments of Automata and Discrete Mathematics.

It would also be advisable to have successfully completed Algebra, which is also taught in the first semester.

According to the grade design, this course ought to help the students to achieve the following competences/skills:

General Competences/skills

CG3:  Abstraction

CG5: Analysis, selection and use of basic and supporting tools

CG7: Writing skills.

CG18: High sense of responsibility

CG19: Effective work habits.

Basic Training Specific Competences/skills

Bas.3: Ability to understand the basic concepts of automata and discrete mathematics and its application to problems of engineering.

Bas.4 Basic knowledge of computers, operating systems, databases and computer programs with application in engineering.

Computer science branch specific skills/competences

Com 6: Basic knowledge of computer science algorithmic procedures and their application to solve problems. Ability to choose the most appropriate solution.

Learning outcomes

The expected learning outcomes are the following:

1.    Understand the basic concepts of discrete mathematics, and formal languages, as well as their generator or recognizer devices.

2.    Acquire a basic knowledge of how to use and programme computer applications related to the manipulation of structures associated with formal languages.

3.    Design appropriate solutions for problems related to this subject

4.    Develop technical documents that properly describe the solutions to the problems

Chapter 1 Regular Languages

  1. Introduction and basic concepts

  2. Regular expressions

  3. Deterministic finite automata, non deterministic finite automata and lambda transitions

  4. Properties of Regular languages

Chapter 2 Context-free Languages

  1. Introduction and basic concepts

  2. Context-free grammars

  3. Simplification of Grammars and Normal Forms

  4. Pushdown automata

Chapter 3 Graphs

  1. Introduction and basic concepts

  2. Accesibility and adjacency

  3. Graph traversal

  4. Trees

  5. Planar Graphs and Graph Coloring

Chapter 4 Recursive language and recursively enumerable language

  1. Introduction and basic concepts

  2. Turing Machine

  3. Chomsky hierarchy

According to the guidelines laid down by the EEES, the subject will be developed through classroom activities and autonomous work.

Classroom activities are those that will always be developed by the teacher and the students, together. They are divided into lectures, small group lectures, laboratory work, group tutorials and review sessions.

  • Lectures: These classes will develop a theoretical approach to the subject, combined with the resolution of small exercises. Students will be encouraged to participate.

  • Small groups: These sessions are aimed at consolidating some concepts outlined in lectures, by means of examples and exercises. Student participation is required.

  • Laboratories: Labs are devoted to solve practical problems related to the concepts presented in lectures.

  • Group tutorials: These sessions are devoted to clear up any doubt students may have both in theory or practical concepts.

  • Evaluation sessions: These will be based on tests, both written or labs.

Besides attending these sessions, the student will have to develop an autonomous work in order to complete the credits. On a regular basis, students will be asked to do some homework, with a submission deadline to be handed in. In addition, at the end of each chapter there will be a written test.

Regarding labs, at the end of each scheduled practice, the student will have to write a report for the lab teacher, explaining the solution implemented and the results obtained. Occasionally, there could also be some exercises to be handed in at the end of the practice session.

The following tables specify the estimated number of hours devoted to each activity:

Estimated workload for the student

TYPE

Hours

ECTS

%

In class activities

Lectures

28

1.12

18.8%

Small Groups

14

0.56

9.3%

Labs

14

0.56

9.3%

Group Tutorials

2

0.08

1.3%

Evaluation

2

0.08

1.3%

Total

60

2.40

40%

Out-of-class learning activities

Reviewing theoretical concepts

30

1.20

20%

Doing homework

25

1.00

17%

Solving lab exercises

25

1.00

17%

Writting reports to hand in

10

0.40

6%

Total

90

3.60

60%

Total

150

6.00

100,00%

 

Distribution of the workload in units

 

Unit

Total Hours

IN CLASS ACTIVITIES

OUT-OF-CLASS

LEARNING

ACTIVITIES

Lectures

Small group lectures

Labs

Group tutorials

Evaluation

Total

Autonomous work

Total

Regular Languages

49

9

5

6

19

30

30

Context-Free Languages

48

9

4

6

18

30

30

Recursive and Recursively enumerable languages

5

1

1

2

3

3

Graphs

44

9

4

2

17

27

27

4

2

2

4

Total

150

28

14

14

2

2

60

90

90


 

Distribution of the workload by topic

Distribution of the workload by topic

In class work

Out-of-class work

Lessons

Total amount of hours

Lectures

Small Group sessions

Labs

Small Groups

Evaluation

Total

Group work

Autonomous Work

Total

Regular languages

49

9

5

6

19

30

30

Context-Free Languages

48

9

4

6

18

30

30

Recursive languages

5

1

1

2

3

3

Graphs

44

9

4

2

17

27

27

4

2

2

4

Total

150

28

15

14

2

2

60

0

90

150

7. Evaluation

7.1 Ordinary evaluation.

The course ordinary grading system is as follows:

  • Lecture tests (20% of final grade) and essays (20% of final grade) : Two tests, one at the end of the first unit and other at the end of the second unit, and one individual essay at the end of the last unit.

  • Final exam (30% of final grade)

  • Laboratory exams (30% of final grade): two practical controls with a weight of 12% for the first one and 18% for the second one.

Attendance to lab classes is compulsory. If a student does not attend 80% of the lab sessions, his laboratory grade will be 0. Attendance to lectures is advisable.

To pass, students must have 4 points out of 10 in both theory and laboratory and their final grade must be 5 out of 10. In other case, their final grade will be the minimum of 4 and the weighted average of the theory and lab parts.

A student should attend or submit tests or lab exams which means more than 50% of the total grade or his final mark will be “no presentado”.

If a student fails the ordinary evaluation his or her grades in both theory and lab can be carried out to the extraordinary evaluation of the same academic year if they happen to be 4 or greater.

Exceptionally, if required because of public health alarm, online evaluation methods may be deployed. In tha case, students will be dutifully infomed.  

Semi-presential modality

For those students enrolled in the semi-presential modality, the ordinary evaluation will consist of one theory exam (70% of final grade) and one lab exam (30% of final grade). 

Students must have 4 points out of 10 in both theory and laboratory and their final grade must be 5 out of 10 to pass. In other case, their final grade will be the minimum of 4 and the weighted average of the theory and lab parts.

Exceptionally, if required because of public health alarm, online evaluation methods may be deployed. In tha case, students will be dutifully infomed.  

7.2 Extraordinary evaluation.

The extraordinary grading system will be as follows:

  1. Final Exam (70% of final grade)

  2. Lab practice (30% of final grade)

Students must have 4 points out of 10 in both theory and laboratory and their final grade must be 5 out of 10 to pass. In other case, their final grade will be the minimum of 4 and the weighted average of the theory and lab parts.

Those students who get 4 points or more in the theory of lab during ordinary evaluation, can avoid doing the equivalent exam in their extraordinary evaluation (during the same academic year).

Exceptionally, if required because of public health alarm, online evaluation methods may be deployed. In tha case, students will be dutifully infomed.  

1.    Rosen, K.H.: Discrete Mathematics and its applications. 5th edition. McGraw-Hill, 2003

2.    Hopcroft, J.E.; Motwanni, R.; Ullman, J.D., Introduction to Automata Theory, Languages and Computation. 2nd edition. Addison-Wesley, 2000.

3.    Kelley, D., Automata and formal Languages: An Introduction. Prentice Hall, 1995.