Teoria da Computação
(cod.11562)

---

Figure 1: ...but don’t they already know how?

---

1  Novidades

• 12/03/2019 - ver alterações de datas na secção datas importante 6.
• 12/03/2019 - Aula de reposição (devido ao carnaval) marcada para o dia 19/03/2019 às 18h00 (sala 6.26)
• 4/03/2019 - Os problemas A, B e C disponíveis. o sistema mooshak já aceita submissões ao problema A e ao problema B.
• 11/02/2019 - A aula teórica do dia 26 de Fevereiro terá lugar excepcionalmente no Museu de Lanifícios (no mesmo horário, das 16h00 às 18h00). Local : Auditório do Museu de Lanifícios - Núcleo da Real Fábrica Veiga, na Calçada do Biribau (junto à Goldra).
• 11/02/2019 - Haverá aulas práticas na primeira semana de aulas.
• 11/02/2019 - O sistema mooshak encontra-se desde já configurado para a presente disciplina. Queira proceder ao seu registo. Aceita-se a formação de grupos de, no máximo, duas pessoas. No processo de registo, escolhe o grupo UBI e defina o nome da equipa da seguinte forma.

  Se for um grupo de um só elemento: numero de aluno + primeiro nome. Por exemplo, Luís com o numero 12345 tem por registo mooshak "12345Luis".

  Se for um grupo de duas pessoas: numero de aluno do primeiro elemento (o de número mais baixo) + primeiro nome+numero de aluno do segundo elemento + primeiro nome. Assim se Luis forma grupo com o João (aluno 13245), então o grupo registra-se com o nome “12345Luis13245Joao”.

• Como colocar uma dúvida ao regente da Unidade Curricular?
  1. Comparecer nas aulas e colocá-la directamente ao regente
  2. Comparecer no horário de atendimento do regente e colocá-la directamente
  3. enviar um email ao regente (desousaUUU@UUUdi.ubi.pt, (retire os UUU) ) com o assunto "TC: XXXX" em que XXX é o título da dúvida em questão. Qualquer outro formato no assunto arrisca condenar o email ao esquecimento.
• Inscrição em turmas práticas: via site dos serviços académicos.
• As aulas práticas começam logo na primeira semana de aulas.
• Os alunos com estatuto de trabalhador estudante devem procurar o regente para discutir eventual adaptação dos critérios de avaliação.
• Primeira versão da página. Encontrará aqui as novidades associadas à disciplina de Teoria da Computação. A sua consulta regular é necessária ao bom funcionamento da Unidade Curricular.

Contents

• 1  Novidades
• 2  Docentes
• 3  Objectivos
• 4  Programa
  • 4.1  Competências da UC ou Resultados da Aprendizagem
• 5  Critérios de Avaliação
  • 5.1  Actividades de Ensino-Aprendizagem e Metodologias Pedagógicas
  • 5.2  Fraudes
  • 5.3  Componente Prática
  • 5.4  Componente Teórica
  • 5.5  Concessão de Frequência e Avaliação Contínua
  • 5.6  Avaliação por Exame
• 6  Datas Importantes
• 7  Horário
• 8  Atendimento
• 9  Material Pedagógico e Funcionamento da Disciplina
• 10  Bibliografia Principal

2  Docentes

• Simão Melo de Sousa (regente) - Gabinete 3.17 - Laboratório Release (6.25) - Bloco VI.

3  Objectivos

Existem limites à capacidade de resolução de problemas por um computador, mesmo na hipótese “idealista” de ausência de restrições, que sejam essas o tempo (de execução) ou o espaço (memória).

Para delinear esses limites, visaremos:

1. perceber a capacidade de computação das máquinas, assim como os seus limites teóricos. Precisaremos de definir formalmente o que é e o que não é um programa, um algoritmo, ou mais genericamente o que é um tratamento efectivo;
2. perceber os conceitos que fundamentam as linguagens de programação. Precisaremos de determinar e estudar formalmente as construções que determinam a expressividade (ou capacidade de computação) das linguagens de programação assim como o comportamento dos programas.

4  Programa

