Bacharelado em Ciência da Computação (BCC) e Matemática Computacional (BMC)
Algoritmos e Estruturas de Dados III

Última alteração: Outubro 29, 2002

1º semestre de 2002
Carga Horária: 60 horas
Créditos: 4
Professores: Nivio Ziviani (BCC) e Wagner Meira Jr (BMC)
Monitores: Robert Pereira Pinto e Fabricio Benevenuto de Souza
Horário: terça e quinta, 09:25 - 11:05
Local: salas 2008 (BCC) e 2015 (BMC) do ICEx

Objetivos da Disciplina

A série de disciplinas Algoritmos e Estruturas de Dados I, II e III tem por objetivo apresentar os algoritmos e e as estruturas de dados básicas para o desenvolvimento de programas de computador. Ao final desta disciplina, a terceira e última da série, o aluno deverá ser capaz de usar as principais técnicas empregadas na implementação de algoritmos de pesquisa e de ordenação em memória secundária. Ele deverá ser capaz de analisar algoritmos e saber o que pode e o que não pode ser resolvido eficientemente pelo computador, através do estudo de fundamentos da teoria de complexidade de algoritmos. Ele deverá conhecer os algoritmos básicos para processamento de cadeias de caracteres. Ele deverá ainda conhecer computação paralela e os algoritmos paralelos mais simples.

Ementa

Análise de algoritmos; Algoritmos em Grafos; Complexidade de Algoritmos; Principais dispositivos de memória secundária; Ordenação e pesquisa em memória secundária; Processamento de cadeias de caracteres; Compressão de arquivos; Algoritmos paralelos.

Programa

Análise de Algoritmos

Medida do tempo de execução de um programa, técnicas de análise (Z1.3-1.4).

Algoritmos em Grafos

Terminologia, representação, busca em profundidade, ordenaçção topológica, componentes fortemente conectados, árvore geradora mínima, caminho mínimo (CLR).

Teoria da Complexidade de Algoritmos

Classes , e -completo, algoritmos não-detrminísticos, teorema de Cook, reduções, heurísticas (HS11-12).

Memória secundária

Ordenação externa: intercalação balanceada e intercalação polifásica (Z3.2). Memória virtual (Z5.1). Organização de arquivos: seqüencial, seqüencial indexado, hashing (Z5). Árvore B (Z5.3).

Processamento de Cadeias de Caracteres

Recuperação de informação em textos. Busca exata e aproximada. Algoritmos sem pré-processamento: força bruta, Boyer-Moore e shift-or (FBY10). Compressão de textos (BYR7).

Algoritmos Paralelos

Classificação das arquitetuiras paralelas (Q1). Algoritmos PRAM (Q2). Formas de organizar processadores (Q3). Projeto de algoritmos paralelos (Q6).

Avaliação da Aprendizagem

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

TP 0: Programação C - Matrizes Esparsas
TP 1: Análise de algoritmos
TP 2: NP-Completo
TP 3: Sistema de Memória Virtual
TP 4: Programação Paralela

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. O TP 0, apesar de opcional, é altamente recomendado. Os trabalhos práticos serão individuais. Para cada trabalho prático, alguns dos alunos serão sorteados para entrevista. Veja aqui maiores detalhes sobre Conduta Acadêmica.
4. Curso de Programação de Linguagem C
5. Links sobre interpretadores para Postscript/PDF, programa make e linguagens Pascal e C (cursos e tutoriais)
6. Roteiro para documentar trabalhos práticos.
7. Exemplos de documentação dos trabalhos práticos: Simulação de Monte Carlo e Heurísticas para Caixeiro Viajante
8. Os trabalhos devem ser feitos em linguagem C e entregues impressos. Veja aqui maiores detalhes sobre instruções para a entrega de trabalhos praticos.

Bibliografia

[BYR] R. Baeza-Yates and B. Ribeiro-Neto Modern Information Retrieval, Addison-Wesley, 1999.

[CLR] T. H. Cormen, C. E. Leiserson e R. L. Rivest, Introduction to Algorithms, McGraw-Hill, 1991.

[F] I. Foster, Designing and Building Parallel Programs, http://www.mcs.anl.gov/dbpp/

[K] J. Kitajima, M. Mendes, Introdução aos Processos Leves, JAI 96, ftp://ftp.dcc.ufmg.br/pub/ftp/research/kitajima/jai96.ps

[FBY] Frakes, W. B. e Baeza-Yates, R. (Eds) Information Retrieval Data Structures & Algorithms. Prentice Hall, 1992.

[HS] Horowitz, E. e Sahni, S. Fundamentals of Computer Algorithms. Computer Science Press, 1978.

[L] Lawler, E. L., Lenstra, J. K., Kan, A. H. and Shmoys, D. B. The Traveling Salesman Problem, Wiley, 1985.

[Q] M. J. Quinn, Parallel Computing Theory and Practice, McGraw-Hill, 1994.

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

Planejamento das Aulas

Aula	Mês	Dia	Assunto	Referência	TPs
01	Jun	04	Apresentacao do Curso		TP0 (E)
02		06	Análise de Algoritmos	Z1.3	TP1 (E)
03		11	Análise de Algoritmos	Z1.3
04		13	Análise de Algoritmos	Z1.4
05		18	Análise de Algoritmos	Z1.4
06		20	Grafos: noções	S29-S34 CLR23-CLR27 Z6
07		25	Grafos: noções	S29-S34 CLR23-CLR27 Z6
08		27	Grafos: noções	S29-S34 CLR23-CLR27 Z6
09	Jul	02	Grafos: noções	S29-S34 CLR23-CLR27 Z6	TP2 (E)
10		04	NP-Completo	Z8 HS
11		09	NP-Completo	Z8 HS
12		11	NP-Completo	Z8 HS
13		16	NP-Completo	Z8 HS
14		18	NP-Completo	Z8 HS
15		23	Revisão
16		25	1ª Prova
17		30	Memória secundária	Z5	TP3 (E)
18	Ago	01	Memória secundária	Z5
19		06	Memória secundária	Z5
20		08	Ordenação externa	Z3.2
21		13	Ordenação externa	Z3.2
22		20	Proc. caracteres	Z7 FBY10
23		22	Proc. caracteres	Z7 FBY10
24		27	Algoritmos Paralelos	Q	TP4 (E)
25		29	Algoritmos Paralelos	Q
26	Set	03	Algoritmos Paralelos	Q
27		05	Algoritmos Paralelos	Q
28		10	Algoritmos Paralelos	Q
29		12	Revisão
30		17	Reserva
31		19	Reserva
32		24	Prova final