2016.2 FMC1, turma de Thanos

Voluntários

Bibliografia

Prerequisito ter aprendido bem o conteudo de matemática elementária. Um livrinho bom para revisar e praticar: Precalculus mathematics in a nutshell, do George Simmons.

(Sem mandar bem o conteudo desse livro, não faz sentido se matricular em FMC1.)

• How to prove it, de Daniel Velleman (capítulos 1, 2, 3, e 6) (google it!)
• The tools of mathematical reasoning, de Tamara J. Lakins (capítulos 1, 2, 3, 4(4.1 e 4.2), 6, e obrigatoriamente a parte "Writing mathematics" no final do livro!)
• Mathematics of Choice: How to count without counting, de Ivan Niven (partes dos capítulos 1–5.)
• A survey of Modern Algebra, dos Birkhoff e Mac Lane: (1.4–1.9)
• Teoria dos números: (1.1–1.7 e 2.1)
• Minhas notas em progesso, e constantamente re-atualizadas, re-visadas, mudadas, etc.

Conteúdo

Conteúdo transversal

Linguagem da matemática. Elementos de lógica matematica. Lógica proposicional. Lógica de predicados. Métodos de prova. Redução ao absurdo. Prova pelo indução. Definições recursivas de funções. Sequências finitas e infinitas. Séries, somatórios, produtórios.

Sistemas de numeração

Bases posicionais notáveis: binário, octal, decimal, hexadecimal, etc. Inteiros, racionais e irracionais: representações finitas e infinitas. Aritmética e conversão entre diferentes bases numéricas.

Elementos de Teoria dos Números

Indução e o princípio da boa ordem. Teorema Fundamental da Aritmética. Infinidade dos primos. Divisibilidade. Aritmética modular. Congruências e resíduos: operações e propriedades. Teorema de Euler e pequeno teorema de Fermat. Teorema chinês dos restos. Introdução em criptografia.

Contagem

Arranjos, permutações, combinações com e sem repetição. Princípios da adição, da multiplicação, da inclusão-exclusão. Elementos de probabilidade.

Para estudar/praticar

• Estudar a secção 6.1 do Velleman e resolver seus problemas
• Resolver os problemas do ``Problem Set A da turma de 2016.1''.
• Estudar as páginas 376–379 do Velleman (“Summary of Proof Techniques”)
• Estudar as secções 1.3–1.4 do Velleman e resolver seus problemas
• Estudar as secções 2.1–2.2 do Velleman e resolver seus problemas
• Prove (em ``full'' detalhe) que:
  • ∀x∀y x + y = y + x;
  • ∀x∀y∀z x + (y + z) = (x + y) + z,
  onde + é a adição que definimos recursivamente no N².
  Dica: Não é necessário sempre usar indução. As vezes uns resultados são imediatos ou provados mais facilmente direitamente.
• Define o ≤ : N² → B recursivamente
• Usando as definições

  +      : N² → N
  m + 0  = m                    (+1)
  m + Sn = S(m + n)             (+2)
  
  ·      : N² → N
  m · 0  = 0                    (·1)
  m · Sn = (m · n) + m          (·2)
  
  ^      : N² → N
  m ^ 0  = S0                   (^1)
  m ^ Sn = (m^n) · m            (^2)
  
  max         : N² → N
  max(m,  0)  = m               (max1)
  max(0,  n)  = n               (max2)
  max(Sm, Sn) = S(max(m,n))     (max3)
  
  min         : N² → N
  min(m,  0)  = 0               (min1)
  min(0,  n)  = 0               (min2)
  min(Sm, Sn) = S(min(m,n))     (min3)
  

  prove que:
  • x · (a + b) = (x · a) + (x · b)
  • x · y = y · x
  • (a^m)ⁿ = a^m·n
  • min(u,v) ≤ max(u,v)
  • se a ≤ b, então x + a ≤ x + b
  • se a ≤ b, então x · a ≤ x · b
• Estudar as secções 3.1–3.5 do Velleman, exceto os exemplos 3.3.4 e 3.3.5 (porque usam umas operações de conjuntos que a gente vai só encontrar em FMC2) (mas leia bem a pagina 118 que fica entre esses dois exemplos!)
• Resolver os problemas das secções 3.1–3.5 do Velleman, exceto aqueles que falam sobre "familias de conjuntos", sobre o operador unitário de união ∪F, e sobre o operador de powerset, P(A)
• Estudar a secção 6.3 do Velleman
• Praticar com notação Σ e Π: Sigma notation de mathcentre.ac.uk
• Prove que o Princípio da Indução Finita implica o Princípio da Boa Ordem
  • Na prova de aula, para provar isso definimos o predicado
    P(n) ⇔ "cada subconjunto S de naturais que possui o n como elemento, tem minimo".
  • Assim, precisamos indução forte
  • Ao invez dessa propriedade P(n), define o:
    Q(n) ⇔ "cada subconjunto S de naturais que possui um elemento menor ou igual de n, tem minimo".
  • Verifique que assim não precisamos indução forte.
