Estruturas Discretas – TIN0109

Obrigatória – 60 horas – 4 créditos
Pré-requisitos: Introdução à Lógica Computacional
Professor Responsável: Alexandre Andreatta

Objetivos da Disciplina

Capacitar o aluno a definir os conceitos básicos de conjuntos, combinatória, relações, funções e teoria dos grafos; definir as principais formas de representação de grafos; definir os principais algoritmos para grafos; identificar as principais aplicações para grafos.

Ementa

Relações Binárias: Conceitos e Propriedades. Aritmética Modular. Noções de Teoria de grafos: isomorfismo, planaridade, coloração, conectividade, propriedades de árvores.

Conteúdo Programático

• Relações Binárias
  • Propriedades de Relações Binárias
  • Fechos de Relações
  • Ordens Parciais e Diagrama de Hasse
  • Relações de Equivalência e Partições
  • Equivalência módulo sobre os inteiros
  • Ordem de crescimento de funções – Notação assintótica.
• Divisibilidade, Aritmética Modular
• Grafos
  • Definições
  • Grafos Isomorfos
  • Grafos Planares e suas propriedades
  • Representação computacional de grafos
  • Coloração e número cromático
  • Conectividade
• Árvores
  • Definições e propriedades
  • Representações de árvores e árvores binárias
  • Algoritmo de Percurso em árvores
• Algoritmos para Grafos
  • Caminho de Euler e Circuito Hamiltoniano
  • Busca em Profundidade e em Nível (em Amplitude)
  • Algoritmos para Caminho Mínimo em grafos

Metodologia

A disciplina estará calcada em aulas expositivas de apresentação de conteúdo teórico, com a realização de exercícios ao longo das aulas.

Avaliação

São três provas constando dos assuntos ministrados.

Bibliografia

• KENNETH, R., Matematica Discreta e suas Aplicações. 6ª Ed., 2009.
• GERSTING, Judith L., Fundamentos Matemáticos para a Ciência da Computação. 5ª Ed., 2004.
• MENEZES, P., Matemática Discreta para Computação e Informática. 4ª Ed., 2013.
• CORMEN, Thomas H., et al., Capítulo 31: Algoritmos de Teoria dos Números, Algoritmos: Teoria e Prática. Rio de Janeiro: Elsevier, 2002.