Matemática Concreta (2016/1)

alias Problemas I (Resolução de Problemas e Matemática Discreta)

Para os cursos de graduação em Matemática Aplicada e Engenharias.

Motivação

Este curso surgiu da vontade de explorar novamente o livro Concrete Mathematics e ao mesmo tempo introduzir uma disciplina que fosse acessível a todos os alunos a partir do 2º ano em Exatas, com um conteúdo e proposta diferente da matemática habitual dos cursos (Cálculos e Álgebra Linear).

Assim, o mais importante desta disciplina é que ela trata de assuntos discretos, e não contínuos, como por exemplo recorrências, técnicas para lidar com somatórios e um pouco de combinatória.

Indicações práticas

O objetivo deste curso sendo dar familiaridade com diversas técnicas de matemática discreta, haverá uma importância fundamental nas listas de exercícios. A maior parte destes exercícios será tirada do livro-texto, que possui uma seleção abrangente e com graus crescentes de dificuldade.

Haverá além disso duas avaliações em sala de aula.

Programa

Indução e recorrências, somatórios; Números binomiais, e outros números combinatórios; Funções geratrizes e aplicações

Ementa

I. Recorrência e Indução. Solução de problemas por recorrência. Demonstração por indução. Equações de recorrência. Métodos de Álgebra Linear aplicados às recorrências.

II. Somas. Propriedades do somatório. Manipulação de somas. Somas duplas e múltiplas. Notação de Iverson para somas. Somas como anti-diferenças. Potências decrescentes. Somas por partes.

III. Coeficientes Binomiais. Definição. Generalização para números reais. Propriedades. Identidades binomiais por argumento polinomial. Teorema binomial. Convolução de Vandermonde.

IV. Funções geradoras. Definição. Manipulação algébrica. Manipulação analítica. Propriedades combinatórias. Decomposição em frações parciais. Solução de recorrências não-lineares via funções geradoras.

V. Comportamento Assintótico. Notação assintótica O(), o(). Propriedades formais. Propriedades analíticas. Técnicas de estimativa assintótica. Aproximação usando séries assintóticas divergentes. Exemplos clássicos.

Livro Texto: Concrete Mathematics, R.L.Graham, D.E. Knuth, O. Patashnik

  • 2016/1
    • Planejamento do curso
    • Aula 1: Organização; as Torres de Hanói
    • Aula 2: Problema de Josephus
    • Lista 1: Exercícios do capítulo 1 para dia 20 de Abril
      • Hanói: 2,3,4,11a
      • Linhas: 6,13
      • Josephus: 7,15
      • Indução: 9
    • Aula 3: Introdução a somas: notação de Iverson, manipulação de somas duplas
    • Aula 4: Somas 2: técnicas
    • Lista 2: Exercícios do capítulo 2 para dia 2 de Maio
      • Warmups: 4, 6, 9, 10
      • Basics: 12, 13, 14, 17
      • Homework: 19, 20, 22, 23, 26
    • Aula 5: Cálculo finito: diferenças finitas, somas, analogia com integrais, potências fatoriais, somas por partes
    • Aula 6: Números Binomiais 1: definições, simetria, absorção, princípio polinomial, fórmula de adição e indução, diferenças finitas, teorema binomial
    • Aula 7: Solução da lista 1
    • Aula 8: Binomiais 2: Upper negation, Trinomiais, Convolução de Vandermonde
    • Aula 9: Binomiais 3: Somas com binomiais (1,3,5 e 6)
    • Aula 10: Solução da lista 2
    • Lista 3: Primeira leva de exercícios do capítulo 5 para dia 18 de Maio
      • Warmups: 1 ao 5 (basta entregar 2)
      • Basics: 13 e 14
      • Homework: 35, 38, 39, 43
    • Aula 11: Binomiais 4: Binômio de Newton para operadores, polinômio de Newton
    • Aula 12: Continuação da Solução da lista 2
    • Aula 13: Fórmula de inversão binomial
    • Aula 14: Funções geradoras 1: definições e convolução
    • Aula 15: Funções geradoras 2: fibonacci e outros exemplos
    • Aula 16: Revisão de funções geradoras
    • Aula 17: Funções hipergeométricas 1: termos hipergeométricos
    • Aula 18: Funções hipergeométricas 2: derivadas e equações diferenciais
    • Aula 19: Funções geradoras abstratas: dominós
    • Aula 20: Funções geradoras comutativas: contando moedas, somas de quadrados
    • Aula 21: Funções geradoras para resolver recorrências
    • Lista 4: Segunda parte dos exercícios do capítulo 5 para dia 29 de Junho
      • Warmups: 8, 10, 12
      • Basics: 17, 18, 20, 24, 29, 30
      • Homework: 46, 47, 49, 52
  • 2014/1
    • Planejamento do curso
    • Aula 1: Organização; as Torres de Hanói
    • Aula 2: Indução; Problema de Josephus; mais recorrências
    • Aula 3: Repertório para recorrências; Somas 1
    • Lista 1: Exercícios do capítulo 1 para dia 19 de Março
      • Hanói: 2,3,4,11
      • Josephus: 7,15
      • Indução: 9
      • Recorrências: 16, 20
      • Tradução: aqui
    • Aula 4: Somas 2: somas duplas, 5 métodos de somas
    • Aula 5: Somas 3: operadores diferença e somação
    • Preparar para a aula 6: dois exercícios dentre 14, 21, 22, 30
    • Aula 6: Somas 4: exercícios, operadores bis
    • Aula 7: Binomiais 1: definições básicas
    • Aula 8: Binomiais 2: trinomiais, convolução de Vandermonde, simplificando somas
    • Aula 9: Prova 1
    • Lista 2: Exercícios do capítulo 5 para dia 7 de Maio
      • Warmups: 2, 3, 5
      • Basics: 13, 14, 17
      • Homework: 35, 37, 38, 40
    • Aula 10: Binomiais 3: mais exemplos de somas com binomiais
    • Aula 11: Binomiais 4: Fórmula de interpolação de Newton, inversão binomial
    • Prova 2 - Capítulo 5 para dia 21 de Maio
    • Aula 12: Funções geratrizes 1
UFRJ Departamento de Matemática Aplicada - Instituto de Matemática - UFRJ
Valid XHTML 1.1 Valid CSS! Desenvolvido por: Bernardo Freitas Paulo da Costa Inspirado do padrão: TIC/UFRJ