Go to:
Logótipo
You are in:: Start > CC1004

Computational Models

Code: CC1004     Acronym: CC1004     Level: 100

Keywords
Classification Keyword
OFICIAL Computer Science

Instance: 2019/2020 - 2S Ícone do Moodle

Active? Yes
Web Page: http://www.dcc.fc.up.pt/~rvr/aulas/AC1920/MC19-20/
Responsible unit: Department of Computer Science
Course/CS Responsible: Bachelor in Computer Science

Cycles of Study/Courses

Acronym No. of Students Study Plan Curricular Years Credits UCN Credits ECTS Contact hours Total Time
L:B 2 Official Study Plan 3 - 6 56 162
L:CC 103 Plano de estudos a partir de 2014 1 - 6 56 162
L:F 6 Official Study Plan 2 - 6 56 162
3
L:G 0 study plan from 2017/18 2 - 6 56 162
3
L:M 7 Official Study Plan 2 - 6 56 162
3
L:Q 0 study plan from 2016/17 3 - 6 56 162
MI:ERS 125 Plano Oficial desde ano letivo 2014 1 - 6 56 162
Mais informaçõesLast updated on 2020-02-09.

Fields changed: Calculation formula of final grade

Teaching language

Portuguese

Objectives

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.

Learning outcomes and competences

Students are expected to be able to describe simple formal languages using different models of computation and classify them in the Chomsky hierarchy.

Working method

Presencial

Program

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.

Mandatory literature

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman; Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2006. ISBN: 0-321-47617-4
Dexter C. Kozen; Automata and Computability, Sringer, 1997. ISBN: ISBN 0-387-94907-0
Mark V. Lawson; Finite Automata, Chapman & Hall/CRC, 2004. ISBN: 1-58488-255-7

Teaching methods and learning activities

Lectures: exposition of  the syllabus topics and examples.
Practical Lectures: exercise solving and discussion.

Evaluation Type

Distributed evaluation without final exam

Assessment Components

designation Weight (%)
Teste 100,00
Total: 100,00

Amount of time allocated to each course unit

designation Time (hours)
Estudo autónomo 56,00
Frequência das aulas 106,00
Total: 162,00

Eligibility for exams

Students must attend at least 3/4 of the pratical classes to be admitted to the exams.

Calculation formula of final grade

The final mark corresponds to the classification obtained
- as average grade of three tests to be realized during the semester and at the date of the first exam (each with a classification of at least 6 out of 20 points);
- or the grade of the second exam (época de recurso).

Classification improvement

Distributed evaluation (3 tests) without final exam.
Recommend this page Top
Copyright 1996-2024 © Faculdade de Ciências da Universidade do Porto  I Terms and Conditions  I Acessibility  I Index A-Z  I Guest Book
Page created on: 2024-09-01 at 22:44:46 | Acceptable Use Policy | Data Protection Policy | Complaint Portal