• Apresentação Contextual e Histórica da Teoria da computação
• Modelos da computação: dos autómatos (de estados finitos, com pilha) às máquinas de Turing.
• Modelos de computação alternativos: Funções recursivas de Kleene e calculo lambda.
• Programação em modelos da computação.
• Tese de Church-Turing. Provas de equivalência de modelos.
• A não computabilidade e a indecidibilidade: Problemas indecidíveis, técnica da diagonalização, técnica da redução.
• Complexidade. Introdução: problemas tratáveis e problemas intratáveis. Critérios de catalogação (memória, tempo, etc.). Caracterização das classes NP, P e NP-Completo. Problemas NP-Completos: Exemplos. Técnica da redução polinomial para a demonstração de NP-completude.

4.1  Competências da UC ou Resultados da Aprendizagem

O aluno deverá ser capaz de perceber e usar a capacidade de computação das máquinas, assim como os seus limites teóricos.

Deverá ser capaz de formalizar adequadamente e avaliar se determinados problemas tem solução computacional ou não.

Deverá perceber e saber usar modelos, técnicas e algoritmos de computação simbólica introduzidos na resolução de problemas informáticos do dia-a-dia.

5  Critérios de Avaliação

5.1  Actividades de Ensino-Aprendizagem e Metodologias Pedagógicas

Por fim a avaliar as competências adquiridas, as actividades de Ensino-Aprendizagem avaliarão tanto a compreensão dos conceitos teóricos expostos como a capacidade em por estes em prática.

Assim, a avaliação será constituída por duas componentes: a componente prática (exercícios práticos entregues à equipa docente) e a componente teórica (provas escritas).

Mais precisamente a avaliação será realizada por uma prova escrita e por avaliação contínua baseada na resolução de exercícios práticos.

5.2  Fraudes

A equipa docente realça que qualquer tipo de fraude em qualquer dos itens desta disciplina implica a reprovação automática do aluno faltoso (i.e. Não Admissão), podendo ainda vir a ser este alvo de processo disciplinar.

Listamos a seguir as diferentes componentes da avaliação.

5.3  Componente Prática

• Esta avaliação mede em termos práticos a aquisição dos conceitos expostos. Como tal é baseada na avaliação da resolução de exercícios durante as práticas laboratoriais.
• Os exercícios avaliados são em número de 3 e resolvidos de uma forma sequencial. Os enunciados serão publicados no inicio do semestre. As datas exactas de entrega encontram-se na secção 6. A entrega é feita de forma electrónica no site mooshak da UC.
• A Nota da Componente Prática (NCP, 20 valores) é a soma dos valores atribuídos aos diferentes exercícios resolvidos.

5.4  Componente Teórica

A avaliação da componente teórica consiste numa única prova escrita (frequência), prevista na data anunciada na secção 6.

Da avaliação qualitativa da frequência resulta a Nota da Componente Teórica (NCT, 20 valores).

5.5  Concessão de Frequência e Avaliação Contínua

O parâmetro de "Frequência" atribuído no final desta unidade curricular traduz, no contexto da avaliação contínua, a "avaliação mínima" do estudante ao longo do processo de ensino-aprendizagem no final das actividades de contacto.

Considera-se que o estudante demonstrou ter adquirido o grau de conhecimentos mínimos (durante o processo de aprendizagem ao longo das actividades lectivas) quando este demonstrou as mínimas competências em cada componente avaliada.

É assim concedido Frequência ao aluno que obteve os mínimos (6) em vigor na Universidade da Beira Interior em ambas as componentes (NCP e NCT).

No caso de Frequência, a avaliação quantitativa, designada aqui de nota da avaliação contínua, é determinada da seguinte forma:

Se a avaliação quantitativa resultar numa nota maior ou igual a 10 então o aluno é dispensado de exame (Frequência com dispensa de exame).

5.6  Avaliação por Exame

• A prova escrita do exame substituirá a Nota da Componente Teórica da avaliação contínua, dando uma nova NCT.
• Assim a nota final (NFin) após exame é calculada da seguinte forma:

  NFin=if ( NCT≥ 6) then

  NCT× 1.2 + NCP × 0.8 2

  else  Reprovado

6  Datas Importantes

• Data de entrega dos enunciados: Todos os enunciados se encontram disponíveis.
• Entrega do primeiro exercício: semana do dia 2 de Abril de 2019.
• Entrega do segundo: 28 de Abril de 2019.
• Entrega do terceiro exercício: 21 de Maio de 2018.
• Frequência: dia 28 de Maio de 2019 das 16h00 às 18h00.
• Exames : (conferir no site dos académicos)

7  Horário

8  Atendimento

Por marcação (e.g. via email) ou

