Curso: Ciência da Computação, DOURADOS, Integral (2018) - 3a Série
Professor: CLEBER VALGAS GOMES MIRA
Disciplina: Teoria dos Grafos
Carga Horária: 68 h Período Letivo: 01/2018 a 12/2018
Ementa:
Conceitos básicos de grafos, Isomorfismo, Árvores, Árvore Geradora Mínima, Conexidade, Trilhas Eulerianas, Circuitos Hamiltonianos, Emparelhamentos, Conjuntos independentes e cliques, Coloração de vértices e arestas, Planaridade, Representação Computacional e Algoritmos em Grafos.
Objetivos:
- Apresentar a Teoria dos Grafos através de uma visão dos seus principais aspectos teóricos.
- Exercitar os diversos métodos de demonstração.
- Ressaltar a aplicabilidade de grafos na modelagem de problemas.
- Apresentar as estruturas de dados e soluções algorítmicas para tais problemas.
Conteúdo:
Metodologia:
As aulas serão ministradas em sala com o uso do datashow, giz e quadro branco. Serão propostas listas de exercícios para o acompanhamento do conteúdo teórico de sala de aula.
Bibliografia Básica:
CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Algoritmos: Teoria e Prática. Campus, 2002.
BONDY, J. A.; MURTY, U. S. R. Graph Theory with Applications. Elsevier, 1976.
GAREY, M. R.; JOHNSON, D. S. Computer and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
MANBER, U. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
WEST, F. Introduction to Graph Theory. Prentice Hall, 3nd, 2007.
Bibliografia Complementar:
DIESTEL, R. Graph Theory. Springer-Verlag, 4nd, 2010.
GERSTING J. L. Fundamentos Matemáticos para a Ciência da Computação. LTC, 5a Ed., 2004.
LUCCHESI, C. L.; et al. Aspectos Teóricos da Computação, Parte C: Teoria dos Grafos. IMPA, Projeto Euclides, 1979.
NETTO, P. O. B. Grafos: teoria, modelos e algoritmos, Edgard Blücher, 4nd, 2006.
SZWARCFITER, J. L. Grafos e Algoritmos Computacionais, Campus, 1988.
WILSON, R. J. Introduction to Graph Theory. Addison-Wesley, 4nd, 1996.
Critérios de Avaliação:
Serão efetuadas 4 provas. As prováveis datas das provas são:
P1: 26/04
P2: 5/07
P3: 27/09
P4: 22/11
SUBSTITUTIVA 29/11
EXAME 6/12
A média final (MF) será computada pela fórmula:
MF = (P1 + P2 + P3 + P4) / 4, onde
P1, P2, P3 e P4 são as notas das respectivas provas com valor entre 0 e 10.
A prova substitutiva substitui a prova com menor nota dentre as P1, P2, P3 e P4, caso tenha um valor maior. A substitutiva tem valor entre 0 e 10,0 e o conteúdo é referente a toda a matéria.
A Nota Final (F) é calculada da seguinte maneira:
Caso o valor de MF do aluno for igual ou superior a 6,0, então a nota final é F = MF.
Caso o valor de MF do aluno for entre 3,0 e 6,0, o aluno terá direito a fazer o Exame Final (E) com valor entre 0 e 10 e a nota final será F = (MF + E)/2.
O aluno com nota de MF inferior a 3,0 é automaticamente reprovado.
O Exame Final cobrará o conteúdo de toda a matéria
Será aprovado o aluno cuja nota final F for igual ou superior a 5,0.