Teoria da Computação

Prévia do material em texto

05/10/2017
1
TEORIA DA COMPUTAÇÃO
UFRPE-UAST
Sistemas de Informação
Prof. Sérgio Paiva
EMENTA
 Introdução e Conceitos Básicos: Notas 
Históricas, Abordagem e Conceitos Básicos
Autômatos 
2.1 Finitos (Determinísticos e Não-
determinísticos)
2.2 a Pilha
2.3 Máquina de Turing
2.4 Equivalência de Máquinas 
Linguagens Formais 
3.1 Regular
3.2 Livre de Contexto 
3.3 Sensível ao Contexto 
3.4 Estrutura de Frases
3.5 Gramáticas 
3.6 Hierarquia de Chomsky
EMENTA
Computabilidade
4.1 Modelos Computacionais 
4.2 Funções Recursivas 
4.3 Funções não-computáveis
4.6 Problema da Parada
4.7 Decidibilidade
Conclusões
5.1 Resumo dos Principais Conceitos 
5.2 Contribuições da Teoria da Computação
AVALIAÇÃO
 A avaliação se dará através das seguintes 
modalidades:
 Verificação de aprendizagem
 Pespectivas das Datas para 2017-02
 1 VA : 13/dez
 2 VA : 31/jan
 3 VA : 07/fev
 Final: 14/fev
05/10/2017
2
BIBLIOGRAFIA
 DIVERIO, Tiaraju A.; MENEZES, Paulo F. Blauth. 
Teoria da Computação – Máquinas Universais e 
Computabilidade. 2a. Edição. Porto Alegre: Sagra-
Luzzatto, 2000. 205p. 
 Menezes, P.F.B. LINGUAGENS FORMAIS E 
AUTÔMATOS. Série Livros Didáticos. Instituto de 
infromática da UFRGS. ( 3 Edição). ISBN 85-241-0554-
2 
BIBLIOGRAFIA - OUTROS
 SERNADAS, C. Introdução à Teoria da Computação. Lisboa: Editorial 
Presença, 1993. 
 Introdução à Teoria de Autômatos, Linguagens e Computação. 
John E. Hopcroft, Jeffrey D. Ulman e Rajeev Motwani. Trad. da 
segunda edição, Editora Campus. (Livro Texto) 
 Acióly, Benedito M.; Bedregal, Benjamín R. C.; Lyra, Aarão. 
Introdução à Teoria das Linguagens Formais, dos Autômatos e 
da Computabilidade. Edições UnP, 2002.
 BIRD, Richard. Programs and Machines - an introduction to the theory of 
computation. London: John-Wiley, 1976. 
 BRAINERD,W. S.; LANDWEBER L. H. Theory of Computation. New 
York: Wiley, 1974.
CONTATOS
 sslpaiva@gmail.com
 sergio.paiva@uast.ufrpe.br
 Página do curso:
 https://sites.google.com/site/sslpaiva/teoria-da-
computacao
Atenção:
- Serão postadas as aulas e exercícios na página do 
curso.
- Serão colocados avisos na página.
OBJETIVO
 Dar aos alunos noção formal de algoritmo, 
computabilidade e do problema de decisão, de 
modo a deixá-lo consciente das limitações da 
ciência da computação. 
 Aparelhá-los com as ferramentas de modo a 
habilitá-lo a melhor enfrentar a solução de 
problemas com o auxílio do computador. 
 Dar subsídios para os alunos poderem definir 
linguagens de programação, isto é, sua sintaxe e 
semântica, através do estudo das gramáticas 
formais. 
05/10/2017
3
MOTIVAÇÃO
 O objetivo do curso é entender os fundamentos da 
computação.
 O que significa uma função ser computável ?
 Existem funções não – computáveis? 
 Como a capacidade computacional depende das estruturas 
de programação ?
 Como diferentes tipos de computadores, com diferentes 
arquiteturas, e os diversos tipos de linguagens de 
programação, podem afetar na computação de um 
problema? 
 A Computação é um tipo de modelagem matemática? 
Porquê?.
 Programas e máquinas são entidades distintas? São 
complementares e necessárias para a definição de 
computação?
ÊNFASE
 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. 
INTRODUÇÃO
 Responda: O que é computação?
INTRODUÇÃO
 Computabilidade
 Intuitivamente, uma função é dita computável se é 
possível calcular o seu valor, dado qualquer elemento 
do seu dominio
 Será toda função bem definida computável?
05/10/2017
4
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). 
DESENVOLVIMENTO
 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.
DAVID HILBERT
 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)
 David Hilbert acreditava que todo problema bem 
