Portal do Ementário

Ter familiaridade com a terminologia básica de funções, relações e conjuntos, assim como executar operações sobre essas construções, relacionando exemplos práticos ao modelo adequado e interpretando as operações associadas e terminologia no contexto. Ter familiaridade com os conceitos relacionados à cardinalidade de conjuntos, conjunto finito, infinito contável e incontável [Familiaridade]. Reconhecer e utilizar os operadores básicos da álgebra booleana. Construir tabelas-verdade [Familiaridade]. Identificar a técnica de prova utilizada em uma dada prova [Familiaridade]. Esboçar a estrutura básica de cada técnica de prova (direta, por contradição e por indução) [Uso]. Aplicar cada técnica de prova corretamente na construção de um argumento sólido [Uso]. Determinar qual tipo de prova é melhor para um dado problema [Avaliação]. Explicar os paralelos entre ideias de indução matemática ou indução estrutura em recursão e estruturas definidas recursivamente [Avaliação]. Explicar o relacionamento entre indução forte e fraca e dar exemplos do uso apropriado de cada [Avaliação]. Aplicar argumentos de contagem, incluindo regras de soma e produto, princípio da inclusão-exclusão e progressões aritméticas/geométricas [Uso]. Aplicar o princípio das casas de pombos no contexto de uma prova formal [Uso]. Calcular permutações e combinações de um conjunto e interpretar o significado no contexto de uma aplicação particular [Uso]. Mapear aplicações do mundo real em formalismos de contagem apropriados (ex.: determinar o número de formas de arranjar pessoas em uma mesa, sujeito a restrições no arranjo dos assentos) [Uso]. Resolver uma variedade de relações de recorrência básicas [Uso]. Analisar um problema para determinar relações de recorrência ocultas [Uso]. Realizar cálculos envolvendo aritmética modular [Uso]. Apresentar os conceitos básicos da teoria dos grafos, assim como algumas das propriedades e casos especiais de cada tipo de grafo/árvore [Familiaridade].

Conjuntos, relações e funções. Álgebra booleana. Técnicas de prova. Contagem. Introdução a grafos.

MENEZES, Paulo Blauth. Matemática discreta para computação e informática. 3. ed. Porto Alegre: Bookman, 2010. 350 p. (Série livros didáticos informática UFRGS ISBN 9788577806812      STEIN, Clifford; DRYSDALE, Robert L.; BOGART, Kenneth. Matemática discreta para ciência da computação. São Paulo, SP: Pearson, 2013. xxi, 394 p. ISBN 9788581437699 Gersting, Judith L. "Fundamentos Matemáticos Para a Ciência da Computação." 7a ed. Rio de Janeiro: Livros Técnicos e Científicos, 2017. ISBN 9788521632597.

ROSEN, K.  “Discrete Mathematics and Its Applications”. 7 ed. 2011. McGraw-Hill. ISBN 978-0073383095 GRAHAM, Ronald L.; KNUTH, Donald Ervin; PATASHNIK, Oren. “Matemática concreta: fundamentos para a ciência da computação”. 2. ed. Rio de Janeiro: Livros Técnicos e Científicos, 1995. 475 p. ISBN 9788521610403 (broch.) FARRER, Harry. Algoritmos estruturados. 3. ed. Rio de Janeiro: Livros Técnicos e Científicos, c1999. 284 p. (Programação estruturada de computadores) ISBN 8521611806 (broch.) CORMEN, Thomas H. et al. Introduction to algorithms. 3rd ed. Cambridge, Mass.: The MIT Press; New York: McGraw-Hill, 2009. xix,1292 p. ISBN 9780262533058 (broch.) BOAVENTURA NETTO, Paulo Oswaldo. Grafos: teoria, modelos, algoritmos. 5. ed. rev. ampl. São Paulo: Blucher, 2012. xiii, 311 p. ISBN 9788521206804 (broch.).