MAC228 -- Combinatória e Teoria dos Grafos - 2o. semestre de 2004

Informações Gerais

Ementa da disciplina

Permutações, combinações, identidades binomiais, aplicações em várias áreas. Princípio da inclusão-exclusão. Fórmulas de recorrência simples. Conceitos básicos em grafos: caminhos, circuitos, árvores, colorações. Algoritmos envolvendo caminhos, circuitos e árvores. Planaridade (idéias); fórmula de Euler. O Teorema das Quatro Cores. Noções da Teoria de Ramsey.

• L. Lovász, J. Pelikán and K. Vetsztergombi, Discrete Mathematics (Elmenatry and Beyond) , Springer, N. York, 2003.
• G. Berman, K.D. Fryer, Introduction to Combinatorics, Academic Press, 1972.
• J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, Macmillan, 1976.
• D.I.A. Cohen, Basic Techniques of Combinatorial Theory, John Wiley, 1978.
• R. L. Graham, D. E. Knuth , O. Patashnik. Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, Reading 1989. (Tradução para português por V. I. Magalhães, Matemática Concreta, Livros Técnicos e Científicos, Rio de Janeiro, 1995.)
• M. Hausner, Discrete Mathematics, Saunders College Publishing, 1992.
• C.L. Liu, Elements of Discrete Mathematics, McGraw-Hill, 1977.
• A. Tucker, Applied Combinatorics, John Wiley, 3rd. edition, 1995.
• R. Wilson, Introduction to Graph Theory, Academic Press, N.Y., 1972.

2a.f. das 19:20h às 21h; e 5a.f. das 21:10 às 22:50h -- Sala B-6 - IME.

• Duas provas: P1 no dia 14/outubro (5a.f) e P2 no dia 2/dezembro (5a.f))
• Listas de exercícios (devem ser entregues pontualmente)
• Trabalhos

• P = Média ponderada das provas
  P = (P1+2*P2)/3.
• L = Média aritmética das listas de exercícios
• T = Média dos trabalhos
• M = Média final
  se P >= 5.0 e L >= 5.0
  então M = (2*P+L+ p*T) / (3+p), onde 0 <= p <= 1 (a ser decidido)
  senão M = min{P, L, 4.5}.

• se M >= 5.0
  então "aprovado"
  senão se M >= 3.0
  então "vai para recuperação"
  senão "reprovado".