Avisos importantes:
Ausências previstas da Profa. Cláudia: 27, 29 e 31 de março; 10, 12 e 14 de abril e 17 e 19 de maio.
Ausências previstas da Profa. Ana Teresa: 8, 10 e 12 de maio.
A lista de exercícios 6 das turmas A e B estão disponíveis. As datas de entrega já foram marcadas.
Horário, Local, Atendimento, Objetivos, Ementa, Pré-requisito, Avaliação (provas e listas de exercícios), Livro-texto e Bibliografia adicional, Programa.
Segunda, Quarta e Sexta, 14:00h - 16:00h
Turma A: Auditório da Matemática. Campus do Pici.
Turma B: Bloco 919 - Sala 1.
Nas salas das professoras, em qualquer horário, desde
que com reserva antecipada. Uma reserva pode ser feita via correio
eletrônico ou na sala de aula.
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.
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.
Não há.
Critérios: a avaliação
será feita através de provas (três) e listas de
exercícios (seis) . O cálculo das notas será
feito em duas etapas: dada a média das provas (AP1 + AP2 +
AP3)/3, será acrescentado à média um décimo
(0,1) para cada lista de exercícios entregue em dia e hora
marcados.
Datas aproximadas das provas: AP1 :
03/05.
AP2: 05/06.
AP3: 28/06.
Prova Final: 05/07.
Listas de Exercícios e Datas de entrega para a Turma A:
lista 1 (arquivo postscript): Entrega em 22/03/2000
lista 2 (arquivo postscript): Entrega em 05/04/2000
lista 3 (arquivo postscript): Entrega em 03/05/2000
lista 4 (arquivo postscript) : Entrega em 26/05/2000
lista 5 (arquivo postscript) : Entrega em 05/06/2000
lista 6 (arquivo postscript) : Entrega em 28/06/2000
Listas de Exercícios e Datas de entrega para a Turma B:
lista 1 (arquivo .rtf): Entrega em 29/03/2000
lista 2 (arquivo postscript): Entrega em 10/04/2000
lista 3 (arquivo .rtf)
lista 4 (arquivo postscript) : Entrega conforme combinado em sala
lista 5 (arquivo postscript) : Entrega em 05/06/2000
lista 6 (arquivo postscript) : Entrega em 28/06/2000
Bibliografia Básica (por ordem de uso) :
Kelly, J. The Essence of Logic. The Essence of Computing Series. Prentice Hall. London.1997.
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.
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.
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
Operações
e Estruturas
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)
Teorema da Recursã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
Ana Teresa Martins e Cláudia Linhares Sales
DC/UFC
Campos do Pici, Bloco 910
60455-760 Fortaleza, CE
Brazil
{linhares, ana}@lia.ufc.br
http://www.lia.ufc.br/~linhares
http://www.lia.ufc.br/~ana
+55 85 288-9841 (voice/fax)
+55 85 288-9847 (voice)
Updated on March 2000