MAC0450 / MAC5727 -- Algoritmos de Aproximação -- 2o. Semestre de 2020

1. Material básico

1. Livro-texto: Uma introdução sucinta a algoritmos aproximação (disponível em formato pdf e ps.gz)

2. Outros livros e notas de aula

1. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation: Combinatorial approximation problems and their approximability properties
2. D. Hochbaum (ed.), Approximation Algorithms for NP-hard problems, PWS Publishing Company, 1997. (Disponível na Biblioteca do IME - BIME)
3. V. Vazirani, Approximation Algorithms Informações sobre o livro (Disponível na BIME)
4. D.P Williamson and D. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011
5. M. Goemans, Approximation algorithms, 1994. (notas de aula)
6. R. Motwani, Lectures Notes on Approximation Algorithms

3. Conhecimentos prévios necessários e/ou bem-vindos (suprir se necessário)

1. Programação Linear
   • V. Chvátal, Linear Programming, W.H. Freeman, N. York, 1983. (Disponível na BIME)
2. Teoria dos Grafos
   • J.A. Bondy and U.S.R. Murty, Graph Theory, (Graduate Texts in Mathematics, Volume 244) Springer, 2008 . Tem versão online - veja aqui
   • R. Diestel, Graph Theory, (Graduate Texts in Mathematics, Volume 173) Springer, Heidelberg. (Disponível na BIME) [veja aqui versão online]
3. Skiena's Analysis of Algorithms Lectures (slides)
4. Problemas em P, em NP e a questão "P versus NP"

4. Outros textos recomendados (para melhorar a formação)

1. Como escrever "provas matemáticas" (1a. edição disponível na BIME)
2. Como escrever textos matemáticos(Handbook of Writing for the Mathematical Sciences (N.J. Higham) | Mathematical Writing (Knuth, Larrabee, Roberts) | How to write Mathematics (Steenrod, Halmos, Schiffer, Dieudonné)

3. Nova ortografia da língua portuguesa
   • Guia Prático da Nova Ortografia (em pdf) e-book gratuito (distribuído pela Michaelis - editora Melhoramentos) --- obtido aqui

5. Atividades para avaliação do aprendizado do aluno

• Listas de exercícios (entrega obrigatória)
• Provas: (a decidir)
• Possivelmente um seminário (online) a ser dado pelo aluno -- vai depender do tamanho da turma e outros fatores

7. Aulas

• Sinopse das aulas (página atualizada frequentemente -- dados sobre aulas futuras podem sofrer mudanças) <================== Consultem!
• Consultem também a disciplina MAC0450/5727 na plataforma e-disciplinas (Moodle USP). Todos os alunos matriculados já estão cadastrados. Link para esse acesso: e-disciplinas.usp.br/acessar. Escolha a opção "ACESSAR" (forneça seu email da USP) e faça busca pela disciplina MAC0450/5727.

6. Listas de exercícios

• (poostados no e-disciplinas ou enviados por e-mail)

Last modified: Thu Aug 27 19:04:00 BRT 2020