Licenciatura | Engenharia Informática

Introdução à Ciência dos Computadores

Área Científica

Ciências Informáticas

Duração

Semestral

ECTS

6

Horas de Contacto Teórico Prático

60h

OBJETIVOS DA APRENDIZAGEM

Para concluir com sucesso esta unidade curricular, os alunos deverão demonstrar possuir os seguintes conhecimentos e capacidades:

  1. Compreender a importância teórica da ciência dos computadores;
  2. Adquirir os conhecimentos matemáticos necessários para a abordagem dos fundamentos teóricos da ciência dos computadores;
  3. Dominar as noções fundamentais sobre teoria dos autómatos e linguagens formais;
  4. Compreender o conceito de máquina de Turing;
  5. Compreender a relevância da máquina de Turing para a análise de sistemas computacionais;
  6. Analisar o conceito de decidibilidade de linguagens;
  7. Compreender os fundamentos teóricos que permitam analisar os problemas da computabilidade;
  8. Compreender os fundamentos teóricos que permitam analisar a complexidade dos algoritmos computacionais.

PROGRAMA

1. Introdução à lógica computacional
2. Fundamentos matemáticos

2.1. Conjuntos, relações e funções

2.2. Grafos e árvores

2.3. Princípio de indução matemática

3. Teoria dos autómatos

3.1. Conceito de autómato

3.2. Descrição de autómatos finitos

3.3. Máquinas de estados finitos

4. Linguagens formais

4.1. Conceito

4.2. Gramáticas

4.3. Linguagens geradas por gramáticas

4.4. Operações em linguagens

4.5. Linguagens e autómatos

5. Conjuntos regulares e gramáticas

5.1. Expressões regulares

5.2. Autómatos finitos e expressões regulares

5.3. Gramáticas regulares

6. Máquinas de Turing

6.1. Modelo de máquina de Turing

6.2. Representação de máquinas de Turing

6.3. Máquinas de Turing e linguagens

7. Decidibilidade

7.1. Algoritmos

7.2. Linguagens decidíveis

7.3. Linguagens indecidíveis

8. Computabilidade

8.1. Conceitos fundamentais

8.2. Análise da computabilidade

9. Complexidade computacional

9.1. Funções de crescimento

9.2. Classes P e NP

9.3. Análise da complexidade de algoritmos

DEMONSTRAÇÃO DE COERÊNCIA ENTRE CONTEÚDOS PROGRAMÁTICOS E RESULTADOS DA APRENDIZAGEM

Os conteúdos programáticos foram definidos por forma a permitir uma progressão que, partindo de conceitos básicos, possibilite a compreensão do edifício conceptual que sustenta os fundamentos teóricos da ciência dos computadores, especialmente no que respeita aos problemas de computabilidade e da complexidade espacial e temporal dos algoritmos.

METODOLOGIA DE ENSINO E AVALIAÇÃO

Esta unidade curricular tem uma natureza teórico-prática. Estão previstas 60 horas de contato. O tempo total de trabalho do aluno corresponde a 162 horas. Tratando-se de uma unidade curricular com elevado nível de abstração, é fundamental que os conceitos apresentados sejam de imediato ilustrados com exemplos práticos que permitam aos alunos testar a compreensão das matérias.
De acordo com o Regulamento de Funcionamento do ISTEC a avaliação é efetuada através de um exame escrito individual e obrigatório. Na classificação final, poderão ser considerados elementos de avaliação contínua, tais como testes, trabalhos individuais ou em grupo, assim como a participação nas aulas presenciais e em recursos de aprendizagem proporcionados por sistemas de e-learning.

DEMONSTRAÇÃO DE COERÊNCIA ENTRE METODOLOGIAS DE ENSINO E RESULTADOS DE APRENDIZAGEM

A metodologia usada, constituída por exposições teóricas, exemplos práticos e exercícios resolvidos na aula, permitirá aos alunos assimilar os conceitos teóricos necessários para compreender os fundamentos teóricos da ciência dos computadores, designadamente a teoria dos autómatos, das linguagens formais, da computabilidade e da complexidade computacional.

BIBLIOGRAFIA

Fundamental:
N. Chandrasekaran, Theory of Computer Science: Automata, Languages and Computation
Michael Sipser, Introduction to the Theory of Computation 3rd Edition

Complementar:
Shyamalendu Kandar, Introduction to Automata Theory, Formal Languages and Computation
Krithivasan ,Kamala and R Rama, Introduction to Formal Languages, Automata Theory and Computation

INTERNET:
Acesso a publicações da especialidade, gratuitamente, através da rede SPRINGER:

https://link.springer.com/