Quando é ciência da computação teórica útil?

https://stackoverflow.com/questions/235394

04-07-2019
|

Pergunta

Em classe, nós aprendemos sobre o problema da parada, máquinas de Turing, reduções, etc. Um monte de colegas estão dizendo estes são todos os conceitos abstratos e inúteis, e não há nenhum ponto real no conhecê-los (ou seja, você pode esquecer-los uma vez o curso é longo e não perder nada).

Por que é teoria útil? Você já usá-lo no seu dia-a-dia de codificação?

Solução

Quando me formei na faculdade, eu assumi que eu estava a par com todos os outros: "Eu tenho um BS em CS, e assim fazer um monte de outras pessoas, e todos nós podemos fazer essencialmente as mesmas coisas." Eu finalmente descobri que minha suposição era falsa. Eu estava fora, e minha formação teve muito a ver com isso -. Particularmente meu grau

Eu sabia que havia uma "ligeira" diferença, em que eu tinha um "B. S." no CS porque minha faculdade foi um dos primeiros (supostamente como 2 em 1987) no país a receber a acreditação para o seu programa CS grau, e me formei na segunda classe para ter esse credenciamento. Na época, eu não acho que isso importasse muito.

Eu também tinha notado durante o ensino médio e na faculdade que eu fiz muito bem no CS - muito melhor do que meus colegas e até mesmo melhor do que muitos dos meus professores. I foi pediu ajuda muito, fiz algumas aulas, foi solicitado a ajuda com um projeto de pesquisa, e foi permitido fazer estudo independente quando não havia mais ninguém. Fiquei feliz em poder ajudar, mas eu não pensei muito sobre a diferença.

Depois da faculdade (USAFA), passei quatro anos na Força Aérea, dois dos quais estavam aplicando meu grau CS. Não notei que muito poucos dos meus colegas tinha graus ou mesmo formação relacionada com computadores. A Força Aérea enviou-me a cinco meses de treinamento de certificação, onde eu novamente encontrou uma falta de graus ou treinamento. Mas aqui eu comecei a notar a diferença - tornou-se totalmente óbvio que muitas das pessoas que encontrei realmente não sabia o que estavam fazendo, e que incluiu as pessoas com treinamento ou graus. Permita-me por favor para ilustrar.

Na minha treinamento de certificação da Força Aérea foram um total de treze pessoas (inclusive eu). Como oficiais da Força Aérea ou o equivalente, todos nós tínhamos graus BS. Eu estava no meio com base na idade e posição (eu era um O-2 entre seis S-1s e seis S-3 e acima). No final desta formação, a Força Aérea a todos nós carimbado como igualmente competente para adquirir, construir, design, manter e operar qualquer sistema de computador ou de comunicação para qualquer parte do Departamento de Defesa.

No entanto, dos treze de nós, apenas seis tiveram qualquer forma de grau de informática; os outros sete graus tiveram que variam de aeronáutica à química / biologia à psicologia. Dos seis de nós com graus CS, eu aprendi que dois nunca tinha escrito um programa de qualquer tipo e nunca tinha usado um computador mais do que casualmente (papéis de escrita, jogos, etc.). Eu aprendi que outros dois de nós tinha escrito exatamente um programa em um único computador durante o seu programa de grau CS. Apenas uma outra pessoa e eu tinha escrito mais de um programa ou utilizado mais de um tipo de computador -. De fato, descobrimos que nós dois tinham escrito muitos programas e usado muitos tipos de computadores

No final de nosso treinamento de cinco meses, a nossa classe foi atribuído um projeto de programação e nós foram divididos em quatro grupos para separadamente empreendê-lo. Nossos instrutores dividiram a classe, a fim de difundir o "talento programação" de forma justa, e eles atribuídos papéis de líder da equipe, líder técnico e desenvolvedor. Cada grupo foi dada uma semana para implementar (em Ada) um ecrã completo, baseado em texto de interface de utilizador (este era 1990) para um simulador de vôo em cima de uma biblioteca de vôo-mecânica fornecida pelo instrutor. Fui designado como líder técnico para a minha equipe de quatro pessoas.

