CONTEUDO ASPECTOS TEÓRICOS

Prévia do material em texto

ASPECTOS TEÓRICOS DA COMPUTAÇÃO
TURMA: CIÊNCIAS DA COMPUTAÇÃO
Professor: Rogério Gião
ATC - INTRODUÇÃO
A teoria da computação encontra-se entre os campos das Ciências da
Computação e a matemática, onde a partir de um dado problema é
estudado como ele pode ser solucionado (computado) em
determinado modelo da computação, ou seja, analisa os modelos
computacionais e sua referente capacidade de computar relacionando
quais os problemas podem ser resolvidos por cada modelo.
ATC - INTRODUÇÃO
As linguagens formais surgiram por volta do século XX, década de 50,
com o objetivo de distanciar as linguagens naturais humanas e a
linguagens dos computadores, formou-se então as linguagens de
programação.
Uma linguagem (L) é um conjunto finito de sentenças de comprimento
finito, que são construídas considerando determinado alfabeto
composto por um conjunto finito de símbolos. (CHOMSKY, 1959)
ATC - INTRODUÇÃO
Linguagem Regular
Pode ser expressa por expressões regulares e pertence ao nível 3 na
hierarquia. Conjunto de palavras que necessita apenas de memória
finita para ser corrigida sintaticamente e a estrutura delas segue um
padrão.
Todas linguagens finitas são regulares e podem ser reconhecidas por
autômatos finitos.
É uma restrição sobre a forma das produções, pode-se criar uma nova
classe de gramáticas de grande importância no estudo dos
compiladores por possuírem propriedades adequadas para a obtenção
de reconhecedores simples.
ATC - INTRODUÇÃO
Linguagem Livre de Contexto
Palavras que podem ter seus padrões estruturais sequenciais.
Pertence ao nível 2 na hierarquia, é produzida por alguma gramática
livre de contexto e é reconhecida por autômatos com pilha.
São aquelas em que é levantado o condicionamento das substituições
impostas pelas regras definidas pelas produções. Este condicionamento
é eliminado impondo às produções uma restrição adicional, que
restringe as produções à forma geral.
ATC - INTRODUÇÃO
Linguagens Sensíveis ao Contexto
Encontra-se no nível 1 na hierarquia e é reconhecida por autômatos
lineares limitados (Turing limitada).
Se as regras de substituição forem sujeitas à restrição de que nenhuma
substituição possa reduzir o comprimento da forma sentencial à qual a
substituição é aplicada, cria-se uma classe chamada sensíveis ao
contexto
ATC - INTRODUÇÃO
Gramática com Estrutura de Frase - Recursivamente Enumerável
Pertence ao nível 0 na hierarquia e pode ser reconhecida por
Máquinas de Turing.
Aquelas às quais nenhuma limitação é imposta.
O universo das linguagens que se podem definir através dos
mecanismos gerativos definidos pela gramática corresponde
exatamente ao conjunto das linguagens que esta classe de gramática é
capaz de gerar.
ATC – HIERARQUIA DE CHOMSKY
Hierarquia de Chomsky foi uma classificação desenvolvida por Noan
Chomsky em 1959. A categorização possui 4 níveis, onde os níveis 2 e 3
que são os dois últimos são os amplamente utilizados na definição de
linguagem de programação e na implementação de interpretadores e
compiladores.
Mais especificamente, o nível 2 é utilizado em analise sintática e o
nível 3 em analise léxica.
ATC – HIERARQUIA DE CHOMSKY
Possui a característica de exibir o mérito de agrupar as linguagens em
classes, de tal forma que elas possam ser hierarquizadas segundo a sua
complexidade relativa.
Basicamente a hierarquia é um arranjo de gramáticas formais onde são
divididas em 4 níveis, 0 até 3, e cada nível da classificação descreve o
nível de liberdade da linguagem.
ATC – HIERARQUIA DE CHOMSKY
Representação da Hierarquia de Chomsky
ATC – HIERARQUIA DE CHOMSKY
Gramática Tipo 0
As gramáticas classificas com esse nível são conhecidas como
‘Gramáticas irrestritas’, são aquelas que não possuem limitações.
Inclui todas as linguagens formais e gera exatamente o grupo com
todas as linguagens que podem ser identificadas pela Máquina de
Turing.
ATC – HIERARQUIA DE CHOMSKY
Gramática Tipo 1
As "Gramáticas sensíveis ao contexto" estão sujeitas a regra de
substituição.
Esse grupo gramatical forma o conjunto que é reconhecido por
autômatos lineares limitados (uma máquina de Turing limitada).
ATC – HIERARQUIA DE CHOMSKY
Gramática Tipo 2
As gramáticas deste tipo são as ‘Gramáticas livres de contexto’.
Estas são a base teórica para a maioria das linguagens de programação
e são definidas por uma regra que especifica as substituições que
podem ser feitas neste tipo de gramática. São reconhecidas pelos
chamados autômatos com pilha.
ATC – HIERARQUIA DE CHOMSKY
Gramática Tipo 3
Nas gramáticas de tipo 3 temos as chamadas "Gramáticas Regulares"
que são reconhecidas pelos autômatos de estados finitos.
Neste nível as linguagens possuem regras bem restritas o que torna
fácil o seu reconhecimento.
ATC – HIERARQUIA DE CHOMSKY
Pelo fato de as linguagens serem classificadas na hierarquia de
Chomsky de acordo com as limitações impostas nas regras de produção
das gramáticas, ao se descer na hierarquia de Chomsky, mais
flexibilidade é promovida por parte das gramáticas, de modo que toda
linguagem regular é uma linguagem livre de contexto, toda linguagem
livre de contexto é uma linguagem sensível ao contexto e toda
linguagem sensível ao contexto é uma linguagem de nível 0.
ATC – HIERARQUIA DE CHOMSKY
Teoria dos Autômatos
ATC – HIERARQUIA DE CHOMSKY
Teoria dos Autômatos:
É o estudo das máquinas abstratas ou autômatos, bem como
problemas computacionais que podem ser resolvidos usando esses
objetos.
A palavra autômato vem do grego e significa “autuação” (em tradução
livre), isto é, sem influência externa.
Representação de assuntos
Relacionados.
ATC – HIERARQUIA DE CHOMSKY
Linguagem Formal:
Entende-se por linguagem formal estudo de modelos matemáticos que
possibilitam a especificação e o reconhecimento de linguagens (no
sentido amplo da palavra), suas classificações, estruturas,
propriedades, características e inter-relacionamentos .
ATC – HIERARQUIA DE CHOMSKY
Linguagem Formal:
A importância dessa teoria na ciência da computação é dupla: ela tanto
apoia outros aspectos teóricos da ciência da computação
(decidibilidade, computabilidade, complexidade computacional, por
exemplo), como fundamenta diversas aplicações computacionais tais
como processamento de linguagens, reconhecimento de padrões,
modelagem de sistemas.
ATC – HIERARQUIA DE CHOMSKY
Gramática Formal:
Em teoria das linguagens formais, uma gramática formal (algumas
vezes simplesmente chamada de gramática) é um conjunto de regras
de produção de cadeias em uma linguagem formal, ou seja, um objeto
que permite especificar uma linguagem ou língua. As regras descrevem
como formar cadeias ― a partir do alfabeto da linguagem ― que são
válidas de acordo com a sintaxe da linguagem.
Uma gramática não descreve significado das cadeias ou o que pode ser
feito com elas em um contexto ― apenas suas formas.
ATC – HIERARQUIA DE CHOMSKY
Em uma Linguagem de Programação (Java, C#, por exemplo) ocorrem
três componentes da Hierarquia de Chomsky: a componente regular, a
livre de contexto e a dependente de contexto.
O compilador, que é o software que traduz a Linguagem de
Programação de alto nível para a Linguagem de Máquina, emprega
algoritmos advindos do estudo das Linguagens Regulares e Livres de
Contexto.
ATC – HIERARQUIA DE CHOMSKY
A análise de cada palavra de um programa escrito em uma Linguagem
de Programação qualquer, denominada Análise Léxica, usa os
algoritmos obtidos do estudo das Linguagens Regulares.
Estes algoritmos são a realização do modelo computacional
denominado Máquina de Estados Finitos.
ATC – HIERARQUIA DE CHOMSKY
Análise Léxica
É o processo de analisar a entrada de linhas de caracteres (tal como o
código-fonte de um programa de computador) e produzir uma
sequência de símbolos chamado "símbolos léxicos" (lexical tokens), ou
somente "símbolos" (tokens), que podem ser manipulados mais
facilmente por um leitor de saída.
Um Token em computação éum segmento de texto ou símbolo que
pode ser manipulado por um analisador sintático, que fornece um
significado ao texto; em outras palavras, é um conjunto de caracteres
(de um alfabeto, por exemplo) com um significado coletivo.
ATC – HIERARQUIA DE CHOMSKY
Análise Léxica
Tokens são os padrões que ocorrem em uma string, por exemplo: em
uma data, 29/03/1991, poderia utilizar dois tokens para dividir a string
em três partes, utilizando a barra / como padrão.
Desse modo, qualquer data que for inserida poderá ser dividida e
analisada separadamente em dia, mês e ano.
O mesmo pode ser feito com expressões regulares, mas o método de
tokens utiliza muito menos processamento, e, portanto, é mais rápido,
apesar de não ser tão robusto.
ATC – HIERARQUIA DE CHOMSKY
Análise Léxica
A Análise Léxica é a forma de verificar determinado alfabeto.
Quando analisamos uma palavra, podemos definir através da análise
léxica se existe ou não algum caractere que não faz parte do nosso
alfabeto, ou um alfabeto inventado por nós.
O analisador léxico é a primeira etapa de um compilador, logo após virá
a análise sintática.
ATC – HIERARQUIA DE CHOMSKY
A análise de cada comando (if, while, atribuição) e demais estruturas
sintáticas (classes, declarações de variáveis, etc.) de um programa
desenvolvido em uma Linguagem de Programação, a Análise Sintática,
emprega algoritmos advindos de estudo das Linguagens Livres de
Contexto.
ATC – HIERARQUIA DE CHOMSKY
A componente Dependente de Contexto em uma Linguagem de
Programação pode ser identificada na concordância entre a declaração
de tipos das variáveis de uma variável, e uso das mesmas, na
concordância entre o número de parâmetros na declaração de um
método de uma classe e o número de argumentos no uso do método
de um objeto, em sobrecarga de métodos, etc.
ATC – HIERARQUIA DE CHOMSKY
Análise Sintática
Em ciência da computação e linguística, análise sintática (também
conhecida pelo termo em inglês parsing) é o processo de analisar uma
sequência de entrada (lida de um arquivo de computador ou do
teclado, por exemplo) para determinar sua estrutura gramatical
segundo uma determinada gramática formal.
Essa análise faz parte de um compilador, junto com a análise léxica e
análise semântica.
ATC – HIERARQUIA DE CHOMSKY
Análise Sintática
A análise sintática transforma um texto na entrada em uma estrutura
de dados, em geral uma árvore, o que é conveniente para
processamento posterior e captura a hierarquia implícita desta
entrada.
Através da análise léxica é obtido um grupo de tokens, para que o
analisador sintático use um conjunto de regras para construir uma
árvore sintática da estrutura.
ATC – HIERARQUIA DE CHOMSKY
Análise Sintática
Em termos práticos, por exemplo, pode também ser usada para
decompor um texto em unidades estruturais para serem organizadas
dentro de um bloco.
A vasta maioria dos analisadores sintáticos implementados em
compiladores aceitam alguma linguagem livre de contexto para fazer a
análise.
MÁQUINA DE ESTADOS FINITOS
Definição
As máquinas de estados finitos são máquinas abstratas que capturam
as partes essenciais de algumas máquinas concretas.
Essas últimas vão desde máquinas de vender jornais e de vender
refrigerantes, passando por relógios digitais e elevadores, até
programas de computador, como alguns procedimentos de editores de
textos e de compiladores.
MÁQUINA DE ESTADOS FINITOS
Definição
Existem, basicamente, dois tipos de máquinas de estados finitos: os
transdutores e os reconhecedores (ou aceitadores) de linguagens.
Os transdutores são máquinas com entrada e saída, e os
reconhecedores são máquinas com apenas duas saídas possíveis;
geralmente uma delas significa “aceitação” da entrada, e a outra,
“rejeição” da entrada.
MÁQUINA DE ESTADOS FINITOS
Definição
Uma característica fundamental de uma máquina de estados finitos é
que sua memória é limitada e exclusivamente organizada em torno do
conceito de “estado”.
MÁQUINA DE ESTADOS FINITOS
Definição
Uma máquina de estados é um modelo matemático usado para
representar programas.
• Conjunto de estados.
• Regras de transição entre estados.
• Estado atual.
MÁQUINA DE ESTADOS FINITOS
Representação Clássica
MÁQUINA DE ESTADOS FINITOS
Exemplo
Um exemplo bem simples de uma FSM é um interruptor de luz.
MÁQUINA DE ESTADOS FINITOS
Em um sistema computacional normalmente uma FSM não é tão
simples assim, visto que geralmente os agentes podem ter um
conjunto muito maior de estados.
MÁQUINA DE ESTADOS FINITOS
Exemplo:
Jogo Pac Man
Os fantasmas Inky, Pinky, Blinky e Clyde do jogo Pac-man são
implementados via FSM.
Os fantasmas tem 3 comportamentos:
• Caçar (Chase)
• Fugir (Evade)
• Dispersar (Scatter)
MÁQUINA DE ESTADOS FINITOS
Exemplo:
MÁQUINA DE TURING
Definição:
Trata-se de um dispositivo imaginário embasado por uma teoria
revolucionária do seu autor, o britânico Alan Mathison Turing,
concebida aos 24 anos de idade.
A máquina de Turing formou a estrutura básica para fundamentar a
ciência da computação moderna e a computabilidade.
Foi responsável anos depois, pelo reconhecimento da comunidade
científica, declarando Turing com o título simbólico de “pai da
computação”.
MÁQUINA DE TURING
A teoria foi publicada pela primeira vez em 1936, num artigo intitulado
"On Computable Numbers, with an Application on the
Entscheidungsproblem".
Apesar da máquina de Turing não ter sido implementada fisicamente,
na totalidade pelo seu autor, o processo computacional foi
matematicamente demostrado e provado no artigo.
MÁQUINA DE TURING
Turing explicitou um dispositivo lógico que ele chamou de "automatic
machine" (ou “a-machine”), capaz de ler, escrever e apagar símbolos
binários em uma fita de comprimento ilimitado e dividida por
quadrados de igual tamanho. Uma cabeça de leitura/gravação se
moveria em qualquer direção ao longo da fita, um quadrado
por vez, e uma unidade de controle poderia interpretar uma lista de
instruções simples, movendo-se para a direita ou esquerda. A regra
executada determina o que se convencionou chamar de estado da
máquina.
MÁQUINA DE TURING
Representação da Máquina de Turing
Fita:
Usada simultaneamente como dispositivo de entrada, de saída e de
memória de trabalho;
É finita à esquerda e infinita (tão grande quanto necessário) à direita,
sendo dividida em células, cada uma das quais armazenando um
símbolo.
MÁQUINA DE TURING
O conceito de máquina de Turing é semelhante ao de uma fórmula ou
equação. Assim, há uma infinidade de possíveis máquinas de Turing,
cada uma correspondendo a um método definido ou algoritmo.
Turing propôs que cada algoritmo, formalizado como um conjunto
finito de instruções bem definidas, pudesse ser interpretado e
executado por um processo mecânico.
MÁQUINA DE TURING
Formalmente a máquina de Turing pode ser definida como uma
máquina que contém:
• Um conjunto finito de estados Q com um estado inicial distinto,
• Um conjunto finito de símbolos Σ.
MÁQUINA DE TURING
A interpretação e execução dos algoritmos são realizadas por estados e
uma função de transição determina o novo conteúdo da fita. Deste
modo, por restrição imposta ao algoritmo, pode-se alterar o conteúdo
de apenas um quadrado por vez ou movimentar a cabeça, no máximo
uma célula em qualquer direção.
É permitida também a utilização de qualquer conjunto finito de
símbolos para o alfabeto Σ, mesmo que a definição original tenha
insistido em Σ = {0,1}.
Esta mudança não tem impacto sobre a definição do conjunto de
funções computáveis pela máquina.
MÁQUINA DE TURING
Símbolos de uma MT
Os símbolos podem pertencer:
Inicialmente, a palavra a ser processada ocupa as células mais à
esquerda, após o marcador de início de fita, ficando as demais com
branco.
MÁQUINA DE TURING
Unidade de Controle
Reflete o estado corrente da máquina.
• Possui um número finito e predefinido de estados.
• Possui uma unidade de leitura e gravação (cabeça da fita),a qual
acessa uma célula da fita de cada vez.
• A cabeça da fita lê o símbolo de uma célula de cada vez e grava um
novo símbolo. Após a leitura/gravação (a gravação é realizada na
mesma célula de leitura), a cabeça move-se uma célula para a
direita ou esquerda.
MÁQUINA DE TURING
Programa ou Função de Transição.
• O programa comanda as leituras e gravações, o sentido de
movimento da cabeça e define o estado da máquina.
• Programa é uma função que, dependendo do estado corrente da
máquina e do símbolo lido, determina o símbolo a ser gravado, o
sentido do movimento da cabeça e o novo estado.
MÁQUINA DE TURING
Símbolos
MÁQUINA DE TURING
Função de Transição.
A Função de Transição será definida da seguinte forma:
• Um estado que lê um símbolo indo para outro estado onde escreve
outro símbolo e nos informa a direção que deve ser seguida.
MÁQUINA DE TURING
Modelo Formal
MÁQUINA DE TURING
Modelo Formal
MÁQUINA DE TURING
Modelo Formal
MÁQUINA DE TURING
Modelo Formal
MÁQUINA DE TURING
Exemplo 1
MÁQUINA DE TURING
Exemplo 2
MÁQUINA DE TURING
Linguagem Recursivamente Enumerável
Definição:
Em matemática, lógica e ciência da computação, uma linguagem
recursivamente enumerável é um tipo de Linguagem formal que
também é chamada de linguagem Turing-reconhecível.
MÁQUINA DE TURING
Linguagem Recursivamente Enumerável
Existem três equivalentes definições importantes para o conceito de
uma linguagem recursivamente enumerável:
1. Uma linguagem recursivamente enumerável formal é um
subconjunto recursivamente enumerável no conjunto de todas as
palavras possíveis sob o alfabeto da linguagem.
MÁQUINA DE TURING
Linguagem Recursivamente Enumerável
2. Uma linguagem recursivamente enumerável é uma linguagem
formal para a qual existe uma máquina de Turing que irá enumerar
todas as cadeias válidas da linguagem. Note que, se a linguagem é
infinita, o algoritmo de enumeração fornecido pode ser escolhido
de forma que evite repetições, uma vez que podemos testar se a
cadeia produzida para o número n é já é produzida para um
número que é inferior a n. Se ela já é produzida, use a saída da
entrada n+1 (recursivamente), mas mais uma vez, teste se é uma
cadeia nova.
MÁQUINA DE TURING
Linguagem Recursivamente Enumerável
3. Uma linguagem recursivamente enumerável é uma linguagem
formal para a qual existe uma máquina de Turing que irá parar e
aceitar quando se roda com qualquer cadeia da linguagem na
entrada e pode parar e rejeitar ou entrar em loop quando se roda
com qualquer cadeia que não é da linguagem. Esta é a diferença
entre linguagem recursiva, que exige que a máquina de Turing
sempre pare.
MÁQUINA DE TURING
Linguagem Recursivamente Enumerável
MÁQUINA DE TURING
Linguagem Recursivamente Enumerável
MÁQUINA DE TURING
Linguagem Recursiva
MÁQUINA DE TURING
Linguagem Recursiva
MÁQUINA DE TURING
Hipótese de Turing – Church
A tese de Turing- Chuch diz respeito à noção de um método mecânico e
efetivo no contexto da Lógica e Matemática. Efetivo e seu sinônimo
mecânico, são termos destas disciplinas. Não apresentam o significado
do nosso dia-a-dia.
Um método, ou procedimento, M, que é empregado para se obter um
resultado desejado é denominado “efetivo” ou mecânico.
MÁQUINA DE TURING
Hipótese de Turing – Church
Assim M:
- Deve ser descrito em um número finito de instruções exatas. (Cada
instrução sendo expressa por um número finito de símbolos);
- Se M não apresentar erros, deve produzir o resultado desejado em
um número finito de etapas;
- M pode ser realizado por um ser humano sem o auxílio de uma
máquina, ou seja, empregando apenas “lápis e papel”;
- O método M não deve exigir nenhuma inferência e nem mesmo
inventividade do ser humano que o executa.
MÁQUINA DE TURING
Hipótese de Turing – Church
O que é um algoritmo?
“Informalmente, um algoritmo é qualquer procedimento
computacional que recebe como entrada um ou mais valores e produz
como saída um ou mais valores. Um algoritmo é portanto uma
sequência etapas computacionais que transformam valores de entrada
para valores de saída” .
MÁQUINA DE TURING
Hipótese de Turing – Church
"As máquinas de Turing são versões formais de algoritmos e nenhum
procedimento computacional é considerado um algoritmo a não ser
que possa ser apresentado na forma de uma máquina de Turing"
MÁQUINA DE TURING
Hipótese de Turing – Church
Estabelece-se assim, a equivalência entre algoritmos e a Máquina de
Turing
Hipótese de Turing – Church: “Uma função da teoria dos números é
computável por um algoritmo se, e somente se, for computável por
Turing.”
Este enunciado da hipótese de Turing – Chuch é contemplado para a
computação dos números inteiros.
A máquina de Turing pode executar cálculos de números inteiros.
MÁQUINA DE TURING
Exemplo:
MÁQUINA DE TURING
Exemplo:
MÁQUINA DE TURING
Máquinas equivalentes à Máquina de Turing
Há provas formais que demonstram que o dispositivo da MT com fita
infinita possui exatamente o poder computacional de qualquer outra
versão estendida, tais como as seguintes:
- Múltiplas trilhas;
- Múltiplas fitas;
- Múltiplos cursores;
- Fita ilimitada em ambos os sentidos;
MÁQUINA DE TURING
Máquinas equivalentes à Máquina de Turing
- Transições que deslocam o cursor um número variável de posições;
- Transições sem leitura ou gravação de símbolos;
- Máquinas de Turing Multidimensionais;
- Máquinas de Turing com uma estrutura de memória auxiliar
organizada em pilha.
MÁQUINA DE TURING
Máquinas de Turing Não- Determinísticas
Nas máquinas de Turing, a função de transição g remete para o não
determinismo inerente aos dispositivos aceitadores apresentados.
Em outras palavras: dada uma mesma combinação de estado corrente
e de símbolo na fita de trabalho, é possível especificar múltiplas
transições.
MÁQUINA DE TURING
Máquina de Turing – Exemplo
Máquinas de Turing que aceita as seguintes linguagens
L = {w | w possui o mesmo número de a’s e b’s}
Resolução: 
M=({q0, q1, q2, q3, q4, q5}, {a,b}, {A,B }, δ, q0, □, {q5}, φ) 
MÁQUINA DE TURING
Máquina de Turing – Exemplo
MÁQUINA DE TURING
Máquina de Turing – Exemplo
Operação: 
- Se a partir do estado inicial (q0) é lido da fita o caractere “a” este é 
escrito “A” e a unidade de controle se desloca para direita até 
encontrar um “b” correspondente e escrever “B” no lugar deste, 
identificando um par de “a e b”. A partir deste ponto a unidade de 
controle se desloca para a esquerda até encontrar o “A” já marcado e o 
processo se reinicia. 
MÁQUINA DE TURING
Máquina de Turing – Exemplo
Operação
- Outro caminho possível a partir do estado inicial é ler o caractere “b”, 
escrever “B” e deslocar a unidade de controle para a direita até 
encontrar o “a” que formará o par e escrever “A”, de forma análoga ao 
outro caminho a unidade de controle se desloca para a esquerda até 
encontrar um “B” marcado e o processo se reinicia. 
Fim da operação: o processo termina quando a entrada for uma 
palavra vazia ou quando for encontrados todos os pares de a’s e b’s e o 
próximo caractere a ser lido for branco chegando ao estado final q5 
reconhecendo a palavra pertencente a linguagem. 
MÁQUINA DE TURING
Máquina de Turing – Simulador
Um software bastante conhecido como simulador de uma Máquina de
Turing é o JFLAP Version 7.1
http://www.jflap.org/
MÁQUINA DE TURING
Máquinas de Turing Universais
• Uma máquina de Turing Universal é uma máquina de Turing capaz
de simular qualquer outra apropriadamente codificada.
• “Processa programas que são codificações de máquinas de Turing.”
(Ramos, Vega e Neto, 2009).
• Simula a máquina descrita e produz como resultado o mesmo
resultado que a máquina simulada produziria.
• É universal, pois é capaz de executar qualquer algoritmo.
MÁQUINA DE TURING
Problema Solucionável (ou decidível)
Um problema é dito Solucionável ou Totalmente Solucionável se existe
um algoritmo que solucione o problema tal que sempre para qualquerentrada, com uma resposta afirmativa (aceita) ou negativa (rejeita).
MÁQUINA DE TURING
Problema Não-Solucionável (Não decidível)
Um problema é dito Não-Solucionável se não existe um algoritmo que
solucione o problema tal que sempre para, qualquer que seja a
entrada.
MÁQUINA DE TURING
Problema Parcialmente Solucionável ou Computável
Um problema é dito Parcialmente Solucionável ou Computável se
existe um algoritmo que solucione o problema tal que pare quando a
resposta é afirmativa (aceita).
Entretanto quando a resposta esperada for negativa, o algoritmo pode
parar (rejeita) ou permanecer processando indefinidamente.
MÁQUINA DE TURING
Problema Completamente Insolúvel
Um problema é dito Completamente Insolúvel ou Não-Computável se
não existe um algoritmo que solucione o problema tal que pare
quando a resposta é afirmativa.
É importante observar que alguns problemas não-solucionáveis são
parcialmente solucionáveis. Ainda, existem problemas não-
solucionáveis que possuem solução parcial.
MÁQUINA DE TURING
Problema Completamente Insolúvel
A Classe dos Problemas Solucionáveis é equivalente à Classe das
Linguagens Recursivas.
A Classe dos Problemas Parcialmente Solucionáveis é equivalente à
Classes das Linguagens Recursivamente Enumeráveis.
MÁQUINA DE TURING
Problema da Parada
O problema da parada é um problema de decisão sobre as
propriedades de programas de computadores em um determinado
modelo Turing-completo de computação, por exemplo todos os
programas que podem ser escritos em uma linguagem de programação
que é geralmente o suficiente para ser equivalente a uma máquina de
Turing.
O problema é determinar para uma dada entrada se o programa irá
parar com ela.
MÁQUINA DE TURING
Problema da Parada
Um problema de decisão é uma questão sobre um sistema formal com
uma resposta do tipo sim-ou-não.
Por exemplo, o problema: "dados dois números x e y, y é divisível por
x?" é um problema de decisão. Ou ainda: "Dado um número inteiro x, x
é um número primo?". A resposta para esses problemas pode ser 'sim'
ou 'não', e depende dos valores que as variáveis assumem em cada
instância do problema.
MÁQUINA DE TURING
Problema da Parada
Um problema de decisão também pode ser formalizado como o
problema de verificar se uma determinada cadeia de caracteres
pertence ou não a um conjunto de cadeias de caracteres, também
chamado de linguagem formal. O conjunto contém exatamente as
cadeias para as quais a resposta à pergunta é 'sim'.
MÁQUINA DE TURING
Problema da Parada
Métodos usados para resolver problemas de decisão são chamados de
procedimentos ou algoritmos.
Um algoritmo para o problema anterior explicaria em quais situações y
é divisível por x, dados x e y.
Um problema de decisão que pode ser resolvido por algum algoritmo é
chamado de problema de decisão decidível.
MÁQUINA DE TURING
Problema da Parada
Nesta área de trabalho abstrata não há limitações de memória ou
tempo necessário para a execução de um programa, pois poderão ser
necessários tempo e espaço arbitrários para o programa parar.
MÁQUINA DE TURING
Problema da Parada
A questão é se o programa simplesmente poderá parar com uma certa
entrada.
Por exemplo, em pseudocódigo, o programa:
enquanto Verdadeiro: continue
Não para, pelo contrário, entra em loop infinito. Por outro lado, o
programa:
imprimir "Hello World!"
Para muito rapidamente.
MÁQUINA DE TURING
Problema da Parada
Um programa mais complexo pode ser mais difícil de se analisar.
O programa pode rodar por um tempo fixo e se ele não parar, não há
um jeito de saber se o programa irá parar eventualmente ou se ele irá
continuar rodando para sempre.
Turing provou que não há um algoritmo que pode ser aplicado a
qualquer programa arbitrário, com uma entrada, para decidir se o
programa para ou não com esta entrada.
MÁQUINA DE TURING
Problema da Parada
A definição impõe que para uma dada entrada numérica de uma MT,
que possui um índice qualquer, a mesma irá parar para a condição
onde a entrada é igual ao índice pertencente ao estado da máquina. O
conjunto de entradas numéricas deve pertencer ao conjunto de
números naturais definidos para a máquina.
Quando isso acontece a MT para e indica através de uma determinada
sequência numérica.
Essa indicação pode ser através de uma sequência de valores 1, por
exemplo.
MÁQUINA DE TURING
Problemas Indecidíveis
Um problema indecidível é um problema de decisão em que é
impossível construir um algoritmo que sempre responde corretamente
sim ou não.
Um problema de decisão é qualquer questão arbitrária de sim-ou-não
sobre um conjunto infinito de entradas.
Por causa disto, é comum definir o problema de decisão de maneira
equivalente como: o conjunto de entradas para o qual o problema
retorna sim.
Estas entradas podem ser números naturais, mas também podem ser
outros valores de outros tipos, como cadeias de uma linguagem formal.
MÁQUINA DE TURING
Problemas Indecidíveis
Na teoria da computabilidade, o problema da parada é um problema
de decisão que pode ser estabelecido como:
Dada a descrição de um programa e uma entrada finita, decida se um
programa termina de executar ou se ele executará para sempre.
MÁQUINA DE TURING
Problemas Indecidíveis
Alan Turing que um algoritmo genérico, sendo executado sobre uma
máquina de Turing, que resolve o problema da parada para todos os
pares de entrada do programa possíveis necessariamente não pode
existir.
Consequentemente, o problema da parada é indecidível para
máquinas de Turing.
MÁQUINA DE TURING
Problemas Indecidíveis
Problemas indecidíveis podem estar relacionados a diferentes tópicos,
tais como lógica, máquinas abstratas ou topologia.
Observe que, como existem incontáveis problemas indecidíveis,
qualquer lista é, necessariamente, incompleta.
MÁQUINA DE TURING
Problemas Indecidíveis
É um exemplo de problema não solucionável:
a) Não existem problemas não solucionáveis.
b) Minimização de um autômato finito.
c) Detector universal de loops.
d) Reconhecimento de linguagens recursivas.
e) Tratamento de não determinismos em linguagens regulares.
Resposta: a alternativa correta é a c). O detector universal de loops, diz
respeito ao Problema da Parada.
MÁQUINA DE TURING
Complexidade Computacional
A teoria da complexidade computacional é um ramo que se concentra
em classificar problemas computacionais de acordo com sua
dificuldade inerente, e relacionar essas classes entre si.
Neste contexto, um problema computacional é entendido como uma
tarefa que é, em princípio, passível de ser resolvida por um
computador (o que basicamente significa que o problema pode ser
descrito por um conjunto de instruções matemáticas).
MÁQUINA DE TURING
Complexidade Computacional
Informalmente, um problema computacional consiste de instâncias do
problema e soluções para essas instâncias do problema.
Por exemplo, o teste de primalidade é o problema de determinar se um
dado número é primo ou não.
As instâncias deste problema são números naturais, e a solução para
uma instância é sim ou não, dependendo se o número é primo ou não.
MÁQUINA DE TURING
Complexidade Computacional
Um problema é considerado como inerentemente difícil se a sua
solução requer recursos significativos, qualquer que seja o algoritmo
usado.
A teoria formaliza esta intuição através da introdução de modelos
matemáticos de computação para estudar estes problemas e
quantificar os recursos necessários para resolvê-los, tais como tempo e
armazenamento.
MÁQUINA DE TURING
Complexidade Computacional
Outras medidas de complexidade também são utilizadas, tais como a
quantidade de comunicação (usada em complexidade de
comunicação), o número de portas em um circuito (usado na
complexidade de circuito) e o número de processadores (usados em
computação paralela).
Um dos papéis da teoria da complexidade computacional é determinar
os limites práticos do que os computadores podem e não podem fazer.
MÁQUINA DE TURINGComplexidade Computacional
Um modelo de computação é a definição de um conjunto de
operações que podem ser usadas numa computação e seus respectivos
custos.
Somente assumindo certo modelo de computação é possível analisar
os recursos computacionais requeridos, como tempo de execução e
espaço de armazenamento, ou discutir as limitações de algoritmos ou
computadores.
Na área de análise de algoritmos, é comum especificar um modelo de
computação em termos de operações primitivas, cada uma com um
custo unitário associado.
MÁQUINA DE TURING
Complexidade Computacional
Um modelo de computação é a definição de um conjunto de
operações que podem ser usadas numa computação e seus respectivos
custos.
Somente assumindo certo modelo de computação é possível analisar
os recursos computacionais requeridos, como tempo de execução e
espaço de armazenamento, ou discutir as limitações de algoritmos ou
computadores.
Na área de análise de algoritmos, é comum especificar um modelo de
computação em termos de operações primitivas, cada uma com um
custo unitário associado.
MÁQUINA DE TURING
Complexidade Computacional
Um problema computacional pode ser visto como uma coleção infinita
de instâncias em conjunto com uma solução para cada instância.
A sequência de entrada para um problema computacional é referido
como uma instância do problema, e não deve ser confundido com o
problema em si.
Na teoria da complexidade computacional, um problema se refere à
questão abstrata para ser resolvido.
Em contraste, uma instância deste problema é uma expressão
concreta, que pode servir como entrada para um problema de decisão.
MÁQUINA DE TURING
Classificação dos Problemas
Problema de Otimização
É um problema em que cada solução possível tem um valor associado e
desejamos encontrar a melhor solução com relação a esse valor.
Dentre as soluções possíveis, identificar qual é a melhor.
MÁQUINA DE TURING
Classificação dos Problemas
Problema de Otimização
Exemplo: Dado um grafo e dois vértices U e V, encontrar o caminho de
U até V que tenha o menor número de arestas (menor caminho)?
Neste problema procura-se encontrar o melhor caminho dentre
algumas opções possíveis de solução, por esse motivo ele se classifica
como um problema de otimização.
MÁQUINA DE TURING
Classificação dos Problemas
Problema de Decisão
São problemas cuja a resposta será sempre do tipo SIM ou NÃO.
Existe uma solução para um dados problema?
MÁQUINA DE TURING
Classificação dos Problemas
Exemplo:
Dado o grafo abaixo, verificar se existe uma trilha fechada que passa
por todas as arestas.
1 2
MÁQUINA DE TURING
Classificação dos Problemas
Verifica-se que o grafo 1 possui um caminho que passa por todas as
arestas enquanto que o grafo 2 não possui um caminho que consegue
passar por todas.
Essa á definição do que conhecemos como grafo Euleriano.
Euler demonstrou que um grafo conexo possui um ciclo euleriano, se e
somente se, ele não possui vértices de grau ímpar.
MÁQUINA DE TURING
Classificação dos Problemas
Um Caminho Euleriano é um caminho em um grafo que visita toda
aresta exatamente uma vez.
Com caso especial, um Circuito Euleriano é um caminho Euleriano que
começa e termina no mesmo vértice.
O que se constata somente no grafo 1 do exemplo.
MÁQUINA DE TURING
Classificação dos Problemas
Exemplo: Problema do grafo hamiltoniano
Um caminho hamiltoniano é um caminho que permite passar por
todos os vértices de um grafo G, não repetindo nenhum, ou seja,
passar por todos uma e uma só vez por cada. Caso esse caminho seja
possível descrever um ciclo, este é denominado ciclo hamiltoniano (ou
circuito hamiltoniano) em G.
MÁQUINA DE TURING
Classificação dos Problemas
Exemplo: Problema do grafo hamiltoniano
Dado o grafo abaixo, determinar se existe um circuito hamiltoniano.
Podemos verificar que ambos os exemplos se classificam como
problemas de decisão onde o objetivo é se obter uma resposta SIM ou
NÃO.
MÁQUINA DE TURING
Problemas Classe P e NP
Existe uma preocupação constante em definir se um problema é de
Otimização ou Decisão.
A Teoria da Complexidade não se aplica diretamente a problemas de
Otimização e sim a Problemas de Decisão.
MÁQUINA DE TURING
Problemas Classe P
Formada por problemas de decisão tratáveis, isto é, que podem ser
resolvidos por um algoritmo polinomial.
Exemplo: O problema do grafo euleriano pertence a classe P.
Esse tipo de problema é classificado dessa forma já que podemos
elaborar um algoritmo que defina se todos os vértices do grafo são de
grau par, não restando dúvida em relação a sua classificação.
MÁQUINA DE TURING
Problemas Classe NP (não determinístico em tempo polinomial)
Formada por problemas de decisão que possuem um verificador
polinomial para a resposta SIM.
NP denota o conjunto de linguagens que podem ser aceitas em tempo
polinomial por uma máquina de Turing não determinística.
Para classificação desse tipo de problema precisamos determinar o
verificador polinomial para se obter a resposta SIM a um determinado
questionamento.
MÁQUINA DE TURING
Problemas Classe NP (não determinístico em tempo polinomial)
Um problema de decisão está em NP se existe um algoritmo A tal que:
- Para qualquer instância X do problema com resposta SIM, existe um
certificado Y, tal que A(X,Y) devolve SIM.
- A consome tempo polinomial em |X|.
MÁQUINA DE TURING
Problemas Classe NP (não determinístico em tempo polinomial)
Exemplo: Problema do grafo hamiltoniano.
Dado uma instância cuja resposta é SIM, ou seja, dado um grafo que é
hamiltoniano, qual é o certificado de que ele é hamiltoniano?
Isso pode ser verificado em tempo polinomial?
MÁQUINA DE TURING
Problemas Classe NP (não determinístico em tempo polinomial)
Exemplo: Problema do grafo hamiltoniano.
Dado uma instância cuja resposta é SIM, ou seja, dado um grafo que é
hamiltoniano, qual é o certificado de que ele é hamiltoniano?
Verificar se o circuito passa por todos os vértices.
Circuito hamiltoniano <V1, V2,..., VN> Esse é o próprio certificado
Isso pode ser verificado em tempo polinomial?
Sim, pois existe uma passagem por todos os vértices e sequência.
Podemos concluir que o problema está na classe NP
MÁQUINA DE TURING
Problemas Classe P = NP
Computacionalmente até os tempos atuais não se conseguiu
comprovar a equivalência entre problemas do tipo P e NP.
MÁQUINA DE TURING
Redução entre Problemas
Uma forma comum de resolver um problema A é transformá-lo em um
outro problema B, cuja solução é conhecida e converter a solução de B
para uma solução de A.
Dado dois problemas A e B, uma redução de A para B (A≤B) é um
algoritmo polinomial que resolve A utilizando B.
MÁQUINA DE TURING
Redução entre Problemas
Exemplo:
A seleção de k-ésimo mínimo pode ser reduzido ao problema da
ordenação.
Encontrar, por exemplo, o terceiro mínimo de um certo vetor.
• Utiliza-se então o algoritmo de ordenação para acertar o vetor em
uma determinada ordem.
• Então encontra-se o terceiro elemento desse vetor ordenado.
MÁQUINA DE TURING
Redução entre Problemas
Se um problema A se reduz a outro problema B, então A não é mais
difícil de resolver do que B.
Afirmativa 1: Se A≤B e B P então A P
Se A pode ser reduzido a B e B faz parte da classe P então A também
faz parte da classe P.
Afirmativa 2: Se A≤B e B≤C então A≤C
Se A pode ser reduzido a B e B pode ser reduzido a C então A pode ser
reduzido a C
MÁQUINA DE TURING
Problema NP-Completo
Um problema NP-completo é um subconjunto de NP, o conjunto de
todos os problemas de decisão os quais suas soluções podem ser
verificadas em tempo polinomial.
Um problema p em NP também está em NPC Se e somente se todos os
outros problemas em NP podem ser transformados em p em tempo
polinomial.
MÁQUINA DE TURING
Problema NP-Completo
Um problema de decisão P é NP-completo se:
1. P está em NP, e
2. Todo problema em NP é redutível para P em tempo polinomial.
MÁQUINA DE TURING
Problema Caixeiro Viajante
Suponhaque um caixeiro viajante tenha de visitar n cidades diferentes,
iniciando e encerrando sua viagem na primeira cidade.
Suponha, também, que não importa a ordem com que as cidades são
visitadas e que de cada uma delas pode-se ir diretamente a qualquer
outra.
O problema do caixeiro viajante consiste em descobrir a rota que torna
mínima a viagem total.
MÁQUINA DE TURING
Problema Caixeiro Viajante
Exemplificando o caso n = 4:
se tivermos quatro cidades A, B, C e D, uma rota que o caixeiro deve
considerar poderia ser:
saia de A e daí vá para B, dessa vá para C, e daí vá para D e então volte
a A.
Quais são as outras possibilidades?
MÁQUINA DE TURING
Problema Caixeiro Viajante
É muito fácil ver que existem seis rotas possíveis:
• ABCDA
• ABDCA
• ACBDA
• ACDBA
• ADBCA
• ADCBA
MÁQUINA DE TURING
Problema Caixeiro Viajante
O problema do caixeiro é um clássico exemplo de problema de
otimização combinatória.
A primeira coisa que podemos pensar para resolver esse tipo de
problema é reduzí-lo a um problema de enumeração: achamos todas
as rotas possíveis e, usando um computador, calculamos o
comprimento de cada uma delas e então vemos qual a menor.
MÁQUINA DE TURING
Problema Caixeiro Viajante
Para acharmos o número R(n) de rotas para o caso de n cidades, basta
fazer um raciocínio combinatório simples e clássico.
De modo semelhante, para o caso de n cidades, como a primeira é fixa,
o leitor não terá nenhuma dificuldade em ver que o número total de
escolhas que podemos fazer é (n-1) x (n-2) x ... x 2 x 1. De modo que,
usando a notação de fatorial: R(n) = (n-1)!.
MÁQUINA DE TURING
Problema Caixeiro Viajante
Assim que nossa estratégia reducionista consiste em gerar cada uma
dessas R(n) = (n-1)! rotas, calcular o comprimento total das viagens de
cada rota e ver qual delas tem o menor comprimento total.
Trabalho que não necessariamente possa ser facilmente resolvido de
forma computacional.
MÁQUINA DE TURING
Problema Caixeiro Viajante
Suponhamos temos um muito veloz computador, capaz de fazer 1
bilhão de adições por segundo. Isso parece uma velocidade imensa,
capaz de tudo.
Com efeito, no caso de 20 cidades, o computador precisa apenas de 19
adições para dizer qual o comprimento de uma rota e então será capaz
de calcular / 19 = 53 milhões de rotas por segundo.
MÁQUINA DE TURING
Problema Caixeiro Viajante
O problema é que a quantidade ( n - 1 )! cresce com uma velocidade
alarmante, sendo que muito rapidamente o computador torna-se
incapaz de executar o que lhe pedimos.
O crescimento é mostrado na tabela abaixo.
MÁQUINA DE TURING
Problema Caixeiro Viajante
Observe que o aumento no valor do n provoca uma muito lenta
diminuição na velocidade com que o computador calcula o tempo de
cada rota (ela diminui apenas de um sexto ao n aumentar de 5 para
25), mas provoca um imensamente grande aumento no tempo total de
cálculo.
Em outras palavras: a inviabilidade computacional é devida à presença
da fatorial na medida do esforço computacional do método da
redução.
MÁQUINA DE TURING
Problema Caixeiro Viajante
Com efeito, se essa complexidade fosse expressa em termos de um
polinómio em n o nosso computador seria perfeitamente capaz de
suportar o aumento do n.
Confira isso na seguinte tabela que corresponde a um esforço
computacional polinomial R( n ) = :
MÁQUINA DE TURING
Problema Caixeiro Viajante
A existência ou não de um método polinomial para resolver o
problema do caixeiro viajante é um dos grandes problemas em aberto
da Matemática.
Costuma-se resumir essas propriedades do problema do caixeiro
dizendo que ele pertence à categoria dos problemas NP - completos.
MÁQUINA DE TURING
Problema do Particionamento
Na ciência da computação, o problema da partição é a tarefa de
decidir se um determinado multiconjunto S de números inteiros
positivos pode ser particionado em dois subconjuntos de S1 e
S2 , tais que a soma dos números em S1 é igual à soma dos
números em S2.
Embora o problema da partição seja NP-completo, existe uma
solução com programação dinâmica com tempo pseudo-
polinomial e há uma heurística que resolve o problema, em
muitos casos, de forma otimizada, ou aproximadamente.
MÁQUINA DE TURING
Problema do Particionamento
Por esta razão, ele tem sido chamado de "o problema NP-difícil
mais fácil".
Há uma versão otimizada do problema da partição, que é
particionar o multiconjunto S em dois subconjuntos S1, S2 , tais
que a diferença entre a soma dos elementos de S1 e a soma
dos elementos de S2 é minimizada.
MÁQUINA DE TURING
Problema do Particionamento
A versão de otimização é NP-difícil, mas pode ser resolvida de
forma eficiente na prática
Exemplo:
Dado S = {3,1,1,2,2,1}, uma solução válida para o problema da
partição é formada pelos dois conjuntos S1 = {1,1,1,2} e S2 =
{2,3}.
MÁQUINA DE TURING
Resumo
Problemas intratáveis ou difíceis são comuns na natureza e nas
áreas do conhecimento.
• Problemas podem ser classificados em:
– “fáceis”: resolvidos por algoritmos polinomiais.
– “difíceis”: os algoritmos conhecidos para resolvê-los são
exponenciais.
MÁQUINA DE TURING
Resumo
• Complexidade de tempo da maioria dos problemas é polinomial
ou exponencial.
• Polinomial: função de complexidade é O(p(n)), onde p(n) é um
polinômio.
– Exemplos: pesquisa binária (O(log n)), pesquisa sequencial
(O(n)), ordenação por inserção (O( )), e multiplicação de
matrizes (O( )).
MÁQUINA DE TURING
Resumo
• Exponencial: função de complexidade é O( ), c > 1.
– Exemplo: Problema do Caixeiro Viajante (PCV) (O(n!)).
– Mesmo problemas de tamanho pequeno a moderado não
podem ser resolvidos por algoritmos não-polinomiais.
MÁQUINA DE TURING
Problema do Particionamento
Ambos os conjuntos a soma é de 5, e eles são partições de S.
Note que esta solução não é única. S1 = {3,1,1} e S2 = {2,2,1} é
outra solução.
Nem todos os multiconjuntos de números inteiros positivos tem
uma partição em duas metades, com igual soma. Um exemplo
de um conjunto S = {2,5}.
MÁQUINA DE TURING
Satisfabilidade Booleana
O problema de satisfatibilidade booleana (SAT) é um problema de
decisão, cuja instancia é uma expressão booleana escrita somente com
operadores AND, OR, NOT, variáveis, e parênteses.
A questão é: dada uma expressão, será que há alguma atribuição de
valores VERDADEIROS e FALSOS para as variáveis que torne a expressão
inteira verdadeira?
MÁQUINA DE TURING
Satisfabilidade Booleana
Uma fórmula da lógica proposicional é dita satisfatível- ou seja,
avaliada como VERDADEIRA - se for possível atribuir valores lógicos a
suas variáveis de tal maneira que eles tornem a fórmula verdadeira.
A classe de fórmulas satisfatíveis proposicionais é NP-completa.
MÁQUINA DE TURING
Problema da Mochila
Consiste na escolha de itens de um conjunto S segundo um limite de
capacidade do sistema b, normalmente dados por peso ou tamanho.
Deve-se preencher a mochila de forma a obter o máximo valor de
utilidade.
Cada item possui um peso e um valor
MÁQUINA DE TURING
Problema da Mochila
• Objetivo de maximizar a utilização da mochila.
• Restrição do tamanho e / ou peso
Exemplo: Considere uma mochila com capacidade para 15kg e cinco
itens para colocar nela.
Deseja-se maximizar a soma dos valores dos itens adicionados a
mochila. Item Valor Peso
A 4 12
B 2 2
C 1 1
D 2 1
E 10 4
MÁQUINA DE TURING
Problema da Mochila
Max Z = 8
Limitações: 5 7
, {0,1} - todas as variáveis devem assumir
valores 0 e 1
MÁQUINA DE TURING
Problema da Mochila
Algoritmo de Força Bruta
Compara todas as possibilidades de preenchimento da mochila que
não violem a restrição de capacidade e retorna a melhor solução
encontrada.
Este algoritmo funciona quando o número de possibilidades é
pequeno.
MÁQUINA DE TURING
Problema da Mochila
Problema NP-difícil: tempo de resolução cresce exponencialmente com
a dimensão.
Conforme o número de objetos aumenta, o problema cresce de forma
a ser impossível gerar e analisar todasas possíveis soluções em tempo
aceitável.
MÁQUINA DE TURING
Problema da Mochila
Para que a heurística tenha melhor desempenho, calcula-se o valor de
utilidade de cada objeto do conjunto como:
/
Dessa forma conseguimos avaliar o valor por quilo de cada objeto
tendo uma visão melhor do que é mais valioso a ser carregado.
A cada interação objetiva-se analisar se cabe mais um objeto na
mochila de acordo com o valor de utilidade.
MÁQUINA DE TURING
Problema da Mochila
Enquanto existir objeto no conjunto S que caiba na mochila:
• Escolha desses objetos, aquele de maior valor de utilidade
Algoritmo Guloso
Item Valor Peso Vu
A 4 12 0,333
B 2 2 1
C 1 1 1
D 2 1 2
E 10 4 2,5
MÁQUINA DE TURING
Problema da Mochila
Algoritmo Guloso
MochilaA
B
C
D
E Item Valor Peso Vu
A 4 12 0,333
B 2 2 1
C 1 1 1
D 2 1 2
E 10 4 2,5
MÁQUINA DE TURING
Problema da Mochila
Algoritmo Guloso
Capacidade Disponível: 11
MochilaA
B
C
D
E Item Valor Peso Vu
A 4 12 0,333
B 2 2 1
C 1 1 1
D 2 1 2
E 10 4 2,5
MÁQUINA DE TURING
Problema da Mochila
Algoritmo Guloso
Capacidade Disponível: 8
MochilaA
B
C
D
E Item Valor Peso Vu
A 4 12 0,333
B 2 2 1
C 1 1 1
D 2 1 2
E 10 4 2,5
MÁQUINA DE TURING
Problema da Mochila
Algoritmo Guloso
Capacidade Disponível: 7
A não pode ser inserida devido a limitação de peso.
MochilaA
B
C
D
E Item Valor Peso Vu
A 4 12 0,333
B 2 2 1
C 1 1 1
D 2 1 2
E 10 4 2,5
MÁQUINA DE TURING
Problema da Mochila
Algoritmo Guloso
Valor total da mochila: $ 15,00
Existirá solução melhor com o objeto A?
MochilaA
B
C
D
E
MÁQUINA DE TURING
Problema da Mochila
Neste caso, outros modelos mostraram a mesma solução, portanto
para este problema muito simples esse algoritmo se mostrou eficiente.
Mas não temos a garantia de ter sempre o mesmo resultado, ou o
ótimo como retorno.
MÁQUINA DE TURING
Problema da Mochila
O problema da mochila é um problema de optimização combinatória.
O nome dá-se devido ao modelo de uma situação em que é necessário
preencher uma mochila com objetos de diferentes pesos e valores.
A formulação do problema é extremamente simples, porém sua
solução é mais complexa.
Algumas soluções podem ser aplicadas para resolvê-lo, porém nem
todos podem apresentar um resultado ótimo.
MÁQUINA DE TURING
Teorema de Cook
Na teoria da complexidade computacional o teorema de Cook afirma
que o problema de satisfatibilidade booleana é NP-completo.
Isto é, qualquer problema em NP pode ser reduzido em tempo
polinomial por uma máquina de Turing determinística para o problema
de determinar se uma fórmula booleana é satisfatível.
O problema de satisfatibilidade booliana é o problema de determinar
se existe uma determinada valoração para as variáveis de uma
determinada fórmula booliana tal que esta valoração satisfaça esta
fórmula em questão.
MÁQUINA DE TURING
Teorema de Cook
Uma importante consequência desse teorema é que se existe um
algoritmo de tempo polinomial para resolver a satisfatibilidade, então
existe um algoritmo de tempo polinomial para resolver todos os
problemas em NP.
Crucialmente, o mesmo acontece para qualquer problema NP-
completo.
MÁQUINA DE TURING
Teorema de Cook
Definição:
• Um problema de decisão está em NP se pode ser resolvido por um
algoritmo não determinístico em tempo polinomial.
• Um caso do problema booleano da satisfatibilidade é uma expressão
booleana que combina variáveis booleanas usando operadores
booleanos.
• Uma expressão é satisfatível se existe alguma atribuição de valores
as variáveis que faz toda a expressão verdadeira.
MÁQUINA DE TURING
Teorema de Cook
Conceito
Dado qualquer problema de decisão em NP, construir uma Máquina de
Turing não determinística que o resolva em tempo polinomial.
Então, para cada entrada nessa máquina, construir uma expressão
booleana tal que a entrada é passada para a máquina, a máquina roda
corretamente, sempre que a máquina dá a resposta "sim".
MÁQUINA DE TURING
Teorema de Cook
Conceito
Então a expressão pode ser satisfeita se e somente se existe um forma
da máquina rodar corretamente e a resposta ser "sim", então a
satisfatibilidade da expressão construída é equivalente a perguntar se a
máquina vai responder "sim".
MÁQUINA DE TURING
Teorema de Godel
Os teoremas da incompletude de Gödel são dois teoremas da lógica
matemática que estabelecem limitações inerentes a quase todos os
sistemas axiomáticos, exceto aos mais triviais.
Sistema axiomático:
Na matemática, um sistema axiomático, é qualquer conjunto de
axiomas que podem ser ligados em conjunção para logicamente
derivar teoremas. Uma teoria matemática consiste em um sistema
axiomático e todos os seus teoremas. Um sistema axiomático que é
completamente descrito é um tipo especial de sistema formal. Uma
prova formal é uma versão completa de uma prova matemática dentro
de um sistema formal.
MÁQUINA DE TURING
Teorema de Godel
Axiomas:
Na lógica tradicional, um axioma ou postulado é uma sentença ou
proposição que não é provada ou demonstrada e é considerada como
óbvia ou como um consenso inicial necessário para a construção ou
aceitação de uma teoria. Por essa razão, é aceito como verdade e serve
como ponto inicial para dedução de outras verdades (dependentes de
teoria).
MÁQUINA DE TURING
Teorema de Godel
O primeiro teorema da incompletude afirma que nenhum sistema
consistente de axiomas, cujos teoremas podem ser listados por um
“procedimento efetivo” (e.g., um programa de computador que pode
ser qualquer tipo de algoritmo), é capaz de provar todas as verdades
sobre as relações dos números naturais (aritmética). Para qualquer um
desses sistemas, sempre haverá afirmações sobre os números naturais
que são verdadeiras, mas que não podem ser provadas dentro do
sistema.
MÁQUINA DE TURING
Teorema de Godel
O segundo teorema da incompletude, uma extensão do primeiro,
mostra que tal sistema não pode demonstrar sua própria consistência.
Teorema 1: "Qualquer teoria axiomática recursivamente enumerável e
capaz de expressar algumas verdades básicas de aritmética não pode
ser, ao mesmo tempo, completa e consistente. Ou seja, em uma teoria
consistente, sempre há proposições que não podem ser demonstradas
nem verdadeiras, nem falsas."
MÁQUINA DE TURING
Teorema de Godel
Teorema 2: "Uma teoria, recursivamente enumerável e capaz de
expressar verdades básicas da aritmética e alguns enunciados da teoria
da prova, pode provar sua própria consistência se, e somente se, for
inconsistente."