logo_uerj.gif (2426 bytes)

UERJ/IME 04-11311
Algoritmos em Grafos (Teoria dos Grafos)
Prof. Paulo Eustáquio

Ementa

Programa

Livro Texto | Bibliografia Adicional

Avaliação | Links

Período Atual (2017-2)

Demonstrações (trabalhos de alunos):

Ementa:

Introdução e motivação à Teoria dos Grafos, Classes principais de grafos, Algoritmos de reconhecimento, Conectividade, Árvores e Florestas, Planaridade, Conjuntos Independentes e Cliques, Coloração, Caminhos Eulerianos, Ciclos Hamiltonianos, Emparelhamentos, Coberturas. Teoria da intratabilidade de problemas. Classes P e NP. Método da Redução. Teorema da Satisfatibilidade. Problemas pseudo-polinomiais. Problemas NP-Completos. Algoritmos Randômicos e Aproximativos.

 

Programa:

Livro Texto:

Bibliografia Adicional:

Avaliação:

A avaliação constará de 2 provas (P1 e P2), pequenos trabalhos em casa (TC), em sala (TS), no Laboratório (LAB), extra (TE).

Nota  =  0.35(P1+P2) + 0.3TC + LAB + TS + TE

Trabalhos de casa são obrigatórios e individuais (em dupla quando forem programas) e só podem ser entregues até 1 mês após a data básica de entrega. Os trabalhos em sala, extra e no Laboratório somente aumentam a nota.

Última atualização: 04/04/2018


home
Home

topo
Topo