113450 - Fundamentos Teóricos da Computação (Turma C)

Table of Contents

Quadro de avisos

  • Plano de ensino
  • Todos os emails enviados ao professor devem conter a expressão [FTC] no assunto da mensagem.
  • Uma longa noite aprendendo
  • Monitoria (Kevin Masinda Mahema - kevinmasinda16@gmail.com)
    • Horário de atendimento: Todas as segundas de 13h às 14h
    • Local: Sala de monitoria do prédio CIC/EST
  • Primeira lista de exercícios (pdf)

Quadro de Notas

Matrícula Prova 1 Prova 2 Prova 3 Faltas(*) Faltas (%) Nota Final Menção
               
Média              

(*) Última atualização:

Calendário de aulas

<2017-03-07 Ter 08:00>–<2017-03-07 Ter 09:50> Introdução e motivação ✓

  • Apresentação do curso:
    • Ementa
    • Critérios de avaliação
    • Datas das provas
    • Bibliografia
  • Motivação
    • Fundamentos matemáticos para a Ciência da Computação
    • Linguagens naturais e seus problemas.
    • Definições básicas: proposições e sintaxe da lógica proposicional (LP).
    • Semântica da LP. (Seção 1.1)
      • Exercícios recomendados: 29-41 (p. 15-16) (Rosen 7th edition).

<2017-03-09 Qui 08:00>–<2017-03-09 Qui 09:50> Lógica Proposicional (LP) ✓

  • Um pouco mais sobre a implicação proposicional.
  • Contrapositiva.
  • Aplicações (sec. 1.2):
    • Exercícios recomendados: 1-43 (p.22 , 23 e 24) (Rosen 7th edition).
  • Equivalências (sec. 1.3):
    • Exercícios recomendados: 1-6 (p. 34), 9-15 (p. 35), 44, 45 (p. 36) (Rosen 7th edition).

<2017-03-14 Ter 08:00>–<2017-03-14 Ter 09:50> Lógica de Primeira Ordem (LPO) ✓

  • Predicados e quantificadores (sec. 1.4):
    • Equivalências
  • Quantificadores aninhados (sec. 1.5).

<2017-03-16 Qui 08:00>–<2017-03-16 Qui 09:50> Lógica de Primeira Ordem (LPO) ✓

  • Exercícios sugeridos (em Dedução Natural):
    1. Utilize (PPC) para provar (\(\bot_e\))

      Isto nos permite concluir que (\(\bot_e\)) é uma regra derivada na lógica proposicional clássica.

    2. Utilize (PPC) para provar (\(\neg\neg_e\))
    3. Utilize (\(\neg\neg_e\)) para provar (PPC)

      Os itens 2. e 3. estabelecem uma espécie de equivalência entre as regras (PPC) e (\(\neg\neg_e\)) de forma que (\(\neg\neg_e\)) também caracteriza a lógica clássica.

    4. Utilize (\(\neg\neg_e\)) para provar (LTE)
    5. Utilize (LTE) (e possivelmente (\(\bot_e\))) para provar (\(\neg\neg_e\))

<2017-03-21 Ter 08:00>–<2017-03-21 Ter 09:50> Lógica de Primeira Ordem (LPO) ✓

  • Regras de inferência (sec. 1.6).
    • Exercícios sugeridos: 19 (p. 79), 20, 23-29, 32, 33 (p. 80)
    • Mostre que as regras de inferências apresentadas na tabela 1 (p. 72) podem ser provadas a partir das regras do sistema de dedução natural apresentado em aula.

<2017-03-23 Qui 08:00>–<2017-03-23 Qui 09:50> Lógica de Primeira Ordem (LPO) ✓

  • Técnicas de prova (sec. 1.7).
    • Exercícios sugeridos: 1-42 (p.91 e 92)
  • Estratégias de prova (sec. 1.8).
    • Exercícios sugeridos: 1-15 (p.108) 38 (p. 109)

<2017-03-28 Ter 08:00>–<2017-03-28 Ter 09:50> Indução ✓

  • Indução Matemática (sec. 5.1).
    • Exercícios sugeridos: 3-8 (p.329), 9-37 (p.330),

<2017-03-30 Qui 08:00>–<2017-03-30 Qui 09:50> Aula de exercícios ✓

<2017-04-04 Ter 08:00>–<2017-04-04 Ter 09:50> Indução ✓

  • Indução Forte e o Princípio da Boa Ordenação (sec. 5.2).
    • Exercícios sugeridos: 7, 9 (p.342), 27-29 (p.343), 30-35, 41-43 (p.344)

<2017-04-06 Qui 08:00>–<2017-04-06 Qui 09:50> Aula de exercícios e Indução estrutural ✓

  • Indução Estrutural (sec. 5.3).
    • Exercício: Considere a estrutura de listas definida como a seguir: \[l ::= [] \mid a::l\]

      onde \([]\) representa a lista vazia, e \(a::l\) representa a lista com primeiro elemento \(a\) e cauda \(l\). O comprimento de uma lista é definido recursivamente por:

      \[|l| = \left\{\begin{array}{ll} 0, & \mbox{ se } l = [] \\ 1 + |l'|, & \mbox{ se } l = a::l' \end{array}\right.\]

      A concatenação de listas também pode ser definida por uma função recursiva: \[l_1\circ l_2 = \left\{\begin{array}{ll} l_2, & \mbox{ se } l_1 = [] \\ a::(l' \circ l_2), & \mbox{ se } l_1 = a::l' \end{array}\right.\]

      O reverso de listas é definido por: \[rev(l) = \left\{\begin{array}{ll} l, & \mbox{ se } l = [] \\ (rev(l')) \circ (a :: []), & \mbox{ se } l = a :: l' \end{array}\right.\]

      1. Prove que \(|l_1 \circ l_2| = |l_1| + |l_2|\), para listas \(l_1, l_2\) quaisquer. (Feito em sala).
      2. Prove que \(l \circ nil = l\), para qualquer lista l.
      3. Prove que a concatenação de listas é associativa, isto é, \((l_1 \circ l_2)\circ l_3) = l_1 \circ (l_2 \circ l_3)\) para listas \(l_1, l_2\) e \(l_3\) quaisquer.
      4. Prove que \(|rev(l)| = |l|\), para qualquer lista l.
      5. Prove que \(rev(l_1 \circ l_2) = (rev(l_2))\circ (rev(l_1))\), para listas \(l_1, l_2\) quaisquer.
      6. Prove que \(rev(rev(l)) = l\), para qualquer lista l.
    • Exercícios sugeridos: 12-16 (p.358), 35-52 (p.359), 53-55 (p.360)

<2017-04-11 Ter 08:00>–<2017-04-11 Ter 09:50> Aula de exercícios ✓

<2017-04-13 Qui 08:00>–<2017-04-13 Qui 09:50> Recursão ✓

  • Algoritmos recursivos (sec. 5.4).
    • Exercícios sugeridos: 8, 16 (p.370), 23-35, 43-55 (p.371)

<2017-04-18 Ter 08:00>–<2017-04-18 Ter 09:50> Indução e recursão ✓

  • Correção de programas (sec. 5.5).

<2017-04-20 Qui 08:00>–<2017-04-20 Qui 09:50> Aula de exercícios

<2017-04-25 Ter 08:00>–<2017-04-25 Ter 09:50> Aula de exercícios

<2017-04-27 Qui 08:00>–<2017-04-27 Qui 09:50> Prova 1

Author: Flávio L. C. de Moura

Email: flaviomoura@unb.br

Created: 2017-04-19 Qua 22:15

Validate