MAC338 - Análise de Algoritmos

BCC - 1o. Semestre de 2006

Sinopse das aulas - Março

Quarta 1/3/2006	Quarta-feira de Cinzas
Sexta 3/3/2006	Semana de break do BCC
Aula 3 Quarta 8/3/2006	CLRS 4.1 e 4.2. Chão e teto. Análise da busca binária (tabela + chute + indução; número de bits na representação binária de um número). Recorrências do tipo divisão e conquista; recorrência da ordenação por intercalação (mergesort); análise através da "árvore de recursão"
Aula 4 Sexta 10/3/2006	Mais exemplos de recorrências em geral e recorrências do tipo divisão-e-conquista.
Aula 5 Quarta 15/3/2006	Enunciado de alguns exercícios O problema do segmento de soma máxima. Algoritmo cúbico, algoritmo quadrático, algoritmo baseado em divisão e conquista (n log n), e algoritmo linear.
Aula 6 Sexta 17/3/2006	Multiplicação de inteiros grandes; o algoritmo de Karatsuba e Ofman e sua análise
Quarta 22/3/2006	Professor no LATIN 2006 (não houve aula)
Aula 7 Sexta 24/3/2006	Professor no LATIN 2006; o monitor deu uma aula de exercícios.
Aula 8 Quarta 29/3/2006	Análise do algoritmo de Karatsuba e Ofman (continuação) Multiplicação de matrizes grandes; o algoritmo de Strassen e sua análise
Aula 9 Sexta 31/3/2006	Exemplo de uma análise de caso médio: determinação do máximo de um vetor Quicksort (introdução)

Calendário

        February 2006              March 2006               April 2006     
     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               1  2  3  4                        1 
      5  6  7  8  9 10 11      5  6  7  8  9 10 11      2  3  4  5  6  7  8 
     12 13 14 15 16 17 18     12 13 14 15 16 17 18      9 10 11 12 13 14 15 
     19 20 21 22 23 24 25     19 20 21 22 23 24 25     16 17 18 19 20 21 22 
     26 27 28                 26 27 28 29 30 31        23 24 25 26 27 28 29 
                                               
           May 2006                June 2006                July 2006      
     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  6                  1  2  3                        1 
      7  8  9 10 11 12 13      4  5  6  7  8  9 10      2  3  4  5  6  7  8 
     14 15 16 17 18 19 20     11 12 13 14 15 16 17      9 10 11 12 13 14 15 
     21 22 23 24 25 26 27     18 19 20 21 22 23 24     16 17 18 19 20 21 22 
     28 29 30 31              25 26 27 28 29 30        23 24 25 26 27 28 29 
                                                       30 31

Sinopse das aulas de MAC338 (BCC - 1o. Semestre de 2006)
Página principal de MAC338 (BCC - 1o. Semestre de 2006)

Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Tue May 16 17:49:18 EST 2006