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

Última alteração: June 29, 2006

Modelo de trabalho em Latex
Arquivo Latex do TP1

Seminários a Serem Apresentados em 2006

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 2006
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)
Monitor: Fabiano C. Botelho

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 da disciplina o aluno deverá ser capaz de lidar com classes específicas de problemas e com os principais paradigmas de projeto de algoritmos, 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. Paradigmas de projeto 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.

Grafos

Representação, busca em profundidade e em largura, ordenação topológica, componentes fortemente conectados, AGM, caminhos mais curtos.

Paradigmas de Projeto de Algoritmos

Indução, recursividade, tentativa e erro, divisão e conquista, balanceamento, programação dinâmica, algoritmos gulosos, algoritmos aproximados e algoritmos paralelos.

Problemas -Completo

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

Tópicos

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

[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.(Livro texto para a parte de programação paralela)

[Z] Ziviani, N. Projeto de Algoritmos Com Implementações em Pascal e C, Pioneira Thomson Learning, 2004, segunda edição. (Livro 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.

Brassard, G. e Bradley, P. (1996) Fundamentals of Algorithmics, Prentice Hall.

[CLR] T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein, Introduction to Algorithms, McGraw-Hill, 2001, second edition. 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.128 páginas.

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

[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 (http://www.dcc.uchile.cl/$\sim$rbaeza).

[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.

[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.

Navarro, G. e Raffinot, M. (2003) Flexible Pattern Matching in Strings. Cambridge University Press.

[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.
• As soluções dos trabalhos práticos devem ser disponibilizadas em html, e os melhores trabalhos serão colocados na página da disciplina.
• Pequenas alterações na ementa do Curso podem acontecer.
• Curso de Programação de Linguagem C
• 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
• 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 $^{\underline{o}}$, 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 48 horas (sendo tolerado até no máximo 24 horas) conta créditos para a avaliação. A entrega do artigo deverá ser na forma de um arquivo pdf ou html que será colocado na página da disciplina.

Sugestões de tópicos:

1. 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. 2. Pesquisa em Textos com Pré-processamento: Suffix Arrays, U. Manber e E. Myers, ACM-SIAM Symposium On Discrete Algorithms.
3. 3. Fatoração de Inteiros Através de Computação Distribuída, CACM 34(11), nov 1991, 94-103.
4. 4. Quicksort Externo, Quicksort Em Ambiente de Memória Virtual. [GBY], Tese doutorado M.C. Monard (1980), [Z04] Ziviani (2004).
5. 5. Sef-Adjusting Multi-Way Search Trees. Árvores B em ambiente de memória virtual. Information Processing Letters v. 38, maio de 1991, 135-141.
6. 6. 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.
7. 7. 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.
8. 8. 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.
9. 9. Compressão de sequências ascendentes de inteiros (como as sequências que aparecem em listas invertidas). [WMB99].
10. 10. Algoritmos Paralelos. Quais problemas em $\cal P$ estão em $\cal NC$ (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.
11. 11. 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.
12. 12. Flexible Pattern Matching in Strings, Navarro e Raffinot, 2002, Cambridge University Press.
13. 13. Busca em textos usando estruturas em dois niveis. IR00, U. Manber and S. Wu, A two-level approach to information retrieval, TR93-06, University of Arizona, 1993.
14. 14. Programação Genética. John R. Koza. "Genetic Programming: On the Programming of Computers by Means of Natural Selection", MIT Press, 1992 (http://www.genetic-programming.com/johnkoza.html). Weiguo Fan and Michael D. Gordon and Praveen Pathak. "A generic ranking function discovery framework by genetic programming for information retrieval". Information Processing and Management, 40(4):587-602, 2003.
15. 15. 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.
16. 16. Hashing dinâmico. P. Larson, Dynasmic Hash Tables, CACM 31(4), 1988, 446-457. P. Larson, Dynamic Hashing, BIT 18(2), 1978, 184-201.
17. 17. Hashing perfeito preservando ordem. [Z04] cap. 4, seção 5.5.4, [WMB99], Theoretical Computer Science 182, 1997, 1-143, IPL 43(5), 1992, 257-264. Realizar estudo sobre algoritmo que obtem a função de transformação perfeita mínima com ordem preservada.
18. 18. Hashing perfeito sem preservar ordem. Botelho, F.C., Kohayakawa, Y. and Ziviani, N. "A Practical Minimal Perfect Hashing Method", 4th International Workshop on efficient and Experimental Algorithms (WEA05), Springer-Verlag Lecture Notes in Computer Science, vol. 3505, Santorini Island, Greece, May 2005, 488-500. Fox, E.A., Chen, Q.F. and Heath, L. S. "Practical Minimal Perfect Hash Functions For Large Databases". Communications of the ACM, 1(35):105-121, 1992. Fox, E.A., Heath, L. S., Chen, Q. and Daoud, A. M. "A Faster Algorithm for Constructing Minimal Perfect Hash Functions". Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 1992. Pagh, R. "Hash and Displace: Efficient Evaluation of Minimal Perfect Hash Functions". Workshop on Algorithms and Data Structures, 1999. Hagerup, T. and Tholey, T. "Efficient minimal perfect hashing in nearly minimal space". The 18th Symposium on Theoretical Aspects of Computer Science (STACS), volume 2010 of Lecture Notes in Computer Science, 2001. Realizar estudo sobre algoritmo que obtem a função de transformação perfeita mínima sem ordem preservada.
19. 19. 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.
20. 20. 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 .
21. 21. 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.
22. 22. Recuperação de Imagens na Web. PhotoFinder (http://image.altavista.com). Coelho, T., Vieira, R., Laender, A. e Ribeiro-Neto, B. Image Retrieval Using Multiple Evidence Ranking. IEEE Transactions on Knowledge and Data Engineering, to appear. Haramndas et al., ACM SIGIR'97. Flickener et al., IEEE Computer 8(9), 1995, 23-32. Chang, IEEE Signal Processing Magazine, July 1997.
23. 23. 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.
24. 24. 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.
25. 25. Algoritmos Distribuídos - Recuperação em paralelo: Badue, C., Baeza-Yates, R., Ribeiro-Neto, B. e Ziviani, N., Distributed Query Processing Using a Partitioned Inverted Files, Spire 2001, ACM SIGIR 2005, 577-578i, ACM SIGIR Workshop on Heterogeneous and Distributed IR, 2005.
26. 26. 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.
27. 27. Í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.
28. 28. 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.

Acesso a Bibliotecas Online

Mais instruções no site Biblioteca do ICEx seguindo a opção Sites de Pesquisa dentro de links (ou com a bibliotecária).

• Portal Periódicos da CAPES permite acesso a várias bibliotecas, inclusive a todo IEEE, a partir de qualquer endereço da UFMG, podendo ser acessado via site da Biblioteca do ICEx
• ACM: acesso a todas as publicações e conferências, de qualquer máquina do DCC/UFMG, da ACM Digital Library
• Computer Science Bibliography, permite busca por autor, titulo de papers em geral ()
• IEEE: acesso a vários títulos da biblioteca online da IEEE acesso via portal Periódicos da CAPES a partir de qualquer endereço da UFMG, podendo ser acessado via site da Biblioteca do ICEx (verifique com a bibliotecária)
• Google Scholar
• DBLP
• BDComp
• Web of Science: contém informação bibliográfica de três bancos de dados: Science Citation Index Expanded, Social Science Citation Index, Arts and Humanities Citation Index Web of Science
• USENIX: Advanced Computing Systems Association, pegar senha com a bibliotecária
• Mathscinet: acesso aos banco de dados Association Mathematical Society com cobertura nas áreas de matemática e computação, podendo ser acessado via site da biblioteca do ICEx

Planejamento das Aulas

Aula	Mês	Dia	Assunto	Referência	TPs
01	Mar	07	Apresentacao do Curso
02		09	Medida Tempo Execução de Algoritmos	Z1.3	TP1 (E)
03		14	Medida Tempo Execução de Algoritmos	Z1.3
04		16	Técnicas de Análise de Algoritmos	Z1.4,Z2.4
05		21	Paradigmas de Projeto de Algoritmos	Z2
06		23	Paradigmas de Projeto de Algoritmos	Z2
07		28	Algoritmos em Grafos	Z7
08		30	Algoritmos em Grafos	Z7
09	Abr	04	Algoritmos em Grafos	Z7	TP2 (E)
10		06	NP-Completo	Z9
11		11	NP-Completo	Z9
12		18	Algoritmos Aproximados: PCV	Z9
13		20	Algoritmos Aproximados: PCV	Z9
14		25	Reserva
15		27	1ª Prova
16	Mai	02	Processamento de Cadeias de Caracteres	Z8
17		04	Processamento de Cadeias de Caracteres	Z8	TP3 (E)
18	Mai	09	Processamento de Cadeias de Caracteres (compressão)	Z8
19	Mai	11	Processamento de Cadeias de Caracteres (compressão)	Z8
20		16	Correção Prova 1
21		18	Algoritmos Paralelos	Alg.paralelos
22		23	Algoritmos Paralelos	Alg.paralelos
23		25	Algoritmos Paralelos	Alg.paralelos
24		30	Algoritmos Paralelos	Alg.paralelos	TP4 (E)
25		30	Sockets
26	Jun	01	Reserva
27		06	Seminários
28		08	Seminários
29		13	Seminários
30		20	Seminários
31		22	Seminários
32		27	Seminários
33		29	2ª Prova

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