O meu chefe de equipe (que não têm um grau de computador) pediu aos outros três de nós para dividir o projeto em tarefas e, em seguida, recebe um terço deles para cada um de nós. Eu terminei minha terceira das tarefas por meio desse primeiro dia, depois passou o resto do dia ajudando meus outros dois companheiros de equipe, falando com o meu chefe de equipe (BSing; ^)., E jogar no meu computador

Na manhã seguinte (dia dois), meu chefe de equipe me informou reservadamente que os outros dois companheiros de equipe tinha feito nenhum progresso (um não poderia realmente escrever um "if" que compile), e ele me pediu para leváem seu trabalho. Eu terminei o projeto inteiro por meio da tarde, e minha equipe passou o resto do dia voando o simulador.

O outro cara com o grau CS comparável também foi designado como um líder técnico para a sua equipa, e eles concluída até o final do dia três. Eles também começaram a voar seu simulador. As outras duas equipes não tinha terminado, ou até mesmo um progresso significativo, até o final da semana. Nós não foram autorizados para ajudar outras equipes, por isso foi deixado para isso.

Enquanto isso, por meio de três dias, eu tinha notado que o simulador de vôo apenas parecia se comportar "errado". Desde um dos meus colegas tinha um diploma em aeronáutica, eu perguntei a ele sobre isso. Ele estava confuso, em seguida, confessou que ele realmente não sabia o que fez uma mosca avião!?! Fiquei estupefato! Acontece que todo o seu programa de graduação foi sobre a segurança e as investigações de acidentes - nenhuma matemática real ou ciência por trás vôo. Por outro lado, eu tinha talvez um menor em aeronáutica (lembre-se USAFA?), Mas nós tinha projetado asas e realizou testes de túnel de vento real. Portanto, eu calmamente passou o resto da semana reescrevendo a biblioteca de vôo-mecânica fornecida pelo instrutor até o simulador voou "direito".

Desde então, passei quase duas décadas como um empreiteiro e, ocasionalmente, como um empregado, sempre fazendo desenvolvimento de software além de atividades relacionadas (DBA, arquiteto, etc.). Eu continuei a encontrar mais do mesmo, e, eventualmente, eu desisti de minha suposição jovem.

Então, o que exatamente tem que descobri? Não cada um é igual, e que está bem - eu não sou uma pessoa melhor porque eu posso programar de forma eficaz, mas eu sou mais útil se é isso que você precisa de mim. Eu aprendi que a minha experiência realmente importava: crescendo em uma família de eletricistas e engenheiros elétricos, construção de kits de eletrônicos, lendo literalmente cada livro de computador na escola / bibliotecas públicas porque eu não tiver acesso a um computador real, em seguida, movendo-se para uma nova cidade onde minha escola tinha computadores, em seguida, obter o meu próprio computador como um presente, indo para as escolas que tinham computadores de diferentes tamanhos e tipos (PCs a mainframes), obter um grau acreditado de uma escola muito boa engenharia, ter de lotes de gravação de programas em diferentes línguas em diferentes tipos de computadores, ter que escrever programas rígidos (como a minha própria máquina virtual com uma linguagem assembly personalizado, ou uma implementação de compressão Huffman, etc.), ter que resolver para mim, construir meus próprios computadores a partir de peças e instalação de todo o software, etc.

Em última análise, eu aprendi que minhas habilidades são construídas sobre uma fundação de saber como funcionam os computadores do nível elétrico em cima - discretos eletrônicos componentes, circuitos, subsistemas, interfaces, protocolos, bits, bytes, processadores, dispositivos, drivers, bibliotecas, programas, sistemas, redes, em até os conglomerados maciços de classe empresarial que trabalham rotineiramente agora. Então, quando a coisa misbehaves malditos, eu sei exatamente como e porquê. E eu sei que não pode ser feito, bem como o que pode. E eu sei muito sobre o que tem sido feito, o que foi tentado, eo que resta relativamente inexplorado.

