Problemas Computacionais: Classificação e Conceitos

Classifique, Conceitue e Exemplifique Problemas Computacionais (Classes e Subclasses):

Problemas Indecidíveis:

• Impossíveis de serem solucionados;

Problemas Intratáveis:

• Possíveis com recursos ilimitados, porém impossíveis com recursos limitados;

Problemas Tratáveis:

• Possíveis de serem solucionados com recursos limitados;

Conjuntos Recursivos e Conjuntos Recursivamente Enumeráveis

Um conjunto é dito Recursivamente Enumerável se ele pode ser representado (solucionado) por uma procedure, e Recursivo se ele pode ser representado (solucionado) por um algoritmo.

Problemas Decidíveis e Indecidíveis X Algoritmos e Procedures

Um problema é decidível (tratável ou não) se e somente se ele é resolvível por um algoritmo, para qualquer entrada pertencente ao seu domínio; caso contrário ele é um problema indecidível.

Em que consiste especificar uma Linguagem de Programação?

Consiste em um método padronizado para comunicar instruções para um computador. É um conjunto de regras sintáticas e semânticas usadas para definir um programa de computador. Linguagens de programação podem ser usadas para expressar algoritmos com precisão.

Defina Formalmente Sentença, Forma Sentencial, Linguagem e os Diferentes Tipos de Derivação.

• Sentença: Uma sentença sobre um alfabeto V, é uma sequência (ou cadeia) finita de símbolos do alfabeto;
• Forma Sentencial: É uma sequência qualquer (composta por terminais e não terminais) produzida (gerada) a partir do símbolo inicial de uma gramática;
• Linguagem: É definida pelo conjunto de sentenças que podem ser derivadas a partir do símbolo inicial da gramática que a representa;

Procedure:

É um conjunto finito de passos (instruções), os quais podem ser executados mecanicamente em uma quantidade fixa de tempo e com uma quantidade fixa de esforço.

Algoritmo:

É uma procedure que sempre para; ou seja, uma procedure cuja execução chegará ao final, independentemente de quais sejam suas entradas.

Tradutor

• É um programa que traduz um programa fonte escrito em uma linguagem qualquer (denominada linguagem fonte) para um programa objeto equivalente escrito em outra linguagem (denominada linguagem objeto)

Compilador

• É um Tradutor em que a linguagem fonte é uma linguagem de alto nível e a linguagem objeto é uma linguagem de baixo nível (assembly ou máquina)

Interpretador

• É um programa que interpreta diretamente as instruções do programa fonte, gerando o resultado.

Tradutor / Interpretador

• Esquema híbrido para implementação de linguagens de programação

Montador

• É um Tradutor em que o programa fonte está escrito em linguagem assembly e o programa objeto resultante está em linguagem de máquina

Pré-processador

• É um Tradutor em que tanto o programa fonte quanto o programa objeto estão escritos em linguagens de alto nível