Primeiro quadrimestre de 2016

Horário: 3a (10:00-12:00) e 5a (8:00-10:00)

Sala de aula: S-301-3

Professor: Jerônimo C. Pellegrini

Sala do professor: S 805 (bloco B)

Email do professor: jeronimo.pellegrini ufabc edu br

Vista/revisão

A revisão de prova será na quinta, 8:00 (horário da aula), na sala 805 do bloco B.

Novidades

17/05 -- Resultado do exame publicado
10/05 -- Conceitos finais disponíveis
22/04 -- Conceitos da prova III disponíveis; contabilização das listas (até lista 5) disponível
19/04 -- Link para "Dynamic Programming Practice Problems", de Brian Dean
06/04 -- Lista V corrigida (havia um problema de cpoy/paste; peguem a nova versão!)
05/04 -- Lista V disponível
05/04 -- Conceitos T2 disponíveis
15/03 -- Lista III pode ser entregue dia 17
11/03 -- Lista III disponível
11/03 -- Prazo para Lista II adicionado
10/03 -- Conceitos T1 e contabilização da L1 disponíveis
25/02 -- Link para notas de Wayne Goddard, sobre divisão-e-conquista para determinar envoltória convexa
23/02 -- Lista 02 disponível
23/02 -- datas das avaliações disponíveis
23/02 -- seção 1.1 do Dasgupa incluída na recomendação de leitura
23/02 -- data de entrega da Lista I disponível (01/03)
20/02 -- Lista 01 disponível
17/02 -- indicação de leitura para cada tópico, no programa (veja abaixo)
16/02 -- início do curso

Ementa

Conceitos básicos. Análise de Complexidade: melhor caso, caso médio e pior caso -- estudo de caso.
Relações de recorrência. Complexidade de Problemas: limite de Complexidade de um problema, classes de problemas, intratabilidade.

Requisitos

Algoritmos e Estruturas de Dados I. (E o curso fica muito mais fácil se você também tiver feito Matemática Discreta)

Avaliação

O conceito final será dado pela regra a seguir:

Prova substitutiva

Somente para os casos previstos em lei!

Caso o aluno perca uma das provas e apresente justificativa, poderá fazer uma substitutiva no final do quadrimestre.

Exame

Alunos com conceito F terão direito a exame, valendo 14. O conceito final, neste caso, será dado pela mesma regra para as notas, mas usando (8n + 6e)/14 ao invés de n.

Datas das avaliações

Exercícios

Conceitos

Aqui!

Programa

Este programa está sujeito a mudanças simples. Grandes mudanças não devem acontecer.

  1. Crescimento de funções; Complexidade de tempo
    • Dasgupta, cap 0; apêndice cripto, C.1 e C.3; Cormen 2 e 3
  2. Recorrências e métodos para sua solução
    • Dasgupta 2.2;
  3. Divisão e conquista
    • Dasgupta 1.1 e 2; Cormen 4; envoltória convexa: notas do Wayne Goddard -- veja "Rough drafts of brief texts for: Algorithms" nesta página.
  4. Algoritmos gulosos
    • Dasgupta 5; Cormen 16-->16.3
  5. Programação dinâmica
    • Dasgupta 3.1, 3.2, 3,3; 4.15 (antes de chegar em prog. dinâmica)
    • Dasgupta 6; Cormen 15.
  6. Análise amortizada
  7. Classes de Complexidade: P, NP, NP-completude
    • Dasgupta 8; Cormen 34; Apêndice C das notas de Cripto de C.3 em diante (Kleinberg & Tardos, cap 8 pode ajudar)
  8. Algoritmos aproximados
    • Dasgupta 9.2; Cormen 35

Bibliografia

Principal

Secundária