Técnicas de Busca e Ordenação

Raul H.C.Lopes 8 de Dezembro de 2003

1 Programa

O curso será organizado em torno de três exercícios fundamentais, que servirão de temas para os trabalhos práticos:

• Pesquisa em bases estruturadas

• Pesquisa em textos

• Pesquisa em grafos Para cada um desses temas serão estudadas estruturas e algoritmos seguindo

a ementa:

1. Ordenação

2. Árvores como estruturas de indexação

3. Árvores de prioridade

4. Representação de conjuntos

5. Pesquisa em string

6. Pesquisa em grafos Cada algoritmo estudado será abordado do ponto-de-vista de correção e

análise de complexidade.

1. Correção de programas • A metodologia Floyd-Dijkstra-Hoare

• Propriedade invariante e correção parcial de programas • Variável derivada e término de programas

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

• Recorrências e somas

• Análise de melhor e pior caso

• Análise de caso médio

2 Referências básicas

O seguinte conjunto de referências será usado ao longo do curso. Obviamente, serão abordados alguns tópicos de cada uma delas. De qualquer forma, qualquer aluno que leve a sério sua formação em Ciência da Computação deve considerar cedo ou tarde a aquisição, pelo menos, dos três primeiros.

• 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

• Concrete Mathematics R.L.Graham,D.E. Knuth, O. Patashnik

• An Introduction to Combinatorial Analysis J. Riordan

• The Science of Programming D. Gries

Além disso, artigos e notas de aula serão indicados ao longo do curso.

3 Regras de Avaliação

Este será certamente um de seus cursos mais trabalhosos, o que não significa que será difícil.^{1}

A nota final será dada pela média aritmética das notas dos trabalhos e provas. Estará aprovado quem obtiver média igual ou superior a 7. Alunos que obtenham média igual ou superior a 6 e tenham aproveitamento de, pelo menos, 50% nas provas e nos trabalhos também estarão aprovados. Aos outros restará o limbo da prova final, do qual só Dante voltou.

3.1 Datas das Provas

1. Prova 0: 22/12/03

2. Prova 1: 03/03/04

3. Prova 2: 14/04/04

3.2 Datas dos Trabalhos

• Trabalho 0 – especificação: 17/12/03 – entrega: 30/01/04

• Trabalho 1 – especificação: 02/02/04 – entrega: 05/03/04

• Trabalho 2 – especificação: 01/03/04 – entrega: 16/04/04

1Na verdade, se você se dedicar desde o primeiro dia, acabará descobrindo que a fama de carrasco do Senhor do Castelo está acima de tudo relacionada ao fracasso de um monte de incompetentes e preguiçosos que o pedagogismo reinante neste departamento insiste em parir todos os anos. Alunos com potencial excelente são desperdiçado por supostos pedagogos e tios preguiçosos que não cobram para não ser cobrados.