"Office-hours"

Semestre: 1.o semestre de 1997

Horário:

3.a feiras: 16 - 18 h

5.a feiras: 14 - 16 h

Sala: 259 Bloco A - 2.o andar

Data da primeira prova: dia 13 de maio de 1997

Data da segunda prova: dia 24 de junho de 1997

Data da terceira prova (opcional ver critério de avaliação abaixo): dia 1 de julho de 1997

Requisitos:

Boa experiência em programação, em Pascal ou C.

- Manual de uso do sistema ("guia de sobrevivência") em .html

ou em postscipt .ps disponível também para Xerox na pasta do Siang na Sala de Xerox, bloco B térreo.

- Notas de aula sobre orientação a objetos e tipos abstratos de dados (em postscipt .ps) disponível também para Xerox na pasta do Siang na Sala de Xerox, bloco B térreo.

Outros avisos:

Para informações sobre prazos de matrículas, trancamento, dias sem aula, etc. veja o

Calendário da Pós-Graduação para 1997.

Conteúdo da disciplina:

• Preliminares: Complexidade de algoritmos
• Listas lineares: pilhas, filas, filas duplas, filas de prioridade. (em postscript .ps)
• Implementação sequencial e ligada.
• Conceitos de programação orientada a objetos e tipos abstratos de dados (em postscript .ps)
• Árvores: árvores binárias, algoritmos de travessia, árvore de busca, árvores balanceadas AVL, árvores-B
• Coleta de lixo
• Programação LISP

Referências bibliográficas:

• Wirth, N. Algorithms + Data Structures = Programs. Prentice Hall, 1976.
• Knuth, D.E. The Art of Computer Programming. Volume 1, Addison Wesley, 1973.
• Aho, A.V., Hopcroft, J.E. and Ullman, J.D. Data structures and algorithms. Addison Wesley, 1987.
• Szwarcfiter, J. L. e Markenzon, L. Estruturas de Dados e seus Algoritmos. LTC Editora, 1994.
• Terada, R. Desenvolvimento de algoritmos e estruturas de dados. McGraw Hill do Brasil, 1991.
• Ziviani, N. Projeto de Algoritmos com Implementações em Pascal e C. Livraria Pioneira Editora, São Paulo, 1993.
• Takahashi, T. e Liesenberg, H.K.E. Programa\c{c}\~ao Orientada a Objetos. VII Escola de Computação, IME/USP, 1990.
• Stroustrup, B. The C++ programming language. Addison Wesley, 1987.
• Pinson and Wiener. An Introduction to Object-Oriented Programming and C++ . Addison Wesley, 1988. (Tem tradução para português - editora Makron.)

Avaliação:

Listas de exercícios: média E

Listas de programas: média ponderada Pg

Nota de aproveitamento final A:

se Pg < 5 ou P < 5 então A = min(Pg, P) ``reprovado''

senão A = (0.5 E + 3.5 Pg + 6 P )/10

Exercícios:

• Exercício 1
• Exercício 2
• Exercício 3 (em postscript .ps)
• Exercício 4
• Exercício 5

Programas:

• Programa 1
• Programa 2 (em postscript .ps)
• Programa 3
• Programa 4
• Programa 5

Provas:

• Prova 1

Assuntos tratados em aulas:

Aula 1 (11/03/1997): Descrição do curso; uso de equipamentos; homepage do curso; Complexidade de algoritmos. Passar para casa Exercício 1.

Aula 2 (13/03/1997): Limite ou cota superior (upper bound) e limite ou cota inferior (lower bound); listas lineares (.ps) : pilhas, filas.

Aula 3 (18/03/1997): Implementação de pilhas e filas usando alocação sequencial. Passar o programa 1.

Aula 4 (25/03/1997): Exercício em classe: como compartilhar um espaço de tamanho m por n pilhas, usando alocação sequencial. Alocação ligada ou encadeada: motivação, lista livre, rotinas para sua manipulação. Pilha em alocação ligada. Algoritmo para inserir na pilha.

Aula 5 (01/04/1997): Continuação de alocação ligada ou encadeada: algoritmo para remover da pilha; algoritmos para inserir e remover da fila. Alocação dinâmica de espaço em Pascal (comandos new, dispose etc.) Passar para casa Exercício 2.

Aula 6 (03/04/1997): Listas ligadas circulares; listas duplamente ligadas. Exercício em classe sobre um algoritmo ingenhoso (devido a Knuth) que permite percorrer uma lista linear ligada em ambos os sentidos, sem usar dois apontadores por elemento.

Aula 7 (08/04/1997): Ordenação topológica: um exercício usando várias estruturas de dados. Passar para casa Exercício 3 (em postscript .ps).

Aula 8 (10/04/1997): Ordenação topológica: continuação da aula anterior, concluindo o algoritmo. Comentar sobre o exercício programa no. 2, sobre átomos, listas, e sua representação.

Aula 9 (15/04/1997): Fila de prioridade, conceito, alternativas de implementacao.

Aula 10 (17/04/1997): Coleta de lixo (garbage collection): conceito, método de marcação e varredura; método de contador de referências.

Aula 11 (22/04/1997): Conceitos de programação orientação a objetos e tipos abstratos de dados.

Aula 12 (24/04/1997): Exemplo de especificação de um tipo abstrato de dados: pilha. Árvores: conceitos e nomenclatura.

Aula 13 (29/04/1997): Árvores binárias; representar expressões aritméticas com operadores binários; contrução de uma árvore binária perfeitamente balanceada. Passar o Exercício 4. Passar o Programa 3.

Aula 14 (06/05/1997): Algoritmos para percorrer uma árvore binária de maneira sistemática, visitando todos seus nós: pré-ordem, in-ordem, pós-ordem. Pergunta: o procedimento printtree visto na aula passada parece com que tipo de percurso? Árvore binária de busca: característica. Percorrer uma árvore de busca em in-ordem produz os valores em ordem crescente.

Aula 15 (08/05/1997): Aulas de exercícios em classe.

Aula 16 (13/05/1997): Prova. Local da prova: Sala 1 do bloco B.

Aula 17 (15/05/1997): Árvore binária de busca: algoritmos para localizar um dado (função loc) e inserir um dado novo (procedimento search).

Aula 18 (20/05/1997): Resolução da prova. Árvore binária de busca: algoritmo para remover um dado.

Aula 19 (22/05/1997): Análise do desempenho (número médio de comparações). Discussão sobre quando é interessante usar a árvore binária de busca.

Aula 20 (27/05/1997): Aula não dada e a ser reposta com aulas mais longas nas próximas duas terças feiras.

Aula 21 (03/06/1997): Aula "reforçada" com 3 horas de duração: Árvore AVL - árvore de busca balanceada (alturas de subárvores diferem em no máximo um). Rotação LL, RR, LR e RL para rebalanceamento da árvore. Árvore ótima de busca: definição e exemplos.

Aula 22 (05/06/1997): Árvore ótima de busca: algoritmo de construção usando a técnica de programação dinâmica.

Aula 23 (10/06/1997): Aula "reforçada" com 3 horas de duração: Árvore ótima de busca: idéia do algoritmo de construção usando a técnica de programação dinâmica. Outro exemplo usando programação dinâmica: multiplcação de n matrizes. B-árvores: motivação e um exemplo simples.

Aula 24 (12/06/1997): B-árvores: definição, busca, inserção e remoção. Tabela de espalhamento (hashing).

Aula 25 (17/06/1997): Tabela de espalhamento (hashing): tratamento de colisão. LISP: introdução.

Aula 26 (19/06/1997): LISP: definição de funções, exemplos. Aula com demonstração.