Projeto e Análise de Algoritmos

Raul H.C.Lopes

7 de Janeiro de 2003

1 Programa

1. Correção de programas em ACL2 • Funções aritméticas

• Listas

• Ordenação

• Árvores

2. Análise de algoritmos • Crescimento de funções e notação assintótica

• Recorrências e somas

• Análise de pior caso e caso médio

3. Ordenação • inserção

• troca

• seleção

• distribuição

4. Permutaçoes • coeficientes binomiais

• funçoes geradoras

• permutações

5. Árvores • Binárias

• Red-Black

• B-trees

• Suffix trees and string matching

6. Heaps • heapsort

• árvores de prioridade

• heaps binomiais

7. busca geométrica e em grafos • range searching

• hulls

• árvores geradores

• caminho mais curto

8. Teoria NP

9. hash

2 Referências básicas

• Introduction to Algorithms T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein

• The Art of Computer Programming: Vol. I, III D.E. Knuth

• Analysis of Algorithms R. Sedgewick, P. Flajolet • Concrete Mathematics

R.L.Graham,D.E. Knuth, O. Patashnik

• An Introduction to Combinatorial Analysis

J. Riordan

• The Science of Programming

D. Gries

• A methodology of programming

E. W. Dijkstra and W.H.J. Feijen

• PVS em http://www.pvs.csl.sri.com

Manuais, tutoriais, artigos, provador.

• ACL2 em tools/acl2.tar.gz

Manuais, tutoriais, artigos, provador.

3 Regras de Avaliação

O processo de avaliação será realizado através de 2 provas (obrigatórias) e 4 trabalhos (opcionais) de implementação. Estão definidas duas linhas distintas de avaliação: teórica pura, mista.

3.1 Avaliação téorica em complexidade e correção de programas

O aluno pode optar por realizar dois trabalhos teóricos nas áreas de: correçao de programas, usando as ferramentas ACL2, PVS ou Coq, complexidade de algoritmos, exercício teórico, possivelmente, usando MuPAD ou Singular.

Estes trabalhos substituem as duas provas, isso significando que o aluno que optar por esta linha será avaliado exclusivamente pelos 2 trabalhos.

A nota final neste caso é dada pela média dos dois trabalhos.

3.2 Avaliação mista em complexidade e correção de

programas

O aluno que optar por esta linha de avaliação deverá realizar obrigatoriamente 2 provas. Além disso, poderá opcionalmente implementar até 4 trabalhos práticos.

A nota final será dada pela seguinte fórmula

\frac{((P_{0} + P_{1})/2) ∗ (10 − t) + ∑_{0≤i<t} T_{i}}{10}

onde:

• t(0 ≤ t < 5) é o número de trabalhos implementados pelo aluno;

• P_{0}, P_{1} são as notas das provas 0 e 1;

• T_{i}, são as notas dos trabalhos.

4 Datas das Provas

1. Prova 0 (a) Data: 05/02/03

2. Prova 1 (a) Data: 26/03/03

5 Trabalhos

Primeiro trabalho prático e primeiro trabalho teórico nesta página, no próximo dia 13/01.