"Office-hours"

Semestre: 1.o semestre de 2005

Horário:

2.a feiras: 14 - 16 h

4.a feiras: 16 - 18 h

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

Data da primeira prova:
Dia 4 de maio de 2005 (quarta feira).
(Prova com consulta. Matéria até a aula 10 inclusive.)

Data da segunda prova:
Dia 22 de junho de 2005 (quarta feira).
(Prova com consulta. Matéria desde a aula 11 até a aula 21 inclusive.)

Data da terceira prova (opcional ver critério de avaliação abaixo):
Dia 29 de junho de 2005 (quarta feira).
(Prova com consulta. Matéria: aulas 1 até a aula 21 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 2005.

Conteúdo da disciplina:

• Preliminares: Complexidade de algoritmos (em .html ou em .pdf)
• Listas lineares: pilhas, filas, filas duplas, filas de prioridade (em .ps ou em .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 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é 6 de abril de 2005.)
• Exercício 2 (Entregar até 27 de abril de 2005 .)
• Exercício 3 (em postscript .ps) (em .pdf) (Entregar até xxxx .)

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). Os resultados testes devem ser impressos pelo seu programa. Não é para voce digitar esses testes. Não entregue o diskette.

• Programa 1 (Entregar até 27/04/2005 .)
  
• Programa 2 (.html) (Entregar até 11/05/2005.)
• Programa 3. (Entregar até 20/06/2005.)

Provas:

Assuntos tratados em aulas:

Assuntos tratados em aulas:

Aula 2 (16/03/2005): Conceito de upper bound (limite ou cota superior) e de lower bound (limite ou cota inferior). Introduzir 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. Passar para fazer em casa (e entregar) Exercício 1.

Aula 3 (28/03/2005): Listas lineares: pilha e fila. 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. 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 4 (30/03/2005): Fila circular (em alocação sequencial). Alocação ligada ou encadeada. Pilhas implementadas com alocação ligada. Passar o Programa 1.

Aula 5 (06/04/2005): Filas em alocação ligada. Pedir para ler a apostila sobre as 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), e (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). Um esquema que permite caminhar nos dois sentidos (para direita e para esquerda) em uma lista linear ligada com um campo apenas para link.

Aula 6 (11/04/2005): 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. Problema de ordenação topológica: relações de ordem parcial, propriedades, definição de ordem topológica.

Aula 7 (13/04/2005): Aplicações da ordenação topológica, um algoritmo eficiente para obter uma ordem topológica.

Aula 8 (18/04/2005): Passar Exercício 2 (em .html). Passar o Exercício 3 (em .ps ou em .pdf). 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. Algoritmos de inserção e remoção: ambos de complexidade O(log n).

Aula 9 (25/05/05): Passar o Programa 2: soma de duas matrizes esparsas usando cabeças de lista, e listas ortogonais. Coletor de lixo (garbage collector) (.pdf 42K) - rotina do sistema para identificar e recuperar dados não mais ativos. Vemos dois métodos. Método 1 "marca-varre ("mark-scan"): é o método mais geral (sem funciona) e consiste de duas fases, uma de marcação e outra de varredura. Método 2 (mais restrito, não funciona em certas condições) chamado método de contador de referências. Não recolhe o lixo constituído de listas circulares, nem quando o contador tem seu valor máximo já atingido.

Aula 10 (27/04/2005): Á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). Construção de árvore de altura mínima, perfeitamente balanceada (função tree).

Aula 11 (02/05/2005): Resolver dúvidas de listas de exercícios. Impressão de árvore por meio do procedimento printtree (usando uma ordem de percurso da árvore semelhante à in-ordem). 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, e o percurso por profundidade (depth-first).

Aula 12 (04/05/2005): Primeira Prova.

Aula 13 (09/05/05): Aplicação dos métodos para percorrer árvores: mostrar um algoritmo para calcular as alturas de todos os nós de uma árvore binária dada, usando pós-ordem e uma rotina apropriada de visita. Conversão de uma floresta de árvores genéricas (com qualquer número de filhos) para uma árvore binária. Explicar e passar o Programa 3.

Aula 14 (11/05/05): Arvore binária de busca: conceitos e complexidade. Busca na árvore de busca (function loc). Inserção na árvore binária de busca (procedimento search, ou seja, busca com inserção). Comentário sobre a complexidade de busca e de inserção: depende da altura da árvore. O 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 15 (16/05/05): 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 16 (18/05/05): 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.

Aula 17 (30/05/05): Árvore de busca AVL: definição de árvore balanceada, estrutura da pior árvore AVL.

Aula 18 (01/06/05): Inserção e remoção em árvore de AVL, por meio de rotações visando o rebalanceamento: rotação LL, rotação RR, rotação LR e rotação RL. (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 19 (06/06/05): Introduzir o conceito de árvore de busca ótima: conhecidas as probabilidades de acesso de cada chave. Algoritmo para criação de uma árvore de busca ótima, dadas as chaves e suas probabilidades de acesso.

Aula 20 (08/06/05): Obtenção árvore binária de busca ótima, dadas todas as chaves e suas probabilidades (ou frequências) de acesso, pelo método de programação dinâmica; ilustração do método por um exemplo.

Aula 21 (13/06/05): Uso da técnica de programação dinâmica para resolver um outro problema: multiplicação de n matrizes. 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 22 (15/06/05): Aula prática sobre LISP. Uma pequena introdução da linguagem LISP. Ver os vários sistemas LISP na Página do Prof. Marcelo Melo. (Obs: o assunto LISP não entra nas provas.)

Aula 23 (20/06/05): Aula para tirar dúvidas.

Aula 24 (22/06/05): Segunda Prova.

Aula 25 (29/06/05): Terceira Prova (opcional).