Computing Theory
Keywords |
Classification |
Keyword |
OFICIAL |
Programming Fundamentals |
Instance: 2007/2008 - 2S
Cycles of Study/Courses
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.