Computing Theory

Code:

EIC0022

Acronym:

TCOM

Keywords
Classification	Keyword
OFICIAL	Programming Fundamentals

Instance: 2007/2008 - 2S

Active?	Yes
Web Page:	http://www.fe.up.pt/si/conteudos_adm.conteudos_list?pct_pag_id=1639&pct_parametros=p_ano_lectivo=2007/2008-y-p_cad_codigo=EIC0022-y-p_periodo=2S
Responsible unit:	Informatics Section
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
LEIC	0	Plano de estudos de transição para 2006/07	2	-	6	56	162
MIEEC	0	Syllabus since 2007/2008	4	-	6	56	162
MIEIC	147	Syllabus since 2006/2007	2	-	6	56	162

Teaching language

Portuguese

Objectives

To understand some fundamental concepts of computing models such as finite automata and Turing machines.
To improve the capacity of formal thought about computing and to distinguish rigorous proofs from ad-hoc "evidence".

Program

Automata theory. Finite automata.
Regular expressions and languages. Properties of regular languages.
Context-free grammars and languages.
Pushdown automata.
Properties of context-free languages.
Introduction to Turing machines.
Undecidability. Tractability.

Mandatory literature

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

Complementary Bibliography

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 > Mathematics > Computational mathematics
Physical sciences > Computer science

Evaluation Type

Distributed evaluation with final exam

Assessment Components

Description	Type	Time (hours)	Weight (%)	End date
Subject Classes	Participação presencial	56,00
FInal Exam	Exame	2,00
Midterm exam	Exame	1,00		2008-04-08
	Total:	-	0,00

Amount of time allocated to each course unit

Description	Type	Time (hours)	End date
Study and tutorial exercises	Estudo autónomo	56	2008-07-31
	Total:	56,00

Eligibility for exams

Distributed evaluation not inferior to 6 marks.

Calculation formula of final grade

Grade = rounded (0,3 AD + 0,7 EF).

Special assessment (TE, DA, ...)

Final exam.

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.