MCTB019 -- Matemática Discreta -- 2022.1

Turmas NA (Seg 19–21h, Qui 21–23h) e NB (Seg 21–23h, Qui 19–21h)


Atualizado em 08/02
Página do curso entra no ar.

Expediente

Ementa

Teoria intuitiva dos conjuntos. Operações com conjuntos. Álgebra de conjuntos. Relações: relações de equivalência, relações de ordem. Funções. Coleções de conjuntos. Conjuntos numéricos. Cardinalidade. Técnicas de demonstração: prova direta, prova por contradição. Indução Finita. Introdução à análise combinatória. Princípio multiplicativo. Princípio aditivo. Permutação, arranjo, combinação. Princípio de inclusão e exclusão. O princípio da casa dos pombos. Funções geradoras. Partição de um inteiro. Relações de recorrência. Recomendação: Funções de Uma Variável

Avaliações e critérios

  • 5 listas de exercícios (enunciados e correções no Moodle)
Lista Data de Entrega
$L_1$ 03/03 @ 23:59h
$L_2$ 21/03 @ 23:59h
$L_3$ 07/04 @ 23:59h
$L_4$ 25/04 @ 23:59h
$L_5$ 10/05 @ 23:59h

Nota nominal: média aritmética das 4 melhores dentre as 5 listas $$ N = \frac{1}{4}\max\left\{\sum_{j\in S}L_j\,:\,S\in\binom{[5]}{4}\right\} $$

Conceito nominal ($C_N$): reflete o seu desempenho frente ao material apresentado e às avaliações realizadas; obtido pelo encaixe de $N$ em um dos intervalos: $$-\infty < \mathbf{F} < 5.0 \leq \mathbf{D} \leq 6.0 < \mathbf{C} \leq 7.0 < \mathbf{B} \leq 8.5 < \mathbf{A} < \infty.$$

Normalização

Sejam $\mu$ e $\sigma$ a média e o desvio padrão das notas $N$ atribuídas a todos os alunos. Cada aluno obterá uma nota normalizada: $$M = (N-\mu)/\sigma.$$

Conceito normalizado ($C_M$): reflete o seu desempenho perante os seus colegas; obtido pelo encaixe de $M$ em um dos intervalos: $$-\infty < \mathbf{F} < 0 \leq \mathbf{D} < \frac{1}{4}\sigma \leq \mathbf{C} < \frac{1}{2}\sigma \leq \mathbf{B} < \sigma \leq \mathbf{A} < \infty.$$

Considerando-se a ordenação $\mathbf{A} > \mathbf{B} > \mathbf{C} > \mathbf{D} > \mathbf{F}$, seu conceito efetivo (final / pré-recuperação) será maior ou igual ao seu conceito nominal: $$C_F = \max\{C_N,C_M\}.$$

Recuperação

Caso seu conceito $C_F$ seja $\mathbf{D}$ ou $\mathbf{F}$, você tem direito a uma prova online de recuperação $P_R$. Esta será única e contemplará toda a matéria do quadrimestre. Uma nova nota nominal $\overline{N}=(N+P_R)/2$ será utilizada para gerar um novo conceito (nominal) final pós-recuperação $\overline{C}_N$. Não haverá normalização na recuperação. Seu conceito final pós-recuperação pode ser menor que o pré-recuperação: uma vez feita, a recuperação é parte integrante da sua avaliação.

Bibliografia

Nossas referências primárias serão os textos [Gri], [LLM], [KT] e [Ros]. Os pdfs dos dois intermediários estão disponíveis gratuitamente online:

  • [Gri] R. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th ed., Pearson Addison-Wesley (2004)
  • [LLM] E. Lehman, F. Leighton, A. Meyer, Mathematics for Computer Science, MIT Creative Commons 3.0 (2018)
  • [KT] M. Keller, W. Trotter, Applied Combinatorics, Preliminary ed.
  • [Ros] K. Rosen, Discrete Mathematics and its Applications, 8th ed., McGraw Hill (2019)

Outros livros bons para consultas sobre o tema são:

  • [Big] N. Biggs, Discrete Mathematics, Clarendon Press (1985)
  • [Bon] M. Boná, A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, 4th ed., World Scientific (2017)
  • [GKP] R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed., Addison–Wesley (1994)
    (tradução: Matemática Concreta: Fundamentos para Ciência da Computação, 2a ed., LTC (1995))
  • [Juk] S. Jukna, Extremal Combinatorics with Applications in Computer Science, 2nd ed., Springer (2011)
    (material um pouco mais avançado)
  • [LPV] L. Lovász, J. Pelikán, K. Vesztergombi, Discrete Mathematics: Elementary and Beyond, Springer (2003)
    (tradução: Matemática Discreta, 2a ed., SBM (2013))
  • [Mer] R. Merris, Combinatorics, 2nd ed., Willey (2003)
  • [MN] J. Matousek, J. Nesetril, Invitation to Discrete Mathematics, 2nd ed., Oxford University Press (2008)
  • [RT] F. Roberts, B. Tesman, Applied Combinatorics, 2nd ed., CRC Press (2009)
  • [Tuc] A. Tucker, Applied Combinatorics, 6th ed., John Wiley & Sons (2012)