• Prove o último teorema da aula de 14/10/2016, que deixamos sem provar. Dica: considera o conjuntos de todas as combinações lineares (como denotamos isso?), prove que ele é fechado sobre + e -, use o teorema anterior!
• Seja um conjunto de inteiros S. Prove que:
  • S fechado sobre - implica que ele é fecdo sobre + também
    (Ou seja, não precisamos no teorema da aula 14/10/2016 a hipótese que o S é fechado sobre +!)
  • No outro lado, S fechado sobre + não implica que ele é fechado sobre -. (Prove!)
• ANTES da aula extra do dia 29/10: Praticar com os assuntos dos ultimos dias, para ficar bem confortável com:
  • Achar o (a,b).
  • Achar inteiros s,t tais que (a,b) = as + bt
  • Fatorização em primos
  • A notação a ≡ b (mod m)
  • As propriedades de congruências
  • Resolver por x congruências da fórma: ax ≡ b (mod m)
  • Achar o inverso de uma classe de inteiros módulo m, quando existe
• Sobre contagem:
  • É um exercísio (de programação) bom implementar (na sua linguagem favorita) todas as fórmulas que encontramos nas aulas (combinações, permutações, etc.), e tentar fazer isso no jeito mais eficiente.
  • Para quem quer verificar suas respostas nos exercísios, tenho aqui meu Comb.hs em Haskell. (Obs: essas implementações estão numa balança (pra mim...) entre eficiência e claridade.) Para usar essa biblioteca, tendo instalado primeiro a Haskell, baixa o arquivo e executa ghci Comb.hs. Depois pode usar suas funções para teus cálculos (exemplo de uso).
  • Equações com soluções restritas separadamente: Tente generalizar o que a gente viu na aula de "positivo" e "natural" para o caso onde cada x_i tem que ser pelo menos c, e depois onde cada x_i tem que satisfazer x_i > c_i. (A resposta fica na secção 4.4 do Niven, pp. 61--64.)
  • Implemente na sua linguagem de programação favorita uma simulação do Monty Hall one o jogador é programado para nunca mudar a sua primeira escolha. Executa tua simulação para 10 jogos, depois 100, 1000, 100000... O que percebes? Qual a fracção das vezes que ele ganha sobre as vezes totais?
  • Assista a palestra do Peter Donnelly ``How stats fool juries''.
• Para a 4a prova: (tl;dr: tudo tá dentro (veja histórico das aulas))

  Sugestão para estudar:

  • Velleman: 1, 2, 3, 6
  • Minhas notas: 5, 9, 10, 12
  • Niven: 2, 3.1–3.7, 4.1–4.3, 5.1, 5.3, 5.4,

Provas

Unidade 1

• Provinha 1.0: (points: 55 34/100; bonus: 21 0) (dia: 02/09/2016)
  { censored, uncensored, answers }
• Prova 1.1 (points: 66/100; bonus: 12) (dia: 07/10/2016)
  { censored, uncensored, answers }

Unidade 2

• Prova 2 (pts: 120/100; bonus: 18) (dia: 23/11/2016)
  { censored, uncensored, answers }

Unidade 3

• Prova 3 (pts: 128/100; bonus: 8) (dia: 09/12/2016)
  { censored, uncensored, answers }

Prova de recuperação

Uma prova sobre todo o conteudo de FMC1, comum para todos.

• Prova 4 (pts: 200/100; bonus: 33) (dia: 16/12/2016)
  { censored, uncensored, answers }

Histórico de aulas

25/07/2016

• Resumo do conteúdo
• Definições, teoremas, noções primitivas, axiomas
• Um teorema: n ímpar implique n² ímpar

27/07/2016

• Variações do teorema anterior
• Sua generalização, e como provar
• Prova pela indução
• O somatório 1 + 2 + ... + n

08/08/2016

• Provas como jogo
• Como provar formulas de vários tipos
• Nomes e scopos de variáveis (similaridades com programação)
• Provas por indução:
  • 2⁰ + ... + 2ⁿ = 2ⁿ⁺¹ - 1
  • 3 | n³ - n

10/08/2016

