Redutibilidade
Esta página ou se(c)ção precisa ser formatada para o padrão wiki. (Setembro de 2013) |
As referências deste artigo necessitam de formatação. (Setembro de 2013) |
Redutibilidade é o principal método de provar que problemas são computacionalmente insolúveis. Sabemos que a Máquina de Turing é um modelo de um computador de propósito geral e que existem diversos exemplos de problemas que são solúveis por máquinas de Turing como também problemas computacionalmente insolúveis. Ao se examinar problemas insolúveis introduzimos o método de redutibilidade que prova que alguns problemas são computacionalmente insolúveis.
A Redutibilidade não diz nada em resolver A ou B sozinhos, mas somente sobre a solubilidade de A na presença de um método para resolver B. Como exemplo de Redutibilidade em aspectos matemáticos podemos citar que a medição da área de um retângulo se reduz ao problema de se medir seu comprimento e largura. O Problema de se resolver um sistema de equações lineares se reduz ao problema de se inverter uma matriz. Quando A é redutível a B, resolver A não pode ser mais difícil que resolver B, porque uma solução para B dá solução para A. Em resumo, nosso método para provar que um problema é indecidível será mostrar que algum outro problema já conhecido como sendo indecidível se reduz a ele. Aborda uma determinada entrada para Máquina de Turing, estabelecendo uma relação de redução para definirmos se a máquina pára (aceitando ou rejeitando) sobre a entrada anteriormente definida.
Ex: Problema = {<M,w> | M é uma MT e M pára sobre a entrada w}.
A principal chave da questão é o problema de entrada e o de comportamento. Vemos que um faz a redução do outro (a entrada para uma máquina, definindo o estado de comportamento). A Redutibilidade é diretamente ligada com a indecidibilidade.Os teoremas ilustram as estratégias para provar que um problema é indecidível. O método da Redutibilidade faz uso de notações, exceto,quando nos referimos a própria Máquina de Turing,sendo essa provada através do método da diagonalização. Diagonalização é uma técnica de comparação de métodos ou problemas, envolvendo tamanhos,espaços ou quantidades. Indecidibilidade é um problema de decisão com conjunto de números naturais; o "problema" é determinar se um número em particular pertence ao conjunto ou notação, afetando em sua decisão. O método de história da computação é uma técnica importante para provar que uma entrada é redutível a certas linguagens.Esse método é freqüentemente útil quando o problema a ser mostrado como indecidível envolve testar a existência de algo. A história de computação para uma máquina de Turing sobre uma entrada é simplesmente a seqüência de configurações pelas quais a máquina passa à medida que processa a entrada. É um registro completo da computação dessa máquina.
Tomemos duas definições que descrevem essas vias:
Primeira Definição: Seja M uma máquina de Turing e w uma cadeia de entrada.Uma história de computação de aceitação para M sobre w é uma seqüência de configurações, C1, C2. . . Cn, onde C1 é a configuração inicial de M sobre w,Cn é uma configuração de aceitação de M, e cada Ci segue legitimamente de Ci-1 conforme as regras de M. Uma história de computação de rejeição para M sobre w é definida similarmente, exceto que Cn é uma configuração de rejeição.
Segunda Definição: Um autômato linearmente limitado é um tipo restrito de máquina de Turing na qual a cabeça de leitura-escrita não é permitida mover-se para fora da parte da fita contendo a entrada. Se a máquina tentar mover sua cabeça para além de qualquer uma das extremidades da entrada, a cabeça permanecerá onde está, da mesma maneira que a cabeça não se movimentará para além da extremidade esquerda da fita de uma máquina de Turing ordinária.
Traduzindo a segunda via, podemos dizer que um autômato limitado é uma Máquina de Turing com quantidade limitada de memória.Ela só pode resolver problemas que requerem memória que possa caber dentro da fita usada para entrada. A Indecidibilidade não está somente confinada a problemas relacionados a autômatos. É a formalização da Redutibilidade. A noção de reduzir um problema a outro pode ser definida formalmente de várias maneiras, a forma mais simples é definida por Mapeamento. De forma resumida, dizemos que ser capaz de reduzir um problema A ao problema B usando uma redução por mapeamento significa que existe uma função computável que converte instâncias do problema A para instâncias do problema B. Uma Máquina de Turing computa uma função iniciando com a entrada para a função sobre a fita e parando com a saída da função sobre a fita.
Redução
editarUma Redução (complexidade) é uma maneira de converter um problema em outro de forma que uma solução para o segundo problema possa ser usada para resolver o primeiro. Essas redutibilidades aparecem frequentemente no dia-a-dia, mesmo que em geral não nos refiramos a ela dessa forma.
Por exemplo, supondo que uma pessoa deseje se orientar em uma cidade nova. Seria muito mais fácil se a pessoa em questão tivesse consigo um mapa. Consequentemente o problema pode ser reduzido ao problema de se obter um mapa da nova cidade em que se está.
A redutibilidade sempre envolve dois problemas, que denominamos A e B. Se A se reduz a B, podemos usar uma solução para B para resolver A. Assim no nosso exemplo, A é o problema de se orientar na cidade e B é o problema de se se obter um mapa da cidade. Notemos que a redutibilidade não diz nada sobre resolver A ou B separados, mas apenas sobre a solubilidade de A na presença de uma solução para B.
O que se segue são exemplos adicionais de redutibilidades. O problema de se viajar de Recife a Londres se reduz ao problema de se comprar uma passagem aérea entre as duas cidades. Esse problema, por sua vez, se reduz ao problema de ganhar o dinheiro para passagem. E esse último problema se reduz ao problema de se encontrar uma fonte de renda.
Problemas Matemáticos
editarA redutibilidade também se encontra em problemas matemáticos. Por exemplo, o problema de se medir a área de um retângulo se reduz ao problema de se medir seu comprimento e largura, assim como em um quadrado o problema se reduziria a encontrarmos a medida de um de seus lados. O problema de se resolver um sistema de equações lineares se reduz ao problema de se inverter uma Matriz.
Teoria da Complexidade
editarA redutibilidade desempenha um importante papel na classificação de problemas por decidibilidade e, posteriormente, em teoria da complexidade também.
Quando A é redutível a B, resolver A não pode ser mais difícil do que resolver B, porque uma solução para B dá uma solução para A. Em termos de teoria da computabilidade, se A for redutível a B e B for decidível, A também será decidível. Equivalentemente, se A for indecidível e redutível a B, B será indecidível. Essa última versão é a chave para provar que vários problemas são indecidíveis.
Em resumo, um excelente método para provar que um problema é indecidível será mostrar que algum outro problema já conhecido como sendo indecidível se reduz a ele
Redutibilidade por mapeamento em tempo polinomial
editarUma linguagem A é redutível por mapeamento em tempo polinomial, ou simplesmente redutível em tempo polinomial, à linguagem B se existe uma função computável em tempo polinomial onde para toda w, w pertença a A se e somente se f(w) pertença a B. A função é denominada redução de tempo polinomial de A para B. Em alguns livros-texto redutibilidade por mapeamento também pode ser chamado de redutibilidade muitos-para-um.
A linguagem A é redutível por mapeamento à linguagem B, escrito A ≤m B, se existe uma função computável ƒ: Σ → Σ, onde para toda w, w ∈ A ←→ ƒ(w) ∈ B. A função ƒ é denominada a redução de A para B.
Funções computáveis
editarUma máquina de Turing computa uma função iniciando com a entrada para a função sobre a fita e parando com a saída da função sobre a fita. Uma função ƒ: Σ → Σ* é uma função computável se alguma máquina de Turing M, sobre toda entrada w, pára com exatamente ƒ(w) sobre a fita. Todas as operações aritméticas usuais sobre inteiros são funções computáveis. Por exemplo, podemos construir uma máquina que toma entrada <m,n> e retorna m+n, a soma de m e n.
Relações de redutibilidade
editarUma relação de redutibilidade é uma relação binária em conjuntos de números naturais que são:
- Reflexiva : todo conjunto é redutível a ele mesmo.
- Transitiva : Se um conjunto A é redutível a um conjunto B e um conjunto B é redutível a um conjunto C, então A é redutível a C.
As noções de redutibilidade estudadas na teória da computação têm a propriedade informal de que A é redutível a B se e somente se algum (possivelmente até mesmo não efetivo) procedimento de decisão para B pode ser efetivamente convertido para um procedimento de decisão para A. As diferentes relações de redutibilidade variam de métodos para métodos, que permitem ou não o uso de processos de conversão.
Referências
editar- K. Ambos-Spies and P. Fejer, 2006. "Degrees of Unsolvability." Unpublished preprint.
- P. Odifreddi, 1989. Classical Recursion Theory, North-Holland. ISBN 0-444-87295-7
- P. Odifreddi, 1999. Classical Recursion Theory, Volume II, Elsevier. ISBN 0-444-50205-X
- E. Post, 1944, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society, volume 50, pages 284–316.
- H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability, second edition 1987, MIT Press. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
- G Sacks, 1990. Higher Recursion Theory, Springer-Verlag. ISBN 3-540-19305-7
- Michael Sipser, Thomson Pioneira, ISBN 8522104999, 2007. (Tradução brasileira de Introduction to the Theory of Computation, Michael Sipser, Second Edition, PWS Publishing Company, February 2005, ISBN 0-534-95097-3.)
- Almeida, L. S. & Freire, T. Metodologia da investigação em psicologia e educação. Braga: Psiquilíbrios. 2003.
- Bessa- Oliveira. Níveis de ajustamento e auto-regulação académica em estudantes universitários. Universidade de Aveiro. Dissertação de Mestrado. 2000.
- Biggs, J. B. . Assessing study approaches to learning. Australian Psychologist, 23, 197-206.1988
- Biggs, J.B. Student Approaches to Learning and Stydying. Hawthorm: Australian Council for Educational Research. 1987.
- Boekaerts, M.; Pintrich, P. e Zeidner,M.(Eds.) Handbook of Self-Regulation. Academic Press. Sage. 2000.
- Cross, S. E. & Markus, H. R. Self-schemas, possible selves, and competent performance,Journal of Educational Psychology, 86, 423-438.1994.
- Entwistle, N. J. La comprensión del aprendizaje en el aula. Barcelona: Paidós.1988.
- Marton, F. Hounsel, D. e Entwistle,N. (Eds.) The Experience of Learning. Edinburgh: Scottish Academic Press. 1997.
- McCombs, B. L. & Marzano, R. J. Putting the self in self-regulated learning: The self as agent in integring will and skill. Educational Psychologist, 25, 51-69.
- Pascarela, E.T. e Terenzinni,P.T. How College affect students. San Francisco: Jossey-Bass Publishers. 1991.
- Pintrich, P. R. & Schrauben, B. Students´ motivational beliefs and their cognitive engagement in classroom academic task. In D. H. Schunk & J. L. Meece (Eds.), Student perceptions in the classroom. Hillsdale, NJ: Erlbaum. 1992
- Rosário (2000).
- Santos, L. Adaptação académica e rendimento escolar: estudo com alunos universitários do 1ºano. Braga. Universidade do Minho.Grupo de Missão para a Qualidade do Ensino / Aprendizagem. 2001
- Schunk, D.H. e Zimmerman, B.J. Self-regulation of learning performance: issues and educational applications. Hillsdale: Erlbaum Associates. 1994.
- Soares, A.P.; Osório, A.; Capela, J.V.; Almeida, L. ; Vasconcelos, R.M.; Caíres, S.M. Transição para o Ensino Superior. Braga: Universidade do Minho. 2000.
- Tavares, J. e Santiago, R. (Orgs.) Ensino Superior: (in)sucesso académico. Porto: Porto Editora. 2000.
- Tinto, V. Leaving College: Rethinking the causes and cures of student attrition. Chicago,IL: University of Chicago Press. 1991.
- Upcraft, M.L. e Gardner, J.N. (Eds.) The Freshman Year Experience. San Francisco: Jossey-Bass Publishers. 1989.