O mais importante, depois de eu ter aprendido tudo isso, eu aprendi que eu não sei uma coisa maldita. Em face de tudo o que há potencialmente saber, meu conhecimento é minúsculo.

E eu estou bastante contente com isso. Mas eu recomendo que você tente.

Outras dicas

A verdadeira história:

Quando eu consegui meu primeiro emprego de programação fora da escola de pós-graduação, os caras que possuíam a empresa que eu trabalhava para eram pilotos. Algumas semanas depois de ter sido contratado, um deles me fez esta pergunta:

Existem 106 aeroportos em Arkansas. Você poderia escrever um programa que faria encontrar o mais curto para a necessária derrota terra em cada um deles?

Eu seriamente pensei que ele estava me questionando sobre meu conhecimento do vendedor ambulante problema e NP-completude. Mas acontece que ele não era. Ele não sabia nada sobre isso. Ele realmente queria um programa que iria encontrar o caminho mais curto. Ele ficou surpreso quando eu expliquei que não havia soluções 106-fatoriais e encontrar a melhor foi um problema computacionalmente intratável conhecida.

Então, isso é um exemplo.

Claro, é útil.

Imagine um desenvolvedor trabalhando em um modelo de motor. Você sabe o tipo de coisa ...

Blah blah blah ${MyTemplateString} blah blah blah.

Ele começa simples, com um pouco de expressão regular atrevido que efetuar as substituições.

Mas, gradualmente, os modelos ficam um pouco mais extravagante, eo desenvolvedor inclui recursos para templatizing listas e mapas de cordas. Para conseguir isso, ele escreve uma gramática simples e pequeno e gera um analisador.

ficando muito astuto, o modelo de motor pode, eventualmente, incluir uma sintaxe para a lógica condicional, para exibir diferentes blocos de texto, dependendo dos valores dos argumentos.

Alguém com uma base teórica em CS seria reconhecer que a linguagem de template está lentamente se tornando Turing completa, e talvez o padrão Interpreter seria uma boa maneira de implementá-lo.

Tendo construído um intérprete para os modelos, um cientista da computação pode notar que a maioria dos pedidos de templates são duplicados, regenerando os mesmos resultados repetidas vezes. Então um cache é desenvolvido, e todas as solicitações são encaminhadas através do cache antes de executar a transformação caro.

Além disso, alguns modelos são muito mais complexos do que outros e levar muito mais tempo para renderizar. Talvez alguém tem a idéia para estimar a execução de cada modelo antes de torná-la.

Mas espera !!! Alguém sobre os pontos da equipe que, se o modelo de linguagem realmente é Turing completa, então a tarefa de estimar o tempo de execução de cada operação de renderização é uma instância do Deter Problema !! Caramba, não faça isso !!!

A coisa sobre a teoria, na prática, é que toda a prática é baseada na teoria. Teoricamente.

As coisas que eu uso mais:

complexidade computacional de algoritmos de gravação que escala graciosamente
compreensão de como a alocação de memória, paginação, e CPU trabalho caching para que eu possa escrever código eficiente
compreensão de estruturas de dados
compreensão de segmentação, bloqueio e problemas associados

Como a esse material em máquinas de Turing etc. Eu acho que é importante porque define as restrições sob as quais todos nós operamos. Isso é importante para apreciar.

É a diferença entre aprender álgebra e sendo ensinado como usar uma calculadora

Se você sabe álgebra, você percebe que o mesmo problema pode se manifestar em diferentes formas, e você compreender as regras para transformar o problema em uma forma mais concisa

se você só sabe como usar uma calculadora, você pode perder um monte de perfuração botões de tempo em um problema que é ou (a) já resolvido, (b) não pode ser resolvido, ou (c) é como algum outro problema (resolvido ou não resolvido) que você não reconhece porque é de uma forma diferente

fingir, por um momento, que a informática é a física ... seria a questão parecer bobagem?