definido poderia ser resolvido. O fracasso na solução de 
um problema era devido a má escolha das váriaveis ou 
um raciocinio errôneo
KURT GÖDEL
 Em 1931, Kurt Gödel - Incompleteness Theorem
(teorema da não completude), onde demonstrou que 
tal problema (mecanização do processo de prova de 
teoremas) não tinha solução. 
 Gödel criou sua prova começando com o “Paradoxo 
do Mentiroso” — que é a afirmação:
“Eu estou mentindo.”
 “Eu estou mentindo” é autocontraditória, já que, se 
é verdade, eu não sou um mentiroso, e, se é falsa, 
eu sou um mentiroso, então é verdade.
05/10/2017
5
KURT GÖDEL
Expresso em Linguagem Formal:
 O teorema de Gödel diz: “Qualquer teoria 
efetivamente gerada capaz de expressar aritmética 
elementar não pode ser tanto consistente quanto 
completa. Em particular, para qualquer teoria 
formal consistente e efetivamente gerada que 
prova certas verdades aritméticas básicas, existe 
uma afirmação aritmética que é verdadeira, mas 
que não pode ser provada em teoria.”
ALONZO CHURCH
 Em 1936, Church usou dois formalismos 
para mostrar que o problema de Hilbert não tem 
solução: -calculus (Church, 1936) e funções 
recursivas (Kleene, 1936). 
 Procedimentos efetivos - “São caracterizações tão 
gerais da noção do efetivamente computável 
quanto consistentes com o entendimento intuitivo 
usual” (Church).
 Está hipótese é assumida como verdadeira porém 
não é demonstrável pois trata-se de uma noção 
intuitiva do que é computável.
ALAN TURING
 Turing propôs, em 1936, um formalismo para a 
representação de procedimentos efetivos. Esse foi o 
primeiro trabalho a identificar programas escritos 
para uma “máquina computacional autômata”, como 
noções intuitivas de efetividade. 
 A intenção do modelo de Turing era simular, tanto 
quanto possível, as atitudes humanas relacionadas à 
computação.
OUTROS FORMALISMOS
Desde então, muitos outros formalismos 
foram propostos, os quais possuem o 
mesmo poder computacional que as 
funções recursivas (ou Cálculo Lambda): 
 Sistema Canônico de Post (1943);
 Algoritmo de Markov e a Linguagem Snobol 
(1954);
 Máquinas de Registradores (1963);
 RASP (Random Acess Stored Programs -
1964). 
05/10/2017
6
REPRESENTAÇÃO
 Representar as entidades envolvidas num 
problema computacional
 Representação por Símbolos
 Problema : Calculo da Folha de pagamento
 Representação computacional: Programa que 
implementa uma folha de pagamentos
 Sequencia de símbolos 
 O modelo matemático:
 No caso acima o modelo matemático utilizado na 
solução do problema proposto é o que chamamos de 
ALGORITMO. 
PROGRAMAS
Programa é definido como sendo um 
procedimento efetivo, pode ser descrito 
usando qualquer dos formalismos 
equivalentes. Ou seja, qualquer destes 
formalismos permite descrever todos os 
procedimentos possíveis que podem ser 
executados em um computador 
Procedimento Efetivo = Programa que éuma seqüência finita de instruções que 
podem ser executados mecanicamente em 
um tempo finito.
CONCEITOS BÁSICOS
 Noções de Conjuntos e suas representações
 Relação
 Função
 Função Parcial (Relação) e Função Total
 f:A→B (lê se f de A em B) é uma relação binária 
tal que (x,y) ε f e (x,z) ε f então y=z .
 Outra forma de notação: F(x)=y 
 Se não existe y para F(x) então a função é 
indefinida pra x, logo Função Parcial
 Se para todo x ε A existe um y ε B, então a função 
é dita TOTAL 
CONCEITOS BÁSICOS
 Dados A e B dois conjuntos.
 Função Injetora:
 Se para x,y ε A, x≠y → f(x) ≠f(y)
 Função Sobrejetora
 Se B é imagem de f
 Função Bijetora
 Injetora e sobrejetora
 Exs:
 F: N → N tal que f(x)=2x
 F: Z → N tal que f(x)=|x|
 F: Z → N tal que f(x)=2x (para x≥0) e f(x)=-(2x+1) cc
05/10/2017
7
CONCEITOS BÁSICOS
 Conjuntos Enumeráveis
 Para comparar o tamanho de dois conjuntos A e B, 
