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.