Avisos:

Todas as notas.

A entrega de exercícios pode ser ou em papel ou por email.
Se voce entregar por email, mande para song"at"ime"ponto"usp"br".
Se prefere entregar em papel, entregue em aula ou na Sala 293 Bloco A (pode ser colocado por baixo da porta se eu não estiver na sala). Neste caso, mande-me um email avisando.

Disciplina oferecida pela Unidade: Instituto de Matemática e Estatística

Departamento: Departamento de Ciência da Computação

Professor responsável: Siang Wun Song

Telefones: 3091-6141, 3091-6135 (Secretaria do Depto.)

Sala do Professor: Sala 293 (2.o andar) - Bloco A do IME

Monitor da disciplina: Não há.

Disciplina oferecida: No curso de pós-graduação no IME/USP

Pré-requisito desejável: Boa experiência em alguma linguagem de programação alto nível (e.g., C, C++, Java, etc.).

Local das aulas: Sala 241 - Bloco A - 2.o andar - IME/USP

Horário das aulas: 3.a feiras: 10-12 h e 5.a feiras: 8-10 h

Programa:

• Preliminares: Complexidade de algoritmos.
• Conceitos de tipos abstratos de dados.
• Listas lineares: pilhas, filas, filas duplas, filas de prioridade.
• Implementação sequencial e ligada.
• Coleta de lixo.
• Árvores: árvores binárias, algoritmos de travessia, árvore de busca, árvore binária de busca ótima, árvore rubro-negra,, árvore-B.
• Conceitos da linguagem LISP.

Bibliografia:

• T. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms, second edition, The MIT Press, 2005.
• N. Wirth. Algorithms + Data Structures = Programs. Prentice Hall, 1976.
• D. E. Knuth. The Art of Computer Programming. Volume 1, Addison Wesley, 1973.
• A. V. Aho, J. E. Hopcroft, and J. D. Ullman. Data structures and algorithms. Addison Wesley, 1987.
• J. L. Szwarcfiter e L. Markenzon. Estruturas de Dados e seus Algoritmos. LTC Editora, 1994.
• A. Drozdek. Estrutura de Dados e Algoritmos em C++. Thompson, 2002.
• N. Ziviani. Projeto de Algoritmos com Implementações em Pascal e C. Livraria Pioneira Editora, São Paulo, 1993.

Slides usados nas aulas:

• Informações sobre a disciplina (pdf 62K). (Aula 1)
• Complexidade de algoritmos (pdf 210K). (Aulas 1 e 2)
• Listas Lineares (pdf 460K). (Aulas 3, 4, 5 e 6)
• Fila de prioridade (pdf 134K). (Aulas 7 e 8)
• Coletor de lixo (garbage collector) (pdf 156K). (Aulas 8 e 9)
• Árvores e árvores binárias (pdf 282K). (Aulas 9, 10 e 11)
• Árvore binária de busca (pdf 349K). (Aulas 13, 14 e 15)
• Árvore binária de busca ótima (pdf 362K). (Aulas 16, 17 e 18)
• Árvore rubro-negra (pdf 209K). (Aulas 19 e 20)
• B-Árvores (pdf 431K). (Aula 21)
• Uma aula prática sobre LISP (pdf 137K). (Aula 22)

Critérios de avaliação:Provas, exercícios e programas

• Duas provas P1 e P2 (mais uma terceira opcional): média P.
• 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

Regime de oferecimento: Cada semestre (1.o semestre de cada ano)

Carga horária semanal e número de créditos: 4 horas - 8 créditos

Data da primeira prova:
Dia 29/04/2008 (terça-feira). Prova com consulta.
Matéria: até a aula 10 inclusive.

Data da segunda prova:
Dia 26/06/2008. Prova com consulta.
Matéria: da aula 11 à aula 21 inclusive.

Data da terceira prova (prova substitutiva opcional):
Dia 01/07/2008. Prova com consulta.
Matéria: toda a matéria, da aula 1 até a aula 21 inclusive.

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

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

Exercícios (essa lista pode ser alterada):

• Exercício 1 (Entregar até 25/03/2008.)
• Exercício 2 (Entregar até 22/04/2008.)
• Exercício 3 (em postscript .ps) (em .pdf) (Entregar até 29/04/2008 .)

Programas (essa lista pode ser alterada):

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é 10/04/2008.)
  
• Programa 2 (.html) (Entregar até 27/05/2008.)
• Programa 3. (Entregar até 26/06/2008.)

Assuntos tratados em aulas:

Assuntos tratados em aulas:

Aula 2 (06/03/2008): 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 superior (upper bound) e cota inferior (lower bound). Exemplo de projeto de algoritmos eficientes para calcular o n-ésimo termo da sequência de Fibonacci. Slides sobre complexidade de algoritmos (continuação) (pdf 210K). Passar a Lista 1 de exercícios.