• Como abstrair, definindo funções e predicados
• Nomes e scopos de variáveis
• Erros comuns na escrita de provas
• Mais provas por indução:
  • 0² + 1² + ... + n² = n(n+1)(2n+1)/6
  • ``triminôs'' e ``xadrez'' de dimensão 2ⁿ × 2ⁿ: de prova para algoritmo

12/08/2016

• Universo de objetos (e.g., números, pessoas, ...)
• Mais sobre funções e predicados
• Compondo funções e predicados
• Mais provas por indução
• Uma prova errada: todos os conjuntos de n pessoas têm apenas membros nascidos no mesmo dia

15/08/2016

• Variáveis livres e ligadas
• Universos de objetos: números, pessoas, conjuntos, ...
• Lógica de predicados: primeiras noções de fórmulas e conectivos
• Definições: Prime(n), Mãe(x), ...

17/08/2016

• Conjuntos
  • Conjuntos como ``black box''
  • A notação { ... }
  • A notação { ..x.. | φ(x) }
  • Operadores (funções) e suas definições formais
  • Relações (predicados) e suas definições formais
• O significado da implicação em matemática
• Árvores sintáticas de expressões de aritmética e de lógica
• Fórmulas vs. termos
• Abreviações de fórmulas:
  • ∀x∈A P(x)
  • ∃x∈A P(x)

19/08/2016

• Mais abreviações de fórmulas: ∃!x∈A P(x), ∃n≥4 Q(n), ∀k<42 R(k), etc.
• Mais sobre a notação de comprehensão de conjuntos { ..x,y,z.. | φ(x,y,z) }
• Implicação e o Wason selection task
• Traduções de português para a linguagem formal de lógica de predicados
• Introdução em recursão: fatorial, o conjunto ℕ dos naturais

22/08/2016

• Recursão e indução
• Definições recursivas de funções e de conjuntos
• O conjunto ℕ de naturais (definido pelo 0 e S)
• Construtores de valores
• Programando e calculando com equações (recursivas)
• Definição recursiva de: adição, multiplicação, exponenciação
• Escolhendo a ``melhor'' variável para a recursão

24/08/2016

• Mais recursão e indução
• Definições recursivas de funções: min, max, iszero, even, odd
• Recursão mutual: even e odd
• Provas por indução em mais que uma variável

26/08/2016

• A ordem de quantificadores e quando podemos a trocar
• Valor de verdade das formulas da lógica de predicados: universos e mundos
• Como provar que duas fórmulas não são equivalentes
• Mais indução & recursão
• Escolhendo a ``melhor'' variável para a indução
• + é comutativa (wow!)
• a^m+n = a^m·aⁿ
• · é associativa

29/08/2016

• Resolução de problemas de recursão e indução.
• Os números Fibonacci.

31/08/2016

• Os números fibonacci e propriedades
• Revisão
• Mais recursão e indução
• Mais sobre escrevendo matemática corretamente
• Mais sobre como argumentar
• Floors and ceilings

02/09/2016

• Provinha 1.0 (U1)

05/09/2016

• Sermão
• Correção da provinha

09/09/2016

• Equivalências e leis de lógica
• Negação
• Prova pelo absurdo
• Os números (racionáis e irracionais)
• O √2 é irracional
• O √2 ``existe''
• Ergo, existem números irracionais

12/09/2016

• Revisão: o √2 é irracional
• O √3 é irracional
• O √4 é... (ir)racional!?

14/09/2016

• Generalização dos teoremas anteriores de irracionalidade
• Somatórios e produtórios
  • definição informal
  • definição formal (recursiva)

16/09/2016

• Somatórios e produtórios vazios; bases comuns em indução
• Número, numeral, e algarismo ou dígito
• Gregos e romanos antígos, al-Khwārizmī, Fibonacci
• Sistemas de numeração posicionais
• O sistema trivial unitário: críticas e eulógios
• Bases de sistemas

21/09/2016

• Números inteiros e racionais na linha e com dígitos
• Aplicações dos sistemas Bin/Hex/Oct
• Números com representação periódica
• Um teorema útil para representação de números em sistemas posicionais

26/09/2016

• Revisão:
  • reductio ad absurdum
  • (irracionalidade de √n para varios n)
  • prova por casos
  • como escrever definições e provas

28/09/2016

• Propriedades de divisibilidade
• O principio da boa ordem (PBO)
• O principio da indução finita (PIF)
• PIF ⇐ PBO

05/10/2016

• Mais provas pelo absurdo:
  • nosso primeiro ε > 0
  • Não existem inteiros x e y tais que 27x + 39y = 1000
• Nao existe inteiro entre 0 e 1
• PIF e PBO, dois lados da mesma moeda

07/10/2016

