Projeto e Análise de Algoritmos

Apresentação da Disciplina

Edirlei Soares de Lima

<edirlei@iprj.uerj.br>

Objetivos da Disciplina

•

Examinar a teoria e a arte de resolver eficientemente problemas

computacionais.

–

Introduzir conceitos mais avançados de desenvolvimento de algoritmos;

Ensinar noções de complexidade em problemas computacionais;

Avaliar a eficiência computacional de algoritmos;

Comparar diferentes algoritmos para a solução de um mesmo problema;

Descrever e empregar os princípios, métodos e técnicas fundamentais

para o projeto de algoritmos corretos e eficientes.

Programa da Disciplina

1

2

. Introdução e Algoritmos de Processamento de Texto:

–

Eficiência de Algoritmos;

Algoritmo Boyer-Moore;

Tries;

Maior subsequência comum (LCS);

. Algoritmos de Ordenação:

–

Selection Sort e Insertion Sort;

Merge Sort;

Quick Sort;

Programa da Disciplina

3

. Algoritmos de Grafos:

–

Busca em Profundidade e Busca Largura;

Ordenação Topológica;

Componentes Fortemente Conectados;

•

Algoritmo de Kosaraju;

•

Algoritmo de Tarjan;

–

Árvores Geradoras Mínimas;

•

Algoritmo de Prim;

•

Algoritmo de Kruskal;

Distâncias Mínimas;

•

Algoritmo de Dijkstra

Critério de Avaliação

•

Avaliação Teórica:

–

Prova teórica envolvendo o conteúdo teórico e prático

apresentado durante as aulas;

Avaliação Prática:

–

Trabalhos e exercícios desenvolvidos em grupo ou

individualmente;

–

Apresentação em aula;

Critério de Avaliação

•

G1:

–

Prova: 7.0

–

Trabalhos e Exercícios: 3.0

G2:

–

Prova: 7.0

–

Trabalhos e Exercícios: 3.0

Media Final = (G1 + G2)/2

Pré-Requisitos

•

Programação

Algoritmos e Estruturas de Dados

Material das Aulas

•

Página do Curso:

–

www.inf.puc-rio.br/~elima/paa/

Contato:

–

edirlei@iprj.uerj.br

Bibliografia Principal

•

Cormen, Leiserson, Rivest e Stein.

Algoritmos – Teoria e Prática (tradução da

2

ª. Edição americana), Editora Campus,

002.

Dasgupta, Papadimitriou e Vazirani.

Algorithms, McGraw-Hill, 2006.