Algoritmos e Estruturas de Dados III

Professores: Márcio Carvalho e Wagner Meira Jr.
Monitor:  
Horário: 3a e 5a das 14:55 às 16:35
Local: 2013

Objetivo

Ao final do curso, o aluno deverá dominar as principais técnicas de programação envolvendo memória principal e dispositivos de armazenamento mais lentos e com maior capacidade como discos magnéticos e fitas. Ele também deverá conhecer alguns algoritmos básicos de processamento de caracteres e fundamentos de programação paralela, teoria de complexidade de algoritmos e criptografia. Além de se familiarizar com o ambiente de programação do sistema operacional UNIX e a linguagem C.

Ementa

Descrição e comparação dos dispositivos principais de memória secundária; Ordenação e Pesquisa em Memória Secundária; Busca de Caracteres; Programação paralela; Criptografia e Complexidade de Algoritmos.

Avaliação

Notas

Provas:
duas - 50 % da nota final
Trabalhos Práticos:
quatro - 50 % da nota final.
TP 0:
Programação C - Multiplicação de Matrizes
TP 1:
Sistema de Memória Virtual
TP 2:
Programação Paralela
TP 3:
Pesquisa em Texto e heursíisticas

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. Os trabalhos devem ser feitos em linguagem C e entregues impressos.

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

\begin{displaymath} \frac{2^{d-1}}{0.32} \%\end{displaymath}

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

Roteiro para documentar trabalhos práticos e exemplos de documentação dos trabalhos práticos: Simulação de Monte Carlo e Heurísticas para Caixeiro Viajante .
Instruções para a entrega de trabalhos práticos.

Referências Bibliográficas

[Z]
N. Ziviani, Projeto de Algoritmos com implementações em Pascal e C , Editora Pioneira, 1993.
[Q]
M. Quinn, Parallel Computing Theory and Practice, Second Edition, McGraw-Hill, 1994.
[CLR]
T. Cormem, C. Leiserson, R. Rivest, Introduction to Algorithms, MIT Press, 1992
[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
[HS]
E. Horowitz, S. Sahni. Fundamentals od Computer Algorithms, Computer Science Press, 1978
[S]
R. Sedgewick. Algorithms in C, Addison Wesley, 1990.

Plano de Curso

Aula Data Tema Referência Obs.
1 31/08 Disp. Memória Secundária Z3.1  
2 02/09 Merge-sort Z3.2  
3 09/09 Sort Polifásico Z3.2  
4 14/09 Organização Arquivos Z5 TP0
5 16/09 Árvore B Z5.3  
6 21/09 Memória Virtual Z5.3  
7 23/09 Grafos: noções S29-S34 CLR23-CLR27  
8 28/09 Grafos: noções    
9 30/09 Grafos: noções    
10 05/10 Grafos: noções    
11 07/10 ProcPar: Introdução Q,F,K  
12 14/10 Prova    
13 19/10 ProcPar: Arquiteturas Q,F,K  
14 21/10 ProcPar: Paradigmas   TP1
15 26/10 ProcPar: Algoritmos    
16 28/10 ProcPar: Programação Threads    
17 04/11 ProcPar: Programação Threads    
18 09/11 String Search: RK/AF CLR34  
19 11/11 String Search: KMP/BM    
20 16/11 String Search: LI, PAT    
21 18/11 String Search: Busca aproximada    
22 23/11 Compressão CLR33 TP2
23 25/11 Criptografia: Chave Pública    
24 30/11 Complexidade: Não determinismo CLR36 HS11 S43  
25 02/12 Teorema de Cook, NP-C, NP-A    
26 09/12 Exemplos de reduções    
27 14/12 SNP-A: Guloso Prog. Din. B&B    
28 16/12 SNP-A: Sim. Aneal. Alg. Gen.    
29 21/12 Revisão   TP3
30 23/12 Prova    

Wagner Meira Jr
12/27/1999