Universidade Federal de Minas Gerais
Departamento de Ciência da Computação

BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO
ALGORITMOS E ESTRUTURAS DE DADOS II

2o semestre de 2009
Carga Horária: 60 horas
Créditos: 4
Professora: Jussara Almeida
Estagiário Docente:
Horário: segunda e quarta, 11:10 -- 12:50
Local: sala 2013

Avisos

Bem vindos ao site da disciplina AEDS2 - turma C, 2o semestre de 2009

Objetivos

Apresentar os algoritmos e as estruturas de dados básicas para o desenvolvimento de programas de computador. Ao final do curso o aluno deverá ser capaz de utilizar a programação modular, dominando as principais técnicas utilizadas na implementação de estruturas de dados básicas, de algoritmos de pesquisa e de algoritmos de ordenação em memória principal. Ele ainda deverá ser capaz de efetuar análises simples da complexidade de algoritmos.

Ementa

Estruturas de Dados e de Tipos Abstratos de Dados; Alocação Dinâmica de Memória; Algoritmos Recursivos; Estruturas de Dados em Memória Principal; Algoritmos de Pesquisa em Memória Principal; Pesquisa Digital, Algoritmos de Ordenação Interna.

Programa

1. Conceito de Estruturas de Dados e de Tipos Abstratos de Dados. Alocação Dinâmica de Memória. Análise de Algoritmos. Medida de Tempo de Execução. Notação O.
2. Algoritmos Recursivos.
3. Estrutura de Dados na Memória Principal: Listas Lineares. Pilhas. Filas. Alocação Sequencial e Encadeada. Árvores. Árvores Binárias. Árvores Balanceadas.
4. Algoritmos de Ordenação Interna: Seleção Direta. Inserção Direta. Seleção e Troca. Shellsort. Heapsort. QuickSort. Mergesort. Radixsort.
5. Algoritmos de Pesquisa em Memória Principal: Dicionários. Pesquisa em Tabelas. Pesquisa Sequencial. Pesquisa Binária. Pesquisa Fibonacciana. Pesquisa com Transformação de Chaves. Árvores Binárias de Pesquisa.
6. Pesquisa Digital: Árvores de Pesquisa Digital. Árvores Tries. Árvores Patrícia.

Avaliação da Aprendizagem

3 provas	(15+15+20) pontos
4 trabalhos práticos	(10+12+12+12) pontos
4 listas de exercícios (em sala)	(2+2+2+2) pontos

Trabalhos Práticos

Trabalho Prático 4

Trabalho Prático 3

Trabalho Prático 2

Trabalho Prático 1

Regras para realização e entrega dos TPs

Importante

1. Não haverá prova suplementar.
2. Todas as provas são individuais e sem consulta.
3. Compilador devPASCAL (software livre). Se tiver problemas, pegue o instalador aqui.
4. Compilador devC . Um microtutorial de como criar um projeto no devC pode ser encontrado aqui/
5. Curso de C
6. Bubblesort
7. Merge Sort e Distribution Counting
8. Radix Sort
9. Radix Exchange : Animação
10. Straight Radix: Animação
11. Animações dos algoritmos de ordenação:

    http://math.hws.edu/TMCM/java/xSortLab/

    http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

    http://www.dcc.unicamp.br/~rezende/ASTRAL/Sort.exe  (Arquivo executável para Windows)

12. Jogo Belesminha para treinar recursividade
13. Software ProfesSort para auxílio ao aprendizado de algoritmos de ordenação

Bibliografia

• Livro Texto: Nívio Ziviani, Projeto de Algoritmos com Implementações em Pascal e C, Segunda Edição, Editora Pioneira, 2004.
• Cormen, T.H., Leiserson, C.E. and Rivest, R.L., Introduction to Algorithms, MIT Press, Cambridge, Mass., 1992.
• Aho, A.V., Hopcroft, J.E. and Ullman, J.D., Data Structures and Algorithms, Addison-Wesley, 1983.
• Sedgewick, R., Algorithms, Second Edition, Addison-Wesley, 1988.
• Wirth, N., Algorithms and Data Structures, Prentice-Hall, 1986.

Planejamento das Aulas

