Code: | CC1004 | Acronym: | CC1004 | Level: | 100 |
Keywords | |
---|---|
Classification | Keyword |
OFICIAL | Computer Science |
Active? | Yes |
Web Page: | http://piazza.com/up.pt/spring2021/cc1004 |
Responsible unit: | Department of Computer Science |
Course/CS Responsible: | Bachelor in Computer Science |
Acronym | No. of Students | Study Plan | Curricular Years | Credits UCN | Credits ECTS | Contact hours | Total Time |
---|---|---|---|---|---|---|---|
L:B | 1 | Official Study Plan | 3 | - | 6 | 56 | 162 |
L:CC | 117 | Plano de estudos a partir de 2014 | 1 | - | 6 | 56 | 162 |
L:F | 3 | Official Study Plan | 2 | - | 6 | 56 | 162 |
3 | |||||||
L:G | 1 | study plan from 2017/18 | 2 | - | 6 | 56 | 162 |
3 | |||||||
L:M | 4 | Official Study Plan | 2 | - | 6 | 56 | 162 |
3 | |||||||
L:Q | 0 | study plan from 2016/17 | 3 | - | 6 | 56 | 162 |
MI:ERS | 149 | Plano Oficial desde ano letivo 2014 | 1 | - | 6 | 56 | 162 |
Teach fundamental concepts and results about three computational models (finite automata, pushdown automata, Turing machines) and the related classes of formal languages, with emphasis on regular and context free languages.
Students are expected to be able to describe simple formal languages using different models of computation and classify them in the Chomsky hierarchy.
Notion of formal language. Deterministic finite automata and non-deterministic finite automata. Regular expressions and finite automata. Properties of regular languages. Minimization of finite automata. Pumping lemma for regular languages. Context-free grammars and languages. Derivation trees. Ambiguity. Simplification of context-free grammars and normal forms. Push-down automata. Properties of context-free languages. Pumping lemma for context-free grammars. Turing machines and notion of computability.
Lectures: exposition of the syllabus topics and examples.
Practical Lectures: exercise solving and discussion.
designation | Weight (%) |
---|---|
Exame | 100,00 |
Participação presencial | 0,00 |
Teste | 0,00 |
Total: | 100,00 |
designation | Time (hours) |
---|---|
Estudo autónomo | 106,00 |
Frequência das aulas | 56,00 |
Total: | 162,00 |
Students must attend at least 75% of the pratical classes to be admitted to the exams.
If COVID'19 Pandemic allows it, there will be two optional tests during the semester (TE1, TE2). To attend TE2, it is required a minimum grade of 8.0/20.0 in TE1. The second test covers all topics. A minimum grade of 8.0/20.0 is required also.
The final grade is given by
max(0.4*TE1+0.6*TE2, TE2, FinalExam)
Students do not need to take the final exam if max(0.4*TE1+0.6*TE2, TE2) >= 9.5.