"Office-hours"

Semestre: 1.o semestre de 2003

Horário:

2.a feiras: 16 - 18 h

4.a feiras: 14 - 16 h

Sala de Aula: 259 Bloco A - 2.o andar

Data da primeira prova:
Dia 28 de abril de 2003 (segunda feira)
(Matéria da primeira prova: até a aula 10 inclusive.)

Data da segunda prova:
Dia 16 de junho de 2003 (segunda feira)
(Matéria da segunda prova: desde a aula 11 até a aula 23 inclusive.)

Data da terceira prova (opcional ver critério de avaliação abaixo):
Dia 2 de julho (quarta feira) às 14h.
(Toda matériada desde a aula 1 até a aula 23 inclusive.)

Requisitos:

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

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

Conteúdo da disciplina:

• Preliminares: Complexidade de algoritmos
• Listas lineares: pilhas, filas, filas duplas, filas de prioridade. (em postscript .ps) (em pdf .pdf)
• Implementação sequencial e ligada.
• Á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 (Entregar até 12/março/2003.)
• Exercício 2 (Entregar até 23/abril/2003.)
• Exercício 3 (em postscript .ps) (em .pdf) (Entregar até 16/junho/2003.)

Programas:

Atenção: os programas devem ser feitos individualmente.

O que voce deve entregar: Deve ser entregue uma listagem com a impressão do programa fonte, e a impressão do resultado (alguns testes que comprovam que o programa está funcionando de acordo). Não entregue o diskette.

• Programa 1 (Entregar até o dia 23 de abril de 2003.)
  
