Computing Theory

Code:

EIC0022

Acronym:

TCOM

Keywords
Classification	Keyword
OFICIAL	Programming Fundamentals

Instance: 2011/2012 - 1S

Active?	Yes
Web Page:	https://moodle.fe.up.pt/1112/course/view.php?id=3586
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
MIEEC	7	Syllabus (Transition) since 2010/2011	4	-	6	56	162
			5
		Syllabus	4	-	6	56	162
			5
MIEIC	143	Syllabus since 2009/2010	2	-	6	56	162

Teaching language

Portuguese

Objectives

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.

Program

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. A mini-test will be done to check if the basic concepts are being understood by the majority of students.

keywords

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

Evaluation Type

Distributed evaluation with final exam

Assessment Components

Description	Type	Time (hours)	Weight (%)	End date
Attendance (estimated)	Participação presencial	48,00
Exam	Exame	2,50
Preparation for Exam/Midterm Exam	Exame	26,00
Midterm Exam	Exame	1,50
	Total:	-	0,00

Amount of time allocated to each course unit

Description	Type	Time (hours)	End date
Homework	Estudo autónomo	18
Weekly study and preparation	Estudo autónomo	66
	Total:	84,00

Eligibility for exams

Distributed evaluation with the grade in the mini-test (MT) not inferior to 6 marks and submission of at least 8 of the 9 homeworks.

Calculation formula of final grade

AD: distributed evaluation consists of two components, MT and TPC = 0.80 MT + 0.20 TPC

TPC: resolution of the homeworks

MT: mini-test.

EF: final exame.

Grade = rounded(0.4 AD + 0.6 EF).

Examinations or Special Assignments

None.

Special assessment (TE, DA, ...)

One of the following possibilities:
- Final Exam, or
- Final Exam (EF) + mini-test (MT), and in this case: Grade = rounded(0.3 MT + 0.7 EF).

Classification improvement

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

Observations

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.