- Professor: Hugo Nobrega
- Turma: 11642
- Grupo de discussões: Discord
- Monitores: Matheus do Ó, Matheus Gorchinsky
- Local das aulas: F2-007
Funcionamento da disciplina
O meio primário de comunicação entre os alunos, monitores e professores será o grupo listado acima.
As aulas serão realizadas em modalidade presencial, com aulas às 4as e 6as de 08:00 às 10:00 na sala F2-007 do CCMN.
Bibliografia
- Notas de aula de Petrucio Viana e Renata de Freitas (UFF)
- David J. Hunter, Fundamentos de Matemática Discreta, Capítulo 3: Pensamento Recursivo. LTC, 2019
- Apostila de autômatos, linguagens formais e computabilidade do Collier & Luis Menasché
Listas de Exercícios
| Lista | Data Limite de Entrega |
|---|---|
| Lista 1 | 29 de abril às 20:00 |
| Lista 2 | 20 de maio às 20:00 |
| Lista 3 (atualizada em 4 de julho) | 5 de julho às 20:00 |
| Lista Extra | 20 de julho às 23:59 |
Regras de colaboração
As listas de exercícios podem ser entregues em duplas. Não poderá haver repetição de duplas em diferentes listas! Isso é feito para aumentar a confiança do professor ao dar uma nota individual para cada aluno no final da disciplina.
As diferentes duplas podem sempre discutir os problemas e as ideias de como resolvê-los (e isso é recomendado, pois é uma ótima forma de estudar e aprender!), porém: soluções de exercícios não devem ser compartilhadas entre diferentes duplas (nem de outros períodos). O recomendável é que você não mostre suas soluções completas para alunos de outras duplas, nem veja as soluções completas de outros.
Soluções iguais ou parecidas demais entre duplas diferentes serão desconsideradas.
Cronograma planejado/registro de atividades
| Data | Aula | Conteúdo | Material |
|---|---|---|---|
| 20/3 qua | 1 | Apresentação da disciplina (burocracia); Discussão sobre a disciplina (formalismo, história da computação, etc) | Vídeo, Slides |
| 22/3 sex | - | aula cancelada (chuvas) | |
| 27/3 qua | 2 | Recursão | Vídeo, Slides |
| 29/3 sex | - | Feriado (6a Santa) | |
| 3/4 qua | 3 | Indução como caso particular de recursão (exemplos: número de vértices de árvore estritamente binária; número de arestas de grafo completo; 3 divide (4^n -1) para todo natural n) | Vídeo, Slides |
| 5/4 sex | 4 | Recursão: o conceito e importância de Legibilidade Única; Lógica Proposicional: sintaxe (início) | Vídeo, Slides, Código |
| 10/4 qua | 5 | Sintaxe da LC: representações, classificações, subfórmulas; simbolização de frases da linguagem natural para a LC | Vídeo, Slides, Código |
| 12/4 sex | 6 | Semântica da LC: definição; teorema da concordância (enunciado) | Slides |
| 17/4 qua | 7 | Semântica da LC: teorema da concordância (prova); tabelas de verdade; classificação de fórmulas (tautológicas, contraditórias, satisfazíveis, falsificáveis, contingentes) | Vídeo, Slides |
| 19/4 sex | 8 | Semântica da LC: consequência semântica | Vídeo, Slides |
| 24/4 qua | 9 | Semântica: equivalência; conectivos completos. Sistema dedutivo: a ideia das árvores de avaliação (tableaux) | Vídeo, Slides |
| 26/4 sex | 10 | Árvores de Avaliação | Vídeo, Slides |
| 1/5 qua | - | Feriado (Dia do Trabalhador) | |
| 3/5 sex | 11 | Discussão sobre P1 e Lista 1; Árvores de avaliação (exemplos); Consequência semântica; enunciado dos teoremas de Corretude e Completude | Vídeo, Slides |
| 8/5 qua | 12 | Prova do Teorema de Corretude | Vídeo; Slides |
| 10/5 sex | 13 | Lógica de Primeira ordem, LPO: motivação, sintaxe (início) | Vídeo, Slides |
| 15/5 qua | 14 | LPO: variáveis livres e ligadas; substituição; notação de De Bruijn | Vídeo, Slides |
| 17/5 sex | 15 | Sintaxe de LPO: substituição; Semântica da LPO: estruturas | Vídeo, Slides |
| 22/5 qua | - | sem aula (paralisação docente) | |
| 24/5 sex | 16 | Semântica da LPO | Vídeo, Slides |
| 29/5 qua | 17 | Revisão para a P1 | Vídeo, Slides |
| 31/5 sex | - | Recesso (Corpus Christi) | |
| 5/6 qua | P1 | PROVA 1 | - |
| 7/6 sex | 18 | Revisão da semântica da LPO; Teorema da Concordância para LPO | Vídeo, Slides |
| 12/6 qua | - | sem aula (operações policiais na Maré) | |
| 14/6 sex | 19 | Semântica da LPO: consequência, validade, etc; Árvores de Avaliação (tableaux) para LPO: a ideia | Vídeo, Slides |
| 19/6 qua | 20 | Árvores de avaliação para LPO | Vídeo, Slides |
| 21/6 sex | 21 | Mais exemplos de árvores para LPO; Máquinas de Turing (introdução e definição informal) | Vídeo, Slides |
| 26/6 qua | 22 | Diagonalização, redução entre problemas, PARADA, SAT | Vídeo, Slides |
| 28/6 sex | 23 | Definição formal de Máquinas de Turing e exemplos | Vídeo, Slides |
| 3/7 qua | 24 | Melhorias para MTs que não afetam o modelo: memória “RAM”; fita com várias trilhas; várias fitas “independentes”; não-determinismo. Definições de classes de linguagens: Recursivamente Enumeráveis (RE) e Decidíveis (DEC) | (sem vídeo), Slides |
| 5/7 sex | 25 | Simulando uma MT com outra MT; problemas “Aceita” (RE mas não decidível), “Parada” (RE mas não decidível), “Diag” (não RE); EXTRA: indecidibilidade da LPO In | Vídeo, Slides, Vídeo (Indecidibilidade da LPO), Slides (Indecidibilidade da LPO) |
| 10/7 qua | 26 | Revisão para a P2 (assíncrona) | Vídeo (revisão), Vídeo (exercícios), Slides |
| 12/7 sex | - | PROVA 2 | |
| 17/7 qua | - | PROVA de segunda chamada | |
| 19/7 sex |
Método de avaliação
Teremos ?? listas de exercícios e 2 provas.
Descartaremos a pior nota dentre as listas de exercícios, e ML será a média aritmética das restantes.
MP será a média ponderada das notas das provas, sendo a maior nota com peso 3 e a menor nota com peso 2.
A média final é:
- MP, se MP \(<\) 4;
- a média ponderada entre ML e MP, sendo ML com peso 1 e MP com peso 2, caso contrário.
A nota para aprovação é 5,0; não há prova final.