2016.1 FMC1, turma de Thanos

Atividades / Exercícios / Problemas

Vocês podem mandar suas soluções pelo email (pode ser foto/scan de papel, ou arquivo PDF escrito em TeX/LaTeX/etc., mas não em Word/LibreOffice/etc.), ou entregar em papel mesmo.

1. Sem olhar para notas, livros, etc., tenta:
   Não vai ter aula hoje, 02/03/2016.
   • escrever a definição do que é um número racional.
   • provar que √2 é irracional.
2. Problem set A (prazo: 07/03/2016 09/03/2016, 16h50). [Vale pontos!]

Voluntários

• Unidade 1
  • André Silva (3)
  • André Morreira (2)
  • Bia (1)
  • Marcus (2)
  • Pedro Henrique Giacomeli (2)
  • Johnny (1)
• Unidade 3
  • André Morreira (3)
  • Susanny (2)
  • Johnny (3)
  • Pedro Henrique (4)
  • Paulo Vitor (1)
  • Paulo Henrique (3)
  • Daniel (1)

Bonus points

• Unidade 1
  • André Moreira (0,7)
  • Jeckson (0,1)
• Unidade 2
  • André Moreira (0,1)
  • Jeckson (0,2)
  • Jonas (0,2)
  • Paulo Vitor (0,2)
  • Pedro Henrique (0,2)
• Unidade 3
  • André Moreira (0,1)
  • Paulo Henrique (0,2)
  • Paulo Vitor (0,2)

Bibliografia

• Propositional and Predicate Calculus, de Derek Goldrei (capítulo 2, e secções 4.1-4.3)
• Mathematics of Choice: How to count without counting, de Ivan Niven (partes dos capítulos 1-5.)
• Teoria dos números: (1.1-1.7 e 2.1)
• A survey of Modern Algebra: (1.4-1.9)

Conteúdo (meio fluido)

O conteúdo dessa disciplina é baseado no seguinte:

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.

Elementos de Teoria dos Números

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.

Contagem

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

Sistemas de numeração

Bases posicionais notáveis: binário, octal, decimal, hexadecimal, etc. Aritmética e conversão entre bases.

Relações de recorrência & recursão sobre os naturais.

Definições recursivas de funções. Sequências finitas e infinitas. Séries, somatórios, produtórios. Funções geradoras e soluções explícitas de relações de recorrência.

Representação computacional de números.

Inteiros: representação sinalizada, complemento-de-dois. Racionais e irracionais: representações finitas e infinitas, em diferentes bases numéricas. Sistemas de ponto flutuante, erros absoluto e relativo, ulps. Problemas: não fechamento aritmético, perda de propriedades aritméticas

Provas

Prova I (04/04/2016)

• Lógica (proposicional e de predicados)
  • fórmulas bem formadas de F₀ e F₁
  • árvores sintáticas de fórmulas
  • atribuações de valores
  • tabelas de valores
  • estruturas (``mundos'') e modelos
  • fórmulas equivalentes
  • negação de fórmulas, manipulação de quantificadores
  • conjuntos completos de conectivos
• Definições recursivas (de conjuntos e de funções)
• Simples provas diretas, por casos e pelo absurdo, irracionalidades, etc.
• Provas pelo indução: no N, no F₀, no F₁, etc.
• somatórios e produtos

Material para praticar

• Seções I 4.4, I 4.6, I 4.7 do livro "Calculus, Volume I", de Tom Apostol
• Usando as definições recursivas dos +, *, ^, min, max, e ≤ prove que:
  • x + (y + z) = (x + y) + z
  • x + y = y + x
  • x * (y * z) = (x * y) * z
  • x * y = y * x
  • x * (a + b) = (x * a) + (x * b)
  • a ^ (m + n) = a^m * a^n
  • (a ^ m) ^ n = 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
• Todos os problemas exceto o B.8 do problem set B da minha turma de FMC2.

Prova II (13/05/2016)

• Análise combinatória. Do conteudo do livro do Niven:
  • Chap 2: todo
  • Chap 3: todo exceto o 3.8
  • Chap 4: todo exceto o 4.4
  • Chap 5: todo exceto o 5.2
  • Chap 10: todo (claro!!)
• Representação de números
  • Bases: decimal, binária, octal, hex, n
  • Ponto fluntuante, operações e erros

Prova III (10/06/2016)