Um amigo meu está fazendo um trabalho em uma linguagem com alguns modelos. Fui convidado para fazer um pouco de consultoria. Parte de nossa discussão foi sobre o recurso de modelo, porque se os modelos foram Turing completa, eles teriam que realmente considerar propriedades VM-ish e como / se o seu compilador iria apoiá-lo.

A minha história é a este ponto: teoria de autômatos ainda é ensinada, porque ele ainda tem relevância. O problema da parada ainda existe e fornece um limite para o que você pode fazer.

Agora, essas coisas têm relevância para um jockey martelar banco de dados fora código C #? Provavelmente não. Mas quando você começar a se mover para um nível mais avançado, você vai querer entender as suas raízes e fundações.

Embora eu não aplicá-los diretamente no trabalho do dia-a-dia, eu sei que a minha educação em ciência formal computador tem afetado o meu processo de pensamento. Eu certamente evitar certos erros desde o início, porque eu tenho as lições aprendidas com as abordagens formais incutiu em mim.

Pode parecer inútil, enquanto eles estão aprendendo; mas eu aposto que o seu colega de classe acabará se depara com um problema onde eles vão usar o que eles foram ensinados, ou pelo menos os padrões de pensamento por trás dele ...

Wax on ... Wax off ... Wax on ... Wax off ... O que isso tem a ver com Karate, de qualquer maneira?

Em um trabalho que foi atribuída a tarefa de melhorar o algoritmo de rastreamento de rede do nosso modelo de distribuição elétrica, como o que eles estavam usando era muito lento. A rede de três fases foi essencialmente três n-árvores (desde laços não são permitidos em redes eléctricas). Os nós da rede estavam no banco de dados e alguns membros da equipe original não conseguia descobrir como construir um modelo in-memory para que o rastreamento foi feito por sucessivas SELECTs profundidade no banco de dados, a filtragem em cada fase. Então, para traçar um nó dez nós a partir da subestação exigiria pelo menos 10 consultas de banco de dados (os membros da equipe originais eram gênios de banco de dados, mas faltava um fundo decente em algoritmos).

I escreveu uma solução que transforma as redes 3-n em árvore dos nós da base de dados numa estrutura de dados, onde cada nó foi armazenado uma vez em uma matriz de estrutura de nó e a relação de n-árvore foi convertido para três árvores binárias utilizando doubly- ponteiros ligados dentro da matriz para que a rede poderia ser facilmente rastreada em qualquer direção.

Foi pelo menos duas ordens de magnitude mais rápido, de três em traços muito longo jusante.

O triste era que eu tinha para ensinar praticamente uma classe em N-árvores, árvores binárias, ponteiros e listas duplamente ligadas a vários dos outros programadores que haviam sido treinados em bases de dados e VB para que eles para entender os algoritmos.

É uma dicotomia clássica, entre o "como" e "o que". Seus colegas estão olhando para software "como" programa, e eles estão muito focados no foco próximo; a partir dessa perspectiva, a perspectiva de implementação, parece saber coisas como estados vacilantes e máquinas de Turing não são importantes.

"Como" é muito pouco o trabalho real que você se espera fazer com Ciência da Computação, no entanto. Na verdade, os engenheiros mais bem sucedidas que eu conheço provavelmente colocá-lo em menos de 20 por cento do trabalho real. "O que" a fazer é muito mais importante; e para isso, os fundamentos da Ciência da Computação são críticos. "O que" você quer fazer relaciona muito mais ao projeto de implementação; e um bom design é ... bem, vamos apenas chamá-lo de "não-trivial".

"Há duas maneiras de construir um projeto de software: É uma maneira de torná-lo tão simples que obviamente não há deficiências, e a outra maneira é torná-lo tão complicado que não há óbvio deficiências O primeiro método é muito mais difícil " -.. CAR Hoare

Boa sorte com seus estudos!

Eu acho que a compreensão dos modelos fundamentais da computação é útil: a certeza de que nunca precisará ser capaz de traduzir uma máquina de Turing em uma máquina de registo na prática, mas aprender a ver que dois problemas muito diferentes são realmente instâncias do mesmo conceito é uma habilidade crítica.

