Exatas

1 Introdução 1.1 Motivação Qualquer que seja a área cientifica de estudo, existem limites que não podem ser superados, qualquer que seja a tecnologia utilizada. Existem problemas da matemática que não podem ser resolvidos por um programa de computador. Tais problemas devem ser identificados. Para isso, precisamos formalizar as noções de: - Problema (Como dar uma representação genérica de qualquer problema? Numa forma que o computador vai entender?) - Programa (O que é exatamente um algoritmo em computação ?)

1.3 Noção de Programa Um programa (escrito em C por exemplo) que sempre fornece uma resposta para um problema dado é chamado de Procedimento Efetivo. Uma linguagem de programação ficará associada à noção de procedimento efetivo somente se existe um procedimento de interpretação ou compilação que transformará o programa num código diretamente executado pelo processador. Para formalizar a noção de procedimento efetivo, serão utilizados formas de linguagens de programação tão simples que o procedimento de interpretação será imediato : tais programas serão chamados de Autômatos.

E a noção de Algoritmo ? Até hoje não existe uma definição única e aceita por todos. Para Minsky (1967) por exemplo, um algoritmo (um conjunto de regras que especificam a cada instante o próximo comportamento) é sinônimo de procedimento efetivo. Um dos objetivos da disciplina é de formalizar a noção de procedimento efetivo e de analisar os procedimentos efetivos utilizados como solução de problemas.

1.4 Formalização da noção de Problema Para poder estudar a noção de procedimento efetivo, independentemente do programa e da máquina que o executa, a representação dos dados de entrada do problema deve fazer abstração dos tipos de dados particulares utilizados pelas linguagens de programação. Cada instância do problema será então representada por uma seqüência finita de símbolos que pertencem a um conjunto de símbolos que dependem do problema. Exemplos : - {0,...,9} para um