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

1. Material básico

1. Livro-texto: Uma introdução sucinta a algoritmos aproximação (disponível em formato pdf e ps.gz)
2. Notas de aula (de alguns tópicos extras.

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]
   • P. Feofiloff, Y. Kohayakawa e Y. Wakabayashi, Uma Introdução Sucinta à Teoria dos Grafos -- Notas de aula de um mini-curso oferecido na II Bienal de Matemática -- Salvador, julho/2004
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: (datas a decidir)
• [Seminário (a ser dado pelo aluno)? -- vai depender do tamanho da turma e outros fatores]

6. Aulas

• Sinopse das primeiras aulas (demais aulas -- vejam no e-disciplinas)
• Entrem no e-disciplinas (Moodle USP) e acessem o par de disciplinas MAC0450/MAC5727. Link para esse acesso: e-disciplinas.usp.br/acessar.

7. Listas de exercícios

• (Serão poostados no e-disciplinas)

Last modified: 31 jul 19:04:00 BRT 2023