
Theory of Computation
Code: 107891Credits: 6
| Degree programme | Type | Course |
|---|---|---|
| Computer Engineering | FB | 1 |
Contact lecturer
- Name :
- Joan Serra Sagrista
- Email :
- joan.serra@uab.cat
Teaching staff
- Joaquim Borges Ayats
- Marc Masdeu Sabate
- Sebastià Mijares i Verdú
Group languages
You can consult this information at the end of the document.
Prerequisites
Notice on the language of instruction and syllabus translations:
- The language of instruction for all groups of this course is Catalan.
- Automatic translations of the syllabus into English and Spanish are provided for informational purposes only.
- In case of any discrepancy or inconsistency between versions in different languages, the Catalan version shall prevail as the official reference.
Although there are no official prerequisites, it is essential that students have a very good command of the most basic notions of mathematics, such as:
- Master the manipulation of mathematical language
- Master proofs by induction and contradiction
- Mastering the ability to abstract
Students who do not have a minimum background in previous mathematics will have to make an effort to worry about solving these deficiencies.
Objectives
- Sort the properties of the formal models on which computers are based
- Identify the possibilities and limits of computing
- Acquire good programming habits
Learning outcomes
- CM05 (Integrate computational model-based techniques into computer science problems.) Integrate computational model-based techniques into computer science problems.
- KM09 (Explain algorithmic procedures of computational theory for solving computer engineering problems.) Explain algorithmic procedures of computational theory for solving computer engineering problems.
- SM13 (Apply knowledge of automatons, grammars and computational complexity to solve problems.) Apply knowledge of automatons, grammars and computational complexity to solve problems.
Contents
1. Formal languages and abstract calculation models.
1.1. Alphabets, words and languages.
1.2. Problems, formal languages and calculation models.
1.3. Digital systems.
1.4. Demonstration methods.
2. Finite automata and regular languages.
2.1. Deterministic finite automata.
2.2. Non-deterministic finite automata.
2.3. Operations, expressions and regular languages.
2.4. Automata with output.
3. Context-independent grammars.
3.1. Introduction.
3.2. Definitions. Language generation.
3.3. Simplification of grammars.
3.4. Chomsky and Greibach normal forms.
4. Stack Automata.
4.1. Description.
4.2. Acceptance by final state and empty stack.
4.3. Stacked automata and context-independent languages.
4.4. Properties of context-independent languages.
5. Turing machines.
5.1. Description of the basic model.
5.2. Computable languages and functions.
5.3. Variants of the Turing machine.
5.4. Church's hypothesis. Von Neumann machine.
6. Undecidability.
6.1. Decidable and undecidable problems and languages.
6.2. Recursive and recursively enumerable languages.
6.3. Universal Turing machine and undecidable problems.
6.4. The Post Correspondence Problem and the Stop Problem.
6.5. Examples of non-recursive languages.
7. Computational complexity.
7.1. Introduction. Types of problems.
7.2. Complexity classes.
7.3. NP-Completeness,
7.4. Some NP-Complete problems.
Learning activities and methodology
| Title | Hours | ECTS | Learning outcomes |
|---|---|---|---|
| Theory and Exercises Sessions | 50 | 2 | CM05, KM09, SM13 |
| Preparation and autonomous work | 26 | 1.04 | CM05, KM09, SM13 |
| Exercises | 28 | 1.12 | CM05, KM09, SM13 |
| Study and preparation of evaluating activities | 38.5 | 1.54 | CM05, KM09, SM13 |
- The sessions will be taught according to the type of Classroom Practices (PAUL):
Discussion and realization of exercises and activities in group or individually.
- The teaching methodology is oriented towards the learning of the subject on a continuous basis. Activities that will be developed throughout the course:
Theory and problem sessions, where teachers will provide information on knowledge and strategies for acquiring, expanding and organising it. The active participation of students will be encouraged. Learning will be monitored through individual and/or group development of validation and achievement activities.
Assessment
Continuous assessment activities
| Title | Weight | Hours | ECTS | Learning outcomes |
|---|---|---|---|---|
| Exercises delivery and/or validation activities | 30 | 3.5 | 0.14 | CM05, KM09, SM13 |
| Partial Exam 1 | 35 | 2 | 0.08 | CM05, KM09, SM13 |
| Partial Exam 2 | 35 | 2 | 0.08 | CM05, KM09, SM13 |
- Along the course, a series of exercises and/or validation activities will be carried out. The grades of these exercises and/or activities will account for 30% of the final grade. This part of the grade will NOT be recoverable.
- There will be a first midterm exam (First Partial = P_1) before mid-semester in which the work done up to that moment will be evaluated. The grade of this exam will contribute 35% of the final grade. All students who take this exam can no longer be graded as NOT ASSESSED. Any student who has not taken this exam will not be entitled to retake it (except for duly justified reasons, in which case the retake exam will be allowed).
- At the end of the semester there will be a second midterm exam (Second Partial = P_2) in which the knowledge taught after the first partial will be evaluated. The grade of this exam will contribute another 35% of the final grade. All students who take this exam can no longer be graded as NOT ASSESSED. Any student who has not taken this exam will not be entitled to retake it (except for duly justified reasons, in which case the retake exam will be allowed).
- Any student who has not taken any midterm exam (first and second partials) will be recorded as NOT ASSESSED for academic purposes.
Qualification:
- If the average of the grades (out of 10) of the two midterms M=(P_1+P_2)/2 is less than 2.5, the student has failed the subject, with a final grade of M, without the right to go to the retake exam.
- If M is greater than 2.5 but less than or equal to 3.5, the student must take the retake exam.
- If M is greater than or equal to 3.5 then if NF=0.7 M + 0.3 S, (where S is the average grade of the delivery of validation exercises and/or activities, out of 10) is greater than or equal to 5 the student has passed and has NF as the final grade, otherwise he/she must go to the retake exam.
- If the student has to take the retake exam, then if the retake grade R is less than 3.5, the student has failed with a final grade R; if R is greater than or equal to 3.5 the final grade will be min({0.7 R + 0.3 S},7) where R is the grade of the retake exam (out of 10).
- The use of a calculator in the midterm exams and in the retake exam is NOT allowed.
- 5% of the highest grades may obtain the Honors grade provided that: the NF grade described above exceeds 9. These evaluation conditions will be the same for all students enrolled in the subject, regardless of whether they are first enrolled or if they had already enrolled in previous years. The final decision on the MH grade will be decided by the teaching staff.
- For each assessment activity, a place, date and time of review will be indicated in which the student will be able to review the activity with the teaching staff. In this context, complaints may be made about the grade of the activity, which will be evaluated by the teaching staff responsible for the subject. If the student does not attend this review, this activity will not be reviewed later. The dates of the midterm exams and the retake exam will be published by the Degree Coordination and may be subject to possible programming changes for reasons of adaptation to possible incidents; the Virtual Campus (CV) will always inform of these changes since it is understood that the CV is the usual mechanism for exchanging information between lecturer and students.
- In this subject, the use of any type of digital device is NOT allowed in the classroom (no computers, tablets, no mobile phones, ...); consequently, the use of Artificial Intelligence (AI) technologies is not allowed in the classroom. Any work done in the classroom that includes fragments generated with AI will be considered a lack of academic honesty and may result in a partial or total penalty in the grade of the activity, or greater penalties in cases of seriousness. The use of Artificial Intelligence (AI) technologies is allowed in autonomous activities outside the classroom.
- Without prejudice to other disciplinary measures that are considered appropriate and in accordance with current academic regulations, irregularities committed by a student that may lead to a variation in thegrade will be graded with a zero (0). For example, plagiarism, copying, allowing copying, having communication devices (such as mobile phones, smart watches, etc.) in an evaluation activity, will imply failing this evaluation activity with a zero (0). Assessment activities graded in this way and by this procedure will not be recoverable. If it is necessary to pass any of these assessment activities to pass the subject, this subject will be suspended directly, without the opportunity to recover it in the same year. The numerical grade of the transcript will be the lowest value between 3.0 and the weighted average of the grades in the event that the student has committed irregularities in an evaluation act (and therefore it will not be possible to pass by compensation). The assessment of transversal competences is integrated into the rubric (or problem correction guideline) of the midterm exams. The score of the sections of the rubric corresponding to transversal competences has a value of between 5% and 10% of the score of the corresponding problem.
- This subject does not contemplate a differentiated treatment for repeating students.
- This subject does not provide for the single assessment system.
Bibliography
PRIMARY REFERENCES
- Borges, J.; Serra, J i Arqués, J. M. (1996). Teoria d’autòmats. Materials 28, Publicacions de la UAB.
AUXILIARY REFERENCES
- Casas, R. i Màrquez, L. (2000). Llenguatges, gramàtiques i autòmats. Curs bàsic. Aula teòrica 41, UPC.
- Hopcroft, J. E.; Motwani, R. and Ullman, J. D. (2002). Introducción a la teoría de autómatas, lenguajes y computación. Addison Wesley.
(https://docencia.eafranco.com/materiales/teoriacomputacional/books/TeoriaDeAutomatas,lenguajesYComputacion-Hopcroft.pdf)
- Linz, P. (2001). An Introduction to Formal Languages and Automata. Jones and Bartlett Publishers.
- Martin, J. C. (2004) [2003]. Lenguajes formales y teoría de la computación. McGraw-Hill Interamericana.
Software
There are no Laboratory Practices.
Course groups and languages
The information provided is provisional until November 30. After this date, you will be able to consult the language of each group through this link. To access the information, you will need to enter the course CODE
| Type of teaching | Group | Language | Semester | Shift |
|---|---|---|---|---|
| (PAUL) Classroom practices | 411 | Catalan | second semester | morning-mixed |
| (PAUL) Classroom practices | 412 | Catalan | second semester | morning-mixed |
| (PAUL) Classroom practices | 431 | Catalan | second semester | morning-mixed |
| (PAUL) Classroom practices | 432 | Catalan | second semester | morning-mixed |
| (PAUL) Classroom practices | 451 | Catalan | second semester | afternoon |
| (PAUL) Classroom practices | 452 | Catalan | second semester | afternoon |