Marcelino Pequeno
Avisos importantes:
Notas aqui.
Turma A - Profa Cláudia
Turma B - Prof. Marcelino
Boas noticias !!!!! Temos dois monitores !!! Ver informações detalhadas em atendimento .
Horário, Local, Atendimento, Objetivos, Ementa, Pré-requisito, Avaliação (provas e listas de exercícios), Livro-texto e Bibliografia adicional, Programa.
Turma A:
Segunda, Quarta e Sexta, 10:00h - 12:00h
Turma
B: Segunda, Quarta e Sexta, 14:00h -
16:00h
Turma A: Campus do Pici,
Bloco 950, Sala 2004.
Turma B:
Campus do Pici ,Bloco 919, Sala 5.
Os monitores dessa disciplina são dois: Ana Shirley e Robledo.
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
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 - Turma A
:AP1: 18/04/2001
AP2: 04/06/2001
AP3: 29/06/2001
Prova Final: 05/07/2001
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 20/04/2001
lista 3 (arquivo
postscript): Entrega em 25/04/2000
lista 4 (arquivo
postscript) : Entrega em 04/06/2001
lista 5 (arquivo postscript) : Entrega em 06/06/2001
lista 6 (arquivo postscript) : Entrega em 29/07/2001
Listas de Exercícios e Datas de entrega para a Turma B:
Bibliografia Básica (por ordem de uso) :
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.
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