Michael Sipser é Donner Professor of Mathematics no MIT e autor de "Introduction to the Theory of Computation", livro-texto adotado em praticamente toda graduação respeitável em ciência da computação no mundo desde 1996. Foi chefe do Departamento de Matemática do MIT entre 2004 e 2014 e Reitor Interino da Escola de Ciência do MIT em 2013 a 2014.

Sua área central é teoria da complexidade computacional, com contribuições especialmente em algoritmos probabilísticos, classes de complexidade e o problema P versus NP. As gravações de seu curso "Theory of Computation" (18.404J/6.840J) são referência mundial.

Trajetória

  • 1974: graduação em Matemática pela Cornell University.
  • 1980: doutorado em Ciência da Computação pela UC Berkeley, com tese orientada por Manuel Blum.
  • 1980 a 1981: pesquisador de pós-doutorado no IBM Research em San Jose.
  • 1981 em diante: ingressa no MIT, primeiro como professor assistente, depois associado e titular.
  • 2004 a 2014: chefe do Departamento de Matemática do MIT.
  • 2013 a 2014: Reitor Interino da Escola de Ciência do MIT.

Áreas de pesquisa

  • Complexidade computacional: classes P, NP, BPP, IP, PCP. Sipser contribuiu para várias separações entre classes.
  • Algoritmos probabilísticos: introduziu técnicas que viraram parte do vocabulário básico da disciplina.
  • Modelos de computação: máquinas de Turing, autômatos, teoremas de hierarquia.
  • Pesquisa em P versus NP: um dos seis problemas do milênio, com prêmio de US$ 1 milhão para quem resolver, oferecido pelo Instituto Clay.

Cursos do estude.org com Sipser

Para entender por que estudar fundamentos teóricos importa em uma carreira técnica, veja por que estudar algoritmos e por que estudar engenharia de software.

O livro-texto

"Introduction to the Theory of Computation" (1996, com terceira edição em 2012) cobre:

  • Parte I: autômatos e linguagens (autômatos finitos, linguagens regulares, livres de contexto).
  • Parte II: teoria da computabilidade (máquina de Turing, problema da parada, redutibilidade).
  • Parte III: teoria da complexidade (P, NP, NP-completude, espaço, classes de complexidade probabilísticas, criptografia teórica).

É elogiado pela clareza expositiva incomum em livros de teoria da computação. As demonstrações são precisas mas legíveis, e cada capítulo termina com exercícios bem calibrados.

Estilo de ensino

  1. Construção rigorosa, sem atalho. Sipser introduz cada conceito com definição formal e exemplos antes de mostrar consequências.
  2. Demonstrações no quadro. Quase nada em slides; o aluno acompanha o pensamento em tempo real.
  3. Conexão com problemas em aberto. Sipser frequentemente menciona o que ainda não se sabe, mostrando a fronteira viva da disciplina.

Para quem o curso é mais útil

  • Estudantes de ciência da computação que querem solidificar fundamentos teóricos.
  • Engenheiros que pretendem entrar em pós-graduação em computação.
  • Pesquisadores em criptografia, complexidade ou inteligência artificial teórica.
  • Profissionais que querem entender por que certos problemas são intrinsecamente difíceis (NP-completude) e parar de procurar algoritmos eficientes para eles.

Como abordar o curso

Tenha base de programação e raciocínio lógico antes de começar. Recomenda-se ter feito antes algum curso introdutório como o CS50 ou o MIT 6.006 (Algoritmos). Estude o livro em paralelo com as gravações: as duas fontes se complementam, e os exercícios do livro são parte essencial do aprendizado.

Perguntas frequentes

Teoria da computação serve para quê na prática?

Serve para reconhecer quando um problema é intratável (NP-completo, indecidível) e parar de bater cabeça. Também é base para criptografia, compiladores, otimização, verificação formal e segurança.

É preciso saber matemática avançada?

Lógica de primeira ordem, indução matemática e teoria dos conjuntos básica. O livro de Sipser introduz esses pré-requisitos no apêndice. Análise real e álgebra abstrata não são necessárias.

Posso ler o livro sem fazer o curso?

Pode. O livro é completo e foi escrito para ser usado em cursos universitários. Muita gente aprende teoria de computação inteira por conta própria com ele.

Há tradução em português?

Sim. A editora Cengage publicou tradução brasileira como "Introdução à Teoria da Computação". A qualidade da tradução é razoável; serve para quem não domina inglês técnico.

Onde pesa

Sipser representa o tipo de matemático-cientista da computação que combina contribuição técnica original com talento didático escasso. Seu livro-texto definiu, por mais de duas décadas, como teoria da computação é ensinada no mundo inteiro. Para qualquer estudante sério da disciplina, é leitura obrigatória.