Curso de Pós-graduação em Ciência da Computação
Projeto e Análise de Algoritmos

Última alteração: Outubro 29, 2002

Artigos dos Seminários Apresentados em 2002

Solução dos Trabalhos Práticos

• Trabalho Prático 1
• Solução 1
• Solução 2
• Trabalho Prático 2
• Solução 1
• Solução 2
• Trabalho Prático 3
• Solução 1
• Solução 2
• Trabalho Prático 4
• Solução 1
• Solução 2

1º semestre de 2002
Carga horária: 60 horas
Horario : Terça: 14:55 - 16:35, Quinta: 14:55 - 16:35, Sala: 2029
Professor: Nivio Ziviani (ICEx - Sala 4024)
Monitora: Claudine Santos Badue
Horário de monitoria: Segunda e Quinta, 13:00 - 14:00 horas, sala 3029

Objetivos da Disciplina

Apresentar um conjunto de técnicas de projeto e de análise de algoritmos, com ênfase em estruturas de dados e nos algoritmos relacionados. A comparação de alternativas é sempre feita utilizando-se técnicas de análise de algoritmos. Ao final do curso o aluno deverá ser capaz de lidar com classes específicas de problemas e soluções eficientes para eles, dominando as principais técnicas utilizadas para projetar e analisar algoritmos e sabendo decidir o que pode e o que não pode ser resolvido eficientemente pelo computador.

Ementa

Análise de algoritmos. Problemas -Completo. Limite inferior para diferentes classes de problemas. Algoritmos paralelos. Tópicos: algoritmos em grafos, algoritmos para casamento de padrão, compressão de dados.

Programa

Análise de Algoritmos

Medida de tempo de execução de programas: comportamento assintótico de funções, classes de comportamento assintótico; Técnicas de análise de algoritmos: somatórios, recorrências, árvores de decisão, limite inferior: oráculos, limite inferior para ordenação.

Problemas -Completo

Classes de complexidade: , e -Completo; Heurísticas; O que pode e o que não pode ser resolvido eficientemente por computadores.

Tópicos

Algoritmos em grafos; casamento de padrões com e sem pré-processamento; compressão de dados.

Algoritmos Paralelos

Modelos de computação paralela; Projeto de algoritmos paralelos; Ordenação; Pesquisa.

Bibliografia Básica

[FBY] Frakes, W. B. e Baeza-Yates (Eds) Information Retrieval Data Structures and Algorithms. Prentice Hall, 1992.

[HS] E. Horowitz e S. Sahni, Fundamentals of Computer Algorithms, Computer Science Press, 1978. O livro é bom em estruturas de dados, programação dinâmica, algoritmos branch-and-bound e na apresentação de problemas -Completo. Vamos utilizar o capítulo 11 do texto.

[Q] M. J. Quinn, Parallel Computing Theory and Practice, McGraw-Hill, 1994. É um bom livro sobre algoritmos paralelos. Vamos utilizar os capítulos 1. 2, 3, 5 e 6.

[Z] Ziviani, N. Projeto de Algoritmos Com Implementações em Pascal e C, Pioneira Thomson Learning, 1993. Vamos utilizar as seções 1.3 e 1.4 do texto.

Bibliografia Geral

[A74] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974. É um clássico na área, mas faltam alguns tópicos mais recentes.

[A83] A. V. Aho, J. E. Hopcroft, e J. D. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983. Apresenta uma versão revisada e mais elementar dos seis capítulos de The Design and Analysis of Computer Algorithms.

[BYR] R. Baeza-Yates and B. Ribeiro-Neto Modern Information Retrieval, Addison-Wesley, 1999.

[B] J. L. Bentley, Writing Efficient Programs, Prentice-Hall, 1982. O livro trata dos aspectos práticos da implementação de algoritmos, sob o ponto de vista da eficiência da implementação.

[CLR] T. H. Cormen, C. E. Leiserson e R. L. Rivest, Introduction to Algorithms, McGraw-Hill, 1991. Excelente em análise de algoritmos e tópicos avançados em projeto de algoritmos e estruturas de dados. O texto trata de muitos tópicos, contendo 1.028 páginas.

[GJ] M. R. Garey e D. S. Johnson, Computers and Intractability: A Guide to the Theory of -Completeness, W. H. Freeman, 1979. Um excelente livro dedicado a teoria -Completo. A segunda metade contém uma lista grande de problemas -Completo.

