Algorithmics is more than a branch of computer science. It is the core of computer science, and, in all fairness, can be said to be relevant to most of science, business, and technology. The very nature of algorithmics renders it particularly applicable to those disciplines that benefit from the use of computers, and these are fast becoming an overwhelming majority." Em "Algorithmics: The Spirit of Computing" por D. Harel

BC1435 Análise de Algoritmos



2ª 21hs e 5ª 19hs sala 302-2
Atendimento: Após as aulas nas 5ªs, ou em horário agendado por email.
Monitoria: não tem.
TPI: 4-0-4 Carga Horária: 48 horas

Ementa:

Conceitos básicos: recorrências, medidas de complexidade: melhor caso, caso médio e pior caso. Técnicas gerais de projeto de algoritmos. Classes de complexidade: P, NP e NP-completude.

Recomendação: Matemática Discreta e Algoritmos e Estruturas de Dados I




Avaliação:
A avaliação é composta por duas provas e uma sub no final com todo o conteúdo das aulas, e listas de exercícios.
Na correção das avaliações será atribuída uma nota de 0 a 10.
80% da média das provas e 20% da média das listas compõem a média final m. O conceito final é atribuído segundo o critério:
A 8,9 < m
B 7,4 < m < 8,9
C 4,9 < m < 7,4
D 4,4 < m < 4,9
F m < 4,4

Prova 1 dia 21/03. Prova 2 dia 28/04.

Listas de exercícios: Lista 1 Lista 2 Lista 3 Lista 4 Lista 5

Exercícios para entregar: Entregar em 28/04 no começo da aula: 3,9,15,16,17 da lista 1; 3,6,9(m),10 da lista 2; 6,8,21 da lista 3; 2,4,7 da lista 4; 1,9,10 da lista 5.


Bibliografia Básica:

  • [CLR] - CORMEN, Thomas H et al. Algoritmos: Teoria e prática. 2 ed. Rio de Janeiro: Editora Elsevier; Editora Campus, 2002. [005.1 / CORa / 2 ed.]
  • [DPV] - DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos; VAZIRANI, Umesh. Algorithms. Boston: McGraw-Hill Higher Education, c2008. [518.1 / DASa]
  • [Man] - MANBER, Udi. Introduction to algorithms: a creative approach. Reading, Mass: Addison-Wesley, [c1989.005.73 / MANi]
Bibliografia Complementar:
  • GREENE, Daniel H.; KNUTH, Donald E. Mathematics for the analysis of algorithms. 3rd ed. Boston: Birkhäuser, 1990. [005.1 / GREm3 / 3rd ed.]
  • KNUTH, Donald Ervin. The art of computer programming. 3rd ed. Reading, Mass: Addison-Wesley, c1997. [005.1 / KNUa3 / 3rd ed. / 1]

Calendário acadêmico:

fevereiro: 26 data limite para cancelamento de disciplina

março: 7,8,9 Carnaval
23-27 Matricula

abril: 25 - 2/5 Lançamento de notas 



       February 2011              March 2011               April 2011     
     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
            1  2  3  4  5     27 28  1  2  3  4  5     27 28 29 30 31  1  2 
      6  7  8  9 10 11 12      6  7  8  9 10 11 12      3  4  5  6  7  8  9 
     13 14 15 16 17 18 19     13 14 15 16 17 18 19     10 11 12 13 14 15 16 
     20 21 22 23 24 25 26     20 21 22 23 24 25 26     17 18 19 20 21 22 23 
                                                       24 25 26 27 28 29 30

   sem aula
   prova
   algum evento importante do calendário academico

Aulas:
aula tema referências exercícios
aula 1 Apresentação da disciplina.
Funções monótonas. Funções chão e teto.		 notas de aula
 exercícios 1,2,3 das notas de aula
 03/02
aula 2 Revisão de indução. Funções(sequências) definidas recursivamente.Recorrências. notas de aula exercícios da nota de aula 07/02
aula 3
 Recorrência para número de comparações do MergeSort, solução exata. nota de aula exercicios da nota de aula 10/02
aula 4 Notação assintótica. notas de aula, [CLR]
 Lista 1
 14/02
aula 5 Soluções assintóticas de recorrências. notas de aula, [CLR] Lista 2
 17/02
aula 6 aula de duvidas

21/02
aula 7 Soluções assintóticas de recorrências(cont). Quicksort. [CLR] Lista 2 24/02
aula 8 Quicksort, pior caso.
 [CLR] Lista 3 28/02
aula 9 reunião com avaliadores do MEC

03/03
aula 10 Quicksort, caso médio. Limite inferior de ordenação (baseada em comparação) e ordenação em tempo linear [CLR], notas de aula Lista 3 10/03
aula 11 Problema computacional, representação, pior caso, caso médio. [CLR], [DPV], notas de aula Lista 3 14/03
aula 12 aula de exercícios

17/03
aula 13 Prova

21/03
aula 14 Seleção, algoritmos probabilistico e deterministico
 [CRL] e notas de aula
 Lista 3
 24/03
aula 15 Algoritmo probabilistico para corte mínimo em grafos.
 notas de aula
 lista 4 e exercícios das notas de aula
 28/03
aula 16 union/find
 [CLR] e notas de aula
 lista 4 e exercícios das notas de aula 31/03
aula 17 alg.guloso:Kruskal [CLR] e notas de aula
 lista 5 04/04
aula 18 prog.dinamica: Floyd-Warshall [CLR] e notas de aula lista 5 07/04
aula 19 Correção de algoritmos
 notas de aula
 lista 5 11/04
aula 20 Correção de algoritmos
notas de aula
lista 5 14/04
aula 21 Aula de duvidas

18/04
aula
feriado!!!!!

21/04
aula 22 Aula reservada para dúvidas e exercícios

25/04
aula 23 Prova

28/04
aula 24 Prova sub
 02/05

Links - alguns sítios relacionados à disciplina