CCM-104: Teoria da Computação Terceiro Quadrimestre de 2023

Avisos importantes

  • 🆕 19/12 - Notas da P2 liberadas
  • 🆕 06/12 - Notas da P1 liberadas
  • 29/11 - Atualização da data da P2
  • 29/11 - Slides sobre: MT e Decidibilidade foram adicionados
  • 11/11 - Slides sobre lema do bombeamento para linguagens livres de contexto foi adicionado ao site
  • 31/10 - Notas de aula sobre gramática foram atualizadas; Slides sobre automato com pilha foram adiconados; lista de exercício de gramática foi atualizada.
  • 28/10 - Notas de aula sobre gramática foram adicionadas
  • 20/10 - Notas de aula sobre o lema do bombeamento foram adicionadas
  • 22/09 - Slide de AFD foi atualizado
  • 20/09 - Seção Atendimento foi atualizada
  • 19/09 - Página está no ar.

Objetivos

  1. Apresentar os conceitos fundamentaisda teoria da computação. (ii) Familiarizar o aluno com modelos teóricos de um computador e o tratamento formal de tais modelos. (iii) Apresentar ao aluno as diferentes classes de linguagens.
  2. Preparar o aluno para o posterior estudo de técnicas de construção de Compiladores e processamento de Linguagem Natural. (v) Refinar a habilidade do aluno para tratar com conceitos formais abstratos.

Ementa da disciplina

Linguagens Regulares: autômatos finitos determinísticos e não-determinísticos, expressões regulares. Linguagens livres de contexto: gramáticas livres de contexto e autômatos com pilha. Máquinas de Turing: decidibilidade e reconhecibilidade. O problema da parada. Redução. Classes de complexidade: P, NP e NP-completo.

Recomendação

Fundamentos de Ciências da Computação I, Análise de Algoritmos e Estruturas de Dados.

Para facilitar o acompanhamento do curso, é recomendado que você já possua:

  • Conhecimentos de programação (em qualquer linguagem imperativa)
  • Familiaridade com estruturas de dados básicas (vetores, pilhas)
  • Familiaridade com linguagem matemática (conjuntos, sequências, relações, funções)
  • Capacidade para seguir argumentos lógicos em uma demonstração matemática

Materiais de apoio para esses tópicos:

Bibliografia

Livro texto

  1. SIPSER, M. Introduction to the Theory of Computation. 2nd edition. Boston, Massachusetts: Thomson, 2006.
    • Errata
    • Tradução: SIPSER, M. Introdução à teoria da computação. 2 ed. São Paulo, SP: Thomson Learning, 2007.

Livros auxiliares

  1. HOPCROFT, J. E.; ULLMAN, D. J.; MOTWANI, R. Introdução à teoria de autômatos, linguagens e computação. 2. ed. Rio de Janeiro, RJ: Campus, 2003.
  2. Vieira, N. J.. Introdução aos Fundamentos da Computação: Linguagens e Máquinas. 1a edição. Cengage Learning. 2006.

Dias, horários e locais das aulas

  • Terças-feiras: 14h - 16h (Sala A - S-307-1).
  • Quintas-feiras: 14h - 16h (Sala A - S-307-1).

Critério de avaliação

A média final ( MF ) será calculada da seguinte forma:

\[ MF = \frac{P1 + P2}{2}, \]

onde,

  • P1 e P2 são as notas da primeira e segunda avaliações, respectivamente.

\[ CF = \begin{cases} \textbf{A} ,& \text{se } MF \in [8.5;10.0]\\ \textbf{B} ,& \text{se } MF \in [7.0;8.5) \\ \textbf{C} ,& \text{se } MF \in [6.0;7.0) \\ \textbf{F} ,& \text{se } MF < 6.0\\ \textbf{F} ,& \text{Se o número de faltas exceder 25% do total de aulas (independente do valor MF)} \end{cases} \]

🚨 Caso seja verificado ocorrência de fraude acadêmica, o aluno será automaticamente reprovado com F.

Datas Importantes

  • Prova 1: 07/11
  • Prova 2: 07/12 14/12

Atendimento

Local: Bloco A, Torre 2, Piso 5, Sala 518-2

  • Horário: Terćas-feiras das 16h às 18h.

Aulas

Sobre o curso e conhecimentos necessários

Alfabetos e linguagens, Autômatos finitos determinísticos e Linguagens Regulares

Autômatos finitos não determinísticos

Gramática Livre de Contexto (GLC) - Parte 2

Máquinas de Turing (MT)

Decidibilidade

Decidibilidade (Cont.)

Listas de exercícios

Ao todo teremos 4 listas, que serão liberadas em pequenas partes. O objetivo principal é prover problemas representativos dos conceitos vistos, equivalentes aos que serão cobrados nas avaliações.

Notas