[GBY] G. H. Gonnet e R. Baeza-Yates, Handbook of Algorithms and Data Structures, Addison-Wesley, 1991, 2a. edicão. É um bom manual de algoritmos. Contém apontadores para analises em artigos de pesquisa, código em Pascal e C, e comparações de tempos reais de execução dos algoritmos.

[K] D. E. Knuth, The Art of Computer Programming, Addison-Wesley. Uma excelente referência, do tipo enciclopédica, em três volumes: (1) Fundamental Algorithms, (2) Seminumerical Algorithms, e (3) Sorting and Searching.

[L] Lawler, E. L., Lenstra, J. K., Kan, A. H. and Shmoys, D. B. The Traveling Salesman Problem, Wiley, 1985.

[M] U. Manber, Introduction to Algorithms A Creative Approach, Addison-Wesley, 1989. Enfatiza, em profundidade, o aspecto criativo do desenvolvimento de algoritmos, procurando mostrar ao leitor como projetar um novo algoritmo.

[S] R. Sedgewick, Algorithms, Addison-Wesley, 2a. edição, 1988. Cobre uma grande quantidade de tópicos, código em Pascal e C, leve na análise dos algoritmos.

[WMB99] I. H. Witten, A. Moffat, T.C. Bell Managing Gigabytes Compressing and Indexing Documents and Images, Morgan Kaufmann Publishers, 1999 (second edition). Bom livro sobre implementação de sistemas de RI.

Avaliação da Aprendizagem

• Quatro trabalhos práticos: 40 pontos
• Um seminário: 20 pontos
• Dois testes: 40 pontos

Observações

• Os testes são sem consulta.
• Todos os trabalhos são individuais. Você pode participar de discussões em grupo sobre os trabalhos práticos. Entretanto, você tem que trabalhar as soluções dos problemas individualmente. Se você consultar alguém, faça referência ao colaborador na solução de cada problema. Se você obter a solução com ajuda de outros textos, indique a fonte.
• Pequenas alterações na ementa do Curso podem acontecer.
• Curso de Programação de Linguagem C
• Links sobre interpretadores para Postscript/PDF, programa make e linguagens Pascal e C (cursos e tutoriais)
• Roteiro para documentar trabalhos práticos.
• Exemplos de documentação dos trabalhos práticos: Simulação de Monte Carlo e Heurísticas para Caixeiro Viajante
• Os trabalhos devem ser feitos em linguagem C e entregues impressos. Veja aqui maiores detalhes sobre instruções para a entrega de trabalhos praticos.

Seminário Acompanhado de Texto

Cada aluno deverá escolher um tópico, produzir um texto e preparar um seminário para ser apresentado em aula. Com relação a profundidade versus abrangência o trabalho poderá cair em uma das três categorias, a saber:

