Redutibilidade
Introdução
A Redutibilidade não diz nada em resolver A ou B sozinhos, mas somente sobre a solubilidade de A na presença de uma solução para B.
Como exemplo de Redutibilidade em aspectos matemáticos podemos citar: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 inscrever uma matriz.
Desenvolvimento
Quando A é redutível a B,resolverA não pode ser mais difícil que resolver B,por que 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 indecibilidade.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.
Indecibilidade é umproblema de decisãocom 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 é permitido 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 extremidadeesquerda 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 Indecibilidade 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 maissimples é 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.
Conclusão
Técnica de resolução de problemas. . . Envolvendo no mínimo dois..A e B.
Nenhum dos problemas depende um do outro.
Funções e respostas nem sempre complementam todo o problema, apenas solucionando apenas partes dele.
As funções computáveis exercem um exemplo de redução e execução de variáveis.
Redutibilidade está no nosso cotidiano e nas nossas vidas.
Referências
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.
Vermunt, J.D. Metacognitive, cognitive and affective aspects of learning styles and strategies: a phenomenographic analysis. Higher Education, 31, p.25-50. 1996.
Weiner, B. History of motivational research in education. Journal of Educational Psychology, 82, 616-622. 1990.
Autor: maria fernandes
Artigos Relacionados
A Sociedade Industrial Moderna
Se Agarrando Ao Tranco Da Esperança.
O Chão
A Perspectiva Construtivista De Ensino
As Pontuais Mudanças Trazidas Pela Lei 11.689/08 = Júri
Para O Dia Das MÃes - Ser MÃe
Pasma Imaginação