TeoriaCaomputacao e book

1

INTRODUÇÃO

E

CONCEITOS

BÁSICOS

________________________________________________________________________________________

1 INTRODUÇÃO E CONCEITOS BÁSICOS
• Inicia com uma breve história do surgimento e do desenvolvimento dos conceitos, resultados e formalismos nos quais a Teoria da Computação é baseada.

• Formalização dos conceitos de programa e de máquina
¾ Existem diferentes computadores, com diferentes arquiteturas, e existem diversos tipos de linguagens de programação,
¾ Modelos matemáticos simples.
¾ Programas e máquinas são tratados como entidades distintas, mas complementares e necessárias para a definição de computação. 1.1 Notas Históricas

♦ Ciência da Computação é o conhecimento sistematizado relativo à computação.
♦ Na antiga Grécia (século III A.C., no desenho de algoritmos por Euclides)
♦ Na Babilônia (complexidade\reducibilidade problemas).
♦ Interesse atual possui duas ênfases:

¾ ênfase teórica - idéias fundamentais e modelos computacionais: da biologia (modelos para redes de neurônios), da eletrônica
(teoria do chaveamento), da matemática (lógica), da lingüística
(gramáticas para linguagens naturais).
¾ ênfase prática - projeto de sistemas computacionais aplicando a teoria à prática.

No início do século XX, diversas pesquisas foram desenvolvidas com o objetivo de definir um modelo computacional suficientemente genérico, capaz de implementar qualquer Função Computável.

____________________________________________________________
Teoria da Computação - Profs. Tiaraju Diverio e Paulo Blauth Menezes
1

1 INTRODUÇÃO E CONCEITOS BÁSICOS
_________________________________________________________________________________________

Um marco inicial da Teoria da Computação - David
Hilbert, Entscheidungsproblem, o qual consistia em encontrar um procedimento para demonstrar se uma dada fórmula no cálculo de preposições de primeira ordem era válida ou não.
(Fórmula do cálculo de predicados no qual a quantificação é restrita às variáveis individuais)