Teoria da Computação
(cod.11562)

1  Novidades

• 15/06/2015 Notas do Exame aqui.
• 03/06/2015 Notas da Avaliação Contínua aqui.
• 03/06/2015 Os critérios de “Não Admissão” aplicados à NCP foram suspensos até ao dia do exame de primeira chamada (em consequência não haverá temporariamente “Não Admissão” causado exclusivamente pela falha na avaliação prática). Neste dia o site do mooshak estará aberto exclusivamente para o problema E até às 18h00. Nesta hora, os critérios de não admissão ou de reprovação por esta componente retomam a sua normalidade (a não entrega duma solução aceite ao probelma E terá as consequências esperadas no momento da avaliação contínua).
• 22/05/2015 Entrega do quinto problema adiado até dia 2 de Junho.
• 07/05/2015 Entrega do quarto problema adiado até dia 15 de Maio.
• 17/04/2015 Notas da frequência aqui.
• 14/04/2015 Entrega do terceiro problema adiado uma última semana.
• 06/04/2015 Entrega do terceiro problema adiado uma semana.
• 23/03/2015 O mooshak aceita submissões para o quarto e quinto problema.
• 20/03/2015 O quinto problema por resolver encontra-se online (mooshak por configurar).
• 17/03/2015 O quarto problema por resolver encontra-se online (mooshak por configurar).
• 13/03/2015 O mooshak aceita submissões para o terceiro problema.
• 06/03/2015 O terceiro problema por resolver encontra-se online (mooshak por configurar).
• 05/03/2015 O mooshak aceita submissões para o segundo problema.
• 15/02/2015 O segundo problema por resolver encontra-se online.
• 11/02/2015 O Primieiro problema por resolver encontra-se online.
• 11/02/2015 O sistema mooshak encontra-se desde já configurado para a presente disciplina. Queira proceder ao seu registo. No processo de registo, escolhe o seu nome da seginte forma: "a” + numero de aluno + primeiro nome. Por exemplo, Luís com o numero 12345 tem por registo mooshak "a12345Luis".
• 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 são convidados a dirigir-se ao regente para discutir os 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
• 11  Links úteis

2  Docentes

• Simão Melo de Sousa (regente) - Gabinete 3.17 - Laboratório Release (6.25) - Bloco VI.
• Marco Giunti - 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.

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 duas provas escritas e por avaliação contínua baseada na resolução individual 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 5 e resolvidos de uma forma sequencial e individual. Com a excepção do primeiro enunciado que será comunicado no inicio das aulas, os enunciados serão entregue na semana da resolução do exercício anterior. 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 em duas frequências, previstas nas datas anunciadas na secção 6.

Da média destas duas provas 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

• Entrega do primeiro exercício: 6 de Março de 2015.
• Entrega do segundo: 20 de Março de 2015.
• Entrega do terceiro exercício: 24 de Abril de 2015 (nova data).
• Entrega do quarto exercício: 15 de Maio de 2015 (nova data).
• Entrega do quinto exercício: 2 de Junho 2015 (nova data).
• Primeira Frequência: dia 7 de Abril de 2015 das 18h00 às 20h00.
• Segunda Frequência: dia 26 de Maio de 2015 das 18h00 às 20h00.
• Exame Época Normal : (conferir no site dos académicos)
• Exame Época de Recurso : (conferir no site dos académicos)

7  Horário

8  Atendimento

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

• Introdução contextual e histórica à Teoria da Computação
• Conceitos preliminares à Teoria da Computação e às Linguagens Formais
• Complementos sobre técnicas matemáticas - suporte pedagógico auxiliar
• Complementos sobre técnicas matemáticas para a Teoria da Computação (mais detalhes sobre indução estrutural) - suporte pedagógico auxiliar
• Capítulo "OCaml"
• Capítulo "Autómatos"
• Acetatos manuscritos "automatos"  num só pdf
• Acetatos manuscritos "automatos"  formato RAR
• 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)
• Capítulo "Linguagens e Gramáticas"
• Capítulo "Autómatos PushDown e Linguagens Algébricas"
• Capítulo "Máquinas de Turing"

Práticas

• Primeiro Guião OCaml
• Segundo Guião OCaml
• Terceiro Guião OCaml
• Quarto Guião OCaml
• Ficha Prática OCaml
• Ficha "Ocaml" suplementar
• Ficha "Fundamentos"
• Ficha Prática Introdução às Linguagens Formais
• Ficha "Técnicas Matemáticas" (ficha auxiliar)
• Ficha "Linguagens Regulares e Autómatos"
• Ficha "Gramáticas, Linguagens Formais e Linguagens Algébricas"

Algumas resoluções

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

Trabalhos Práticos

• Primeiro exercício por entregar (pdf)
  
• Segundo exercício por entregar (pdf)
  
• Terceiro exercício por entregar (pdf) (material auxiliar aqui)
  
• Quarto exercício por entregar (pdf) (material auxiliar aqui)
  
• Quinto exercício por entregar (pdf)
  

10  Bibliografia Principal

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

11  Links úteis

• Ocaml
  • Site OCaml
  • OCamlMakefile: Makefile genérico para OCaml
  • Tuareg: Emacs Mode para Ocaml
  • Livro: Developing Applications With Objective Caml
  • Manual de Referência Ocaml
  • Hump: Repositório de aplicações/bibliotecas/”material” OCaml
• Emacs
  • Site Emacs - XEmacs
  • Documentação Emacs - XEmacs
  • Comandos principais para o Emacs 23
• Um site sobre Ciências da Computação (contem livros online)
  • Site Programming languages theory texts online

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]

J.E. Hopcroft, R. Motwani, and J.D. Ullman. Introduction to automata theory, languages, and computation. Pearson education, 2001.

[7]

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

[8]

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

[9]

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

[10]

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

[11]

Pierre Wolper. Introduction à la Calculabilité. 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.