- Professor: Hugo Nobrega
- Monitores: Gabriel Amaral, Igor de Andrade, Luan Martins, Lucas de Lyra e Thiago Nobre
- Grupo de discussões no Discord
- Plantão de monitoria: A definir
- Pasta do Google Drive com vídeos de aula e demais arquivos (para acessar, você deve estar inscrito/a na turma e preencher este formulário)
Funcionamento da disciplina
O meio primário de comunicação entre os alunos, monitores e professores será pelo Discord, no grupo listado acima.
As aulas serão realizadas em modo síncrono, com aulas teóricas às 3as e 5as de 8:00 às 10:00 e com aulas práticas/conversas/dúvidas às 2as de 13:00 às 15:00. Esses encontros serão gravados e disponibilizados para todos os alunos que queiram acompanhar em modo assíncrono. A escolha entre modo síncrono e/ou assíncrono é completamente livre para cada aluno.
Bibliografia
- Livro-texto: S. C. Coutinho, Números Inteiros e Criptografia RSA, Segunda Edição, Coleção Matemática e Aplicações, IMPA, 2014
- Slides do minicurso de Python, baseados no material PythonUFRJ
- Leitura complementar: L. M. Schechter, Uma Introdução à Criptografia de Chave Pública Através do Método El Gamal, Notas em Matemática Aplicada, Volume 77, SBMAC, 2014. Disponível gratuitamente na internet
- Uma boa fonte adicional (porém em inglês) para o material de provas, lógica, conjuntos, etc. (que não está presente nos livros acima) é: R. Hammack, Book of Proof, 3a edição. Disponível gratuitamente na internet
Listas de Exercícios & Trabalho Final
| Lista | Data Limite de Entrega |
|---|---|
| Lista 1 | 20 de dezembro às 18:00 |
| Lista 2 | 21 de janeiro às 18:00 |
| Lista 3 | 31 de janeiro às 18:00 |
| Lista 4 | 14 de fevereiro às 18:00 |
| Trabalho Final | 10 de março às 9:00 |
Regras de colaboração
É permitido (e até recomendado) que os alunos estudem juntos, porém cada aluno(a) deve escrever e entregar suas próprias soluções. Soluções iguais ou muito parecidas serão desconsideradas. Para evitar problemas, recomendo que você nem mesmo olhe soluções prontas de seus colegas, e também recomendo que ao discutir soluções com colegas, você não tenha as sua soluções abertas à sua frente.
Cronograma planejado/registro de atividades
| Data | Horário | Aula | Conteúdo | Links |
|---|---|---|---|---|
| ter 16 nov | 8-10 | sem aula | Semana de recepção | |
| qui 18 nov | 8-10 | sem aula | Semana de recepção | |
| seg 22 nov | 13-15 | Aula 0 | Parte 1: Introdução à disciplina e questões administrativas; Parte 2: Exemplos motivadores (cifra de César e cifra multiplicativa) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| ter 23 nov | 8-10 | Aula 01 | Parte 1: Inversos multiplicativos no mundo circular; Parte 2: Abstração em computação e matemática; expressões e variáveis em python | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código |
| qui 25 nov | 8-10 | Aula 02 | Parte 1: Definindo funções em Python; Parte 2: Erros; tipos numéricos | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código |
| seg 29 nov | 13-15 | Aula 03 | Parte 1: Definição de variáveis, atribuições simultâneas, escopo, alias; Parte 2: Tipos numéricos, booleanos | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código |
| ter 30 nov | 8-10 | Aula 04 | Parte 1: Dados Booleanos (True/False); comandos condicionais (if/elif/else); Parte 2: condicional (while) e sequencial (for) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código |
| qui 2 dez | 8-10 | Aula 05 | Parte 1: Recap de while/for; strings; indexação, fatiamento; Parte 2: Mais sobre strings; métodos de strings; cifra de César (início) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código |
| seg 6 dez | 13-15 | Aula 06 | Parte 1: Cifra de César (implementação); Parte 2: Tuplas e listas; mutabilidade | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código |
| ter 7 dez | 8-10 | Aula 07 | Parte 1: Mais sobre mutabilidade; hasheabilidade; Parte 2: Dicionários | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código |
| qui 9 dez | 8-10 | Aula 08 | Parte 1: Algoritmos, teoremas e definições em matemática; Parte 2: Provas em matemática; exemplo de uma prova | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código |
| sex 10 dez | 15-17 | Monitoria 01 | Monitoria 01 | Vídeo, Chat |
| seg 13 dez | 13-15 | Aula 09 | Parte 1: Dúvidas; Parte 2: Recíproca de um teorema; contrapositiva; Parte 3: Divisibilidade (definição e algumas propriedades) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código |
| ter 14 dez | 8-10 | Aula 10 | Parte 1: Mais sobre divisibilidade; mdc (definição); Parte 2: Algumas propriedades do mdc; algoritmo ingênuo do mdc; algoritmo de Euclides (introdução) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código |
| qui 16 dez | 8-10 | Aula 11 | Parte 1: Algoritmo de Euclides (enunciado completo e implementação); Parte 2: Terminação do algoritmo de Euclides; corretude (ideia) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código |
| sex 17 dez | 13-15 | Monitoria 02 | Monitoria 02 | Vídeo, Chat |
| seg 20 dez | 13-15 | Aula 12 | Parte 1: Dúvidas da lista 1; Parte 2: Corretude do Algoritmo de Euclides (ideia novamente) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Código |
| ter 21 dez | 8-10 | Aula 13 | Parte 1: Corretude do Algoritmo de Euclides; Parte 2: Lema para a prova da corretude | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| qui 23 dez | 8-10 | sem aula | Recesso de fim de ano | |
| seg 27 dez | 13-15 | sem aula | Recesso de fim de ano | |
| ter 28 dez | 8-10 | sem aula | Recesso de fim de ano | |
| qui 30 dez | 8-10 | sem aula | Recesso de fim de ano | |
| seg 3 jan | 13-15 | Aula 14 | Parte 1: Recap do conteúdo; Parte 2: Prova do Teorema de Bézout; algoritmo de Euclides estendido (início) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| ter 4 jan | 8-10 | Aula 15 | Parte 1: Enunciado do Algoritmo de Euclides Estendido (AEE); Parte 2: Implementação do AEE; Parte 3: Terminação e Corretude do AEE | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código |
| qui 6 jan | 8-10 | Aula 16 | Parte 1: Estendendo o AEE para números negativos; Parte 2: Números primos e o Teorema Fundamental da Aritmética (TFA, enunciado); Parte 3: Prova de existência no TFA; algoritmo de fatoração em primos (enunciado e implementação) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código |
| seg 10 jan | 13-15 | Aula 17 | Parte 1: Comentários sobre a Lista 2 e sobre as regras de colaboração entre alunos; Parte 2: terminação do algoritmo de fatoração em primos; Parte 3: corretude do algoritmo de fatoração em primos | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código |
| ter 11 jan | 8-10 | Aula 18 | Parte 1: Resolução do exercício L2Q1c; Parte 2: Otimizando a fatoração: o menor fator de um composto é menor ou igual à sua raiz; Parte 3: Comentários sobre a dificuldade do problema da fatoração; Parte 4: Unicidade no TFA (ideia); a Propriedade Fundamental dos Primos (enunciado) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Vídeo 4, Chat 4, Código |
| qui 13 jan | 8-10 | Aula 19 | Parte 1: Propriedade Fundamental dos Primos (prova); Parte 2: Unicidade no TFA (prova) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| sex 14 jan | 15-17 | Monitoria 03 | Monitoria 03 | Quadro, Vídeo, Chat |
| seg 17 jan | 13-15 | Aula 20 | Parte 1: Comentários sobre a Lista 02; Parte 2: Infinitude dos Primos (enunciado); Parte 3: Infinitude dos Primos (prova); Parte 4: Definições recursivas (motivação) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Vídeo 4, Chat 4 |
| ter 18 jan | 8-10 | Aula 21 | Parte 1: Dúvidas da Aula 20, definições recursivas (exemplos e discussão); Parte 2: Definições recursivas (definição oficial); Parte 3: Implementando definições recursivas em programação | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código |
| qui 20 jan | 8-10 | sem aula | Feriado | |
| sex 21 jan | 10-12 | Monitoria 04 | Monitoria 04 | Quadro, Vídeo, Chat |
| seg 24 jan | 13-15 | Aula 22 | Parte 1: Comentários sobre a Lista 2; Parte 2: Torres de Hanói (definição); Parte 3: Torres de Hanói (algoritmo recursivo); Parte 4: Torres de Hanói (implementação em Python) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Vídeo 4, Chat 4, Código |
| ter 25 jan | 8-10 | Aula 23 | Parte 1: Dúvidas da Lista 3; Parte 2: O método de prova por indução; exemplo (soma dos naturais até n); Parte 3: Outro exemplo de prova por indução (fórmula de Binet para Fibonacci) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3 |
| qui 27 jan | 8-10 | Aula 24 | Parte 1: Recapitulação de indução; Parte 2: Prova de terminação do algoritmo de Hanói; Parte 3: Prova de corretude do algoritmo de Hanói; quantidade de movimentos feitos pelo algoritmo | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3 |
| sex 28 jan | 15-17 | Monitoria 05 | Monitoria 05 | |
| seg 31 jan | 13-15 | Aula 25 | Parte 1: Dúvidas da Lista 3; Parte 2: Número de passos do algoritmo de Hanói; Parte 3: Relações; reflexividade, simetria, transitividade, relações de equivalência | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3 |
| ter 1 fev | 8-10 | Aula 26 | Parte 1: Recapitulação de relações; a ‘cara’ das relações de equivalência; Parte 2: Quociente por relação de equivalência; inteiros módulo n; aritmética modular (introdução) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2 |
| qui 3 fev | 8-10 | Aula 27 | Parte 1: Aritmética Modular (adição, subtração, multiplicação); Parte 2: Aritmética Modular (divisão); Parte 3: Aritmética Modular (não há potenciação) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3 |
| sex 4 fev | 15-17 | Monitoria 06 | Monitoria 06 | |
| seg 7 fev | 13-15 | Aula 28 | Parte 1: Revisão de recursão e indução; Aritmética Modular (elevando uma classe de equivalência a um número natural); exemplos; Parte 2: Mais exemplos de exponenciação modular; Parte 3: Pequeno Teorema de Fermat (motivação e enunciado) | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código |
| ter 8 fev | 8-10 | sem aula | Aula cancelada | |
| qui 10 fev | 8-10 | Aula 29 | Parte 1: Dúvidas da Lista 4; Parte 2: Equivalência entre PTF1 e PTF2; Parte 3: Prova do PTF1 | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código |
| sex 11 fev | 15-17 | Monitoria 07 | Monitoria 07 | Quadro 1, Quadro 2, Vídeo, Chat |
| seg 14 fev | 13-15 | sem aula | SIAc | |
| ter 15 fev | 8-10 | sem aula | SIAc | |
| qui 17 fev | 8-10 | Aula 30 | Parte 1: Aplicação do PTF: cálculo de potências em aritmética modular; Parte 2: Aplicação do PTF: teste de primalidade; Parte 3: Pseudoprimos de Fermat, números de Carmichael | Quadro, Vídeo 1, Vídeo 2, Vídeo 3, Código |
| sex 18 fev | 15-17 | Monitoria 08 | Monitoria 08 | |
| seg 21 fev | 13-15 | Aula 31 | Parte 1: Organização do final da disciplina; Parte 2: Recapitulação de resultados antigos usando a linguagem da aritmética modular; Parte 3: O teste de primalidade de Miller–Rabin | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3 |
| ter 22 fev | 8-10 | Aula 32 | Parte 1: Anúncios sobre o trabalho final e monitoria; Parte 2: Implementação e discussão do Teste de Miller–Rabin; Parte 3: A ideia do RSA | Quadro, Vídeo 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código |
| qui 24 fev | 8-10 | Aula 33 | Parte 1: Como garantir b**(ed) = b mod pq; Parte 2: RSA; Parte 3: A conversão de textos para números; a escolha dos primos p, q | Quadro, Vídeo 1, Chat 1, Vídeo 2, Chat 2, Vídeo 3, Chat 3, Código |
| sex 25 fev | 15-17 | Monitoria 09 | Monitoria 09 | Quadro, Vídeo, Chat |
| seg 28 fev | 13-15 | sem aula | Carnaval | |
| ter 1 mar | 8-10 | sem aula | Carnaval | |
| qui 3 mar | 8-10 | sem aula | Carnaval | |
| seg 7 mar | 13-15 | Aula 34 | Dúvidas do trabalho final | Vídeo, Chat |
| ter 8 mar | 8-10 | Sem aula (a princípio) | ||
| qui 10 mar | 9-10 | Final | Atividade especial de encerramento |
Método de avaliação
Teremos listas de exercícios aproximadamente a cada 10 dias, valendo nota, mas descartaremos as N (a definir) piores notas ao longo do período. Além disso, teremos um trabalho final.
Se a nota no trabalho final for menor do que 5,0, essa também será a nota final do/a aluno/a. Caso contrário, a nota final será a média aritmética entre a nota do trabalho e a média aritmética das notas das listas (após os descartes).
Não há provas, nem prova final.
A nota final mínima para aprovação é 5,0.
Os monitores farão a correção das listas, sob supervisão e responsabilidade do professor. O professor fará a correção do trabalho final.