- Professor: Hugo Nobrega
- Monitores: a definir
- Grupo de discussões: Discord
- Plantão de monitoria: a definir
- Local: Sala F3-014
Funcionamento da disciplina
O meio primário de comunicação entre os alunos, monitores e professores será o grupo no Discord listado acima.
As aulas serão realizadas em modalidade presencial, com aulas às 3as e 5as de 8:00 às 10:00 na sala F3-014.
Bibliografia
- Livro-texto: S. C. Coutinho, Números Inteiros e Criptografia RSA, Segunda Edição, Coleção Matemática e Aplicações, IMPA, 2014
- 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
| Lista | Data Limite de Entrega |
|---|---|
| Lista 1 | 18/10 às 21:00 |
| Lista 2 | 3/11 às 21:00 |
| Lista 3 | 13/12 às 21:00 |
| Lista 4 | 14/1 às 23:59 |
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 | Aula | Conteúdo |
|---|---|---|
| ter 30/8 | sem aula | Semana de Recepção |
| qui 1/9 | sem aula | Semana de Recepção |
| ter 6/9 | Aula 1 | Introdução; Discussão conceitual sobre abstração em computação e matemática, teoremas, provas |
| qui 8/9 | Aula 2 | Mais sobre a linguagem da matemática (afirmações simples e compostas, conectivos); definições; anatomia dos teoremas e conjecturas (contexto/hipóteses, afirmação/tese); generalizações, casos particulares; recíproca, contrapositiva |
| ter 13/9 | Aula 3 | Formas de dizer “se A então B” e “A é equivalente a B”; Algoritmos; Teorema da Divisão de Naturais; Prova de xistência: Algoritmo Ingênuo da Divisão (enunciado e testes de mesa) |
| qui 15/9 | Aula 4 | Provas de terminação e corretude do AID; Prova da unicidade no Teorema da Divisão Euclideana |
| ter 20/9 | Aula 5 | Recap do exerício da semana de recepção; cifras “de César” (“aditiva”) e “multiplicativa”; conjectura: na cifra multiplicativa com 26 símbolos, apenas as chaves que têm mdc 1 com 26 servem para encriptar |
| qui 22/9 | Aula 6 | Divisibilidade (definição e algumas propriedades) |
| ter 27/9 | Aula 7 | Mais propriedades da divisibilidade; definição de mdc; algoritmo ingênuo do mdc |
| qui 29/9 | Aula 8 | Algoritmo de Euclides: enunciado, prova de terminação, ideia da prova de corretude; implementação em python; link para rodar online |
| ter 4/10 | Aula 9 | Lema: “para todos inteiros x,y,z, se existe inteiro w tal que x = yw + z, então mdc(x,y) = mdc(y,z)”; prova da Corretude do Alg. Euclides; Teorema de Bézout (motivação e enunciado) |
| qui 6/10 | Aula 10 | Versão mais abrangente do Alg. Euclides (para todos os inteiros); Teorema de Bézout; Algoritmo Estendido de Euclides (prova do Teorema de Bézout) |
| ter 11/10 | Aula 11 | Algoritmo Estendido de Euclides; implementação em python; link pra rodar online |
| qui 13/10 | Aula 12 | Números primos; enunciado do Teorema Fundamental da Aritmética |
| ter 18/10 | Aula 13 | Discussão sobre a equivalência das versões do TFA; prova da “existência” no TFA (Algoritmo Ingênuo da Fatoração, Terminação, prova parcial da Corretude) |
| qui 20/10 | Aula 14 | Prova da coretude do AIF; discussão sobre possíveis melhorias; discussão sobre a ineficiência do AIF (mesmo com melhorias) e qualquer algoritmo conhecido de fatoração |
| ter 25/10 | Aula 15 | Prova da unicidade no TFA |
| qui 27/10 | Aula 16 | Fim da prova de unicidade no TFA; Infinitude dos primos |
| ter 1/11 | Aula 17 | Recursão: discussão e primeiros exemplos |
| qui 3/11 | Aula 18 | Recursão: algoritmo de Hanói |
| ter 8/11 | Aula 19 | Indução: discussão e primeiros exemplos |
| qui 10/11 | Aula 20 | Indução: prova de terminação e corretude (parcial) de Hanói |
| ter 15/11 | sem aula | Feriado |
| qui 17/11 | - | Aula de revisão para a Prova 1 |
| ter 22/11 | Aula 21 | Mais sobre indução e recursão; prova de Corretude do algoritmo de Hanói; prova da quantidade de passos do algoritmo; prova da unicidade do TFA por indução |
| qui 24/11 | - | PROVA 1 |
| ter 29/11 | ||
| qui 1/12 | ||
| ter 6/12 | ||
| qui 8/12 | ||
| ter 13/12 | ||
| qui 15/12 | ||
| ter 20/12 | ||
| qui 22/12 | ||
| ter 27/12 | sem aula | Recesso de fim de ano |
| qui 29/12 | sem aula | Recesso de fim de ano |
| ter 3/1 | ||
| qui 5/1 | ||
| ter 10/1 | ||
| qui 12/1 |
Método de avaliação
Teremos diversas listas de exercícios e \( n \) provas (a definir).
A nota final é calculada de acordo com a seguinte fórmula: \[ M = 0,25*ML + 0,75*MP \] sendo \( ML \) a média aritmética das \( k \) melhores notas das listas (a definir) e \( MP = \ldots \) (a definir).
A aprovação na disciplina se dará se, e somente se, \( M \geq 5 \).
Caso a/o aluna/o precise fazer segunda chamada, essa prova substitui a nota da prova perdida.
Os monitores farão a correção das listas, sob supervisão e responsabilidade do professor. O professor fará a correção das provas.