- Professor: Hugo Nobrega
- Turma: 7545
- Grupo de discussões: Discord
- Monitores: a definir
- Local das aulas: F3-10
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 F3-10 do CCMN.
Conteúdo programático, plano de aulas, previsões de avaliações
Bibliografia
- Notas de aula da turma de 2024-1 dessa disciplina
- 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 | 16 de setembro às 20:00 |
| Lista 2 | 17 de outubro às 20:00 |
| Lista 3+4 | 13 de dezembro às 20:00 |
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 |
|---|---|---|---|
| qua 14 ago | 01 | Apresentação da disciplina; discussão do seu propósito | Vídeo, Quadros |
| sex 16 ago | 02 | Recursão | Vídeo, Quadros, Código |
| qua 21 ago | 03 | Indução | Vídeo, Quadros |
| sex 23 ago | 04 | Indução (mais exemplos) | Vídeo, Quadros |
| qua 28 ago | 05 | Lógica Proposicional (LC): sintaxe; notação, subfórmulas | Vídeo (sem imagem), Vídeo de 24-1, Quadros |
| sex 30 ago | 06 | Semântica da LC: definição, classificações (fórmulas válidas/tautologias, satisfazíveis, etc) | Vídeo, Quadros |
| qua 4 set | 07 | Semântica da LC: teorema da concordância; tabelas-verdade; consequência semântica | Vídeo, Quadros |
| sex 6 set | 08 | Semântica da LC: equivalência semântica; formas normais (incompleto) | Vídeo, Quadros |
| qua 11 set | 09 | Forma Normal Conjuntiva (novamente); Conjuntos de conectivos e suas lógicas; Conjuntos (in)completos de conectivos | Vídeo, Quadros |
| sex 13 set | 10 | Árvores de avaliação: ideia, definição | Vídeo, Quadros |
| qua 18 set | sem aula | Recesso (Libertadores e Rock in Rio) | |
| sex 20 set | 11 | Árvores de avaliação: definição completa, ideia da prova de completude, início da prova de corretude | Vídeo, Quadros |
| qua 25 set | 12 | Corretude das árvores de avaliação; consequência sintática | Vídeo, Quadros |
| sex 27 set | 13 | Lógica de Primeira Ordem: motivação, sintaxe (início) | Vídeo, Quadros |
| qua 2 out | 14 | Sintaxe da LPO: termos, fórmulas, variáveis livres, ligadas, notação de Bruijn | Vídeo, Quadros |
| sex 4 out | 15 | Sintaxe da LPO: substituição, conversão α; Semântica da LPO: estruturas | Vídeo, Quadros |
| qua 9 out | 16 | Semântica da LPO: atribuições, significados de termos e fórmulas | Vídeo, Quadros |
| sex 11 out | 17 | Semântica da LPO: fórmulas válidas, definibilidade de elementos em estruturas | Vídeo, Quadros |
| qua 16 out | 18 | Mais sobre definibilidade em LPO; árvores de av aliação para LPO (a ideia) | Vídeo, Quadros |
| sex 18 out | 19 | Árvores de Avaliação para LPO | Vídeo, Quadros |
| qua 23 out | 20 | Aula de dúvidas para Prova 1 | Vídeo, Quadros |
| sex 25 out | P1 | Prova 1 | |
| qua 30 out | 21 | Discussão da Prova 1; Introdução à teoria da computabilidade | Vídeo, Quadros |
| sex 1 nov | 22 | Máquinas de Turing: definição e primeiros exemplos; Linguagens Recursivamente Enumeráveis (RE); Simulador de MTs em Python | Vídeo, Quadros |
| qua 6 nov | 23 | Mais exemplos de MTs; “melhorias” a MTs que não alteram a capacidade teórica | Vídeo, Quadros |
| sex 8 nov | 24 | Não determinismo em MTs; P vs NP; codificando MTs em linguagem binária; as classes RE e DEC | Vídeo, Quadros |
| qua 13 nov | 25 | Linguagens CODIGO (decidível), ACEITA (r.e. mas não decidível), DIAGONAL (não r.e.), PARADA (r.e. mas não decidível). | Vídeo, Quadros |
| sex 15 nov | sem aula | FERIADO | - |
| qua 20 nov | sem aula | FERIADO | - |
| sex 22 nov | sem aula | aula opcional cancelada por falta de quórum | - |
| qua 27 nov | sem aula | SIAc | - |
| sex 29 nov | sem aula | SIAc | - |
| qua 4 dez | 26 | ACEITA é indecidível; LPO é indecidível | Vídeo, Quadros |
| sex 6 dez | 27 | Aula de dúvidas para P2 | Vídeo, Quadros |
| qua 11 dez | P2 | Prova 2 | |
| sex 13 dez | PSC | Prova de Segunda Chamada | |
| qua 18 dez |
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.