A maioria conhecimento não é "prático", mas ajuda você a pontos de conexão de maneiras que você não pode antecipar, ou dá-lhe um vocabulário mais rico para descrever idéias mais complexas.

Não é os problemas específicos que você estudo que importa, ele é os princípios que você aprende através de estudá-los. Eu uso conceitos sobre algoritmos, estruturas de dados, linguagens de programação e sistemas operacionais todos os dias no meu trabalho. Se você trabalha como um programador que você vai tomar decisões o tempo todo que afetam o desempenho do sistema. Você precisa ter uma base sólida nos conceitos abstratos fundamentais, a fim de fazer as escolhas certas.

Se você trabalha em uma empresa que faz um trabalho inovador, é importante ser capaz de comunicar aos arquitetos e desenvolvedores quais são os benefícios. Há um monte de hype sobre todos os tipos de tecnologias e posicionando-se pode ser difícil. Quando você enquadrar sua inovação em termos científicos e teóricos você está definitivamente em vantagem e clientes sentir que você é a coisa real. Eu posso dizer a povos: há uma nova maneira de lidar com o estado, codificação e não-determinismo (ou seja complexidades) e você pode definitivamente ser mais produtivo do que você é hoje.

Se você tomar a visão de longo prazo na sua aprendizagem carreira sobre a teoria vai lhe dar profundidade, a profundidade que você precisa para crescer. O retorno sobre o investimento em aprender o seu 5º ou 6º linguagem de programação vai ser muito menos, em seguida, aprender a sua 2ª e 3ª. A exposição a teoria vai lhe dar um sentido para a engenharia real, sobre o local onde os graus de liberdade são e como você pode fazer as compensações certas.

Os conceitos importantes 1) estaduais, 2) que codifica, 3) Não-determinismo. Se você não sabe que eles não vão ajudá-lo. O que a teoria deve fornecer-lhe é o retrato grande e uma noção de como conceitos básicos se encaixam. Deve ajudá-lo a aprimorar sua intuição.

Exemplo: algumas das respostas acima mencionar o problema da parada e máquinas de Turing. Quando me deparei com o artigo de Turing na faculdade eu não sente iluminado a todos. Um dia me deparei com teorema da incompletude de Gödel e Gödel numeração em particular. As coisas começaram a fazer um monte de sentido. Anos mais tarde eu li sobre Georg Cantor em uma livraria. Agora eu realmente comecei a entender as máquinas de Turing e o problema da parada. Tente você mesmo e olhar para cima "Argumento Diagonal de Cantor" na Wikipedia. É uma das coisas mais impressionantes intelectualmente que você nunca vai encontrar.

Alimento para o pensamento: Uma máquina de Turing típico não é a única maneira de projetar uma máquina de transição de estado. Uma máquina de Turing com duas em vez de uma fita lhe daria muito mais velocidade para uma série de algoritmos. http://www.math.ucla.edu/~ynm/papers/ eng.ps

Você pode expor-se a esses insights de forma mais eficiente, então eu fiz ao ler este livro. Link na parte inferior deste post. (No mínimo, consulte a tabela de conteúdo sobre a Amazônia para obter uma amostra do que se trata):

Eu encontrei o livro de Rosenberg sensacional. http://www.amazon.com/The-Pillars-Computation-Theory-Nondeterminism/ dp / 0387096388 Se você tem apenas um livro sobre IMHO teoria, isso deve ser o único.

Depois que me formei na CS Pensei semelhante: todo o grupo de teorias que estudamos são completamente inúteis na prática. Isto provou ser bom para um curto período de tempo, no entanto, o momento em que você lidar com tarefas complexas, a teoria é definitivamente mais valioso do que prática. cada um após alguns anos de codificação pode escrever alguns programas que o "trabalho", mas não cada um é capaz de entender como. Não importa o que a maioria de nós vai lidar em um determinado ponto com problemas de desempenho, atrasos na rede, precission, escalabilidade etc. Nesta fase, a teoria é crítica. a fim de projetar uma boa solução quando se lida com sistemas complexos é muito importante saber como funciona o gerenciamento de memória, os conceitos de processo e tópicos, como a memória é atribuídos a eles, ou estruturas de dados eficientes para desempenho e assim por diante.

