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
  • Primeira lista de exercícios: pdf
    • Gabarito parcial: pdf
  • Gabarito da Prova 1: pdf
  • Revisão da prova 1: [2017-05-16 Ter 12:00]–[2017-05-16 Ter 13:00]
  • Segunda lista de exercícios: pdf
  • Gabarito da Prova 2: pdf
  • Revisão da prova 2: [2017-06-13 Ter 12:00]–[2017-06-13 Ter 13:00]
  • No dia [2017-07-06 Qui] todos os alunos que desejarem poderão realizar a prova substitutiva. A nota desta prova substituirá a nota de uma das provas anteriores (a que tiver menor valor).
  • Terceira lista de exercícios: pdf

Quadro de Notas

Matrícula Prova 1 Prova 2 Prova 3 Faltas(*) Faltas (%) Nota Final Menção
110138899 4.5 0.5   5 14.705882 1.6666667  
110143981 2.5 0.5   7 20.588235 1.  
120131510 5.0 4.5   1 2.9411765 3.1666667  
130049107 8.0 6.5   0 0 4.8333333  
130056162 2.5 0.5   7 20.588235 1.  
130130834 4.0     4 11.764706 1.3333333  
140016546 5.0 3.0   5 14.705882 2.6666667  
140030433 4.0 0.0   4 11.764706 1.3333333  
140031111 8.5 5.0   3 8.8235294 4.5  
140082921 5.0 3.0   2 5.8823529 2.6666667  
140140522 10.0 9.5   0 0 6.5  
140141961 5.5 2.5   2 5.8823529 2.6666667  
140156089 6.0 8.0   8 23.529412 4.6666667  
140166378 5.5 4.5   1 2.9411765 3.3333333  
140168915 7.0 5.5   2 5.8823529 4.1666667  
150020597 6.0     8 23.529412 2.  
150118236 5.5 5.0   0 0 3.5  
150126298 4.0 0.5   0 0 1.5  
150126701 9.0 1.0   2 5.8823529 3.3333333  
150143401 3.5 1.0   3 8.8235294 1.5  
150150610 3.5 2.5   9 26.470588 2. SR
150152051         0 0 TR
150158360       23 67.647059 0 SR
160005116 3.5 1.5   1 2.9411765 1.6666667  
160041317         0 0 TR
160046424 7.5 7.0   3 8.8235294 4.8333333  
160056934 4.0     7 20.588235 1.3333333  
160056969 2.5 2.5   5 14.705882 1.6666667  
160080541 0.0 0.0   9 26.470588 0.  
160108721         0 0 TR
160109906 2.5 3.0   8 23.529412 1.8333333  
160112061       14 41.176471 0 SR
160112362 3.5 0.0   5 14.705882 1.1666667  
160116341         0 0 TR
160131103         0 0 TR
160133441 4.5 1.0   8 23.529412 1.8333333  
160135931 3.0 1.0   2 5.8823529 1.  
160160588 6.0 1.0   6 17.647059 2.  
170002713       20 58.823529 0 SR
170003370 4.0 2.0   0 0 2.  
170003752         0 0 TR
Média 4.859375 2.8448276     0 1.6197917  

(*) Última atualização: [2017-06-13 Ter 13:11]

Calendário de aulas

<2017-03-07 Ter 08:00>–<2017-03-07 Ter 09:50> 1. 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> 2. 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> 3. 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> 4. 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> 5. 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> 6. 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> 7. 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> 8. Aula de exercícios ✓

<2017-04-04 Ter 08:00>–<2017-04-04 Ter 09:50> 9. 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> 10. 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> 11. Aula de exercícios ✓

<2017-04-13 Qui 08:00>–<2017-04-13 Qui 09:50> 12. 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> 13. Indução e recursão ✓

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

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

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

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

<2017-05-02 Ter 08:00>–<2017-05-02 Ter 09:50> 17. Fundamentos de Teoria dos Conjuntos ✓

  • Conjuntos (sec. 2.1)
    • Exercícios sugeridos: 9-11 (p. 125), 17-26 (p. 126)

