Home | Administração | Livros | WWW | Diário | Tarefas | Panda |
MAC5770 tem por objetivo introduzir o estudante de pós-graduação em Ciência da Computação aos problemas, aos métodos, e à linguagem da teoria dos grafos. Esta disciplina é útil em todas as áreas da computação. Ela é particularmente importante nas áreas de teoria da computação e otimização combinatória. MAC5770 é vulgarmente conhecida como "Grafinhos". A disciplina MAC5771, mais avançada, é conhecida como "Grafões". Teoria dos grafosA Teoria dos Grafos não é uma teoria: é uma coleção de problemas computacionais. Todos esses problemas são formulados sobre um objeto combinatório conhecido como grafo. Os problemas tornaram-se célebres porque ocorrem em diversas áreas da computação, da engenharia, e em muitas aplicações industriais. A preocupação central da teoria dos grafos é a busca por algoritmos eficientes que resolvam problemas sobre grafos. Mas nesta edição de MAC5770 nossa atitude será menos algorítmica (por exemplo, como encontrar um circuito hamiltoniano num grafo?) e mais estrutural (por exemplo, que tipos de grafos têm circuito hamiltoniano?). [Se você está interessado na implementação de algoritmos para grafos, veja minhas notas sobre análise de algoritmos e algoritmos em grafos.] |
Principais tópicos
Se houver tempo, trataremos também de grafos biconexos, grafos aleatórios, grafos orientados. Pré-requisitosMAC5770 não tem pré-requisitos oficiais. Convém entretanto que o aluno tenha familiaridade com
Alguma experiência de programação em C também é útil. |
AulasEu não gostaria que as aulas fossem meramente expositivas. Eu prefiro que elas sejam um laboratório de resolução de problemas. Para isso, preparei uma coleção de exercícios em formato PDF. Evite imprimir esse material em papel, pois ele será alterado e corrigido freqüentemente. É melhor ler os exercícios na tela do monitor. Use o Acrobat Reader para tirar proveito dos hyperlinks. |
TarefasVeja a página de tarefas |