Postagens

O que é computação?

Imagem
No século XIX, nossa sociedade mudou fundamentalmente a maneira como produzia bens materiais. Enquanto a produção dependia anteriormente do trabalho humano e animal, a máquina a vapor permitia que grande parte desse trabalho fosse transferido para máquinas. Isso tornou a fabricação de muitos bens e serviços mais eficientes e, portanto, mais baratos. Ela disponibilizou outros tipos de produtos que, de outro modo, seriam impossíveis de fabricar. Ao mesmo tempo, causou um deslocamento econômico generalizado, colocando muitos comerciantes qualificados fora do trabalho e obrigando grande parte da população a deixar suas comunidades rurais para as cidades, mudando radicalmente o próprio ambiente em que viviam. A cultura do consumo, a televisão, as empresas e os automóvel, não teria sido possível, ou pelo menos tão influente, sem essa automação da produção, mais conhecida como revolução industrial. Agora ouvimos que estamos no meio de uma "revolução da informação". Como a revo...

Explicado: P vs. NP

Imagem
O problema mais notório da Ciência da Computação Teórica permanece em aberto, mas as tentativas de resolvê-lo levaram a profundas percepções. Os jornalistas de ciência e tecnologia se orgulham da capacidade de explicar ideias complicadas de maneiras acessíveis, mas existem alguns princípios técnicos que encontramos com tanta frequência em nossos relatórios que parafraseando-os ou escrevendo em torno deles começam a sentir falta de uma grande parte da história. Assim, em uma nova série de artigos chamada "Explained", a equipe do MIT News Office irá explicar algumas das ideias centrais nas áreas que eles cobrem, como pontos de referência para futuros relatórios sobre a pesquisa do MIT. No episódio de Halloween de Os Simpsons de 1995, Homer Simpson encontra um portal para a misteriosa Terceira Dimensão, atrás de uma estante de livros, e desesperado para escapar de suas cunhadas, ele mergulha. Ele se encontra vagando por uma superfície escura gravada com ...

Usando a Complexidade de Kolmogorov para resolver o Problema da Parada

Imagem
Assumimos que o leitor esteja familiarizado com as noções de Indecidibilidade, Reduções de Turing, Complexidade de Kolmogorov, Problema da Parada e assuntos relacionados. A prova de que a incomputabilidade da Complexidade de Kolmogorov implica a indecidibilidade do Problema da Parada pode ser encontrada em muitas palestras, notas e livros; geralmente, a prova assume que o Problema da Parada é decidível e deriva a computabilidade da complexidade de Kolmogorov, que é uma contradição. Em outras palavras, dado um oráculo para o Problema da Parada, podemos calcular a complexidade de Kolmogorov de uma cadeia x. Mas também podemos derivar a incomputabilidade da Complexidade de Kolmogorov a partir da indecidibilidade do Problema da Parada; a prova é "menos popular", mas mesmo assim pode ser encontrada depois de algumas pesquisas no Google. Por exemplo, o relatório técnico: Gregory J. Chaitin, Asat Arslanov e Cristian Calude: Program-size Complexity Computes the Halting Prob...

Um novo mapa traça os limites da computação

Imagem
Um grande avanço revela conexões profundas entre as classes de problemas que os computadores podem  —e não podem— possivelmente fazer. À primeira vista, a grande novidade da conferência de verão sobre a teoria da computação pareceu ser uma decepção. Por mais de 40 anos, pesquisadores tentaram encontrar uma maneira melhor de comparar duas sequências arbitrárias de caracteres, como as longas sequências de letras químicas dentro das moléculas de DNA. O algoritmo mais usado é lento e não é tão inteligente: ele segue passo a passo as duas listas, comparando valores em cada etapa. Se um método melhor para calcular essa "distância de edição" pudesse ser encontrado, os pesquisadores seriam capazes de comparar rapidamente genomas completos ou grandes conjuntos de dados, e cientistas da computação teriam uma nova ferramenta poderosa com a qual poderiam tentar resolver problemas adicionais no campo. No entanto, em um artigo apresentado no ACM Symposium on Theory of Computing, doi...