• Programa 2 (em postscript .ps) (em .pdf) (Dicas sobre esse programa serão dadas em classe. (Entregar até 16/junho/2003.)
• Programa 3. (Entregar até 16/junho/2003.)

Provas:

Assuntos tratados em aulas:

Aula 2 (26/02/2003): Importância de estudar a complexidade de algoritmos. Como melhorar a eficiência de um programa: otimizações locais, uso de "profile" para conhecer o perfil de execução, analisar a complexidade e mudar a concepção do algoritmo visando obter uma complexidade melhor. Conceito de cota ou limite superior (upper bound) e cota ou limite inferior (lower bound).

Aula 3 (10/03/2003): Listas lineares (.ps) ou em pdf (.pdf): pilhas, filas, suas características e utilidades. Destacar a diferença entre a especificação ou definição de uma estrutura de dados e sua representação/implementação.

Aula 4 (17/03/2003): Alocação de memória sequencial. Representação de uma pilha em alocação sequencial. Representação de uma fila em alocação sequencial: inserção e remoção. Fila circular (em alocação sequencial). Problema de compartilhar um espaço único por várias filas e/ou pilhas. Vantagens (simplicidade) e desvantagens da alocação sequencial (alocação de espaço é estático, de difícil dimensionamento a priori, dificultando a expansão bem como o compartilhamento do mesmo espaço por várias estruturas de dados).

Aula 5 (19/03/2003): Alocação ligada ou encadeada. Pilhas em alocação ligada. Passar o Programa 1.

Aula 6 (24/03/2003): Filas em alocação ligada. Comparar as as duas representações sequencial e ligada apresentando as vantagens e desvantagens de cada uma. Várias maneiras de implementar a alocação ligada: (1) usando linguagens que não possuem ponteiros (você gerencia tudo, incluindo a lista livre e as rotinas ExtraiLivre e DevolveLivre)

Aula 7 (26/03/2003): Várias maneiras de implementar a alocação ligada: (2) usando linguagens que possuem ponteiros (o próprio sistema cuida da organização do espaço livre e ExtraiLivre e DevolveLivre são feitos pelo sistemas e recebem outros nomes e.g. new e dispose em Pascal). Listas circulares ligadas. Listas duplamente ligadas (tem dois links: um llink apontando para o elemento da esquerda e um rlink apontando para o elemento da direita). Passar o Exercício 2.

Aula 8 (31/03/2003): Exemplo do uso de listas circulares com cabeça de lista: representação de matriz bidimensional esparsa. Um esquema que permite caminhar nos dois sentidos (para direita e para esquerda) em uma lista linear ligada com um campo apenas para link. Introduzir o problema da ordenação topológica: um problema cuja solução ilustra bem o uso de várias estruturas de dados tanto em alocação sequencial como ligada, usando listas lineares ligadas, filas, etc.

Aula 9 (02/04/2003): Problema de ordenação topológica: relações de ordem parcial, propriedades, definição de ordem topológica, algoritmo para obter uma ordem topológica.

Aula 10 (09/04/2003): Fila de prioridade: conceitos, várias formas de implementação, implementação com o uso de heap. Representação de um heap com um vetor.

Aula 11 (23/04/2003): Passar Exercício 3 (em postscript .ps) (em .pdf) Passar Programa 2 (em postscript .ps) (em .pdf) Processamento de listas; processamento simbólico. Comentar sobre o exercício programa no. 2, sobre átomos, listas, e sua representação.

Aula 12 (28/04/2003): Primeira prova. Matéria: até a aula 10 inclusive.

Aula 13 (30/04/2003): Dar uma dica para ler uma lista (procedimento le_lista) e construir a representação correspondente na memória, de forma recursiva. "Garbage collection": reciclagem de células de memória quando se esgota a lista livre. Método 1: marcação e coleta (mark-scan).

Aula 14 (05/05/2003): Continuação "Garbage collection": Método 2: contador de referências. Árvore. Definições e exemplo. Nomenclatura sobre vários termos usados em árvores. Exemplos de uso de árvores: por exemplo em árvores de jogos (usadas em Inteligência Artificial).

Aula 15 (07/05/2003): Construção de árvore de altura mínima, perfeitamente balanceada (função tree). Impressão de árvore por meio do procedimento printtree (usando uma ordem de percurso da árvore semelhante à in-ordem).

Aula 16 (12/05/2003): Para o algoritmo dado na aula anterior, fornecer uma entrada e mostrar o resultado da execução (a árvore construída). Modos de percorrer uma árvore binária: pré-ordem, in-ordem, pós-ordem. Dar algoritmos recursivos e para o percurso pré-ordem, in-ordem e pós-ordem. Comentar o percurso por nível ou por largura (breadth-first), que deve usar uma fila.

Aula 17 (19/05/2003): Comentar que o procedimento visto printtree (visitar a subárvore direita, visita a raiz, visita a subárvore esquerda) é parecido com o percurso da árvore em in-ordem (invertendo direita e esquerda). Arvore binária de busca: conceitos e complexidade. Inserção na árvore binária de busca, comentário sobre sua complexidade: pior caso é O(n) para uma árvore degenerada (desbalanceada). Será mostrado em aulas futuras que a complexidade do caso médio é O(log n).

Aula 18 (21/05/2003): Remoção da árvore binária de busca. Três casos considerados: nó a ser removido não está na árvore (fácil), nó a ser removido possui 0 ou 1 filho, nó a ser removido possui 2 filhos. Comentário sobre sua complexidade.

Aula 19 (26/05/2003): Analisar a complexidade média: número de comparações para buscar uma chave qualquer entre as $n$ possíveis chaves da árvore de busca, quando a árvore de busca é uma arbitrária entre todas as árvores correspondentes às $n!$ permutações das $n$ chaves. Passar Programa 3.

Aula 20 (28/05/2003): Árvore de busca AVL: definição de árvore balanceada, estrutura da pior árvore AVL. Algoritmo de inserção em árvore de AVL, por meio de rotações visando o rebalanceamento. (Informação do Prof. Arnaldo Mandel para quem quer usar árvore AVL: Foi instalada uma biblioteca implementando árvores AVL e Red-Black. A documentação pode ser lida no info (emacs), nó Avl. Os programas fonte estão em /usr/gnu/avl-1.4.0)

Aula 21 (02/06/2003): Árvore de busca AVL: Algoritmo de remoção. Introduzir o conceito de árvore de busca ótima: conhecidas as probabilidades de acesso de cada chave.

Aula 22 (04/06/2003): Algoritmo para criação de uma árvore de busca ótima, dadas as chaves e suas probabilidades de acesso: método de programação dinâmica; ilustração do método por um exemplo.

Aula 23 (09/06/2003): B-árvores, uma técnica para armazenamento e recuperação de grandes volumes de dados. Busca, inserção e remoção em B-árvores: O(log_n N) onde o log é na base n= a ordem da B-árvore, N é o número de chaves na B-árvore.

Aula 24 (11/06/2003): Uma aula prática para apresentar a linguagem LISP, rodando vários exemplos.

Aula 25 (16/06/2003): Segunda prova. Matéria: desde a aula 11 até a aula 23 inclusive.