MC548 - Análise de Algoritmos II
Turma #
Primeiro Semestre de 2013
Conteúdo
desta página:
Avisos Importantes:
- [18/01/2013] Site da disciplina no ar.
Docente:
Dias, Horários e Local de
Atendimento
Terças-feiras, das 17h às 18h, na sala 23 do IC-1.
Importante:
- O atendimento deve ser confirmado com 24h de antecedência, por
email. Você deve enviar uma mensagem com o subject/assunto "[MC448]
Horário de Atendimento" confirmando sua intenção de usar o
horário de atendimento no horário acima (único
disponível). Você receberá um email confirmando o
atendimento.
- Só serão atendidos alunos que confirmarem o atendimento, de
acordo com a regra acima.
- Se você confirmou o interesse pelo horário de atendimento, você
deve comparecer a sala indicada até no máximo às 17:30h. Após este
horário, se não houver alunos, o atendimento será encerrado.
- Se não houver nenhum atendimento confirmado, o horário
estará cancelado.
- Não haverá horário de atendimento na semana
das provas ou do exame.
- Não haverá atendimento de dúvidas por email.
Programa:
- Programação Linear:
- Formulação de problemas como Programação Linear
- Apresentação resumida do algoritmo SIMPLEX e de sua complexidade
- Dualidade em programação linear
- Reduções entre problemas:
- Para obtenção de cotas superiores
- Para obtenção de cotas inferiores
- Classes de Problemas:
- A hierarquia de Complexidade: as classes P, NP, NP-completo e NP-difícil
- A noção de completude e o Teorema de Cook
- Problemas e reduções fundamentais em NP-completude
- Outras classes: co-NP, PSPACE e problemas indecidíveis
- Tratamento de Problemas NP-difíceis:
- Programação Linear Inteira
- Algoritmos exatos
- Algoritmos aproximados
- Algoritmos heurísticos
Referências Bibliográficas:
A seguir encontra-se a bibliografia de base desta disciplina com
alguns comentários visando auxiliá-lo na escola dos livros a
serem pesquisadas durante os seus estudos. Note que, além destes
livros, existem nas bibliotecas da UNICAMP outras boas referências
sobre os assuntos que serão vistos em sala de aula.
-
T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein. Introduction
to Algorithms (Third Edition). The MIT Press, 2009.
Comentário: Livro básico de análise
de algoritmos.
-
T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein. Algoritmos -
Teoria e Prática. Editora Campus, 2002.
Comentário: Versão em português, da
segunda versão da referência anterior.
-
U. Manber. Introduction to Algorithms: A Creative
Approach. Addison-Wesley, 1989.
Comentário: O capítulo 10 trata
exclusivamente sobre reduções entre problemas e é uma
ótima referência para o curso. O mesmo pode ser dito a respeito
do capítulo 11 sobre NP-completude.
-
C. H. Papadimitriou e K. Steiglitz. Combinatorial Optimization: Algorithms
and Complexity. Prentice-Hall, Inc., 1982.
Comentário: Uma boa fonte de referência na
parte de NP-completude, principalmente para explicar as
técnicas de branch-and-bound e apresentar os conceitos básicos
de algoritmos aproximados.
-
E. Horowitz e S. Sahni. Fundamentals of Computer Algorithms. Computer
Science Press, 1978.
Comentário: Outra boa fonte de
referência para NP-completude, algoritmos aproximados,
algoritmos de branch-and-bound e backtracking.
-
M. Garey e D. Johnson. Computers and Intractability: a Guide to the
Theory of NP-Completeness. Freeman, 1979.
Comentário: Referência clássica
sobre a Teoria da Complexidade.
-
P. J. de Rezende e J. Stolfi. Fundamentos de geometria computacional.
Universidade Federal de Pernambuco, Departamento de Informatica, 1994.
IX Escola de Computação, Recife, 24 a 31 de julho de 1994.
Comentário: Uma boa leitura sobre
reduções entre problemas (parte inicial do curso).
-
M. Sipser. Introduction to the Theory of Computation. PWS Publishing
Company, 1997.
Comentário: Este livro é muito bem
escrito e aborda de forma bem mais aprofundada vários tópicos
que são vistos na disciplina.
-
H.R. Lewis e C.H. Papadimitriou. Elementos de Teoria da Computação.
Bookman. 2a edição, 2000.
Comentário: No mesmo nível do livro
acima, porém em português.
-
M.C. Goldbarg e H.P.L. Luna. Otimização Combinatória e Programação
Linear: modelos e algoritmos. Editora Campus, 2000.
Comentário: Uma boa fonte de consulta em
português sobre formulação de problemas usando
PLI.
-
N. Ziviani. Projeto de Algoritmos com implementações em
Pascal e C (3a edição). Thomson, 2010.
Comentário: Um livro recente em
português sobre algoritmos. O Capítulo 9 é
uma boa referência complementar.
Material didático:
Avaliação:
A avaliação será baseada nas notas de quatro
provas denotadas respectivamente
por P1, P2, P3 e P4. Cada prova
terá duração de 1h e será composta de duas questões.
Os seguintes tópicos serão avaliado em cada uma das provas.
Prova 1:
- Programação Linear:
- Formulação de problemas como Programação Linear
- Apresentação resumida do algoritmo SIMPLEX e de sua complexidade
- Dualidade em programação linear
Prova 2:
- Reduções entre problemas:
- Para obtenção de cotas superiores
- Para obtenção de cotas inferiores
Prova 3:
- Classes de Problemas:
- A hierarquia de Complexidade: as classes P, NP, NP-completo e NP-difícil
- A noção de completude e o Teorema de Cook
- Problemas e reduções fundamentais em NP-completude
- Outras classes: co-NP, PSPACE e problemas indecidíveis
Prova 4:
- Tratamento de Problemas NP-difíceis:
- Programação Linear Inteira
- Algoritmos exatos
- Algoritmos aproximados
- Algoritmos heurísticos
A nota final antes do exame (N) será calculada usando a
seguinte fórmula:
- N = (P1 + P2 + P3 + P4)/4
Se 2.5 ≤ N < 5, o aluno terá direito a fazer o exame.
A nota final da disciplina (F) após o exame (E) será
calculada pela fórmula:
- F = min{5, (N + E)/2}, se 2.5 ≤ N < 5 e o aluno fez o exame
- F = N, caso contrário
Observações:
- Não haverá provas ou exame substitutivos.
- As provas e o exame serão realizados sem consulta a
qualquer material.
- Qualquer tentativa de fraude nas provas ou no exame resultará
em média do semestre N = 0 (zero) para todos os envolvidos, sem
prejuízo de outras sanções.
- De acordo com a fórmula acima, caso um aluno seja aprovado
após realizar o exame, sua nota final será igual a F=5 (cinco).
- O exame terá duração de 2h e será composto por 4 questões, sendo
que cada questão cobrirá um tópico de uma das provas.
- Todas as provas e o exame serão realizados na sala 85 do IC, com
início às 17h.
- Após corrigidas, as provas estarão disponíveis para consulta
apenas nos dias e horários divulgados junto com as notas das provas.
Datas Importantes: