Em 1900, o grande e influente matem\u00e1tico David Hilbert, no congresso internacional de matem\u00e1ticos, anunciou os 23 problemas que deveriam nortear a pesquisa no s\u00e9c. 20. Entre eles, o d\u00e9cimo, sobre um algoritmo para busca de ra\u00edzes de equa\u00e7\u00f5es diofantinas (com coeficientes e vari\u00e1veis reais), foi estudado por nada menos que Alan Turing, que na \u00e9poca, d\u00e9cada de 1930, era aluno de doutorado de Alonzo Church (criador do lambda-c\u00e1lculo). Um exemplo de equa\u00e7\u00e3o diofantina \u00e9 ax+by=c, sendo que, dados a, b e c n\u00fameros reais, queremos saber quais valores de x e y levam \u00e0 igualdade. Turing, trabalhando no modelo de computa\u00e7\u00e3o que hoje leva o seu nome, a m\u00e1quina de Turing, descobriu que diversos problemas em matem\u00e1tica n\u00e3o tem algoritmos para sua solu\u00e7\u00e3o. Em 1970, Yuri Matiyasevich, matem\u00e1tico e cientista da computa\u00e7\u00e3o russo, resolveu o problema de forma definitiva, ou seja, n\u00e3o existe um algoritmo para determinar uma solu\u00e7\u00e3o para equa\u00e7\u00f5es diofantinas.
O trabalho pioneiro de Turing, desenvolvido depois do golpe fatal desferido por G\u00f6del em 1931, com seus teoremas da incompletude, formaram a base dos computadores modernos, calcados na arquitetura de Von Neumann, o g\u00eanio H\u00fangaro que contribuiu em diferentes campos do conhecimento, desde teoria dos jogos na economia, fundamentos da mec\u00e2nica qu\u00e2ntica, engenharia qu\u00edmica e, obviamente, matem\u00e1tica.
As m\u00e1quinas de Turing s\u00e3o modelos computacionais mais sofisticados para an\u00e1lises em teoria da complexidade, problemas de decidibilidade, intratabilidade, efici\u00eancia de tempo e espa\u00e7o em algoritmos, etc. Dentro da Teoria da Computa\u00e7\u00e3o, \u00e1rea que abarca o estudo te\u00f3rico dos limites do que pode ser computado, h\u00e1 modelos mais b\u00e1sicos como:
Aut\u00f4matos Finitos Determin\u00edsticos
Aut\u00f4matos Finitos N\u00e3o-Determin\u00edsticos
Aut\u00f4matos Finitos N\u00e3o-Determin\u00edsticos Generalizados
Aut\u00f4matos Finitos com Pilha
Cada modelo lida com um tipo de problema, como linguagens regulares, linguagens livres de contexto, sens\u00edveis ao contexto e irrestritas.
Dentro de teoria da Computa\u00e7\u00e3o e Matem\u00e1tica, um problema famoso e extremamente importante, \u00e9 o de P vs NP. Quando analisamos a complexidade de tempo de um algoritmo, ou seja, como o tempo t varia com o tamanho da entrada n, e, utilizando a nota\u00e7\u00e3o assint\u00f3tica (que descarta constantes, coeficientes e vari\u00e1veis de menor ordem em polin\u00f4mios), encontramos uma hierarquia de performance, como O(1), constante, O(n*log(n)), O(n) linear, O(n\u00b2) quadr\u00e1tico, O(n\u00b3) c\u00fabico, etc. Quando \u00e9 poss\u00edvel verificar e solucionar um problema com um algoritmo em tempo polinomial, dizemos que ele faz parte do conjunto P. NP \u00e9 a classe de problemas que n\u00e3o t\u00eam algoritmo conhecido para solu\u00e7\u00e3o em tempo polinomial, mas que podem ser verificados rapidamente (polinomial) se uma solu\u00e7\u00e3o para um caso espec\u00edfico for conhecida. Um exemplo \u00e9 uma posi\u00e7\u00e3o de xadrez. Se voc\u00ea tiver uma sequ\u00eancia de jogadas que termina em xequemate, \u00e9 f\u00e1cil verificar que funciona, caso contr\u00e1rio, o n\u00famero de possibilidades diferentes de jogadas \u00e9 monstruoso.<\/p>\n","protected":false},"excerpt":{"rendered":"
Em 1900, o grande e influente matem\u00e1tico David Hilbert, no congresso internacional de matem\u00e1ticos, anunciou os 23 problemas que deveriam nortear a pesquisa no s\u00e9c. 20. Entre eles, o d\u00e9cimo, sobre um algoritmo para busca de ra\u00edzes de equa\u00e7\u00f5es diofantinas (com coeficientes e vari\u00e1veis reais), foi estudado por nada menos que Alan Turing, que na […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-48","post","type-post","status-publish","format-standard","hentry","category-ciencia-da-computacao"],"_links":{"self":[{"href":"https:\/\/www.skblog.com.br\/blog\/index.php\/wp-json\/wp\/v2\/posts\/48","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.skblog.com.br\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.skblog.com.br\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.skblog.com.br\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.skblog.com.br\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=48"}],"version-history":[{"count":1,"href":"https:\/\/www.skblog.com.br\/blog\/index.php\/wp-json\/wp\/v2\/posts\/48\/revisions"}],"predecessor-version":[{"id":49,"href":"https:\/\/www.skblog.com.br\/blog\/index.php\/wp-json\/wp\/v2\/posts\/48\/revisions\/49"}],"wp:attachment":[{"href":"https:\/\/www.skblog.com.br\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=48"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.skblog.com.br\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=48"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.skblog.com.br\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=48"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}