• Teoria de Numeros
  (Nas explicações em baixo, p é primo.)
  • Principio da Boa ordem e da Indução
  • Divisibilidade e suas propriedades, mdc, mmc
  • Primos
  • Algoritmo da divisão
  • Algoritmo de Euclides
    • como achar o mdc(a,b)
    • como escrever o mdc(a,b) como combinação linear de a e b
  • Teorema Fundamental da Aritmética
  • Congruências
  • A função "totient" de Euler φ(n): definição e suas propriedades:
    • Se (m,n) = 1 então φ(nm) = φ(n)φ(m)
    • φ(p^k) = p^k - p^k-1 = p^k(1 - (1/p))
    • φ(n) = n (1-(1/p₁)) (1-(1/p₂)) ... (1-(1/p_k)), onde os p_i são os primos dados pelo Teorema Fundamental da Aritmética
  • Teoremas de Fermat:
    • Se (a,p) = 1 então a^p-1 ≡ 1 (mod p)
    • a^p ≡ a (mod p)
  • Teorema de Euler:
    • Se (a,m) = 1 então a^φ(m) ≡ 1 (mod m)
  • Sonho do Calouro:
    • (x + y)^p ≡ x^p + y^p (mod p)
  • Teorema chinês dos restos
• No livro A survey of Modern Algebra: 1.4, 1.6, 1.7, 1.8, 1.9
• No livro Teoria dos números: (1.1-1.7 e 2.1)

Prova IV (17/06/2016)

Histórico de aulas

03/02/2016

• Resumo do conteúdo
• Conjuntos notáveis de números, N, Z, Q, R\Q, R
• Definição: número racional
• Teorema: √2 é irracional
• Umas propriedades de números pares e ímpares
  • "ímpar" tem acento
• Redução ao absurdo (reductio ad absurdum)

12/02/2016

• Detalhes da prova que √2 é irracional
• Adação para provar que √3 é irracional
• O algoritmo da divisão do Euclides
• Noções básicas da aritmética modular
• Prova de impicação (direta, assumindo a premissa)

15/02/2016

• Prova de impicação provando o contrapositívo (prova de: se p² par então p par)
• Prova por casos
• ``Prova'' que √4 é irracional
• Noções básicas da lógica proposicional
  • variáveis proposicionais
  • valores booleanos {F, T}, (ou {0, 1}, ou {F, V}).
  • os conectivos ¬, ∨, ∧, →, ↔
  • aridade (que é palavra em português)
  • formulas bem-formadas

17/02/2016

• logica proposicional
• logica de predicados

19/02/2016

• Definições recursivas (o conjunto dos naturais e o conjunto das formulas proposicionais)
• Prova por indução

22/02/2016

• mais exemplos de provas por indução nos naturais

24/02/2016

• mais exemplos de provas (voluntarios: André e Marcos)
• uma prova por indução errada
• indução no conjunto de fórmulas de lógica proposicional

29/02/2016

• Provas por indução de teoremas ``diferentes''
  • ``Xadrez''
  • Nim
• Funções recursivas definidas nos naturais
• Funções recursivas definidas nas fbf (formulas bem formadas) da lógica proposicional
• Introdução em programação funcional

04/03/2016

• Lógica de predicados

07/03/2016

• Lógica proposicional: significado e valor das fórmulas
• Lógica de predicados: significado e valor das fórmulas
• Interpretações (mundos)
• Negação

09/03/2016

• Correção dos exercícios

14/03/2016

• Negação de formulas de logica proposicional
• Negação de formulas de logica de predicados
• Elementos de análise combinatória
• Mais funções recursivas

16/03/2016

• Como (não) escrever matemática
• Comentarios sobre os exercícios
• Mais recursão, mais indução

18/03/2016

• Mais recursão, mais indução

21/03/2016

• Mais somatórios e produtos
• Mais recursão, mais indução

23/03/2016

• Funções recursivas e provas pelo indução

25/03/2016

Revisão (1)

30/03/2016

Revisão (2)

01/04/2016

Prova! Revisão (3)

04/04/2016

Prova!

06/04/2016

Resolução da prova & sermão

08/04/2016

• Fatorial
• Introdução na análise combinatória
• Principio de multiplicação
• Principio de adição
• Arranjos
• Permutações sem repetições
• Permutações com repetições
• Combinações
• Coeficientes binomiais

11/04/2016

• Quantidade de subconjuntos
• Coeficiente binomial
• Permutações cíclicas

13/04/2016

Revisão
• Generalização dos coeficientes binominais
• Permutações de objetos não todos distintos
• Uma interpretação combinatória do lei do triângulo de Pascal

15/04/2016

18/04/2016

25/04/2016 (aula extra)

25/04/2016 (aula normal)

27/04/2016

29/05/2016

04/05/2016

Patrick: ponto flutuante I

06/05/2016

Patrick: ponto flutuante II

09/05/2016

11/05/2016

• introdução na teoria de números
• divisibilidade
• divisibilidade é relação de ordem

13/05/2016

Prova!

16/05/2016

• Uns teoremas sobre divisibilidade
• O princípio da boa ordem do N
• Nao existe inteiro entre 0 e 1.

18/05/2016

• Mais teoremas sobre divisibilidade
• O princípio da boa ordem do N implica o princípio da indução.

20/05/2016

• O princípio da boa ordem do N é equivalente com o princípio da indução.
• Primos

23/05/2016

• B&ML (Birkhoff & Mac Lane): 1.6

25/05/2016

• B&ML: 1.6-1.7

27/05/2016

• B&ML: 1.7