Uma vez, por exemplo, eu estava trabalhando em um projeto incluindo a abundância de cálculos matemáticos e em um certo ponto o nosso software falhou. durante a depuração eu descobri que depois de alguma operação matemática i recebeu um número como DUPLO de um valor 1,000000000002 mas a partir da perspectiva matemática não poderia ser> 1, que em algum momento mais tarde no programa estava dando o lendário NaN exceção . Passei algum tempo para descobrir isso, mas se eu tivesse prestado mais atenção ao " aproximação das duas vezes e Float " lição eu teria não desperdiçado esse tempo.

Eu não usá-lo em uma base diária. Mas ele me deu um monte de compreensão que me ajuda a cada dia.

Eu achei que todos necessidade I para a felicidade diária do mundo teórico CS é a pronunciação do mantra "baixo acoplamento e alta coesão". Roger S. Pressman tornou acadêmica antes de Steve McConnell tornou moda.

Ya, eu geralmente uso diagramas de estado para projetar a forma e fluxo do programa. Uma vez que funciona na teoria, eu começar a codificação e teste, verificando fora dos estados como eu ir.

Eu acho que eles também são uma ferramenta útil para explicar o comportamento de um processo para outras pessoas.

Simples. Por exemplo:. Se eu estou usando RSACryptoServiceProvider Eu gostaria de saber o que é que e por que eu posso confiar nele

Como os modelos C ++ são realmente algum tipo de cálculo lambda. Veja www.cs.nott.ac.uk/types06/slides/michelbrink_types_06.pdf

Eu estou estudando para meus algoritmos distribuídos curso agora. Há um capítulo sobre a tolerância a falhas e contém algumas provas sobre o limite superior para o número de processos pode falhar (ou misbehave) para que o algoritmo distribuído pode lidar com isso corretamente.

Para muitos problemas, o limite por mau comportamento processos é até um terço do número total de processos. Isto é bastante útil na minha opinião, porque você sabe que é inútil tentar desenvolver um algoritmo de melhor (sob hipóteses dadas).

Mesmo cursos teóricos não estão indo a ser usado diretamente, ele pode ajudá-lo a pensar melhor em alguma coisa.

Você não sabe o que seu chefe vai lhe pedir para fazer, você pode ter que usar algo que você pensou que não será benéfico, como disse Jeffrey L Whitledge.

Para ser honesto, eu meio que não concordar com muitas das respostas aqui. Eu escrevi o meu primeiro compilador (por diversão; I realmente tem muito café / tempo livre) sem ter tomado um curso de compiladores; basicamente, eu só examinou o código para outra compilador e seguiu o padrão. Eu poderia escrever um parser em C em cima da minha cabeça, mas eu não acho que eu poderia lembrar como desenhar um autômato com pilha se minha vida dependesse disso.

Quando eu decidi que queria colocar a inferência de tipos no meu brinquedo (imperativo) linguagem de programação, eu primeiro parecia mais provavelmente cinco trabalhos, olhando para algo chamado "digitado lambda calculus" vai o que .... o .... * *** ....? No começo eu tentei implementar algo com "variáveis ??genéricas" e "variáveis ??não-genéricos" e não tinha idéia do que estava acontecendo. Então eu desfeito tudo, e sentou-se lá com um notebook para descobrir como eu poderia implementar praticamente com suporte para todas as coisas que eu precisava (sub-digitação, funções de primeira classe, tipos parametrizados, etc.) com um par de dias de pensamento e escrevendo programas de teste, eu surpreendeu mais do que um semanas de tentar descobrir a porcaria teórica.

