Computação Científica 1  –  Módulo Introdução a Algoritmos 

2009/1  –  Maio de 2009

 

Apresentação: Introdução a Algoritmos é o segundo módulo dentro da disciplina Computação Científica 1 do Doutorado em Matemática Computacional da UFPE.

 

Conteúdo Programático: Neste módulo da disciplina discutiremos:

1.    Conceitos básicos: algoritmos, procedimentos, funções, scripts, tipos de linguagens, tipos e representação de dados, compilação, interpretação, complexidade de computação, notação assintótica. 

2.    Algoritmos em grafos – Busca, conectividade, árvore geradora de peso mínimo, distâncias, fluxo, problemas NP-completos (Clique, cobertura, etc.)

3.    Caracterização e abordagens para problemas NP-completos:  Heurísticas, branch-and-bound, aproximação e randomização.

 

Professor, Local e Hora

 

Bibliografia Básica em Livro Texto 

     Introduction to Algorithms

     T.H. Cormen, C.E. Leiserson e R. L. Rivest

     McGraw Hill, New York,  1990.

 

 

Programação das Aulas

Aula

Data

Assunto 

1

04/mai

Introdução a Algoritmos e Complexidade de Computação

2

0?/mai

Problemas lineares em grafos – Busca e Conectividade

3

0?/mai

Problemas polinomiais em Grafos – Árvore geradora e Caminhos mais curtos

4

0?/mai

Problema do Fluxo Máximo.  Teorema Max-Flow Min Cut.   Lista de Exercícios

5

0?/mai

Problemas NP-completos – Caracterização e Abordagens

6

0?/mai

Problemas NP-completos 

0?/mai

Avaliação do módulo Introdução a Algoritmos

 

[Última alteração em 04/05/2009 por katia.]

Página pessoal de Katia