9  Material Pedagógico e Funcionamento da Disciplina

Os Apontamentos serão atempadamente disponibilizados nas aulas e por meios electrónicos. É esperado e assumido que o aluno tenha lido os acetatos referentes ao capítulo em curso antes das aulas teóricas.

Teóricas

Computação Simbólica e Programação

consultar a página seguinte (link)

Modelos de Computação

• Aula Inaugural - O nascer de uma disciplina     -     Introdução contextual e histórica à Teoria da Computação (em forma de sebenta)
• Capítulo: Técnicas matemáticas
  • Complementos sobre técnicas matemáticas para a Teoria da Computação (mais detalhes sobre indução estrutural) - suporte pedagógico auxiliar
• Capítulo: Conceitos preliminares à Teoria da Computação e à Teoria das Linguagens Formais
• Capítulo: Autómatos Finitos
  • Acetatos manuscritos "automatos"  num só pdf
  • Acetatos manuscritos "automatos"  formato RAR
• Capítulo: Linguagens e Gramáticas
• Capítulo: Autómatos PushDown e Linguagens Algébricas
• Capítulo: Máquinas de Turing
• Capítulo: Funções Recursivas de Kleene
• Capítulo: A não-computabilidade
• Capítulo: A teoria da complexidade

Código OCaml para suporte às aulas

• Execução genérica de autómatos finitos não determinísticos com є-transições (em ocaml)
• Execução genérica de autómatos finitos determinísticos (em ocaml)

Práticas

• Ficha: Fundamentos da Computação
• Ficha: Técnicas Matemáticas
• Ficha: Prática Introdução às Linguagens Formais
• Ficha: Linguagens Regulares e Autómatos
• Ficha: Gramáticas, Linguagens Formais e Linguagens Algébricas
• Ficha: Máquinas de Turing
• Ficha: Funções recursivas de Kleene
• Ficha: A não computação
• Ficha: Complexidade algorítmica

Algumas resoluções

• Zip contendo enunciados de provas dos anos anteriores
• Correcção da Frequência 2011/2012

Exercícios Por Entregar

• Problema A: Primeiro exercício por entregar (pdf)
  
• Problema B: Segundo exercício por entregar (pdf)
  
• Problema C: Terceiro exercício por entregar (pdf)
  

10  Bibliografia Principal

As referencias principais são: [8, 9, 12, 6, 1] utilizaremos ocasionalmente as referências [5, 11, 2, 10, 4, 7, 3].

References

[1]

J.B. Almeida, M.J. Frade, J.S. Pinto, and S. Melo de Sousa. Rigorous Software Development, An Introduction to Program Verification, volume 103 of Undergraduate Topics in Computer Science. Springer-Verlag, first edition, 307 p. 52 illus. edition, 2011.

[2]

A. Arnold and I. Guessarian. Mathematics for Computer Science. Prentice-Hall, 1996.

[3]

E. Chailloux, P. Manoury, and B. Pagano. Developing applications with objective caml. http://caml.inria.fr/oreilly-book, 2003.

[4]

M. Fernández. Models of Computation: An Introduction to Computability Theory. Undergraduate Topics in Computer Science. Springer, 2009.

[5]

Chris Hankin. Lambda Calculi: A Guide for Computer Scientists, volume 3 of Graduate Texts in Computer Science. Clarendon Press, Oxford, 1994.

[6]

Jason Hickey, Anil Madhavapeddy, and Yaron Minsky. Real World OCaml. O’Reilly, 2014.

[7]

J.E. Hopcroft, R. Motwani, and J.D. Ullman. Introduction to automata theory, languages, and computation. Pearson education, third edition, 560 pages. edition, 2006.

[8]

Harry R. Lewis and Christos H. Papadimitriou. Elements of the Theory of Computation. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1997.

[9]

P. Linz. An introduction to formal languages and automata. Jones and Bartlett Publisher, 2006.

[10]

David Makinson. Sets, Logic and Maths for Computing. Springer Publishing Company, Incorporated, 1 edition, 2008.

[11]

M. Sipser. Introducton to the Theory of Computation. PWS Publishing, 2006.

[12]

Pierre Wolper. Introduction á la Calculabilitér. Dunod, Paris, France, 3 edition, 2006.

Enviar comentários e dúvidas para (retire os UUU) : desousaUUU@UUUdi.ubi.pt

This document was translated from L^AT_EX by H^EV^EA.