Os fundamentos da computação são apresentados nesta obra enfatizando-se o papel desempenhado por máquinas e linguagens. Após a revisão de alguns conceitos, o suficiente para munir o leitor da fundamentação matemática necessária, são estudados três tipos de máquinas, juntamente com as classes de linguagens que estas são capazes de processar: os autômatos finitos, os autômatos de pilha e as máquinas de Turing.
Em seguida, após apresentar estas últimas como possuidoras de poder computacional suficiente para solucionar qualquer problema que tenha solução algorítmica, são mostrados exemplos de problemas para os quais não existem algoritmos, começando pelo célebre “problema da parada”. O livro é finalizado com um capítulo em que são apresentadas as soluções de alguns dos cerca de 380 exercícios formulados ao longo do texto.
Aplicação: Livro-texto para as disciplinas fundamentos da computação, introdução à teoria da computação, linguagens formais e autômatos e teoria de linguagens nos cursos de graduação das áreas de Informatica, como Ciências da Computação, Matemática Computacional, Engenharia da Computação e Sistemas de Informação. Também pode ser utilizado por profissionais da área de Informática em geral, interessados em uma revisão ou em ter um primeiro contato com os fundamentos da computação.
Newton José Vieira
Doutor em Ciências em Informatica pela Universidade Católica do Rio de Janeiro (PUC/RJ) e professor em cursos de graduação e pós-graduação do Departamento de Ciência da Computação, Instituto de Ciências Exatas, da Universidade Federal de Minas Gerais (UFMG), lecionando nos últimos anos disciplinas como fundamentos da teoria da computação, teoria de linguagens, matemática discreta e inteligência artificial.