Aula	Mês	Dia	Assunto	Referência	TPs
1	Agosto	17	Apresentação do curso / Tipo Abstrato de Dados	TAD
2	Agosto	19	Análise de Complexidade	Cap 1 (parte 1)
3	Agosto	24	Análise de Complexidade	Cap 1 (parte 1)
4	Agosto	26	Análise de Complexidade	Cap 1 (parte 1)
5	Agosto	31	Recursividade / Análise	Cap 1 (parte 3)
6	Setembro	02	>Recursividade / Análise	Cap 1 (parte 3)
7	Setembro	09	Lista de Exercícios 1
8	Setembro	14	Alocação Dinâmica	Alocação Dinâmica
9	Setembro	16	Listas Lineares	Cap 3
10	Setembro	21	Listas Lineares	Cap 3
11	Setembro	23	Prova 1
12	Setembro	28	Pilhas e Filas	Cap 3
13	Setembro	30	Árvores	Árvores
14	Outubro	05	Lista de Exercírcios 2
15	Outubro	07	Ordenação	Cap 4
16	Outubro	14	Ordenação	Cap 4
17	Outubro	19	Ordenação	Cap 4
18	Outubro	21	Ordenaçoão	Cap 4
19	Outubro	26	Ordenação	Cap 4
20	Outubro	28	Ordenaçã	Cap 4
21	Novembro	04	Ordenacao	Cap 4
22	Novembro	09	Lista de Exercícios 3
23	Novembro	11	Prova 2
24	Novembro	16	Pesquisa	Cap 5
25	Novembro	18	Pesquisa	Cap 5
26	Novembro	23	Pesquisa	Cap 5
27	Novembro	25	Pesquisa	Cap 5 (parte 2)
28	Novembro	30	Pesquisa	Cap 5 (parte 2)
29	Dezembro	02	Lista de Exercícios 4
30	Dezembro	09	Prova 3

Links de Interesse

• Animação de algoritmos e estruturas de dados

  • Diversos:
    • O livro "Data Structures and Algorithms in Java," Second Edition. Robert Lafore, 2002, vem acompanhado de diversas animações de algoritmos vistos no curso.

  • Ordenação:
    • Algoritmos de ordenação: passo a passo - Pode ser usado no browser e permite a execução dos algoritmos passo a passo.
    • Algoritmos de ordenação: execução - Grupo da Unicamp - Programa para Windows - visualização da animação
    • Algoritmos de ordenação: execução - Departamento de Computação da University of British Columbia (UBC) - Vancouver. Animação no browser.
    • Diversas estruturas de Dados e algoritmos, incluindo ordenação (indica o que vai fazer na execução); listas encadeadas, buscas, etc. - Departamento de Computação e Engenharia de Software, University of Canterbury, Nova Zelândia
    • Veja no Google outros sites para animação de algoritmos

  • Árvores:
    • University of Michigan - Department of Computer and Information Science - Animação sobre vários tipos de árvores e caminhamentos.

    • Árvores Binárias de Pesquisa
      • Animação livro do Richard Lafore - Começa com uma árvore binária e permite que várias operações sejam feitas sobre ela. Vai descrevendo o que está fazendo passo a passo.
      • Johns Hopkins University - Computer Science Department - Permite inserir, pesquisar e retirar.
      • Institute of Operating Systems and Computer Networks, Alemanha - Começa com uma árvore completa e permite acompanhar operações sobre ela.

    • Árvores 2-3-4
      • University of New Mexico - Department of Computer Science - Permite inserir, pesquisar e retirar - não pode repetir chaves
      • Animação livro do Richard Lafore - Começa com uma árvore 2-3-4, e pode inserir ou buscar elementos. Vai descrevendo passo a passo o que está fazendo.
      • Ohio State University - Department of Computer Science and Engineering - Pode inserir, pesquisar e retirar e permite a repetição de chaves.
    • Árvores B
      • Permite inserir, pesquisar, retirar.

  • Tabelas Hash
    • University of Auckland, Department of Computer Science. - Mostra o hash de palavras com tratamento de colisões por endereçamento aberto passo a passo.
    • York University, Algorithmics Animation Workshop - Faz o hash com tratamento de colisão por lista com chave inteira. Permite inserção, retirada e busca.
    • Animação livro do Richard Lafore - Hash com endereçamento aberto. Permite inserir, procurar e retirar, mostrando passo a passo.
    • Animação livro do Richard Lafore - Hash com listas encadeadas. Permite inserir, procurar e retirar, mostrando passo a passo.