Go to:
Esta página em português Ajuda Autenticar-se
Formação regular da Biblioteca |fevereiro a maio
You are here: Start > EIC0022

Site map
Edifício A (Administração) Edifício B (Aulas) - Bloco I Edifício B (Aulas) - Bloco II Edifício B (Aulas) - Bloco III Edifício B (Aulas) - Bloco IV Edifício C (Biblioteca) Edifício D (CICA) Edifício E (Química) Edifício F (Minas e Metalurgia) Edifício F (Minas e Metalurgia) Edifício G (Civil) Edifício H (Civil) Edifício I (Electrotecnia) Edifício J (Electrotecnia) Edifício K (Pavilhão FCNAUP) Edifício L (Mecânica) Edifício M (Mecânica) Edifício N (Garagem) Edifício O (Cafetaria) Edifício P (Cantina) Edifício Q (Central de Gases) Edifício R (Laboratório de Engenharia do Ambiente) Edifício S (INESC) Edifício T (Torre do INEGI) Edifício U (Nave do INEGI) Edifício X (Associação de Estudantes)

Computing Theory

Code: EIC0022     Acronym: TCOM

Classification Keyword
OFICIAL Programming Fundamentals

Instance: 2014/2015 - 1S Ícone do Moodle

Active? Yes
Web Page: http://moodle.up.pt/course/view.php?id=2875
Responsible unit: Department of Informatics Engineering
Course/CS Responsible: Master in Informatics and Computing Engineering

Cycles of Study/Courses

Acronym No. of Students Study Plan Curricular Years Credits UCN Credits ECTS Contact hours Total Time
MIEIC 183 Syllabus since 2009/2010 2 - 6 56 162

Teaching - Hours

Lectures: 2,00
Recitations: 2,00
Type Teacher Classes Hour
Lectures Totals 1 2,00
Daniel Augusto Gama de Castro Silva 2,00
Recitations Totals 6 12,00
João Tiago Pinheiro Neto Jacob 4,00
Daniel Augusto Gama de Castro Silva 4,00
Luís Filipe Guimarães Teófilo 4,00
Mais informaçõesLast updated on 2014-08-14.

Fields changed: Objectives, Resultados de aprendizagem e competências, Métodos de ensino e atividades de aprendizagem, Fórmula de cálculo da classificação final, Componentes de Avaliação e Ocupação, Obtenção de frequência, Programa, URL da página, Avaliação especial

Teaching language

Suitable for English-speaking students


To prepare students about computing theory topics with a special emphasis to formal language topics.
Students will learn about regular languages, regular expressions, non-regular languages, deterministic and nondeterministic finite automata, context-free languages and grammars, deterministic and nondeterministic pushdown automata, and Turing machines, and how to apply these topics to problems.
Students will be able to express computing problems by using formal languages, automata and Turing machines.
In addition, students will learn how to formally specify computing problems related to formal languages and prove related statements.

Learning outcomes and competences

At the end of the semester, students should:
- Be capable of identifying the important contributions to computing theory and its protagonists;
- Be capable of identifying the problems that can be solved with finite automata and express them rigorously;
- Be capable of comparing deterministic finite automata (DFAs), non deterministic finite automata (NFAs), regular expressions and regular languages;
- Be capable of applying the properties of regular languages;
- Be capable of identifying problems which can be handled by context- free grammars (CFGs);
- Be capable of relating context- free grammars and pushdown automata (PDAs) in the processing of context-free languages;
- Be capable of expressing computing problems by using Turing machines;
- Be capable of relating the studied computing models with their applications in the computability theory and complexity theory.

Working method


Pre-requirements (prior knowledge) and co-requirements (common knowledge)

It is recommended that students have attended the Discrete Mathematics course.


Automata Theory; Finite Automata;
Regular Expressions and Languages;
Properties of Regular Languages;
Context-Free Grammars and Languages;
Pushdown Automata;
Properties of Context-Free Language;
Introduction to Turing Machines.

Mandatory literature

Hopcroft, John E.; Introdução à teoria de autômatos, linguagens e computação. ISBN: 85-352-1072-5

Complementary Bibliography

Sipser, Michael; Introduction to the theory of computation. ISBN: 0-619-21764-2
Sudkamp, Thomas A.; Languages and Machines. ISBN: 0-201-15768-3

Teaching methods and learning activities

In theoretical classes the contents are formally exposed along with presentation and discussion of examples.
In tutorial classes application exercises are proposed.
Two mini-test will be held, approximately six and twelve weeks fromt he start of the semesteer, to check if the basic concepts are being understood by the majority of students.
The foreseen effort beyound classes is of about 4h per week.


JFlap: JFLAP is software for experimenting with formal languages topics. (http://www.jflap.org/)


Physical sciences > Mathematics > Computational mathematics
Physical sciences > Computer science

Evaluation Type

Distributed evaluation with final exam

Assessment Components

Designation Weight (%)
Exame 60,00
Participação presencial 0,00
Teste 40,00
Total: 100,00

Amount of time allocated to each course unit

Designation Time (hours)
Estudo autónomo 103,00
Frequência das aulas 59,00
Total: 162,00

Eligibility for exams

Distributed evaluation not inferior to 7 marks, with the grade of each mini-test (MT) not inferior to 6 marks, and a maximum of 3 non-justified absenses (25%) on the tutorial classes.

Calculation formula of final grade

AD: Distributed Evaluation consists of two components, MT1 and MT2 = 0.5 MT1 + 0.5 MT2 (min: 7 marks)

MT1 and MT2: mini-tests 1 and 2, respectively (min: 6 marks for each)

EF: final exam (min: 7 marks)

Grade = rounded(0.4 AD + 0.6 EF).

Examinations or Special Assignments


Special assessment (TE, DA, ...)

One of the following possibilities (selected by the student):
- Final Exam
- Final Exam (EF) + mini-tests (MT)

Classification improvement

The final grade can be improved with a classification improvement exam.


The pre-requirements are: knowledge of Computational Logic and of programming.

Students that have obtained Distributed Evaluation (AD) in the previous year are able to use their AD grade in the current year.

The official language is Portuguese, but we admit that the classes might be given in English.

Recommend this page Top
Copyright 1996-2019 © Faculdade de Engenharia da Universidade do Porto  I Terms and Conditions  I Accessibility  I Index A-Z  I Guest Book
Page generated on: 2019-05-24 at 12:57:36