PCC104 Projeto e Análise de Algoritmos

Universidade Federal de Ouro Preto
Instituto de Ciências Exatas e Biológicas
Departamento de Computação
Professor: David Menotti (menottid@gmail.br)

2010/1

1 Novidades

Disponível Trabalho Prático 6 (18/12/2010-23:30)
Disponível Lista de Exercícios 2 (03/07/2010 - 23:30)
Disponível Trabalho Prático 5 (03/07/2010 - 14:00)
Disponível Trabalho Prático 4 (14/06/2010 - 19:00)
Disponível notas do Trabalho Prático 1 (14/06/2010 - 00:20)
Disponível notas da 1ł. Lista (30/05/2010 - 11:00)
Disponível Trabalho Prático 3 (24/05/2010 - 21:30)
Disponível Trabalho Prático 2 (05/05/2010 - 19:30)
Disponível Trabalho Prático 1 (29/03/2010 - 16:00)
Disponível Lista de Exercícios 1 - Complexidade (29/03/2010 - 12:30)
Disponível arquivos para teste do Trabalho Prático 0 (23/03/2010 - 16:30)
Disponível Trabalho Prático 0 - Warm up (17/03/2010 - 15:45)
Divulgado o cronograma tentativo para a disciplina (08/03/2010-15:00)

2 Dados gerais

Carga horária:	4 aulas teóricas (semanal) / 60 horas de aula (semestral) ⇒ 72 horas-aula

3 Horário

Terça-feira e Quinta-feira das 10:20 as 12:00

Turma 21 - Sala 201 (Pavilhão Central de Aulas - PCA)
Turma 22 - Sala 201 (Pavilhão Central de Aulas - PCA)

4 Objetivos

Apresentar um conjunto de técnicas de projeto e de análise de algoritmos, com ênfase em estruturas de dados e nos algoritmos relacionados. A comparação de alternativas é sempre feita utilizando-se técnicas de análise de algoritmos. Ao final da disciplina o aluno deverá ser capaz de lidar com classes específicas de problemas e soluções eficientes para eles, dominando as principais técnicas utilizadas para projetar e analisar algoritmos e sabendo decidir o que pode e o que não pode ser resolvido eficientemente pelo computador

5 Ementa

Análise de algoritmos.
Limite inferior para diferentes classes de problemas.
Paradigmas de projeto de algoritmos.
Problemas NP-Completo.
Algoritmos paralelos.
Tópicos: algoritmos em grafos, noções de recuperação da informação, algoritmos para casamento de padrão, compressão de dados.

6 Avaliação da Aprendizagem

Dois testes teóricos	3 pontos
Cinco trabalhos práticos	5 pontos
Duas listas de exercícios	2 pontos
Exame especial	não há!

7 Referências Bibliográficas

Bibliografia Básica