1. um novo resultado;
2. um resumo de 3 ou 4 artigos relacionados, em torno de algum tópico específico, que tenham sido lidos e bem entendidos. O relatório deve apontar, de forma coerente, os principais resultados encontrados, procurando explicitar o que é difícil, interessante e importante nos artigos. O texto deve indicar também possíveis caminhos para trabalho futuro;
3. bibliografia comentada. Um número grande de artigos (10 a 20) podem ser lidos e o resultado catalogado de maneira coerente. Relacione a bibliografia consultada (autor, título, [nome do periódico, n, ano, páginas] ou [editora, ano, páginas consultadas].

O texto não deve ultrapassar um tamanho máximo de 6 páginas (digamos um texto de aproximadamente 2.000 palavras). A entrega do documento com antecedência de no máximo 24 horas pode contar créditos para a avaliação. Cada aluno deverá prover uma cópia para cada colega. Procure entregar o documento em papel formato A4 ou formato de formulário contínuo.

Sugestões de tópicos:

1. Writing Efficient Programs, livro do Bentley [B]. Considerando novos algoritmos que não estão no texto e realizando trabalho semelhante ao do Bentley.
2. Pesquisa em Textos com Pré-processamento: Suffix Arrays, U. Manber e E. Myers, ACM-SIAM Symposium On Discrete Algorithms.
3. Pesquisa em textos: implementações eficientes do algoritmo de Boyre-Moore. A. Hume and D. Sunday, Fast string searching, Software Practice and Experience 21(11): 1221-1248, Nov. 1991. R. Horspool, Practical fast searching in strings, Software Practice and Experience 10: 501-506, 1980. T. Takaoka, A left-to-right processing computation for the Boyer-Moore string matching algorithm, The Computer Journal, 39(5): 413-416, 1995.
4. Fatoração de Inteiros Através de Computação Distribuída, CACM 34(11), nov 1991, 94-103.
5. Quicksort Externo, Quicksort Em Ambiente de Memória Virtual. [GBY], Tese doutorado M.C. Monard (1980).
6. Sef-Adjusting Multi-Way Search Trees. Árvores B em ambiente de memória virtual. Information Processing Letters v. 38, maio de 1991, 135-141.
7. Algoritmos Aleatórios. R. Karp "An Introduction to Randomized Algorithms", Discrete Applied Mathematics, v. 34, 1991, 165-201. Randomized Algorithms, R. Motwani e P. Raghavan, Cambridge University Press, 1995.
8. Compressão de Dados. J. Ziv e A. Lempel "Compression of Individual Sequences Via Variable-Rate Coding", IEEE Trans. on Inf. Theory 17 (24), set. 1978, 530-536. CACM 30 (9), 1987, 792-794. Williams, R. N. Adaptative Data Compression, Kluwer Academic Publishers, 1991, [BCW89] Bell, T.C., Cleary, J.G. e Witten, I. H. Text Compression, Prentice-Hall, 1989.
9. Compressão de textos. [BYR99]. Mostrar as principais técnicas de compressão de textos encontradas na literatura.
10. Técnicas de compressão aplicadas a RI. Ziviani, N., Moura, E. S., Navarro, G., and Baeza-Yates, R. "Compression: A Key for Next-Generation Text Retrieval Systems", IEEE Computer 33 (11), 2000, 37-44. Mostrar as principais técnicas de compressão adequadas para SI da próxima geração.
11. Compressão de sequências ascendentes de inteiros (como as sequências que aparecem em listas invertidas). [WMB99].
12. Algoritmos Paralelos. Quais problemas em estão em (ou quais são os problemas que podem se beneficiar substancialmente de computação massivamente paralela) ? J. Hopcroft e K. W. Kennedy, Computer Science: Achievements and Opportunities, Report of the NSF Advisory Committee for Computer Research, Society for Industrial and Applied Mathematics, 1989.
13. Linguagem para consulta na estrutura e no conteúdo de bancos de dados textuais: Gonzalo Navarro, dissertação de mestrado, DCC, Universidad de Chile, abril de 1995.
14. Busca por proximidade: R. Baeza-Yates, W. Cunto, U. Manber e s. Wu, "Proximity Matching Using Fixed-Queries Trees", Fifth Combinatorial Pattern Matching, 1994. R. Baeza-Yates e W. Cunto, Spire'99, Cancun, Mexico, 1999, The ADT Proximity and Text Proximity Problems.
15. Busca em textos usando estruturas em dois niveis. IR00, U. Manber and S. Wu, A two-level approach to information retrieval, TR93-06, Umiversity of Arizona, 1993.
16. Skip Lists. T. Papadakis, Skip lists and probabilistic analysis of algorithms, TR CS-93-28, University of Waterloo, May 1993. W. Pugh, CACM 33(6): 668-676, Jun 1990.
17. Perfect Hash. [WMB99]. G. H. Gonnet and R. Baeza-Yates, Handbook of Algorithms and Data Structures, Addison-Wesley, 1991.
18. Correção automatica de palavras em textos. Karen Kukich, techniques for automatically correcting words in text, ACM computing Surveys 24(4): 377-440 Dec. 1992. Hellen C. F. Pacheco, Uma Ferramenta de Auxílio à Redação, Dissertação de Mestrado DCC/UFMG, 1996.
19. Maquinas de busca para a Web de terceira geracao. Apresentar os principais algoritmos e estruturas de dados utilizados no armazenamento e recuperação de informacao na Web.
20. Busca por frases em bancos de dados de texto. Ilmerio Reis e Edleno S. Moura, Ranking Documents Using Conceptual Phrases (Anotações pessoais ainda não publicadas). Edleno S. Moura e Ilmerio Reis, Índices para Busca por Frases (Anotações pessoais ainda não publicadas). Marcio Drumond Araujo, IGREP - Um Sistema para Busca Aproximada em Textos Indexados, Dissertação Mestrado DCC/UFMG, 1997.
21. Recuperação de Imagens na Web. PhotoFinder (http://image.altavista.com). Haramndas et al., ACM SIGIR'97. Flickener et al., IEEE Computer 8(9), 1995, 23-32. Chang, IEEE Signal Processing Magazine, July 1997.
22. Busca em Textos Comprimidos. "Direct Pattern Matching on Compressed Text". E. S. de Moura, G. Navarro, N. Ziviani e R. Baeza-Yates. SPIRE'98, IEEE Computer Society, 90-95, Santa Cruz de la Sierra, Bolivia, Setembro, 1998. "Fast sequencial searching on compressed texts allowing errors". E. S. de Moura, G. Navarro, N. Ziviani e R. Baeza-Yates. "Proc. of the 21st Conference on Research and Development in Information Retrieval", ACM SIGIR'98, 298-306, Melbourne, Australia, Agosto, 1998.
23. Algoritmos Distribuídos - Geração de listas invertidas em paralelo: "Efficient Distributed Algorithms to Build Inverted Files". Berthier Ribeiro-Neto, Nivio Ziviani, Edleno Moura e Marden Neuber. SIGIR'99.
24. Algoritmos Distribuídos - Recuperação em paralelo: ACM CIKM02: Balanced Distributed Query Processing Using a Random Layout.
25. Algoritmos Distribuídos - Geração de arranjos de sufixos em paralelo: Navarro, G., Kitajima, J. P., Ribeiro-Neto, B. A. and Ziviani, N. "Distributed Generation of Suffix Arrays", In: A. Apostolico and J. Hein (Eds.) Eigth Symposium on Combinatorial Pattern Matching (CPM'97), Springer-Verlag LNCS v. 1264, 102-115. Kitajima, J. P., Resende, M. D., Ribeiro-Neto, B. and Ziviani, N. "Distributed Parallel Generation of Indices for Very Large Text Databases", IEEE 3rd International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP'97), Melbourne, Australia, December 1997, 745-752.
26. Índices para Pesquisa em Textos Permitindo Erros, Marcio Drumond Araujo, IGREP - Um Sistema para Busca Aproximada em Textos Indexados, Dissertação Mestrado DCC/UFMG, 1997.
27. Busca de palavras em arquivos PostScript (.ps), Extracting Text from PostScript, Nevill-Manning, C.G., Reed, T. and Witten, I.H., Software Practice and Experience 28(5), 1998, 481-491.

Planejamento das Aulas

Aula	Mês	Dia	Assunto	Referência	TPs
01	Jun	04	Apresentacao do Curso
02		06	Análise de Algoritmos	Z1.3	TP1 (E)
03		11	Análise de Algoritmos	Z1.3
04		13	Análise de Algoritmos	Z1.4
05		18	Análise de Algoritmos	Z1.4
06		20	Grafos: noções	S29-S34 CLR23-CLR27 Z6
07		25	Grafos: noções	S29-S34 CLR23-CLR27 Z6
08		27	NP-Completo	Z8 HS
09	Jul	02	NP-Completo	Z8 HS	TP2 (E)
10		04	NP-Completo	Z8 HS
11		09	Heurísticas: PCV	Z8 HS
12		11	Heurísticas: PCV	Z8 HS
13		16	Reserva
14		18	1ª Prova
15		25	Proc. caracteres	Z7 FBY10
16		30	Proc. caracteres	Z7 FBY10	TP3 (E)
17	Ago	01	Algoritmos Paralelos	Alg.paralelos
18		06	Algoritmos Paralelos	Alg.paralelos
19		08	Algoritmos Paralelos	Alg.paralelos
20		13	Algoritmos Paralelos	Alg.paralelos
21		20	Algoritmos Paralelos	Alg.paralelos	TP4 (E)
22		22	Algoritmos Paralelos	Alg.paralelos
23		27	Seminários
24		29	Seminários
25	Set	03	Seminários
26		05	Seminários
27		17	Seminários
29		19	Seminários
30		26	Prova final

Alguma alteração poderá ocorrer, mas, em princípio, pretende-se seguir este planejamento. O livro texto a ser seguido em alguns assuntos aparece na coluna "Referência".

TP1: Análise de algoritmos
TP2: Problemas NP-completo
TP3: Pesquisa em textos
TP4: Algoritmos paralelos