Engenharia de Controle e Automação
Algoritmos e Estruturas de Dados II

Última alteração: Dezembro 28, 2001

2º semestre de 2001
Carga Horária: 60 horas
Créditos: 4
Professor: Nivio Ziviani
Monitora: Claudine Santos Badue
Horário: terça e quinta, 13:00 -- 14:40
Local: sala 2015 do ICEx

Objetivos da Disciplina

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

Tipos abstratos de dados. Introdução às técnicas de análise de algoritmos. Estruturas de dados estáticas e dinâmicas em memória principal. Algoritmos de pesquisa e de ordenação em memória principal.

Programa

Projeto e Análise de Algoritmos

Projeto de algoritmos; Refinamentos sucessivos; Tipos Abstratos de Dados; Alocação dinâmica de memória; Análise de algoritmos: notações O e .

Estruturas de Dados na Memória Principal

Listas lineares; Pilhas; Filas; Árvores: binárias, balanceadas.

Algoritmos de Pesquisa e Ordenação

Pesquisa em tabelas: seqüencial, binária, transformação de chave (hashing). Árvores de pesquisa: binária, tries, Patricia. Ordenação: Seleção direta, Inserção direta, Shellsort, Quicksort, Heapsort, Mergesort, Radixsort.

Avaliação da Aprendizagem

3 provas	50 pontos
4 trabalhos práticos	50 pontos
Total	100 pontos

TP 1: Listas Lineares
TP 2: Recursividade
TP 3: Ordenação
TP 4: Pesquisa

Política para desconto por atraso

A fórmula para desconto por atraso na entrega do trabalho prático é:

onde d é o atraso em dias úteis. Note que após 5 dias úteis, o trabalho não pode ser mais entregue.

Importante:

1. Não haverá prova suplementar.
2. Todas as provas são individuais e sem consulta.
3. As listas de exercícios a seguir devem ser resolvidas com o objetivo de prepará-lo para as provas:
• Lista 1: Capítulo 1
• Lista 2: Capítulo 2
• Lista 3: Capítulo 3
• Lista 4: Capítulo 4
4. Todos os Trabalhos Práticos são individuais. Isto, evidentemente, não significa que é proibido trocar idéias e discutir alternativas de solução. No entanto, na hora de escrever código, o trabalho deve ser individual. Veja aqui maiores detalhes sobre Conduta Acadêmica. Em cada trabalho prático, cada aluno será entrevistado para explicar as soluções adotadas.
5. Links sobre interpretadores para Postscript/PDF, programa make e linguagens Pascal e C (cursos e tutoriais)
6. Instruções para instalação do GNU Pascal.
7. Roteiro para documentar trabalhos práticos.
8. Exemplos de documentação dos trabalhos práticos: Simulação de Monte Carlo e Heurísticas para Caixeiro Viajante
9. Instruções para a entrega de trabalhos praticos.

Livro Texto

[Z] Ziviani, N. Projeto de Algoritmos Com Implementações em Pascal e C, Editora Pioneira, 1993.

Bibliografia Suplementar

[A] Aho, A.V., Hopcroft, J.E. and Ullman, J.D., Data Structures and Algorithms, Addison-Wesley, 1983.

[B] Baase, S., Computer Algorithms -- Introduction to Design and Analysis, Second Edition, Addison-Wesley, 1988.

[CLR] Cormen, T.H., Leiserson, C.E. and Rivest, R.L., Introduction to Algorithms, MIT Press, Cambridge, Mass., 1992.

[GB] Gonnet, G.H. and Baeza-Yates, R., Handbook of Algorithms and Data Structures: in Pascal and C, Second Edition, Addison-Wesley, 1991.

[HS] Horowitz, Ellis and Sahni, Sartaj., Fundamentals of Data Structures Sixth Printing - Computer Science Press, Inc., 1976.

[K1] Knuth, D., The Art of Computer Programming, Volume 1: Fundamental Algorithms, Addison-Wesley, Second Edition, 1973.

[K2] Knuth, D., The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley, 1973.

[S] Sedgewick, R., Algorithms, Second Edition, Addison-Wesley, 1988.

[W] Wirth, N., Algorithms and Data Structures, Prentice-Hall, 1986.

[W] Wirth, N., Algoritmos e Estruturas de Dados, Prentice-Hall do Brasil LTDA,1989.

Planejamento das Aulas

A programação do curso está apresentada a seguir. Pretende-se seguir rigorosamente este planejamento, principalmente as datas de provas e entregas de trabalhos práticos. A parte do livro texto a ser seguida em cada assunto aparece na coluna "Referência" em primeiro lugar na tabela abaixo.

Aula	Mês	Dia	Assunto	Referência	TPs
01	Ago	07	Tipos Abstratos Dados	Z1.1-2, A1.1-1.3	TP1 (E)
02		09	Análise de Algoritmos	Z1.3, A1.4, S6
03		14	Análise de Algoritmos	Z1.4, A1.5, S6
04		16	Análise de Algoritmos	Z1.4, A1.5, S6
05		21	Listas Lineares	Z2.1, A2.1, S3
06		23	Listas Lineares	Z2.1, A2.2, S3
07		28	Como submeter TP1 (Claudine)
08	Jan	08	Revisão Análise de Algoritmos	Z1.1, Z1.2, Z1.3, Z1.4, A1.5, S6
09		10	Revisão Listas Lineares	Z2.1, A2.2, S3
10		15	Pilhas	Z2.2, A2.3-2.4, S3	TP1(D)*
11		17	Filas	Z2.3, A2.3-2.4, S3	TP2 (E)
12		22	Recursividade	W3.1-3.2
13		24	Recursividade	W3.4
14		29	Recursividade	W3.4
15		31	Reserva
16	Fev	05	1ª Prova
17		07	Ord.: Seleção; Inserção	Z3.1, Z3.1.1-3.1.2, S8, A8.2	TP3 (E)
18		19	Quicksort	Z3.1.4, S9, A8.3
19		21	Quicksort	Z3.1.4, S9, A8.3	TP2 (D)*
20		26	Filas Prior.; HeapSort	Z3.1.5, S11, A4.10
21		28	HeapSort	Z3.1.5, S11, A8.4
22	Mar	07	Comparação Métodos	Z3.1.6, W2.2.8	TP3 (D)*
23		12	2ª Prova
24		14	Pesquisa: Seq., Binária	Z4.1-2, S14	TP4 (E)
25		19	Pesquisa: Seq., Binária	Z4.1-2, S14
26		21	Árvores de pesquisa	Z4.3, W4.4.1-4.4.3, S14
27		26	Árvores de pesquisa	Z4.3, W4.4.1-4.4.3, S14
28	Abr	02	Hashing	Z4.5, S16, A4.7
29		04	Hashing	Z4.5, S16, A4.8
30		09	Reserva		TP4 (D)*
31		16	Prova Final

* As datas de entrega aqui mostradas são aproximadas, a data que vale é a indicada no enunciado do TP.