Aula 3 (11/03/2008): Listas lineares: pilha e fila. Conceito de tipos abstratos de dados. Encapsulamento e ocultamento de informação. Separação da especificação de um tipo de dado e da sua implementação. Alocação de memória sequencial. Representação de uma pilha em alocação sequencial: inserção e remoção. Slides sobre listas lineares (pdf 460K).

Aula 4 (13/03/2008): Representação de uma fila (circular) 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). Alocação ligada ou encadeada. Pilhas implementadas com alocação ligada. Slides sobre listas lineares - continuação (pdf 460K). Passar o . Programa 1.

Aula 5 (25/03/2008): Filas em alocação ligada. Várias maneiras alternativas 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. Slides sobre listas lineares - continuação (pdf 460K).

Aula 6 (01/04/2008): Passar Exercício 2 (em .html). 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. Aplicações da ordenação topológica. Um algoritmo eficiente para obter uma ordem topológica. Slides sobre listas lineares - continuação (pdf 460K).

Aula 7 (03/04/2008): Passar o Exercício 3 .pdf. Concluir o algoritmo de ordenação topológica. 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). Slides sobre Fila de Prioridade (pdf 136K).

Aula 8 (08/04/2008): Concluir o assunto fila de prioridade. Comentar o artigo de J. Stolfi sobre heapsort. Coletor de lixo (garbage collector) - 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. Slides sobre Coletor de lixo (garbage collector) (pdf 156K).

Aula 9 (10/04/2008): Concluir o assunto coletor de lixo. Árvore. Definições e exemplo. Nomenclatura sobre vários termos usados em árvores. Slides sobre árvores e árvores binárias (pdf 282K).

Aula 10 (22/04/2008): Passar o Programa 2: soma de duas matrizes esparsas usando cabeças de lista, e listas ortogonais. 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). Impressão de árvore por meio do procedimento printtree (usando uma ordem de percurso da árvore semelhante à in-ordem). Modos de percorrer uma árvore binária: pré-ordem, in-ordem. pós-ordem. Dar algoritmos recursivos e para o percurso pré-ordem e in-ordem. Slides sobre árvores e árvores binárias - continuação (pdf 282K).

Aula 11 (24/04/2008): Dar um algoritmo não recursivo (usando uma pilha) para percurso in-ordem. Comentar o percurso por nível ou por largura (breadth-first), que deve usar uma fila, e o percurso por profundidade (depth-first). 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. Slides sobre árvores e árvores binárias - continuação (pdf 282K).

Aula 12 (29/04/2008): Primeira prova.

Aula 13 (08/05/2008): Árvore binária de busca: conceitos e complexidade. Busca na árvore de busca (function loc). Inserção na árvore binária de busca. 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). Slides sobre árvore binária de busca (pdf 349K).

Aula 14 (13/05/2008): 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. Slides sobre árvore binária de busca (pdf 349K) - continuação.

Aula 15 (15/05/2008): Passar o Programa 3. 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. Slides sobre árvore binária de busca (pdf 349K) - continuação.

Aula 16 (20/05/2008): 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. Slides sobre árvore binária de busca ótima (pdf 362K).

Aula 17 (27/05/2008): 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. Slides sobre árvore binária de busca ótima (pdf 362K) - continuação.

Aula 18 (03/06/2008): Apresentar de forma sucinta o algoritmo da construção da árvore binária de busca ótima e discutir a sua complexidade. Slides sobre árvore binária de busca ótima (pdf 362K) - continuação.

Aula 19 (05/06/2008): Árvore rubro-negra: da classe de árvores binárias de busca ditas balanceadas. Definição e propriedades da árvore rubro-negra. Altura da árvore rubro-negra. Operações rotação: left-rotate e right-rotate. Complexidade das operações de rotação. Inserção em uma árvore rubro-negra. Slides sobre árvore rubro-negra (pdf 209K).

Aula 20 (10/06/2008): Inserção em uma árvore rubro-negra: rotina para re-arranjar a árvore caso a propriedade 2 ou 4 esteja violada. Discutir sem mostrar detalhes a operação de remoção. Slides sobre árvore rubro-negra - continuação (pdf 209K).

Aula 21 (12/06/08): 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. B-Árvores (pdf 431K).

Aula 22 (19/06/08): (Obs: Essa aula sobre LISP não entra nas provas.) Conceito da linguagem e uma pequena demonstração. Slides sobre a aula LISP (pdf 137K). Para quem quer brincar um pouco com o programinha nextterm.lsp, pode pegar o prorama aqui: nextterm.lsp. Execute-o no MuLISP com o comando (rds nextterm.lsp) depois do prompt $.

Aula 23 (26/06/08): Segunda Prova.

Aula 24 (01/07/08): Terceira Prova (opcional).