[atualizado em 09/05]

Matemática Discreta 2023 - 1

Professor Jair Donadelli --- email jair.donadelli 'arroba' ufabc. ...

Matemática discreta (porém, exuberante) expõe o aluno aos princípios, técnicas e metodologias associadas a problemas em estruturas matemáticas discretas, cujo domínio é enumerável (finito ou infinito). Nesta disciplina, em particular, dá-se ênfase a princípios de indução, relações e princípios de contagem e combinatórios.

Se está matriculado, atente para seu email institucional.

O horário semanal é terça das 08:00 às 10:00, sala A-108-0, sexta das 10:00 às 12:00, sala A-108- 0.

Disciplina prévia recomendada: Funções de uma variável T-P-I: 4-0-4

ÍNDICE:

Matemática Discreta 2023 - 1Programação da disciplinaEmentaObjetivos Bibliografia básicaCronogramaBibliografia complementarAtendimentoAvaliaçãoDatasSubstitutiva RecuperaçãoLinks

Programação da disciplina

Ementa

Teoria intuitiva dos conjuntos. Relações: relações de equivalência, relações de ordem. Funções. Cardinalidade. Técnicas de demonstração: prova direta, prova por contradição. Indução. 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.

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.

Bibliografia básica

GRIMALDI, R.P., Discrete and combinatorial mathematics : an applied introduction. [510 GRIMdi5]
ROSEN, K.H. Matemática discreta e suas aplicações. 6ªEdição [510 ROSEma6]

Cronograma

Semana	Tema	Tópicos	Atividades
01	Introdução à lógica	Lógica informal: proposicão, valor-lógico, conectivo lógicos, equivalência logica, implicação lógica. Variáveis, predicados, quantificadores. Conjunto de modo intuitivo, pertinência, inclusão, operações. slides da semana	Leitura: - Seções 1.1 a 1.5, 2.1 a 2.3 de [Rosen 6ªed] ou Cap 2 de [Grimaldi]. - Notas aula Lista de Exercícios: (Rosen 6ªed.)§1.1: 9,13,19,31,42,43, 45,49; §1.3: 7,15,17,21,25,39,52,53; §1.4: 3,1,13,25,30,31,39,47; §1.2: 7,9,18,28,41,57; §1.5: 11,13,15,17,19,23,25,34,35. §2.1 3,5-9,15,21,23,27,35,37; §2.2 5-13,23,29,32,35,45,47,57; §2.3 1,5,18,19,25,67
02	Introdução à Teoria de Conjuntos	Conjuntos de modo axiomático-informal. Par ordenado e produto cartesiano: definição a partir dos axiomas. Relação Relações binárias e as classificações. slides da semana	Leitura: - Seções 8.1, 8.2 de [Rosen 6ªed] ou 3.1,3.2,5.1,5.2,7.1 de [Grimaldi]. - Notas aula (mesmo link da semana anterior) Lista de Exercícios (Rosen,6ªed) §8.1:1,5,23,25,33,35. Exercícios das notas de aula.
03	Relações	Relações de equivalência.	Leitura: - Seções 8.5 de [Rosen 6ªed] ou 7.4 de [Grimaldi]. - Notas aula Lista de Exercícios: 1, 3, 11, 17, 31, 33, 35, 43, 59,68 do Rosen; exercícios das notas de aula.
04	Relações	Relações de ordem. Ordens parciais, totais e boa ordem.	Leitura: - Seções 8.6 de [Rosen 6ªed] ou 7.3 de [Grimaldi]. - Notas aula (mesmo link da semana anterior) Lista de Exercícios: 1,12,13,15,23,33,53,54,55,56,57,60,65 do Rosen; exercícios das notas de aula.
05	Indução estrutural	Indução em conjuntos bem ordenados. Relações bem fundadas e indução bem fundada.	Leitura: - Seções 4.3 de [Rosen 6ªed] ; - Notas aula (mesmo link da semana anterior) Lista de Exercícios: 27, 29, 33, 34, 35, 41,43,44,45,46,36, 48, 50, 51, 56 da seção 4.3 do Rosen; exercícios das notas de aula.
06	Revisão de Indução	Princípios de Indução Finita: indução nos naturais e em conjuntos de inteiros limitados inferiormente, indução passo k, indução com passo pra trás. Equivalência entre princípios. Demonstrações usando indução. slides da semana	Leitura: - Seções 4.1-4.3 de [Rosen 6ªed]; - Notas aula Lista de Exercícios: 9,11,14,19,29,35,39,41,47--49,53,59 de §4.1 de [Rosen 6ªed] 3,11,17,23,24,25,27,29--32,36 de §4.2 de [2] 3,5,12,13,23 de §4.3 de [Rosen 6ªed]
07	Avaliação	P1[pdf]	NOTAS
08	Contagem	Bijeções, cardinalidade, conjuntos finitos, enumeráveis e infinitos. Princípio das gavetas (ou casa dos pombos). Princípios aditivo e multiplicativo.	Leitura: - 1.1, 3.3, 5.5 e Ap. 3 de [Grimaldi]; final da seção 2.4, 5.1 e 5.2 de [Rosen]; - Notas de aula Exerc.: 31,33,37,42,45,47 de §2.4 de [Rosen]; 21,29,33,35,37,39,41, 45 de §5.1 de [Rosen]; o máximo que conseguir de §5.2 de [Rosen]
09	Contagem	Bijeções, cardinalidade, conjuntos finitos, enumeráveis e infinitos. Princípio das gavetas (ou casa dos pombos). Princípios aditivo e multiplicativo.	IDEM
10	Combinatória	Combinação, arranjo, permutação. Solução inteira de equações. Inclusão--exclusão; binômio de Newton; coeficiente multinomial; relações de equivalência, classe de equivalência e contagem.	leitura: Cap 1 de [Grimaldi], Cap 5 de [Rosen]. lista de exercícios.: 3,7,11,19,23,29,35,43,44 de §5.3 de [Rosen] ; 9, 11, 13, 15, 17, 21, 27, 31, 37 de §5.4 de [Rosen]. 7,15,21, 23,30,31, 39, 42, 49,50,53,63 de §5.5 de [Rosen] Notas de aula (inclui as semanas passadas, revista)
11	Combinatória	IDEM	IDEM
12	Avaliação	P2	NOTAS
13	Avaliação	Prova substitutiva
14	Avaliação	Exame recuperação