Observação

Listei as últimas edições acima para questões de referência, numerações de exercícios, etc.
É possível, no entanto, utilizar qualquer edição para estudo do material.

Outro livro com material relacionado que recebeu tradução para o português foi:

  • [Ger] J. Gersting, Fundamentos Matemáticos para a Ciência da Computação, 2a ed., LTC (2001)
    É possível estudar alguns dos tópicos que vamos cobrir por ele. Não o tenho. Logo, não poderei indicar seções.

Páginas úteis

Lista de tópicos por semana

Semana Datas Tópicos
S00 Introdução / Expediente
S01 14/02 e 17/02 Fragmentos de Lógica Proposicional
S02 21/02 e 24/02 Fragmentos de Lógica de Predicado
S03 03/03 e 07/03 Álgebra de Conjuntos e Técnicas de Prova
S04 10/03 e 14/03 Fundamentos de Contagem
S05 17/03 e 21/03 Provas por Indução
S06 24/03 e 28/03 Casas de Pombos, Inclusão-Exclusão, Conjuntos Infinitos
S07 31/03 e 04/04 Grafos: Definições Básicas + Exemplos de Provas
S08 07/04 e 11/04 Conjuntos Parcialmente Ordenados e Reticulados
S09 14/04 e 18/04 Funções Geradoras
S10 25/04 e 28/04 Relações de Recorrência
S11 02/05 e 05/05 Partições de Inteiros
S12 10/05 e 18/05 Fragmentos do Método Probabilístico (se der tempo)
  • Seções para leitura a cada semana no Moodle

Estudando para esta disciplina

Este curso tem nível introdutório e contempla uma coleção de problemas elementares e fundamentais na área. Apesar disso, é normal fazer confusões e sentir-se perdido no início. O motivo é, em geral, a falta de familiaridade com formalismo matemático e raciocínio algorítmico -– algo que o curso pretende reverter.

  • Refaça os exemplos fornecidos em sala de aula e re-prove os principais resultados.
  • Preste atenção ao processo de solução e não foque somente no resultado final.
  • Assista às aulas (vídeos) e resolva os exercícios propostos durante as mesmas e os contidos nas listas (não somente os para entrega).
  • Estude a bibliografia indicada (monte grupos de estudo online) e faça um bom uso dos horários de atendimento.
  • Tenha sempre em mente que aprendizado é uma tarefa ativa; não fique somente assistindo.
  • Se ainda estiver se sentindo perdido, repita os passos acima. Mais cedo ou mais tarde, eles convergirão à compreensão.

Integridade acadêmica e transgressões

O Artigo 25 do Código de Ética da UFABC estabelece, à página 23: “Quanto aos trabalhos acadêmicos, é eticamente inaceitável que os discentes:

  • I - fraudem avaliações;
  • II - fabriquem ou falsifiquem dados;
  • III - plageiem ou não creditem devidamente autoria;
  • IV - aceitem autoria de material acadêmico sem participação na produção;
  • V - vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.”

Trabalhos (listas, provas, programas) suspeitos de cópia ou de outra representação fraudulenta acarretarão aos envolvidos conceitos $\mathbf{F}$ (falha) no curso. A atividade será reportada à Comissão Disciplinar Discente da universidade para que sejam tomadas todas as providências disciplinares cabíveis.

  • S00 – Expediente. Introdução.
    ([LLM] 0; [KT] 1.1 - 1.8)
  • S01 – Fragmentos de Lógica Proposicional.
    ([LLM] 1.1, 3.1 - 3.5, 1.5 - 1.9; [Ros] 1.1 - 1.3; [Gri] 2.1 - 2.2)
  • S02 – Predicados. Conjuntos. Sequências. Provas.
    ([LLM] 1.2, 3.6, 4.1 - 4.2; [KT] A.2 - A.3; [Ros] 1.4 - 1.5, 2.1 - 2.2, 1.7; [Gri] 2.3 - 2.5, 3.1 - 3.2)
  • S03 – Contagem. Permutações. Seleções.
    ([LLM] 15.1 - 15.6, 15.10; [KT] 2.1 - 2.8; [Ros] 6.1, 6.3 - 6.5; [Gri] 1.1 - 1.4)
  • S04 – Indução.
    ([LLM] 2, 5, 7; [KT] 3; [Ros] 5; [Gri] 4)
  • S05 – Princípios da Casa do Pombo e de Inclusão-Exclusão.
    ([LLM] 15.8 - 15.9; [KT] 4.1, 7; [Ros] 6.2, 8.5 - 8.6; [Gri] 5.5, 8)
  • S06 – Funções Geradoras.
    ([LLM] 16; [KT] 8; [Ros] 8.4; [Gri] 9)
  • S07 – Recorrências.
    ([LLM] 22; [KT] 9; [Ros] 8.1 - 8.3; [Gri] 10)
Avatar
Aritanan Gruber
Assistant Professor

“See, if y’all haven’t the same feeling for this, I really don’t give a damn. If you ain’t feeling it, then dammit this ain’t for you!"
(desconheço a autoria; agradeço a indicação)