MATEMÁTICA COMPUTACIONAL (BMC)
ALGORITMOS E ESTRUTURAS DE DADOS III


1o semestre de 2008
Carga Horária: 60 horas
Créditos: 4
Professores: Jussara Marques de Almeida
Estagiário Docente: Thiago
E-mail de contato para eventuais dúvidas: aeds3_turmaN@dcc.ufmg.br
Horário: terça e quinta, 16:40 -- 18:20
Local: Sala 2015

Avisos

 


  • Notas disponíveis aqui.Provas 4 corrigidas disponíveis na sala 4036. Em caso de algum problema, contactar a professora por email (jussara@dcc.ufmg.br). Em relação aos TPs 3 e 4, contactar o monitor Thiago (thiagopes@gmail.com)


  • Site de submissã do TP4 já está no ar!!!
  • TP4 já está disponível!!!! (sem possibilidade de adiamento, sem política de atraso)
  • Site de Submissao do TP3 no ar!!!
  • TP3 já está disponível!!!!
  • Site de Submissao do TP2 no ar!!!
  • TP2 adiado para 15 de Maio
  • Formato da entrada do TP2 disponível na página do TP
  • Trabalho Prático 2 já está no ar!!!
  • Trabalho Prático 1 já está no ar!!!
  • Site de submissão do TP1 já está no ar!
  • O email aeds3_turmaN@dcc.ufmg.br foi criado para que alunos enviem eventuais dúvidas.

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
4 trabalhos práticos 50 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.



Trabalhos Práticos


Durante o semestre o aluno deve executar 4 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.


Regras para realização e entrega dos TPs estão disponíveis aqui

Clique aqui para submeter o seu Trabalho Prático (TP4).

TP 4: Algoritmos Paralelos (em dupla!!!, sem política de atraso, sem adiamento)

TP 3: Sistema de Memória Virtual (em dupla!!!)

TP 2: Passeio pela França (em dupla!!!)

TP 1: Paradigmas de Projeto de Algoritmos - LIMPA-TUDO (2)

TP 0: Programação C - LIMPA-TUDO


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.

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.
  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 (ou C++). Não serão aceitos trabalhos codificados em outra linguagem.
  9. Regras para submissão dos trabalhos serão postadas em breve neste link.

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

Planejamento das Aulas

Aula Mês Dia Assunto Referência TPs
1 Fevereiro 26 Análise de algoritmos cap 1  
2 Fevereiro 28 Análise de algoritmos cap 1  
3 Março 4 Análise de algoritmos cap 1  
4 Março 6 Paradigmas cap 2  
5 Março 11 Paradigmas cap 2  
6 Março 13 Paradigmas cap 2  
7 Março 18 Algoritmos em Grafos cap 7  
Março 20 Recesso - páscoa
8 Março 25 Complexidade cap 9  
9 Março 27
10 Abril 01
11 Abril 03
12 Abril 08
13 Abril 10
14 Abril 15
15 Abril 17
16 Abril 22
17 Abril 24
Abril 29 Recesso - Mostra das profissões
Maio 01 Feriado - Dia do Trabalho
18 Maio 06
19 Maio 08
20 Maio 13
21 Maio 15
22 Maio 20
Maio 22 Corpus Christi
23 Maio 27
24 Maio 29
25 Junho 03
26 Junho 05
27 Junho 10
28 Junho 12 Paralelismo - threads pthreads  
29 Junho 17 Paralelismo Paralelismo
30 Junho 19
31 Junho 24
32 Junho 26
33 Julho 01
34 Julho 03


Jussara M. Almeida
2008-02-25