<2017-05-04 Qui 08:00>–<2017-05-04 Qui 09:50> 18. Fundamentos de Teoria dos Conjuntos ✓

  • Operações sobre Conjuntos (sec. 2.2)
    • Exercícios sugeridos: 5-24 (p. 136)

<2017-05-09 Ter 08:00>–<2017-05-09 Ter 09:50> 19. Fundamentos de Teoria dos Conjuntos ✓

  • Funções (sec. 2.3)
    • Exercícios sugeridos: 24-28 (p. 153), 29, 33-35, 40, 44-54 (p. 154), 69-76 (p. 155)

<2017-05-11 Qui 08:00>–<2017-05-11 Qui 09:50> 20. Fundamentos de Teoria dos Conjuntos ✓

  • Sequências (sec. 2.4)
    • Exercícios sugeridos: 12-19 (p. 168).

<2017-05-16 Ter 08:00>–<2017-05-16 Ter 09:50> 21. Fundamentos de Teoria dos Conjuntos ✓

  • Cardinalidade de Conjutos (sec. 2.5)
    • Exercícios sugeridos: 12-40 (p. 176 e 177).

<2017-05-18 Qui 08:00>–<2017-05-18 Qui 09:50> 22. Relações ✓

  • Relações e suas Propriedades (sec. 9.1)
    • Exercícios sugeridos: 8-10 (p.581), 51-55, 57,58 (p.583),

<2017-05-23 Ter 08:00>–<2017-05-23 Ter 09:50> 23. Relações ✓

  • Relações de Equivalência (sec. 9.5)
    • Exercícios sugeridos: 7, 9-16 (p.615)

<2017-05-25 Qui 08:00>–<2017-05-25 Qui 09:50> 24. Relações ✓

  • Ordens Parciais (sec. 9.6)
    • Exercícios sugeridos: 37-42 (p.631)

<2017-05-30 Ter 08:00>–<2017-05-30 Ter 09:50> 25. Aula de Exercícios ✓

<2017-06-01 Qui 08:00>–<2017-06-01 Qui 09:50> 26. Prova 2

<2017-06-06 Ter 08:00>–<2017-06-06 Ter 09:50> 27. Noções básicas de contagem ✓

  • Regras do produto e da soma (sec. 6.1)
    • Exercícios sugeridos: 1-51 (p.396-398)

<2017-06-08 Qui 08:00>–<2017-06-08 Qui 09:50> 28. Noções básicas de contagem ✓

  • Regras da subtração e da divisão (sec. 6.1)
    • Exercícios sugeridos: 52-72 (p. 398-399)

<2017-06-13 Ter 08:00>–<2017-06-13 Ter 09:50> 29. Princípio da casa dos pombos ✓

  • Princípio da casa dos pombos generalizado (sec. 6.2)
    • Exercícios sugeridos: 1-19 (p.405)

<2017-06-15 Qui 08:00>–<2017-06-15 Qui 09:50> Feriado

<2017-06-20 Ter 08:00>–<2017-06-20 Ter 09:50> 30. Permutações e Combinações ✓

  • Permutações e Combinações (sec. 6.3)
    • Exercícios sugeridos: 7-17 (p.413), 23-25, 33-38 (p.414)
  • Lista de exercícios: pdf

<2017-06-22 Qui 08:00>–<2017-06-22 Qui 09:50> 31. Permutações e Combinações

  • Permutações e Combinações generalizadas (sec. 6.5)
    • Exercícios sugeridos:

<2017-06-27 Ter 08:00>–<2017-06-27 Ter 09:50> 32. Aula de exercícios

<2017-06-29 Qui 08:00>–<2017-06-29 Qui 09:50> 33. Aula de exercícios

<2017-07-04 Ter 08:00>–<2017-07-04 Ter 09:50> 34. Prova 3

<2017-07-06 Qui 08:00>–<2017-07-06 Qui 09:50> 35. Prova de reposição (opcional)

Author: Prof. Flávio L. C. de Moura

Email: contato@flaviomoura.mat.br

Created: 2017-06-20 Ter 21:38

Validate