BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO (BCC), MATEMÁTICA COMPUTACIONAL (BMC) E SISTEMAS DE INFORMAÇÃO (BSI)
ALGORITMOS E ESTRUTURAS DE DADOS III

Última alteração: Novembro 27, 2008

$ {2}^{\underline{\rm o}} $ semestre de 2008
Carga Horária: 60 horas
Créditos: 4
Professores: Wagner Meira Jr e Dorgival Guedes
Estagiário Docente: Pedro Calais
Horário: segundas e quartas, 17:00 - 18:40
Local: Auditório 2 - 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).

Paradigmas de Projetos de Algoritmos

Indução, Recursividade, Algoritmos Tentativa e Erro, Divisão e conquista, Balanceamento, Programação dinâmica, Algoritmos gulosos, Algoritmos aproximados (Z2).

Algoritmos em Grafos

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

Teoria da Complexidade de Algoritmos

Classes $\cal N$, $\cal NP$ e $\cal NP$-completo, algoritmos não-detrminísticos, teorema de Cook, reduções, heurísticas (Z9).

Memória secundária

Ordenação externa: intercalação balanceada e intercalação polifásica (Z4.2). Memória virtual (Z6.1). Organização de arquivos: seqüencial, seqüencial indexado, hashing (Z6). Árvore B (Z6.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 (Z8). 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

4 provas 50 pontos
6 trabalhos práticos 45 pontos
1 resenha 5 pontos
Total 100 pontos

Provas

As provas terão duração total de 1:40 horas, sendo 50 minutos para a resposta às questões constantes da prova e 50 minutos para os alunos corrigirem provas dos colegas. A nota final considera tanto as resposta apresentadas na prova quanto a correção.

Resenha

A resenha é um instrumento importante de síntese e acompanhamento do conteúdo ensinado em sala de aula. As resenhas foram divididas em cinco módulos, sendo cada módulo realizado por um grupo de alunos. A entrega da resenha se fará pelo portal Minha.ufmg.

Os grupos de resenha são:

  1. Análise de Algoritmos e Algoritmos Paralelos - aulas 1 a 6
  2. Paradigmas de Análise de Algoritmos - aulas 7 a 11
  3. Algoritmos em grafos - aulas 12 a 16
  4. Problemas NP-Completo - aulas 17 a 22
  5. Memória Secundária, Ordenação Externa e Processamento de Caracteres - aulas 23 a 33

As datas de entrega das resenhas podem ser vistas no calendário.

Trabalhos Práticos

Durante o semestre o aluno deve executar 6 trabalhos práticos. Há ainda um trabalho prático opcional, o TP0, que tem por objetivo familiarizar o aluno com os conceitos da linguagem C. A execução do TP0 gera pontos extras.



TP 0: Programação C - Elevador

TP 1: Programação Paralela

TP 2: Heurísticas

TP 3: NP-Completo

TP 4: Localidade de Referência

TP 5: Sistema de Paginação

TP 6: Processamento de Cadeia de Caracteres

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


\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.


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, Algoritmos, 2a edição, 2004.

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

[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, Segunda Edição, 2004.

Planejamento das Aulas

Aula Mês Dia Assunto Referência Obs
1 4 8 Análise de Algoritmos Z1.3  
2 6 8 Análise de Algoritmos Z1.4  
3 11 8 Algoritmos Paralelos Q  
4 13 8 Algoritmos Paralelos Q  
5 18 8 Algoritmos Paralelos Q TP0
6 20 8 Algoritmos Paralelos Q  
7 25 8 Paradigmas de Projeto de Algoritmos Z2  
8 27 8 Paradigmas de Projeto de Algoritmos Z2  
9 1 9 Paradigmas de Projeto de Algoritmos Z2 TP1
10 3 9 Paradigmas de Projeto de Algoritmos Z2  
11 8 9 Algoritmos em Grafos Z7  
12 10 9 Algoritmos em Grafos Z7  
13 15 9 Algoritmos em Grafos Z7  
14 17 9 Primeira Prova Aulas 1-10  
15 22 9 Algoritmos em Grafos Z7 TP2
16 24 9 NP-Completo Z9 HS  
17 29 9 NP-Completo Z9 HS  
18 1 10 NP-Completo Z9 HS  
19 6 10 Segunda Prova Aulas 7-15  
20 8 10 NP-Completo Z9 HS  
21 13 10 NP-Completo Z9 HS TP3
22 15 10 NP-Completo Z9 HS  
23 20 10 Memória secundária Z5  
24 22 10 Memória secundária Z5 TP4
25 27 10 Memória secundária Z5  
26 29 10 Terceira Prova Aulas 11-21  
27 3 11 Ordenação externa Z3.2  
28 5 11 Ordenação externa Z3.2  
29 10 11 Proc. caracteres Z8 FBY10  
30 12 11 Proc. caracteres Z8 FBY10 TP5
31 17 11 Proc. caracteres Z8 FBY10  
32 19 11 Proc. caracteres Z8 FBY10  
33 24 11 Reserva    
34 26 11 Reserva    
35 1 12 Reserva    
36 3 12 Prova final Aulas 22-32  
         


Wagner Meira Jr
2008-11-27