Vídeos, rabiscos, exercícios ... das reuniões anteriores
Conteúdo das reuniões
Nos resumos a seguir há links que estão direcionando para páginas da Wikipedia em inglês. Em cada uma destas páginas há um link para a página correspondente em português.
23/07 - Assista ao vídeo: aqui
Hoje conversaremos sobre contagem, bem, mais ou menos: conjuntos, sequências e permutações; árvores binárias; árvores de decisão; limite inferior para ordenação: uma certa aplicação de contagem; princípio generalizado das casas dos pombos.
21/07 - Assista ao vídeo: parte 1 e parte 2
O prato do dia foi conjunto das partes com os vários temperos de infinitos de Georg Cantor. Como sobremesa tivemos o paradoxo do barbeiro do Bertrand Russell.
16/07 - Assista ao vídeo: aqui
Hoje continuamos nossa conversar sobre relações. Falamos sobre: relações e digrafos; ordens parciais; ordens totais; elementos mínimos x minimais; máximos x maximais; digrafos acíclicos e ordenação topológica.
14/07 - Assista ao vídeo: aqui
O papo de hoje foi sobre relações, relações de equivalência, classes de equivalência, partições e representantes de classes.
07/07 - Assista ao vídeo: aqui
Hoje conversamos sobre o teorema Chinês do Resto: se a e b são inteiros positivos coprimos e m e n são dois inteiros quaisquer, então existe um inteiro x tal que x ≡ m mod a e x ≡ n mod b
Este teorema foi usado para demonstrar que se a e b são coprimos, então ϕ(ab) = ϕ(a)ϕ(b).
02/07 - Assista ao vídeo: início e fim
Aviso: O vídeo com início tem apenas 6 minutos. Do minuto 6 até o 15 a gravação deveria ter sido parada.
Hoje utilizaremos tudo que estivemos treinando nas últimas várias reuniões para entendermos o sistema criptográfico de chave pública RSA. Entre as ferramentas que usamos estão: o Teorema de Fermat; inversos multiplicativos; aritmética modular; congruência; equações diofatinas; algoritmo de Euclides estendido; algoritmo de Euclides e lema da divisão.
30/06 - Assista ao vídeo: aqui
O prato do dia foi o teorema de Euler:
Se n e k são coprimos, então kϕ(n) ≡ 1 mod n.
25/06 - Assista ao vídeo: aqui
Interpretação geométrica do mdc. Mais aritmética modula, propriedades de congruência, inversos multiplicativos (mod n), função ϕ de Euler e teorema de Euler. Tudo recheado com exemplos. A demonstração do teorema de Euler fica para uma próxima reunião.
23/06 - Assista ao vídeo: aqui
Começamos a conversar sobre aritmética modular:
18/06 - Assista ao vídeo: aqui
Nota: desculpem, de mais ou menos 1h 10m a 1h 30m, enquanto o pessoal estava no laboratório de programação, eu deveria ter parado a gravação
Aplicamos o algoritmo de Euclides na solução de equações diofantinas e examinaremos o algoritmo sob uma perspectiva um pouco mais de computação.
Eis o caminho que seguimos:
- equações diofantinas
- trabalho de Euclides
- algoritmos autocertificadores
- Euclides não gosta de Fibonacci
- laboratório de programação
- rabiscos e programas feitos
16/06 - Assista ao vídeo: aqui
Desta vez o prato do dia foi o algoritmo de Euclides, com seus 2300 anos de idade. Conversamos também sobre a versão de Luxe do algoritmo de Euclides, o algoritmo de Euclides estendido. Com Euclides estendido provamos, finalmente, a unicidade da fatoração em primos que é uma das promessas do Teorema Fundamental da Aritmética.
11/06 - Assista ao vídeo: aqui
A partir de hoje começamos a tratar de teoria do números. Passaremos a aplicar os métodos e as técnicas vistos até agora para o caminho. Hoje conversamos sobre divisibilidade, máximo divisor comum e sobre o algoritmo a divisão. Na prova do algoritmo da divisão treinamos o uso da boa ordem dos inteiros e provas por casos e contradição. A ideia de olhar possibilidades e ver até onde nos levam será comum. Procuramos começar qualquer prova, programa ou tarefa com algo mais simples que nos leve a um ponto mais próximo do destino.
02/06 - Assista ao vídeo: aqui
Continuamos a olhar para o Princípio da Indução Finita, mas de uma perspectiva um pouco mais ambiciosa. Esta perspectiva combina prova por casos, contradição e indução. Talvez haja ainda mais alguma coisa escondida. A novidade é que gostaríamos de, pelo menos um pouco, chamar a atenção para o poder algorítmico, e portanto computacional, de indução. Frequentemente, uma demostração por indução fornece um processo ou algoritmo para construirmos um objeto. Por exemplo, a demonstração indutiva do Teorema Fundamental da Aritmética nos descreve um processo para escrevermos um número inteiro n ≥ 1 como um produto de números primos.
Hoje usaremos como pretexto para as nossas investigações o Problema da Galeria de Arte. Este problema envolve geometria, isso por si só já tem um sabor um pouco diferente do que temos feito. O Teorema Fundamental da Aritmética nos diz como decompor um número em pedaços mais simples, os número primos. Hoje discutiremos que em geometria, ou qualquer área (nada como exagerar), de maneira semelhante, procuramos trazer o objeto de estudo para nossa zona de comforto}.
28/05 - Assista ao vídeo: inicio e final
Continuamos a nossa jornada pelo reino encantado do Princípio da Indução Finita. Hoje conversamos sobre três demostrações que utilizaram este princípio, cada uma um pouco diferente das outras e das de quarta-feira passada. Todas as demonstração envolviam algum predicado P(n) que dependia de uma variável n:
- Na primeira demonstração tomamos como base b = 5, verificamos que P(5) é verdadeiro e provamos que P(n) ⇒ P(n + 1) é verdadeiro para n ≥ b.
- Na demonstração seguinte tomamos como base b = 1 e 2, verificamos que P(1) e P(2) são verdadeiros e provamos que P(n − 2) ∧ P(n − 1) ⇒ P(n) é verdadeiro para n ≥ b + 2.
- Finalmente, na demonstração mais sexy desta manhã, tomamos como base b = 2 e mostramos que P(b) ∧ P(b + 1) ∧ ⋯ ∧ P(n − 1) ⇒ P(n) vale para n ≥ b + 1.
A conclusão de todas esta demonstrações foi de que, pelo Princípio da Indução Finita, P(n) é verdadeiro para todo n ≥ b.
26/05 - Assista ao vídeo: inicio e final
Hoje começamos a falar do assunto mais importante da história da computação : indução matemática.
21/05 - Assista ao vídeo: iniciozinho e finalzão
Conversamos os tipos de dados matemáticos conjunto e função. Em computação um tipo abstrato de dado (Abstract Data Type, ADT) é um coleção de objetos de algum tipo junto com um conjunto de operações que podemos realizar sobre eles. Essas coisas são herdadas de matemática, acho. Em matemática temos conjuntos e as operações que podemos fazer sobre eles como intersecção, união, complementação e diferença. Em Python set é o tipo de dados nativo que implementa essas operações. Sobre conjuntos fizemos um exercício que usava o Princípio das Casas dos Pombos e estudamos o conjunto das partes ou conjunto potência de um conjunto. Vimos que o conjunto das partes P(X) de um conjunto X com n elementos tem 2n subconjuntos de X. Essa foi a deixa para conversarmos sobre funções injetoras, sobrejetoras e bijetoras. São esses tipos de funções que usamos para medir o tamanho de conjuntos e dizer quem é maior que quem. Essa também foi uma deixa comentar sobre representação de números em outras bases, especialmente a binária. Na base 2 ou binária um número é representado pelos dígitos binários ou bits 0 e 1. Finalmente, na nossa conversa de bar do final das reuniões, que desta vez acabou sendo gravada por descuido do coelho, batemos um papo sobre Georg Cantor e seus conjuntos (com diferentes) infinitos e de como é se hospedar no Grand Hotel de David Hilbert.
19/05 - Assista ao vídeo
Fórmulas lógicas e diagramas de Veen. Isso tem rolado em AlgeBool com a Nina. Sobre condições necessárias e condições suficientes. Validade de proposições, equivalências, e leis de DeMorgan usando diagramas de Veen. Uma fórmula é satisfatível se existe uma atribuição de valores (verdadeiro, falso) para suas variáveis de tal forma que a fórmula seja verdadeira. Uma fórmula é válida se é verdadeira para qualquer atribuição de valores para suas variáveis. Há quem chame tais fórmulas de tautologia.
Rolou uma conversa sobre a conjectura de Goldbach. Quantificadores para todo e existe e maneira abreviada e criptográfica de escrever e, ou, não, para todo, e existe. Também rolou uma conversa sobre o contrapositivo da conjectura de Goldbach. Depois ainda rolou mais uma conversa de bar que não foi gravada.
Curiosidade: O problema SAT consiste em: dada uma fórmula booleana; decidir se ela é satisfatível. Não se conhece um programa que em tempo razoável resolva SAT. Também não se sabe se um tal programa existe ou não existe. Este problema desafiador de existe ou não existe programa, conhecido como problema P versus NP, é um dos Millennium Prize Problems para os quais o Clay Mathematics Institute pagará um milhão de dolares americanos por uma solução.
14/05 - Assista ao vídeo:iniciozinho, meião, finalzinho
Desta vez o que conversamos tem relação com o que tem sido visto em:
- computação com o Denis: operadores lógicos
and,orenote expressões lógicas; - cálculo e vetores com a Lúcia e a Daniela: se f é derivável, então f é contínua; não é verdade que se f é contínua, então f é derivável; se u ou v é o vetor nulo, então uv = 0; não é verdade que se uv = 0, então u ou v é o vetor nulo. Uma coisa é uma coisa, outra coisa é outra coisa, e vice-versa.
- em álgebra booleana com Nina : em algebol vocês tem visto fórmulas que são logicamente equivalentes.
Conversamos sobre fórmulas lógicas e como construir proposições novas e mais complexas a partir de proposições mais simples. Fizemos isso com os operadores não, e, ou, ou exclusivo e implica. Para fórmulas escritas com ou exclusivo e o implica há formulas equivalentes usando apenas não, e e ou. Honestamente, podemos ficar com apenas dois operadores. Estamos treinando a linguagem sem ambiguida utilizada na matemática e em computação.
12/05 - Assista ao vídeo
Bezout e a boa ordem. Vimos mais uma aplicação do princípio da boa ordem. Desta vez foi na demonstração do Teorema de Bezout. Mais adiante veremos uma prova construtiva desse teorema, ou seja, um prova que fornece uma solução da equação x, y e d da equação xa + yb = d. Este teorema tem um papel central em vários algoritmos. Bezout também desempenhará um pepel do Problema de Frobenious.
07/05 - Assista ao vídeo
Hoje continuamos a conversar sobre provas. Vimos uma prova por casos do Teorema de Ramsey. Também conversamos sobre o Princípio da boa ordem e como este princípio é usado em um arcabouço de provas por contradição. No últimos 5 minutos tocamos na questão de como a nossa linguagem diária é ambigua (não há nada de ruim nisso!) e que em matemática e programação há regras claras para tornar afirmações mais precisas. Essa é a nossa deixa para conversarmos sobre fórmulas lógicas e seus mecanismos para criarmos novas proposições a partir de proposições existentes. Conversaremos sobre isso na próxima semana.
05/05 - Assista ao vídeo
Hoje a conversa expressão ou expansão decimal. Eu foi o pretexto para conversarmos de séries geométricas que aparecerão muito quando vocês forem analisar algoritmos, acho. Usando séries geométricas vimos que números que têm como expansão decimal uma dízimas periódica representam um número racional, que se chama sua geratriz. Por exemplo 0.521521521521... = 521/99.
30/04 - Assista ao vídeo
Hoje conversamos sobre proposições e afirmações e fizemos algumas demonstrações. Vimos provas diretas e uma prova por contradição. Em um passo de uma das demonstrações fizemos um argumento que é uma prova por contraposição. Demonstrações são frequentemente classificadas de acordo com a maneira que a argumentação é feita. Isso é uma ferramenta pedagógica, acho…
28/04 - Assista ao vídeo
Conversamos sobre números primos, uma nova prova do Teorema de Euclides, padrões enganosos, conclusões precipitadas, polinômios para gerar números primos e sobre o algoritmo da divisão. No meio da conversa apareceram os números de Euclides.
23/04 - Assista ao vídeo: início, fim
Hoje foi nossa primeira reunião que foi dividida em dois vídeos. Dependendo, uma reunião poderá ser dividida em vários vídeos. No vídeo início vimos uma demonstração do Teorema de Euclides que diz que há infinitos números primos. Conversamos sobre o comportamento recomendado nas reuniões como deixar o microfone desligado e, se possível, a câmera ligada. Exploramos um pouco o Google meet, em particular fizemos uma enquete (poll) e dividimos os participantes em grupos (breakout room). Em fim tivemos um reapresentação do Teorema de Euclides, desta vez em inglês.