Matemática Discreta (MAD-0100)

Prof. Dr. Ricardo Luders

Obs.: A disciplina de Métodos Formais I (MF1-0032) a partir do COLETA 2009 passa a se chamar Matemática Discreta, código MAD0100, sem alterar a ementa.

Raciocínio matemático: métodos de prova, indução e recursividade; Conjuntos e funções: terminologia e operações, contagem e combinatória, notação assintótica; Relações: propriedades, ordem parcial e relações de equivalência; Grafos: terminologia, representação e isomorfismo, problemas clássicos e algoritmos; Modelos de computação: estruturas algébricas; Máquinas de estado finito, máquinas de Turing, linguagens formais.

Discrete Mathematics
Syllabus: Mathematical reasoning: methods of proof, mathematical induction and recursive definitions; Sets and functions: terminology and operations, counting and combinatorial analysis, asymptotic notation; Relations: properties, partial order and equivalence relations; Graphs: terminology, representation and isomorphism, classical problems and algorithms; Modeling computation: algebraic structures, finite-state machines, Turing machines, formal languages.

Bibliografia:

ROSEN, Kenneth H., Discrete Mathematics and Its Applications, 5th ed., McGraw-Hill, 2003.
MENEZES, Paulo B., Matemática Discreta para Computação e Informática, 1a. ed., Série Livros Didáticos-UFRGS, Editora Sagra Luzzatto, 2004.
LIPSHUTZ, S.; LIPSON, M., Teoria e Problemas de Matemática Discreta, Coleção Schaum, 2a. ed., Bookman, 2004.
GERSTING, Judith L., Fundamentos Matemáticos para Ciência da Computação, 5a. ed., Rio de Janeiro: LTC Editora, 2004.
HOPCROFT, J. E.; ULLMAN, J. D., Introduction to Automata Theory, Languages and Computation, 2nd ed., Addison-Wesley, 2000.
ROSS, K.; WRIGHT, C., Discrete Mathematics, 5th ed., Prentice-Hall, 2003.
SANTOS, J. P. O.; MELLO, M. P.; MURARI, I. T. C., Introdução à Análise Combinatória, 3a. ed., Editora da Unicamp, 2002.