Computing Theory
Keywords |
Classification |
Keyword |
OFICIAL |
Programming Fundamentals |
Instance: 2009/2010 - 1S
Cycles of Study/Courses
Acronym |
No. of Students |
Study Plan |
Curricular Years |
Credits UCN |
Credits ECTS |
Contact hours |
Total Time |
MIEIC |
155 |
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
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 |
Attendance (estimated) |
Participação presencial |
52,00 |
|
|
|
Exame |
2,50 |
|
|
|
Exame |
1,50 |
|
|
|
Total: |
- |
0,00 |
|
Amount of time allocated to each course unit
Description |
Type |
Time (hours) |
End date |
|
Estudo autónomo |
78 |
|
|
Estudo autónomo |
26 |
|
|
Total: |
104,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.