MAC430 - Algoritmos e Complexidade de Computação

BCC. 2o. Semestre de 2012

Sinopse das aulas

• Julho
  • (Aula 0) 31/7/2012 Discussão inicial sobre a disciplina. Conceitos básicos.

• Agosto
  • (Aula 1) 2/8/2012 Discussão dos exercícios iniciais da lista de exercícios.

  • (Aula 2) 7/8/2012 Máquinas de Turing. Definição formal e exemplos. Linguagens Turing-reconhecíveis e Turing-decidíveis.

  • (Aula 3) 9/8/2012 Máquinas de Turing (continuação). O 10o. Problema de Hilbert e o Teorema de Matijasevic.

  • (Aula 4) 14/8/2012 Máquinas de Turing (continuação). Variantes: máquinas com várias fitas e máquinas não-determinísticas. Teoremas de equivalência.

  • (Aula 5) 16/8/2012 Máquinas de Turing (continuação). Enumeradores. Teoremas de equivalência. Descrição de alto nível de MTs.

  • 21/8/2012 (Professor fora de São Paulo)

  • (Aula 6) 23/8/2012 Aula de exercícios (professor fora de São Paulo)

  • (Aula 7) 28/8/2012 Decidibilidade. Problemas de decidibilidade envolvendo linguagens regulares e livres de contexto (apenas discussão dos resultados). Diagonalização. Argumentos de contagem e linguagens não Turing-reconhecíveis. O Problema da Parada.

  • (Aula 8) 30/8/2012 O teorema de Rice. Autômatos linearmente limitados.

• Setembro
  • 4/9/2012 Semana da pátria

  • 6/9/2012 Semana da pátria

  • (Aula 9) 11/9/2012 Autômatos linearmente limitados. O Problema da Correspondência de Post.

  • (Aula 10) 13/9/2012 Prova 1

• Outubro

• Novembro

• Dezembro

Calendário

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

         October 2012            November 2012            December 2012    
     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 

Last modified: Wed Sep 12 18:28:56 BRT 2012