Graduação em Computação
DC - UFC

Matemática Discreta

Cláudia Linhares Sales

• Ausências previstas da Profa. Cláudia: 12 a 23 de março.
• PRIMEIRA AVALIACAO PARCIAL em 18/04/2001 !!!!!!! ESTUDE !
• Turma A - Profa Cláudia
• Turma B - Prof. Marcelino
•  Boas noticias !!!!! Temos dois monitores !!! Ver informações detalhadas em  atendimento .

Informações nesta página:

Horário:

Local:

Atendimento:

A Ana Shirley atenderá às  segundas e sextas a partir da 16h, na sala do PET.  Uma mensagem eletrônica pode ser enviada para ela  aqui .

O Robledo atenderá, todos os dias com exceção das quartas, de 12h as 16h, na sala do PET.  Uma mensagem eletrônica pode ser enviada para ele  aqui .
.
Para contactar os professores,  faça uma reserva via  correio eletrônico, com a   Profa Cláudia  ou com o  Prof. Marcelino

 

Objetivos:

 Compreender conceitos matemáticos fundamentais às disciplinas da computação;
 Saber demonstrar teoremas usando estratégias de prova como o princípio da indução, princípio da diagonalização, redução ao absurdo, entre outros.
Aprender noções básicas sobre teoria dos conjuntos, permutações, combinações, probabilidade discreta, grafos e relações de recorrência.

Ementa:

A Matemática Discreta é talvez o braço da matemática que possui a maior interseção com a Ciência da Computação. Daí a importância do estudo de elementos dessa disciplina. A ementa do curso é:

Notação, definições e Introdução a Lógica Matemática.
Teoria dos Conjuntos:  axiomas, operações elementares, relações, funções, ordenação, números naturais, conjuntos contáveis e incontáveis.
Métodos de Enumeração: permutação, combinação e probabilidade discreta.
Grafos: terminologia básica, classes de grafos, grafos ponderados e orientados, ciclos e circuitos, árvores.


Recorrência: relações de recorrência e algoritmos recursivos.

Pré-requisito:

Avaliação:

Datas aproximadas das provas - Turma A : AP1:  18/04/2001
                                                                          AP2:  a divulgar
                                                                          AP3:  a divulgar
                                                                          Prova Final:  a divulgar
 

Listas de Exercícios e Datas de entrega para a Turma A:

lista 1 (arquivo postscript):  Entrega em 28/03/2001
lista 2 (arquivo postscript):  Entrega em 18/04/2001

Livro-texto:

 
Hrbacek, K. & Jech, T. Introduction to Set Theory.  Marcel Dekker, INC. New York, 1984.
Liu, C.L. Elements of Discrete Mathematics. McGraw-Hill Computer Science Series, New York, 1985. 2nd edition.
Diestel, R. , Graph Theory, Springer-Verlag New York, Inc.  1997.
Kelly, J.  The Essence of Logic. The Essence of Computing Series. Prentice Hall. London.1997.

Bibliografia adicional:

H. R. Lewis and C. H. Papadimitriou, Elements of The Theory of Computation , Prentice-Hall International Editions, 1981.
Herbert B. Enderton, Elements of Set Theory, Academic Press College Division, 1977.
Kleene, S. C.  Introduction to Metamathematics. Van Nostrand, Princeton, 1952.
Di Prisco, C.A.  Uma Introducción a la Teoría de Conjuntos y los fundamentos de las matemáticas. Colição CLE, V.20. 1997.


Halmos, P.R. Teoria Ingênua dos Conjuntos. Editora Polígono. São Paulo. 1970.
 

1.   Preliminares
      Lógica Proposicional: Linguagem (fórmulas), Tabelas Verdade
      Conceitos Básicos:  Satisfação, Tautologia, Contradição, Equivalências, Conseqüência Lógica
      Lógica de Predicados: Linguagem (termos e fórmulas)
      Noções Básicas de Prova: Condicionais, Redução ao Absurdo, Generalização, Especialização

2.   Conjuntos
      Introdução
      Propriedades
      Os Axiomas
      Operações Elementares

3.   Relações, Funções e Ordenação
      Pares Ordenados
      Relações
      Equivalências e Partições
      Ordenação
      Reticulados e Cadeias
      Funções
      Princípio da Casa dos Pombos

4.   Números Naturais
      Construção dos Números Naturais como Conjuntos
      Construção dos Números Naturais como Função: Axiomas de Peano (Princípio da Indução)

5.   Conjuntos Contáveis e Incontáveis
      Cardinalidade dos Conjuntos: Princípio da Inclusão e Exclusão
      Conjuntos Finitos
      Conjuntos Contáveis
      Conjuntos Incontáveis: Princípio da Diagonalização

6.   Permutações, Combinações e Probabilidade Discreta
      Regras da Soma e Produto
      Permutações
      Combinações
      Probabilidade Discreta

7.   Grafos e Árvores
       Terminologia Básica:  adjacência, incidência, matrizes de incidência e adjacência, subgrafos, subgrafos
                 geradores e induzidos por vértices e arestas, grau de vértices, grau máximo e mínimo do  grafo,
                 complemento de  um grafo.
       Classes de grafos: grafo vazio, grafo trivial, grafos regulares, grafos bipartites, grafos completos.
       Multi-grafos e grafos ponderados
       Caminhos e Circuitos: passeio, trilha, caminhos, ciclos hamiltonianos e eulerianos, grafos conexos,
                   componentes, grafos desconexos
       Árvores: terminologia, caracterização de árvores

8.   Relações de Recorrência
      Relações de Recorrência:  métodos iterativo e de substituição
      Algorítmos Recursivos

Cláudia Linhares Sales e Marcelino Pequeno
DC/UFC
Campos do Pici, Bloco 910
60455-760 Fortaleza, CE
Brazil

{linhares, marcelino}@lia.ufc.br
http://www.lia.ufc.br/~linhares
 

+55 85 288-9841 (voice/fax)
+55 85 288-9847 (voice)

Updated on March 2001