podemos:
 Contar os elementos dos dois e comparar 
 Verificar se existe uma função bijetora (injetora e 
sobrejetora) de A para B
 Cardinalidade de conjuntos infinitos
 Forma de comparar conjuntos infinitos.
 Dizemos que dois conjuntos tem a mesma 
cardinalidade se existe uma função bijetora de A para 
B
 Um conjunto é dito Enumerável se possui a 
mesma cardinalidade do conjunto N (naturais)
CONCEITOS BÁSICOS
 Exs:
 Conjunto dos números naturais pares P é 
enumerável?
 Um conjunto é enumerável se possui a mesma 
cardinalidade que N. Pegando a função F:N->P tal 
que F(x)=2x que é uma função bijetora. Logo P é 
enumerável 
 Qual conjunto é maior N ou P?
 Como existe a função F(x)=2x que é bijetora não 
podemos dizer que N é maior que P, e sim que tem o 
mesmo “tamanho”.
CONCEITOS BÁSICOS
 Exs:
 O Conjunto Z (inteiros) é maior que N?
 A função f: N->Z tal que: 
 f(x)=x/2 se x é par e f(x)=-(x+1)/2 se x é impar
 Demonstra que N e Z tem a mesma cardinalidade, 
logo N e Z tem o mesmo “tamanho” e Z é enumerável.
CONCEITOS BÁSICOS
Linguagem
 é um conceito fundamental no estudo da 
Teoria da Computação, pois trata-se de uma 
forma precisa de expressar problemas, 
permitindo um desenvolvimento formal 
adequado ao estudo da computabilidade. 
 O dicionário Aurélio define linguagem como: "o 
uso da palavra articulada ou escrita como meio 
de expressão e comunicação entre pessoas". 
 Esta definição não é suficientemente precisa 
para permitir o desenvolvimento matemático 
de uma teoria sobre linguagens. 
05/10/2017
8
CONCEITOS BÁSICOS
Definição 1.1 Alfabeto. 
 Um Alfabeto é um conjunto finito de símbolos ou 
caracteres.
 um conjunto infinito não é um alfabeto:
 o conjunto vazio não é um alfabeto. 
 Qual o alfabeto que devemos considerar, ou seja, quais 
são os símbolos do alfabeto considerado depende do 
contexto em que pretendemos trabalhar. Como 
exemplos de alfabetos, citamos {0, 1} ou {a, b}, o 
alfabeto da língua portuguesa { a, b,c, ç, ¼ z}, o 
conjunto de caracteres ASCII, etc.
CONCEITOS BÁSICOS
Definição 1.1 Alfabeto. 
 Exemplo 1.1
 Os seguintes conjuntos são exemplos de alfabetos:
 {a, b, c};
 {alfabeto português}
 Os seguintes conjuntos não são exemplos de alfabetos:
 conjunto dos números naturais;
 {a, b, aa, ab, ba, bb, aaa,...}.
 Conjunto Vazio 
CONCEITOS BÁSICOS
Definição 1.2 Cadeia de Símbolos, 
Palavra. 
 Uma Cadeia de Símbolos sobre um conjunto 
é uma seqüência de zero ou mais símbolos (do 
conjunto) justapostos. Uma Cadeia de 
Símbolos Finita é usualmente denominada de 
Palavra.
  denota a cadeia vazia ou palavra vazia. 
 Se  representa um conjunto de símbolos (um 
alfabeto), 
 * => o conjunto de todas as palavras 
possíveis sobre ; 
 + denota * - {  }.
CONCEITOS BÁSICOS
 Diferenças entre Cadeias e Conjuntos
 {a,b} = {b,a}, mas ab ≠ ba 
 {a,a,b} = {a,b}, mas aab ≠ ab 
 = conjunto com nenhum 
elemento; vazio. 
 {} = conjunto com 1 elemento, a 
cadeia vazia. 
  = cadeia vazia, que não é 
conjunto. 
05/10/2017
9
CONCEITOS BÁSICOS
Definição 1.2 Cadeia de Símbolos, 
Palavra. 
Definição 1.3 Comprimento ou 
Tamanho de uma Palavra. 
O Comprimento ou Tamanho de uma 
palavra w, representado por w, é o 
número de símbolos que compõem a palavra. 
CONCEITOS BÁSICOS
Definição 1.4 Prefixo, Sufixo, 
Subpalavra. 
 Um Prefixo (respectivamente, Sufixo) de uma 
