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

Última alteração: July 12, 2004

Modelo de trabalho em Latex

Artigos dos Seminários Apresentados em 2004

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

Paradigmas de Projeto de Algoritmos

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

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

[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/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
• 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. A entrega do artigo deverá ser na forma de um arquivo html que será colocado na página da disciplina.

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. Fatoração de Inteiros Através de Computação Distribuída, CACM 34(11), nov 1991, 94-103.
4. Quicksort Externo, Quicksort Em Ambiente de Memória Virtual. [GBY], Tese doutorado M.C. Monar (1980).
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. 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. 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. 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. Compressão de sequências ascendentes de inteiros (como as sequências que aparecem em listas invertidas). [WMB99].
10. 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.
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. 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.
13. 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.
14. Hashing dinâmico. P. Larson, Dynasmic Hash Tables, CACM 31(4), 1988, 446-457. P. Larson, Dynamic Hashing, BIT 18(2), 1978, 184-201.
15. Hashing perfeito. [Z04] cap. 4, seção 5.5.4, [WMB99]. Realizar estudo sobre algoritmo que obtem a função de transformação perfeita mínima com ordem preservada.
16. 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.
17. 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 .
18. 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.
19. 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.
20. 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.
21. 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.
22. 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.
23. 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.
24. Í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.
25. 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 www.biblioteca.icex.ufmg.br seguindo a opç ao 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
• Computer Science Bibliography, permite busca por autor, titulo de papers em geral
• IEEE: acesso a vários títulos da biblioteca online (), acesso via portal Periódicos da CAPES permite um acesso de cada vez, pegar senha com a bibliotecária
• 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
• 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	16	Apresentacao do Curso
02		18	Medida Tempo Execução de Algoritmos	Z1.3	TP1 (E)
03		23	Medida Tempo Execução de Algoritmos	Z1.3
04		25	Técnicas de Análise de Algoritmos	Z1.4,Z2.4
05		30	Paradigmas de Projeto de Algoritmos	Z2
06	Abr	01	Paradigmas de Projeto de Algoritmos	Z2
07		06	Algoritmos em Grafos	Z7
08		13	Algoritmos em Grafos	Z7
09		15	Algoritmos em Grafos	Z7	TP2 (E)
10		20	NP-Completo	Z9
11		22	NP-Completo	Z9
12		27	Algoritmos Aproximados: PCV	Z9
13		29	Algoritmos Aproximados: PCV	Z9
14	Mai	04	Reserva
15		06	1ª Prova
16		11	Processamento de Cadeias de Caracteres	Z8	TP3 (E)
17		13	Processamento de Cadeias de Caracteres	Z8
18		18	Reserva
19		20	Correção Prova 1
20		25	Algoritmos Paralelos	Alg.paralelos
21		27	Algoritmos Paralelos	Alg.paralelos
22	jun	01	Algoritmos Paralelos	Alg.paralelos
23	jun	03	Algoritmos Paralelos	Alg.paralelos	TP4 (E)
23		08	Sockets
24		08	Reserva
25		15	Seminários
26		17	Seminários
27		22	Seminários
28		24	Seminários
29		29	Seminários
30	Jul	01	Seminários
31		08	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