Criada: 2012-07-27
Após uma breve revisão de tópicos vistos em disciplinas anteriores, entraremos no estudo aprofundado de grafos e de diversos algoritmos importantes para resolver problemas em grafos. A seguir, definiremos precisamente os problemas que podem ser resolvidos em tempo polinomial, primeiro com algoritmos determinísticos (P) e depois com algoritmos não-determinísticos (NP). A questão de saber se estas duas classes são iguais (P = NP ?) é uma das mais intrigantes e importantes da computação moderna.
Os alunos serão avaliados através de provas individuais, de trabalhos de programação, e por sua participação em aula. Para manter os alunos sempre em dia com a matéria, haverá exercícios em cada aula sobre a aula anterior.
Utilizaremos o software LEMON, uma biblioteca para manipular grafos em C++, e também conceitos de Jackson Structured Programming, ideais para programar "no pequeno".
© 2012 João Meidanis