palavra é qualquer seqüência inicial 
(respectivamente, final) de símbolos da 
palavra. Uma Subpalavra de uma palavra é 
qualquer seqüência de símbolos contígüa da 
palavra.
CONCEITOS BÁSICOS
Exemplo 1.2 Palavra, Prefixo, Sufixo, 
Tamanho.
 a)abcb é uma palavra sobre o alfabeto {a, b, c};
 b)Se  = {a, b}, então:
+ = {a, b, aa, ab, ba, bb, aaa,...}
* = { , a, b, aa, ab, ba, bb, aaa,...}
 c)abcb = 4 e  = 0;
 d)Relativamente à palavra abcb, tem-se que:
 , a, ab, abc, abcb são os prefixos;
 , b, cb, bcb, abcb são os respectivos sufixos.
 e)Qualquer prefixo ou sufixo de uma palavra é 
uma sub-palavra. 
CONCEITOS BÁSICOS
 Definição 1.6 Concatenação de Palavras. 
 A Concatenação de Palavras é uma operação binária, definida 
sobre uma linguagem L, a qual associa a cada par de palavras 
uma palavra formada pela justaposição da primeira com a 
segunda tal que:
 não necessariamente é fechada em L; a concatenação de duas 
palavras de uma linguagem não necessariamente resulta em uma 
palavra da linguagem. 
 é associativa; v(wt) = (vw)t = vwt
 possui elemento neutro à esquerda e à direita, o qual é a palavra 
vazia.  w = w = w
 Exemplo 1.4 Concatenação de Palavras. 
 Suponha o alfabeto  = {a, b}. 
 Então, para as palavras v = baaaa e w = bb, tem-se que:
 vw = baaaabb
 v = v = baaaa
05/10/2017
10
CONCEITOS BÁSICOS
Definição 1.7 Concatenação Sucessiva de 
uma Palavra. 
 A Concatenação Sucessiva de uma Palavra (com ela 
mesma) ou simplesmente Concatenação Sucessiva, 
representada na forma de um expoente (suponha w 
uma palavra): 
 wn onde n é o número de concatenações 
sucessivas, 
 é definida indutivamente a partir da operação de 
concatenação binária, como segue: 
 w0 = e;
 wn = wn-1w, para n > 0.
CONCEITOS BÁSICOS
Exemplo 1.5 Concatenação Sucessiva.
 Sejam w uma palavra e a um símbolo. Então: 
 w3 = www
 w1 = w 
 a5 = aaaaa
 an = aaa...a (o símbolo a repetido n vezes)
CONCEITOS BÁSICOS
Definição 1.5 Linguagem Formal
 Uma Linguagem Formal ou simplesmente 
Linguagem é um conjunto de palavras sobre um 
alfabeto. 
 Tem uma sintaxe bem definida, de forma que, 
dada uma sentença, seja sempre possível saber se 
ela pertence ou não à linguagem
 Tem uma semântica precisa
Exemplos: Java,C,HTML,Pascal,etc...
CONCEITOS BÁSICOS
Exemplo 1.3 Linguagem Formal.
 Suponha o alfabeto  = {a, b}. Então:
 a)O conjunto vazio e o conjunto formado pela 
palavra vazia são linguagens sobre . 
Obviamente, { }  {  }.
 b)O conjunto de palíndromos (palavras que 
têm a mesma leitura da esquerda para a 
direita e vice-versa) sobre  é um exemplo de 
linguagem infinita. 
 , a, b, aa, bb, aaa, aba, bab, bbb, aaaa,... 
05/10/2017
11
RESUMO: TEORIA DA COMPUTAÇÃO
Computação pode ser definida como a 
solução de um problema ou, formalmente, 
o cálculo de uma função, através de um 
algoritmo. 
A teoria da computação, um subcampo 
da ciência da computação e matemática, 
busca determinar quais problemas podem 
ser computados em um dado modelo de 
computação. 
Por milhares de anos,a computação foi 
feita com lápis e papel, ou giz e quadro, ou 
mentalmente, às vezes com a ajuda de 
tabelas.
RESUMO: TEORIA DA COMPUTAÇÃOA teoria da computação estuda os modelos de 
computação genéricos, assim como os limites da 
computação:
 Quais problemas jamais poderão ser resolvidos por um 
computador, independente da sua velocidade ou 
memória? 
 Quais problemas podem ser resolvidos por um 
computador, mas requerem um período tão extenso de 
tempo para completar a ponto de tornar a solucão 
impraticável? 
 Em que situações pode ser mais difícil resolver um 
problema do que verificar cada uma das soluções 
manualmente? 
EXERCÍCIOS
 Exercício 1 na página da disciplina
 https://sites.google.com/site/sslpaiva/teoria-da-
computacao