Semestre: 1.o semestre de 1996

Horário: 4.a feiras 8 - 10h, 6.a feiras 8 - 10h

Sala: 4.a feira sala 259 - 6.a feira sala 267

Data da primeira prova: 9 de outubro de 1996 (4.a feira) 8-10 h

Data da segunda prova: 22 de novembro de 1996 (6.a feira) 8-10 h

Requisitos:

1. Estruturas de Dados
2. Análise de Algoritmos (*)

Conteúdo:

• Preliminares: Complexidade de algoritmos
• Modelos paralelos
• Técnicas básicas
• Listas e árvores
• Busca e ordenação
• Problemas em grafos
• Problemas em Geometria Computacional
• Processamento de Palavras
• Tópicos diversos

Referêencias bibliográficas:

• JáJá, Joseph. An Introduction to Parallel Algorithms. Addison-Wesley Publishing Company. 1992.
• Leighton, F. Thompson. Introduction to Parallel Algorithms and Architectures: arrays, trees, hypercubes. Morgan Kaufmann Publishers. 1992.
• Dehne, F., Fabri, A. and Rau-Chaplin, A. ``Scalable parallel computational geometry for coarse grained multicomputers''. Proc. ACM Symposium on Computational Geometry, 1993, pp. 298-307.
• Apostolico, A., Iliopoulos, C., Landau, G. M., Schieber, B. and Vishkin, U. ``Parallel construction of a suffix tree with applications''. Algorithmica, Vol. 3, No. 3, pages 347-365. 1988.

Avaliação:

Exercícios:

• Exercício 1 Data de entrega: dia 28/8/96 (4.a feira)
• Exercício 2 Data de entrega: dia 25/9/96 (4.a feira)
• Exercício 3
• Exercício 4
• Exercício 5
• Exercício 6

Provas:

• Primeira prova.

Aula 1 (14/8/96): Descrição do curso; Complexidade de algoritmos.

Aula 2 (16/8/96): Motivação da computação paralela; algumas máquinas massivamente paralelas (MPP) existentes no mercado.

Aula 3 (21/8/96): Conceitos de speed-up, eficiência; modelo paralelo Grafo Orientado Acíclico, escalonamento do GOA; Exemplo 1.1 soma de n números no modelo GOA.

Aula 4 (23/8/96): Exemplo 1.3 multiplicação de matrizes no modelo GOA; modelo de memória compartilhada; Exemplo 1.4 multiplicação de matriz vetor; Algoritmo 1.1 multiplicação matrizes.

Aula 5 (28/8/96): Exemplo 1.5 Soma de n números no PRAM: duas soluções ( a do livro e a do Mauro di Giorgi); variações do PRAM quanto a acessos simultâneos: EREW, CREW, CRCW; notação simplificada (sem usar globalread e globalwrite).

Aula 6 (30/8/96): Exemplo 1.6 Multiplicação de matrizes no PRAM, algoritmo 1.3; modelo de memória distribuída (modelo de rede), array linear, anel; exemplo 1.7 multiplicação matriz vetor no anel e algoritmo 1.4.

Aula 7 (11/9/96): Hipercubo; exemplo 1.8 soma no hipercubo; exemplo 1.10 difusão (broadcast) no hipercubo.

Aula 8 (13/9/96): Exemplo 1.11 multiplicação de matrizes no hipercubo; Passar lista de exercício no. 2 (comentar imersão de grafos).

Aula 9 (18/9/96): Redes shuffle-exchange; Butterfly; cube connected cycles; relações entre as várias estruturas.

Aula 10 (20/9/96): Grafo de Bruijn; Modelo PRAM; desempenho de algoritmos paralelos; paradigma trabalho-tempo; comando pardo; exemplo 1.12 soma de n números no paradigma trabalho-tempo.

Aula 11 (25/9/96): Mágica baseada no Grafo de Bruijn; Princípio de escalonamento trabalho-tempo; conceito de optimalidade: algoritmos ótimos (no sentido fraco) e ótimos no sentido forte; técnicas básicas - árvore balanceada, algoritmo (alg. 2.1) para soma prefixa.

Aula 12 (27/9/96): Técnica de ``pointer jumping''; algoritmo (alg. 2.4) para determinação de raízes de árvores; algoritmo (alg. 2.5) para calcular soma prefixa em árvores.

Aula 13 (2/10/96): Técnica de divisão-e-conquista; algoritmo (alg. 2.6) para o problema de casco convexo.

Aula 14 (9/10/96): Primeira prova.

Aula 15 (11/10/96): Técnica de particionamento; um algoritmo ótimo de intercalação (alg. 2.7).

Aula 16 (16/10/96): Técnica de pipelining; exemplo árvore 2-3. Técnica de aceleração em cascata ("accelerated cascading"); exemplo de achar o máximo.

Aula 17 (18/10/96): Técnica de quebra de simetria; algoritmo para 3-coloração em tempo O(log* n).

Aula 18 (23/10/96): Problema de "list ranking" usando pointer jumping (alg. 3.1); contração de lista (alg. 3.2); um algoritmo ótimo para "list ranking" (alg. 3.3).

Aula não dada (25/10/96): a ser reposta na semana seguinte.

Aula 19 (30/10/96): Problemas em árvores usando circuito de Euler; atribuição de raiz e obtenção de pai de cada vértice; percurso em pós-ordem; determinação de núumero de descendentes; determinaçãoo do nível de cada vértice.

Aula 20 (1/11/96 - aula normal): Contração de árvore; avaliação de expressões aritméticas.

Aula 21 (1/11/96 - aula reposição): Uso da máquina paralela Parsytec PowerXplorer: aula prática. Exemplos de programas em Parix. Transparências usadas num seminário sobre Parix dado por Gubi.

Aula 22 (6/11/96): Algoritmo paralelo de busca usando p processadores(alg. 4.1); intercalação (alg. 4.2).

Aula 23 (8/11/96): Rede de interconexão; algoritmo paralelo de ordenação bitônica.

Aula 24 (13/11/96): Modelo de granularidade grossa em computador paralelo de memória distribuída: exemplo: algoritmo paralelo para list ranking

Aula 25 (20/11/96): Algoritmos paralelos para list ranking de O(log p + log log n) e O(log* n log p) rodadas de comunicação. Ver artigo de Dehne e Song.

Aula 26 (22/11/96): Segunda prova (com consulta; matéria a partir da técnica de pointer jumping).