Ementa:

Conceitos básicos de matemática discreta e de lógica para computação. Técnicas de provas, indução matemática. Relações e conceitos de teoria de grafos.

Programa:

Conteúdo

A seguinte relação de tópicos segue a numeração das seções da referência [1] abaixo que é recomendada como livro texto:

Tópicos de cobertura obrigatória:

1.1 Lógica

1.2 Equivalências Proposicionais

1.3 Predicados e Quantificadores

1.4 Quantificadores encaixados

1.5 Métodos de Provas

1.6 Conjuntos

1.7 Operações em conjuntos

1.8 Funções

3.1 Estratégias de Provas

3.2 Cardinalidade

3.2 Sequências e Somatórios

3.3 Indução Matemática

5.1 Introdução a Probabilidade

5.2 Teoria de Probabilidade

5.3 Valor esperado e Variância

7.1 Relações e suas propriedade

7.2 Relações n-árias e suas aplicações

7.3 Representação de Relações

7.4 Fecho de relações

7.5 Relações de Equivalência

8.1 Introdução a Grafos

8.2 Terminologia de grafos

8.3 Representação de grafos e isomorfismo

8.4 Conectividade

8.5 Caminhos Eulerianos e Hamiltonianos

8.7 Grafos Planares

8.8 Coloração de Grafos

 

Tópicos opcionais à escolha do docente:

4.1 Noções básicas de contagem

4.2 O Princípio da Casa do Pombo

6.4 Funções Geradoras

6.5 Inclusão-exclusão

6.6 Aplicações de Inclusão-exclusão

11.1 Linguagens e gramáticas

11.2 Máquinas de estado-finito com saída

11.3 Máquinas de estado-finito sem saída

11.4 Reconhecimento de linguagens

11.5 Máquinas de Turing

 

Bibliografia:

 

1.  [Livro-texto] K. H. Rosen, Discrete Mathematics and its applications. 5a. Edição,  

     McGraw-Hill, (2003).

2.    J. P. O. Santos, M. P. Mello e I. T. C. Murari, Introdução à análise

    combinatória. Editora da UNICAMP, Campinas (1998).

3.    U. Manber, Algorithms: A Creative Approach, Addison-Wesley (1989).

4.    J. L. Gersting, Fundamentos Matemáticos para a Ciência da Computação. 4a.

     edição, LTC Editora, Rio de Janeiro (2001).