MCTB019 -- Matemática Discreta -- 2023.1

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

Expediente

• Professor: Aritanan Gruber
• Aulas: Ter 19–21h @ S.206-0, Sex 21–23h @ A.108-0
• Atendimento: Ter e Sex 18–19h @ S.539-2
• Moodle: MD23.1 (N) <= Turma A1N (SA)

Ementa

Elementos de lógica clássica de primeira ordem. Teoria intuitiva dos conjuntos. Relações e grafos. Relações de equivalência. Relações de ordem. Funções. Técnicas de demonstração: prova direta, prova por contradição. Indução finita. Relações de recorrência. Cardinalidade: conjuntos finitos e infinitos; conjuntos enumeráveis e não enumeráveis. Princípios de contagem e combinatória. Princípio de inclusão e exclusão. Princípio das casas dos pombos.

Recomendação: Funções de Uma Variável

Objetivos

Utilizar a linguagem da lógica de primeira ordem. Compreender diferentes tipos de relações. Construir demonstrações com uso de notação adequada e argumentação logicamente fundamentada. Entender a necessidade do rigor formal ao se argumentar. Desenvolver, em particular, a capacidade de elaborar provas indutivas. Interpretar problemas de contagem em termos matemáticos. Aplicar técnicas de combinatória básica. Conhecer noções de cardinalidade em geral. Reconhecer as diferenças entre estruturas discretas e contínuas.

Avaliações e critérios

• 2 listas de exercícios, cada uma valendo $10\%$ na nota nominal; entrega via Moodle

Lista	Data		Lista	Data
$L_1$	14/03		$L_2$	28/04

• 2 provas $P_1$ e $P_2$ presenciais e uma substitutiva $P_3$ aberta
  serão escolhidas as 2 melhores dentre as 3 provas, cada qual valendo $40\%$ na nota nominal

Prova	Data		Prova	Data		Prova	Data
$P_1$	17/03		$P_2$	04/05		$P_3$	09/05

Nota nominal: $0.4$ vezes a média aritmética das 2 melhores dentre as 3 provas mais $0.1$ vezes a média aritmética das listas $$ N = \frac{4}{10}\max\left\{\sum_{j\in S}P_j\,:\,S\in\binom{[3]}{2}\right\} + \frac{1}{10}\big(L_1+L_2\big) $$

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 $P_R$ de recuperação – única e contempla 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

Primária

• [Gri] R. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th ed., Pearson Addison-Wesley (2004)
• [Ros] K. Rosen, Discrete Mathematics and its Applications, 8th ed., McGraw Hill (2019)

Secundária

• [Bon] M. Boná, A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, 4th ed., World Scientific (2017)
• [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.
• [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))
• [MN] J. Matousek, J. Nesetril, Invitation to Discrete Mathematics, 2nd ed., Oxford University Press (2008)

Páginas úteis

• Curso OCW-MIT: Mathematics for Computer Science
• Página de Matemática Discreta de Jair Donadelli, UFABC

Lista/Tentativa de tópicos por semana

Detalhes de cada tópico (coberto nas aulas) serão atualizados no Moodle ao longo do quadrimestre.

Estudando para esta disciplina

Este curso tem nível introdutório e contempla uma coleção de técnicas e problemas fundamentais na área. Alguns alunos fazem confusões e ficam confusos no início. Os motivos, em geral, são: a falta de familiaridade com formalismo matemático e raciocínio algorítmico, uma atitude passiva com relação ao aprendizado, e tempo dedicado insuficiente. Alguns procedimentos que costumam funcionar para mitigar os motivos relacionados:

• Refaça os exemplos e re-prove os resultados fornecidos em sala de aula.
• Preste atenção aos processos de solução (aprenda-os!) e não foque somente nos resultados finais.
• Assista ativamente às aulas; resolva os exercícios nelas propostos e os contidos nas listas.
• Estude a bibliografia indicada, monte grupos de estudo, 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. “Ouvir” às aulas e “ler” os livros tem pouco ou nenhum efeito neste curso – e em qualquer disciplina matemática/algorítmica que o valha.
• Se ainda assim, sentir-se perdido, repita os passos acima. Mais cedo ou mais tarde, eles convergirão à compreensão.

Note que você não será convidado a regurgitar respostas fornecidas em aula ou presente nos livros. As questões em listas e provas testarão sua capacidade de entender os problemas e apresentar uma solução para eles; às vezes, serão uma adaptação simples ou uma extensão direta do que foi visto, outras, será necessário relacionar dois ou mais métodos ou conceitos apresentados, e outras ainda, irão requerer análise e raciocínio mais profundo (o que leva tempo, então não deixe nada para a última hora!).

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.

ChatGPT e similares

Antes de mais nada, representam um grande avanço no processamento automático de corpos linguísticos e são, sem sombra de dúvidas, resultados estupendos! [ Mais considerações sobre isso na primeira aula. ]

Dito isso, soluções entregues que tenham sido fornecidas por eles enquadram-se no Artigo 25 acima.

Para pensar ao longo do curso: Do que adianta as máquinas aprenderem e os alunos não?