- Professor: Hugo Nobrega
- Turma: 6673
- Grupo de discussões: Discord
- Monitores: a definir
- Local das aulas: F3-08 (CCMN)
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 quartas e sextas de 8:00 às 10:00 na sala F3-08 do CCMN.
Bibliografia
Listas de Exercícios
| Lista | Data Limite de Entrega |
|---|---|
| Lista 1 | 23 de setembro às 18:00 |
| Lista 2 | |
| Lista 3 | 14 de outubro às 7:59 |
| Lista 4 | 1º de dezembro às 18:00 |
Provas de Períodos Anteriores
Regras de colaboração
Cronograma planejado/registro de atividades
| Data | Aula | Conteúdo | Material |
|---|---|---|---|
| qua 12 ago | 0 | Apresentação da Disciplina; atividade de descriptação de mensagem secreta | Vídeo (sem imagem); Sem quadro (projetor com defeito) |
| sex 14 ago | 01 | Discussão sobre a atividade de encriptação e descriptação; O propósito da disciplina (formalização, abstração) | Vídeo; Quadro |
| qua 19 ago | 02 | Discussão sobre os conceitos de Teorema, Conjectura, Prova, Definição | (sem vídeo nem quadros) |
| sex 21 ago | 03 | Continuação da discussão: Contraexemplo, Algoritmo; O Algoritmo Ingênuo da Divisão (AID); Prova da terminação e corretude (ideia) do AID | Vídeo; Quadro; Código (AID) |
| qua 26 ago | 04 | Prova da corretude do AID; prova da Unicidade no Teorema da Divisão; recap. da motivação para mdc: criptografia por “cifra multiplicativa”; mdc - definição e primeiras propriedades | Vídeo; Quadro; Código (encriptação) |
| sex 28 ago | 05 | Mais propriedades de divisibilidade e mdc; algoritmo ingênuo de mdc; ideia do Algoritmo de Euclides | Vídeo; Quadro; Código (mdc ingênuo) |
| qua 2 set | 06 | Algoritmo de Euclides (enunciado, terminação, corretude); Teorema de Bézout (enunciado e ideia da prova – Algoritmo Estendido de Euclides) | Vídeo; Quadro; Código (Euclides) |
| sex 4 set | 07 | Algoritmo Estendido de Euclides (enunciado, terminação, corretude, implementação) | Vídeo; Quadro; Código (Euclides Estendido) |
| qua 9 set | 08 | Recursão e indução: discussão inicial (“quando funciona??”) | Vídeo; Quadro; Código (implementando algumas das funções) |
| sex 11 set | 09 | Recursão: discussão mais formal dos critérios de “quando fuciona”; exemplos de “agendamentos” de definições recursivas; exemplo das Torres de Hanói | Vídeo; Quadro; |
| qua 16 set | 10 | Hanói: implementação. Indução: “provas escritas por recursão”. Primeiros exemplos | Vídeo; Quadro; Código (Hanói) |
| sex 18 set | 11 | Exemplos de provas por indução | Vídeo; Quadro; Código (exemplo) |
| qua 23 set | sem aula | Paralisação Estudantil | - |
| sex 25 set | 12 | Mais exemplos de provas por indução (incluindo terminação + corretude de Hanói); Teorema Fundamental da Aritmética (enunciado e discussão) | Vídeo; Quadro |
| qua 30 set | 13 | Prova da “Existência” no TFA: o algoritmo ingênuo da fatoração (AIF); terminação e corretude do AIF | Vídeo; Quadro; Código (Fatoração Ingênua) |
| sex 2 out | 14 | Prova da “Unicidade” no TFA; propriedade fundamental dos primos | Vídeo; Quadro |
| qua 7 out | sem aula | 15ª SIAc | |
| sex 9 out | sem aula | 15ª SIAc | |
| qua 14 out | 15 | Revisão para Prova 1 | Vídeo; Quadro |
| sex 16 out | 16 | Infinitude dos primos; relações de equivalência; a relação de equivalência módulo n | Vídeo; Quadro |
| qua 21 out | 17 | Classes de equivalência, quociente de universo por rel. de equivalência; Inteiros módulo n; Aritmética modular: adição e multiplicação | Vídeo; Quadro |
| sex 23 out | P1 | Prova 1 | |
| qua 28 out | 18 | Mais aritmética modular: subtração, divisão, elevação de classe de equivalência a um inteiro | Vídeo; Quadro |
| sex 30 out | sem aula | Feriado | |
| qua 4 nov | 19 | Mais exploração de potências modulares; Pequeno Teorema de Fermat (dois enunciados, ideia da prova) | Vídeo; Quadro |
| sex 6 nov | 20 | Prova do PTF; teste primalidade de Fermat; números de Carmichael | Vídeo; Quadro; Código (Teste de Fermat) |
| qua 11 nov | 21 | Mais exemplos de Fermat e contas em aritmética modular; a ideia do Teste de Miller–Rabin | Vídeo; Quadro; Código (Teste de Primalidade “Ingênuo”) |
| sex 13 nov | 22 | Teste de Miller–Rabin | Vídeo; Quadro; Código (Teste de Miller–Rabin) |
| qua 18 nov | 23 | “Radiciação” (extração de raízes) em aritmética modular; a base do RSA | Vídeo; Quadro |
| sex 20 nov | sem aula | Feriado | |
| qua 25 nov | |||
| sex 27 nov | |||
| qua 2 dez | |||
| sex 4 dez | |||
| qua 9 dez | |||
| sex 11 dez | |||
| qua 16 dez | |||
| sex 18 dez |