Números Inteiros e Criptografia (22-2)

  • 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

Listas de Exercícios

ListaData Limite de Entrega
Lista 118/10 às 21:00
Lista 23/11 às 21:00
Lista 313/12 às 21:00
Lista 414/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

DataAulaConteúdo
ter 30/8sem aulaSemana de Recepção
qui 1/9sem aulaSemana de Recepção
ter 6/9Aula 1Introdução; Discussão conceitual sobre abstração em computação e matemática, teoremas, provas
qui 8/9Aula 2Mais 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/9Aula 3Formas 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/9Aula 4Provas de terminação e corretude do AID; Prova da unicidade no Teorema da Divisão Euclideana
ter 20/9Aula 5Recap 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/9Aula 6Divisibilidade (definição e algumas propriedades)
ter 27/9Aula 7Mais propriedades da divisibilidade; definição de mdc; algoritmo ingênuo do mdc
qui 29/9Aula 8Algoritmo de Euclides: enunciado, prova de terminação, ideia da prova de corretude; implementação em python; link para rodar online
ter 4/10Aula 9Lema: “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/10Aula 10Versã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/10Aula 11Algoritmo Estendido de Euclides; implementação em python; link pra rodar online
qui 13/10Aula 12Números primos; enunciado do Teorema Fundamental da Aritmética
ter 18/10Aula 13Discussã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/10Aula 14Prova 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/10Aula 15Prova da unicidade no TFA
qui 27/10Aula 16Fim da prova de unicidade no TFA; Infinitude dos primos
ter 1/11Aula 17Recursão: discussão e primeiros exemplos
qui 3/11Aula 18Recursão: algoritmo de Hanói
ter 8/11Aula 19Indução: discussão e primeiros exemplos
qui 10/11Aula 20Indução: prova de terminação e corretude (parcial) de Hanói
ter 15/11sem aulaFeriado
qui 17/11-Aula de revisão para a Prova 1
ter 22/11Aula 21Mais 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/12sem aulaRecesso de fim de ano
qui 29/12sem aulaRecesso 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.

A segunda chamada só é direito para casos devidamente justificados dentro do prazo de 48 horas da avaliação 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.