Conhecer os conceitos básicos de computação (ou seja, como funciona a memória virtual, como sistemas de arquivos de trabalho, segmentação / programação, SMP, estruturas de dados), têm provado extremamente útil. A teoria da complexidade e coisas Big-O tem, por vezes, se mostrou útil (especialmente útil para coisas como design RDBMS). O problema da parada e teoria de autômatos / Máquina de Turing? Nunca.

Eu sei que este é antiga, mas a minha resposta curta para aqueles que afirmam que a teoria é 'inútil' e que eles podem exercer a sua profissão sem ele é esta:

Sem a teoria subjacente, há não prática.

Por que é teoria útil?

A teoria é a base subjacente no topo do qual outras coisas são construídas. Quando a teoria é aplicada , a prática é o resultado.

Considere computadores hoje. O computador comum hoje em dia é modelada e construída em cima da máquina de Turing, que, para mantê-lo simples, é um modelo abstrato / teórico para a computação. Este teóricas mentiras modelo no base de computação, e todos os dispositivos de computação que usamos hoje, a partir de servidores high-end para telefones de bolso, o trabalho porque a fundação subjacente é som.

Considere algoritmo de análise. Em termos simples, o algoritmo teoria da análise e tempo de complexidade têm sido usados ??para problemas Classificar (por exemplo, P, NP, EXP, etc), bem como a forma como os algoritmos que temos se comportam ao tentar resolver problemas diferentes em diferentes classes.

Suponha que um de seus amigos consegue um emprego em algum lugar X e, enquanto lá, um gerente faz alguns pedidos simples, como estes exemplos:

Ex 1: Temos uma grande frota de veículos de entrega que visitam diferentes cidades em toda a vários estados. Precisamos você para implementar um sistema para descobrir qual é o caminho mais curto para cada veículo é e escolher o ideal um em todas as possibilidades. você pode fazê-lo?

Pensando a teoria é 'inútil' seus amigos não percebem que eles só me deram o Caixeiro Viajante Problem (TSP) e começar a desenhar esse sistema sem pensar duas vezes, apenas para descobrir sua tentativa ingênua de verificar todas as possibilidades, como inicialmente requerido, é tão lento seu sistema está inutilizável para quaisquer fins práticos.

Na verdade, eles têm nenhuma idéia porque o sistema funciona em um nível "aceitável" ao verificar 5 cidades, mas torna-se muito lento em 10 cidades, e apenas congela quando vai até apenas 40 cidades . Eles argumentam que é única "2x e mais 8x cidades do que o teste 5 da cidade" e admira por isso que o programa não simplesmente exigir "2x e mais 8x tempo", respectivamente ...

Compreender a teoria teria lhes permitiu perceber o seguinte, pelo menos à primeira vista:

É a TSP
O TSP é NP-hard
a ordem de Seu algoritmo de crescimento é O (n!)

Os números falam por si:

+--------------+-------+-----------------------------------------------------------------+
|  No. Cities  | O(N!) |  Possibilities                                                  |
+--------------+-------+-----------------------------------------------------------------+
|       5      |   5!  | 120                                                             |
|      10      |  10!  | 3,628,800                                                       |
|      40      |  40!  | 815,915,283,247,897,734,345,611,269,596,115,894,272,000,000,000 |  <-- GG
+--------------+-------+-----------------------------------------------------------------+

Eles poderiam ter percebido desde o início que o seu sistema era não indo para o trabalho como eles imaginaram que seria. O sistema foi mais tarde considerado impraticável e cancelado depois de uma quantidade significativa de tempo, esforço e outros recursos foram alocados para e, finalmente desperdiçado em, o projeto --e tudo porque o pensamento "teoria é inútil".

Assim, após esta falha, os gerentes pensam "Bem, talvez esse sistema foi subestimada, afinal, não é um monte de cidades em nosso país e nossos computadores simplesmente não são tão rápido quanto nós precisamos deles para ser para o nosso recentemente sistema cancelado ter sido um sucesso".

