Linguagens formais e compiladores

14427 palavras 58 páginas
Universidade Federal de Santa Catarina
Centro Tecnológico

Departamento de Informática e de Estatística

LINGUAGENS FORMAIS E COMPILADORES

(Prof. Olinto José Varela Furtado)

Capítulo I – Introdução

I.1 - Introdução a Compiladores I.2 - Introdução a Teoria da Computação I.3 - Introdução a Teoria das Linguagens Formais

I.1 – Introdução a Compiladores

I.2 - Introdução a Teoria da Computação

O Que é Teoria da Computação? A Teoria da Computação pode ser vista como um guia (um roteiro) que nos orienta no sentido de informar o que pode e o que não pode ser efetivamente computável, explicando porque, de que forma e com que complexidade. Neste sentido, a Teoria da Computação classifica os problemas computacionais em três classes: a) Problemas Indecidíveis (ou impossíveis de serem solucionados); b) Problemas Intratáveis (possíveis com recursos ilimitados, porém impossíveis com recursos limitados); c) Problemas Tratáveis (possíveis de serem solucionadas com recursos limitados).

Esta classificação engloba problemas de toda a natureza, envolvendo desde problemas clássicos que fundamentam a teoria da computação até problemas (ou instâncias de problemas) práticos da ciência da computação, tais como: 1 – Existe programa para solucionar um determinado problema? 2 – Qual o poder de expressão de um determinado modelo de especificação? 3 – Dado um programa qualquer, ele sempre tem parada garantida? 4 – Dois programas P1 e P2 são equivalentes entre si? 5 – Uma determinada solução é a melhor solução para um dado problema? 6 – Qual o significado de um determinado programa? 7 – Dado um programa qualquer, este programa está correto?

Esta lista poderia ser expandida e detalhada, contudo, seu objetivo é enfatizar a abrangência da teoria da computação. Dos tópicos aqui listados, complexidade (5), semântica (6) e correção/construção (7), costumam ser tratados

Relacionados

  • Sr Rafael
    1642 palavras | 7 páginas
  • Aula1
    2097 palavras | 9 páginas
  • Aula 1 2
    2309 palavras | 10 páginas
  • Ciencia da computacao
    575 palavras | 3 páginas
  • Interpretadores de comandos
    2457 palavras | 10 páginas
  • Compiladores
    1915 palavras | 8 páginas
  • COMPILADORES
    22628 palavras | 91 páginas
  • EAD compiladores
    1146 palavras | 5 páginas
  • comecando a programar
    3036 palavras | 13 páginas
  • Administrador de rede
    1373 palavras | 6 páginas