• Prova 1.1 (U1)

10/10/2016

• Uns detalhes da prova 1.1
• Indução forte
• PIF ⇒ PBO
• O algoritmo da divisão (prova informal)
• Provas de unicidade

14/10/2016

• O algoritmo da divisão (prova formal)
• Conjuntos fechados sobre operações
• Teorema: um conjunto não vazio de inteiros S, fechado sobre + e - é o {0} ou possui um mínimo elemento positivo m, e S = {km | m∈Z}
• gcd (mdc): definição (notação: (a,b))
• combinação linear
• Teorema: Sejam a,b inteiros, com a,b ≠ 0. Existem inteiros s,t tais que (a,b) = sa + tb.

17/10/2016

• Prova do último teorema da aula 14/10/2016.
• O algoritmo de Euclides
  • Ideia e descrição
  • Por que termina?
  • Por que calcula mesmo o mdc?

19/10/2016

• O algoritmo de Euclides
  • Como achar o mdc(a,b)
  • Como escrever o mdc(a,b) como combinação linear dos a e b.
  • Exemplos
• Uns teoremas como corolários: (p primo)
  • p|ab ⇒ p|a ou p|b (Euclid's lemma)
  • (d,a)=1 & d|ab ⇒ d|b
  • (a,b)=1 & a|m & b|m ⇒ ab|m
• Primos
• Crivo de Eratosthenes

21/10/2016

• O Teorema fundamental da Aritmética
• Euclides: "o conjunto dos primos é infinito"
• Codificação de seqüências finítas
• Congruências e aritmética modular: introdução
• Congruências: duas definições equivalentes
• ≡ parece = (como?)
• ≡ é uma relação de equivalência
• Propriedades da relação a ≡ b (mod m)

26/10/2016

• Congruências e aritmética modular: revisão
• ``Resolvendo'' a cx ≡ b (mod m)
• Inversos dos inteiros mod m

29/10/2016 (aulas de reposição (4h))

• Definido + e ⋅ nas classes dos inteiros modulo m
• O teorema chinês de restos
• A função "totient" de Euler φ(n): propriedades
• Euler: (a,m) = 1 ⇒ a^φ(m) ≡ 1 (mod m)
• Fermat 1: (a,p) = 1 ⇒ a^p-1 ≡ 1 (mod p)
• Fermat 2: a^p ≡ a (mod p)

31/10/2016

• Critéria de divisibilidade: 3, 9, 11
• A prova do teorema de Euler
• Propriedades da φ(n)

07/11/2016

• Introdução em Criptografia

09/11/2016

• O RSA
• Problemas fáceis vs difíceis
• Exponenciação mod m

23/11/2016

• Prova (U2)

(As secções referencem o livro do Niven na bibliografia)

25/11/2016

[2.1, 2.3, 2.5, 2.6, 3.1]

• Introdução em contagem
• O princípio da adição
• O princípio da multiplicação
• Permutações
• Combinações
• Traduções de problemas
• Permutações circulares

28/11/2016

[2.3, 3.1, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7]

• Quantos números entre... com restrições
• Aplicações dos dois principios
• Permutações de objetos não todos diferentes (e.g. "Mississipi")
• Número de subconjuntos dum conjunto finito (traduzindo para string de "S"/"N")
• O triangulo de Pascal e os coeficientes binomiais

30/11/2016

[3.6, 3.7, 4.1, prova2 2016.1]

• De Pascal para Fibonacci!
• Somando as linhas do triangulo de Pascal
• Somando as linhas do triangulo de Pascal alterando sinais
• Número de subconjuntos dum conjunto finito (separando em casos)
• Contando recursivamente
• Resolvendo o problema dos sapos da Prova II de 2016.1

02/12/2016

[2.5, prova4 2016.1, 4.2]

• Jantar com casais e brigados
• Mais exemplos: carros; caminhos
• Mais resoluções recursivas: Torres de Hanoi
• De arranjos para permutações
• Nova prova do teorema de Fermat
• O sonho do calouro
• Equações com soluções nos: inteiros positivos; naturais

05/12/2016

[5.1, 5.3, 5.4]

• Problemas com permutações cíclicas
• Inclusão--Exclusão
• Probabilidade elementária
• Dados, casinos, Monty Hall

07/12/2016

[4.3, 5.3]

• Combinações com repetições
• Desarranjos
• Erros comuns com probabilidade

09/12/2016

• Prova (U3)

12/12/2016

• Sermão
• Revisão FMC1

14/12/2016

• Revisão FMC1

15/12/2016 (aulas extra (4h))

• Revisão FMC1

16/12/2016

• 4a prova