Bibliografia complementar

Matosek, J. e Nesetril, J.I. An Invitation to Discrete Mathematics [510 MATOin2]
Velleman, Daniel J How to prove it : a structured approach 2. ed. [511.3 VELh2]
Mitchel T. Keller e William T. Trotter Applied Combinatorics [aqui]
Halmos, Paul R. Teoria ingênua dos conjuntos [511.322HALt]
Ronald L Graham; Donald E Knuth; Oren Patashnik.Matemática concreta 2. ed. [510 GRAHma2]

R. Bianconi, Como ler e estudar matemática?

Fernando Q. Gouvêa e Shai Simonson, How to Read Mathematics (uma tradução "rápida e grosseira", segundo o tradutor, aqui).

Atendimento

5ªs 14H15-15h00 na 546-2 bloco A

6ªs depois da aula até 13h15 na própria sala

Avaliação

2 provas presenciais e teste no moodle. As avaliações são individuais. Os critérios de avaliação nas provas incluem

Apresentação clara, legível, discursiva, uniforme e objetiva.
Construção correta e em ordem dos argumentos.
Atendimento às normas de correção ortográfica e gramatical.
Observância às orientações específicas da atividade e aos prazos de entrega quando for o caso.

Serão atribuídas notas de 0 a 100 nas atividades avaliativas e o resultado é definido como segue:

M $\cdot$ $\cdot$ (média dos testes)

M	Conceito final
$<$ Nota	A
$<$ $\leq$ 85	B
$<$ $\leq$ 70	C
$<$ $\leq$ 50	D
$\leq$ 45	F

Datas

P1 – 21/03

P2 – 25/04

Sub – 04/05 (atenção, uma quinta-feira, horário de reposição, 08h00)

Rec - 09/05 (atenção, uma terça-feira, horário de reposição)

Substitutiva

O aluno que perder uma prova por razão justificada de acordo com o regimento da UFABC deve manifestar o interesse em realizar uma prova substitutiva no prazo especificado pelo professor.

Recuperação

Tem direito a exame recuperação, que engloba todo o conteúdo da disciplina, aqueles que foram aprovado com D ou reprovado com F e obtiveram frequência mínima. O resultado do exame é um conceito que compõe com o conceito M obtido nas avaliação regular da disciplina como segue:

O aluno deve manifestar interesse em fazer a recuperação.