[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 3 edition, 2009. ISBN-13: 978-0-262-53305-8.

[2] M. J. Quin. Parallel Computing Theory and Practice. McGraw-Hill, 1994. ISBN-10: 0071138005.

[3] E. Horowitz and S. Sahni. Fundamentals of Computer Algorithms. Computer Science Press, 1978. ISBN-10: 0716780453.

[4] J. L. Gersting. Fundamentos Matemáticos para a Ciência da Computação. Editora LTC, 5 edition, 2004. ISBN-13: 978-85-21614227.

Bibliografia Complementar

[1] D. E. Knuth. The Art of Computer Programming. Addison-Wesley, 1998. ISBN-10: 0201485419.

[2] R. Sedgewick. Algorithms. Addison-Wesley, 2 edition, 1988. ISBN-10: 0201066734.

[3] N. Ziviani. Projeto de Algoritmos com Implementações em Java e C++. Cengage Learning, 2006. ISBN-10: 8522105251.

Bibliografia Auxiliar

[1] V. V. Mizrahi. Treinamento em Linguagem C: módulo 1. Makron Books, 2 edition, 2008. ISBN-13: 978-85-7605-191-6.

[2] V. V. Mizrahi. Treinamento em Linguagem C: módulo 2. Makron Books, 2005. ISBN-13: 978-85-3461-423-7.

[3] Paulo Feofiloff. Algoritmos em linguagem C. Editora Campus, 2009. ISBN-13: 978-85-352-3249-3.

[4] H. Schildt. C Completo e Total. Pearson/Makron Books, 3 edition, 1997. ISBN-10: 8534605955.

8 Cronograma tentativo para 1o. semestre de 2010 (34 encontros)



Encontro	Turmas	Data	Dia da semana	Atividade


1	T21	01/03/2010	Segunda-feira	Semana Inaugural do Mestrado
2	T21	03/03/2010	Quarta-feira	Semana Inaugural do Mestrado
3	T21	08/03/2010	Segunda-feira	Apresentação da Disciplina
				Teste Inicial para avaliar conhecimentos em Projeto e Análise de Algoritmos
4	T21/T22	10/03/2010	Quarta-feira	2o. Teste Inicial para avaliar conhecimentos em Algoritmos e Estruturas de Dados
5	T21/T22	15/03/2010	Segunda-feira	Análise de Algoritmos [slides] (Introdução)
6	T21/T22	17/03/2010	Quarta-feira	Análise de Algoritmos [slides] - a partir do slide 38 (TAD’s x Medida de Custo x Oráculo)
7	T21/T22	22/03/2010	Segunda-feira	Análise de Algoritmos [slides] - a partir do slide 78 (Ordem de Complexidade)
8	T21/T22	24/03/2010	Quarta-feira	Análise de Algoritmos [slides] - a partir do slide 129 (Técnicas de Análise de Algoritmos)
		29/03/2010	Segunda-feira	Ausência Professor
9	T21/T22	31/03/2010	Quarta-feira	Análise de Algoritmos [slides] - a partir do slide 156 (Teorema Mestre)
		05/04/2010	Segunda-feira	Ausência Professor
10	T21/T22	07/04/2010	Quarta-feira	Análise de Algoritmos [slides] - a partir do slide 184 (Análise Amortizada)
11	T21/T22	12/04/2010	Segunda-feira	Paradigmas de Projeto de Algoritmos [slides] (Indução Matemática)
12	T21/T22	14/04/2010	Quarta-feira	Paradigmas de Projeto de Algoritmos [slides] - a partir do slide 19 (Indução Matemática)
13	T21/T22	19/04/2010	Segunda-feira	Paradigmas de Projeto de Algoritmos [slides] - a partir do slide 33 (Indução Matemática e Algoritmos)
14	T21/T22	21/04/2010	Quarta-feira	Paradigmas de Projeto de Algoritmos [slides] - a partir do slide 44 (Recursividade)
15	T21/T22	26/04/2010	Segunda-feira	Paradigmas de Projeto de Algoritmos [slides] - a partir do slide 63 (BackTracking)
16	T21/T22	28/04/2010	Quarta-feira	Exercícios Recursividade/BackTracking
17	T21/T22	03/05/2010	Segunda-feira	Paradigmas de Projeto de Algoritmos [slides] - a partir do slide 71 (Divisão e Conquista)
18	T21/T22	05/05/2010	Quarta-feira	Paradigmas de Projeto de Algoritmos [slides] - a partir do slide 98 (Balanceamento x Programação Dinâmica)
19	T21/T22	10/05/2010	Segunda-feira	Paradigmas de Projeto de Algoritmos [slides] - a partir do slide 118 (Algoritmos Gulosos)
20	T21/T22	12/05/2010	Quarta-feira	Paradigmas de Projeto de Algoritmos [slides] (Algoritmos Aproximados)
		17/05/2010	Segunda-feira	Ausência Professor
21	T21/T22	19/05/2010	Quarta-feira	Teoria dos Grafos [slides] (Definições I)
22	T21/T22	26/05/2010	Quarta-feira	Teoria dos Grafos [slides] - a partir do slide 40 (Definições II)
23	T21/T22	26/05/2010	Quarta-feira	Teoria dos Grafos [slides] - a partir do slide 74 (Definições III x Ciclo Euleriano)
24	T21/T22	09/06/2010	Quarta-feira	Teoria dos Grafos [slides] - a partir do slide 109 (Ciclo Hamiltoniano)
25	T21/T22	14/06/2010	Segunda-feira	Teoria dos Grafos [slides] - a partir do slide 138 (Contando caminhos, Isomorfismo e Busca em Largura)
26	T21/T22	14/06/2010	Segunda-feira	Teoria dos Grafos [slides] - a partir do slide 185 (Busca em Profundidade)
27	T21/T22	16/06/2010	Quarta-feira	Teoria dos Grafos [slides] - a partir do slide 211 (Ordenação Topológica x Comp. Fortemente Conect.)
28	T21/T22	16/06/2010	Quarta-feira	1o. Teste (1,5 pontos) - Análise de Complexidade de Algoritmos
		21/06/2010	Segunda-feira	Ausência Professor
29	T21/T22	23/06/2010	Quarta-feira	Processamento de Cadeias de Caracteres (Prof. Álvaro Jr.) [slides]
30	T21/T22	23/06/2010	Quarta-feira	Processamento de Cadeias de Caracteres (Prof. Álvaro Jr.) [slides]
		28/06/2010	Segunda-feira	Não houve aula - Dispensa por pedido de Pró-Reitor de Pesquisa
31	T21/T22	30/06/2010	Quarta-feira	2o. Teste (1,5 pontos) - Paradigmas de Projeto de Algoritmos
32	T21/T22	05/07/2010	Segunda-feira	Algoritmos Paralelos (Prof. Joubert) [slides]
33	T21/T22	05/07/2010	Segunda-feira	Teoria da Complexidade - NP-Completo [slides]
34	T21/T22	07/07/2010	Quarta-feira	Algoritmos Paralelos (Prof. Joubert) [slides]
35	T21/T22	07/07/2010	Quarta-feira	Teoria da Complexidade - NP-Completo [slides]

9 Trabalhos Práticos

Trabalho Prático 0 - 0,5 pontos extra - entrega 30/03/2010
- arquivos para teste
Trabalho Prático 1 - 1,0 ponto - entrega 02/05/2010
Trabalho Prático 2 - 1,0 ponto - entrega 18/05/2010
Trabalho Prático 3 - 1,0 ponto - entrega 08/06/2010
Trabalho Prático 4 - 1,0 ponto - entrega 27/06/2010
Trabalho Prático 5 - 1,0 ponto - entrega 14/07/2010
Trabalho Prático 6 - 1,0 ponto - entrega 04/08/2010

10 Listas de Exercícios

Lista de Exercícios 1 - 1,0 ponto - entrega 18/04/2010
Lista de Exercícios 2 - 1,0 ponto - entrega 25/07/2010

11 Listas de Exercícios (BCC201 - Introdução à Programação)

Lista de Exercícios 1 - Entrada/Saída, Atribuição e Estrutura Seqüencial (35 exercícios, 7 para cada aluno) [solução] [professor]
Lista de Exercícios 2 - Estrutura Condicional (44 exercícios, 11 para cada aluno) [solução] [professor]
Lista de Exercícios 3a - Estrutura de Repetição (100 exercícios, 20 para cada aluno) [solução] [professor]
Lista de Exercícios 3b - Estrutura de Repetição (100 exercícios, 20 para cada aluno) [solução] [professor]
Lista de Exercícios 4 - Estruturas de Dados Compostas Homogêneas Unidimensionais - Vetores (35 exercícios, 7 para cada aluno) [solução] [professor]
Lista de Exercícios 5 - Estruturas de Dados Compostas Homogêneas Multidimensionais - Matrizes (30 exercícios, 6 para cada aluno) [solução] [professor]
Lista de Exercícios 6 - Modularização - Funções e Procedimentos (30 exercícios, 6 para cada aluno) [solução] [professor]

12 Listas de Exercícios (BCC202 - Estruturas de Dados I)

Lista 1 - Tipos de Dados Abstratos e Estruturas de Dados em C
Lista 2 - Alocação Dinâmica
Lista 3 - Limite Inferior
Lista 4 - Ordem de Complexidade
Lista 5 - Função de Complexidade
Lista 6 - Recursividade
Lista 7 - Listas implementadas por Arranjos
Lista 8 - Listas implementadas por Encadeamento
Lista 9 - Pilha
Lista 10 - Fila
Lista 11 - Árvore
Lista 12 - Ordenação
Lista 13 - Pesquisa

13 Recursos

Softwares
- Borland C
Moodle - http://www.decom.ufop.br/moodle
Apostilas C
- Renato Cardoso Mesquita - DEE/UFMG
- Camillo - PUCPR
- GACLI - UNICAMP
- Menotti - DCC/UFMG
Apostilas e documentos para LATEX
- Símbolos em LATEX - 105 páginas de caracteres e símbolos especiais
- A não tão pequena introdução ao LATEX - 132 páginas - aprenda de tudo um pouco
- Uma não tão pequena introdução ao LATEX - 132 páginas - aprenda de tudo um pouco
Recursos para LATEX
- MiKTeX Project Page - http://www.texniccenter.org/
- TeXnicCenter (The Center of your LaTeX Universe) - http://www.texniccenter.org/