estudante

SISTEMAS DE INFORMAÇÃO

TEORIA DA COMPUTAÇÃO
PROF. SANDRO ROBERTO ARMELIN
1

BIBLIOGRAFIA

[1] DIVERIO, Tiaraju Asnuz; MENEZES, Paulo Blauth. Teoria da computação: máquinas universais e computabilidade. Porto
Alegre, Sagra Luzzatto, 2004.

[2] HOPCROFT, John E.; MOTWANI, Rajeey;
ULLMAN, Jeffrey D. Introdução a teoria de autômatos, linguagens e computação. Rio de Janeiro: Campus, 2002.
[3] LEWIS, H.R.; PAPADIMITRIOU, C.H. Elementos de Teoria da
Computação. 2ª.Porto Alegre: Bookman, 2000.
19/08/2011

2

Contribuições Teoria
Computação.
 Proporciona adequado embasamento teórico necessário para um correto e amplo entendimento da ciência envolvida na computação;  Propicia o desenvolvimento de um raciocínio lógico e formal;
 introduz os conceitos fundamentais que são desenvolvidos em outras áreas.
 Linguagens de Programação e
Compiladores

Contribuições Teoria
Computação.
 Campo Cognitivo
 proporciona mais um estágio na formação do raciocínio lógico, com destaque ao pensamento indutivo ou recursivo.
 aspecto da indução  parte-se de uma instância base, verifica-se a passagem para instâncias superiores, até construir-se o problema como um todo.
 aspecto da recursão  vê-se o problema como um todo e reduz-se o problema a subproblemas menores, até que se chega a um problema base, iniciando assim o processo reverso, com a resolução de cada instância do problema.

Historia - Introdução.
•Década de 1930, antes existirem computadores A.
Turing estudou maquina abstrata que tinha todas as características dos computadores atuais, ou o quanto eles poderiam calcular.
•Estudo da teoria dos autômatos – dispositivos de computação – maquinas.
•Objetivo de Turing – Determinar com exatidão o que as maquinas poderiam fazer e o que não poderiam fazer  este experimento resultou em maquinas de
Turing.

19/08/2011

5

Historia - Introdução.
•Década de 1940 e 50 surgiram tipos de maquinas mais simples chamadas de