A equipa de gestão culpa computadores lentos como a causa da falha do projeto. Afinal, eles não são especialistas em teoria CS, não precisa ser, e aqueles que são supostamente os especialistas sobre o tema e poderia ter informou-os, não o fez.

Mas eles têm outro projeto em mente. A um simples na verdade. Eles vêm a semana mais tarde e pedir dizer o seguinte:

Ex 2: Temos apenas alguns servidores e temos programadores que mantêm programas de apresentação que, devido a razões desconhecidas, acabam em ciclos infinitos e podem contar para baixo os servidores. Precisamos você para escrever um programa que irá processar o código sendo submitido e detectar se o programa apresentado irá causar um ciclo infinito durante a sua execução ou não, e decidir se o programa apresentado deve ser autorizado a executar nesta base. você pode fazê-lo?

Seu querido amigo aceita o desafio de novo e vai trabalhar imediatamente. Depois de várias semanas de trabalho, não está nenhum resultado, seu amigo está estressado, e não sabe o que fazer. No entanto, outro fracasso ... seu amigo agora se sente "burro" por não ter sido capaz de resolver este "problema simples" ... afinal de contas, o próprio pedido feito isso som simples.

Infelizmente, o seu amigo, insistindo que "a teoria é inútil" não perceber que a, supostamente simples, pedido era realmente um problema intratável sobre decidibilidade (ou seja, o próprio problema da parada), e que não foi solução para nenhum conhecido isto. Era uma tarefa impossível.

Portanto, mesmo de começar a trabalhar para resolver esse problema em particular foi um erro evitável e evitável. Teve o arcabouço teórico para entender o que estava sendo solicitado está em vigor, eles poderiam ter apenas propôs um diferente, e realizáveis ??, solução ... tais como a implementação de um processo de acompanhamento que pode simplesmente kill -SIGTERM <id> de qualquer < em> user processo (de acordo com uma lista de usuários), que monopoliza a CPU para algum intervalo arbitrário / razoáveis ??sob certas premissas (por exemplo, sabemos que cada execução do programa deveria ter terminado em 10 minutos, de modo que qualquer instância em execução para 20 + minutos deve ser killed).

Em conclusão, prática sem a teoria é como um edifício sem uma fundação . Cedo ou tarde, a quantidade certa de pressão do ângulo direito irá torná-lo entrar em colapso sobre si mesmo . Sem exceções.

Você já usá-lo no seu dia-a-dia de codificação?

Sim, mas não diretamente . Em vez disso, contamos com ele indiretamente . A advertência aqui é que diferentes conceitos teóricos será mais ou menos aplicáveis, dependendo do domínio do problema acontecer de você estar trabalhando.

Com certeza, nós:

uso de computadores por dia, que se baseia em modelos computacionais (máquinas por exemplo Turing)
código de escrita, que se baseia na teoria da computabilidade (por exemplo, o que é ainda computável) e cálculo lambda (por exemplo, para linguagens de programação)
dependem de teoria da cor e modelos (por exemplo, modelos de cores RGB e CMYK) para telas coloridas e impressão, etc.
teoremas de Euler em computação gráfica para que matrizes podem ser construídos para objetos girar em torno de eixos arbitrários, e assim por diante ...

É um fato de que alguém que simplesmente uso um avião para viajar, não precisa entender a teoria de que os aviões, mesmo permissão para ser construído e voar em primeiro lugar ... mas quando alguém é espera-se que construção disse máquinas e fazê-los funcionar ... você pode realmente esperar um bom resultado de alguém que não entende mesmo os princípios do vôo?

Foi realmente uma coincidência que, durante a maior parte da história, ninguém foi capaz de construir uma máquina voadora (e alguns até morreram testando deles) até que os irmãos Wright compreender certos conceitos teóricos sobre o vôo e conseguiu colocá-los em prática ?

Não é coincidência. Temos um monte de tecnologia trabalhando hoje porque as pessoas que os construíram compreendido e aplicado, os princípios teóricos que lhes permissão para trabalhar em primeiro lugar.

Eu acho que depende de qual campo você entrar.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow