Quão importante é saber programar para o TCS?

Vindo de um fundo mais matemático, nunca aprendi realmente a codificar. Estou iniciando um doutorado em TCS e muitas pessoas ficaram surpresas com o pouco que eu sabia sobre programação (e sobre computador em geral). Sou capaz de escrever algoritmos em pseudo-código, mas não conheço nenhuma linguagem de programação.

Eu posso imaginar que algum dia eu possa ter que implementar alguns algoritmos para o meu trabalho, mas então posso esperar por esse momento? Ou há algo a mais?

Quão importante é saber codificar no TCS (em campos onde a programação não está diretamente envolvida): existem razões que poderiam levar um teórico do CC (por exemplo) a saber codificar? Vale a pena gastar muito tempo aprendendo a codificar? E se houver, existe uma categoria (funcional, imperativa, orientada a objetos ..) de linguagem de programação que seria mais adequada?

A ciência da computação teórica é um campo amplo e a importância da programação depende do que você faz no TCS. Mencionarei duas maneiras pelas quais a programação pode ajudá-lo, sem sugerir que essas são as únicas maneiras.

Primeiro, se você projetar algoritmos para problemas de importância prática, implementar seus algoritmos e disponibilizar o código para outras pessoas pode ser uma grande vantagem. Por exemplo, o problema do casco convexo surge em muitos campos e as pessoas usam pacotes de software como o cdd de Komei Fukuda e lrs de David Avis para resolver esse problema. Se eles tivessem publicado seus algoritmos apenas em artigos, provavelmente menos pessoas teriam usado seus algoritmos. Mais usuários significam mais feedback e provavelmente também mais oportunidades de colaboração, o que é inestimável.

Segundo, mesmo que você não trabalhe em algoritmos, escrever um código único ajuda a testar uma conjectura simples quando a conjectura é adequada ao cálculo numérico. Por exemplo, se você se perguntar se o produto de três matrizes definidas positivas sempre tem um traço positivo, é fácil escrever um código para testá-lo para algumas escolhas aleatórias de matrizes definidas positivas 2 × 2 ou 3 × 3 e encontrar um contra-exemplo. Embora você não anuncie que escreveu algum programa para testar a conjectura, a programação pode economizar o tempo que seria gasto em vão tentando provar uma afirmação falsa.

A linguagem de programação a escolher depende do que você quer fazer com a programação e, na minha opinião, pode ser um tópico para um livro inteiro. Mas se você cria algoritmos e deseja implementá-los para que outras pessoas possam usar a implementação, um fator importante é a disponibilidade. Embora você possa esperar que a maioria dos usuários em potencial do seu código tenha acesso a um compilador C, não pode esperar que as mesmas pessoas tenham acesso a um compilador Haskell. Para programas únicos, a escolha é mais baseada nas bibliotecas disponíveis e inclui ambientes como o Matlab.

A propósito, a programação também pode ser divertida.

Sinto-me compelido a citar Doron Zeilberger sobre isso:

Opinião 37 : Programar é ainda mais divertido do que provar e, mais importante, fornece tanto, se não mais, insight e entendimento.

Leia a opinião, está cheia de pedras preciosas (por mais que ele seja deliberadamente provocador). Por exemplo, "A melhor maneira de entender algo é ensiná-lo. Mas, melhor ainda, ensiná-lo aos seres humanos é ensiná-lo a um computador".

Minha experiência pessoal é que, mesmo ao realizar um trabalho puramente teórico, você precisará de algumas ferramentas de computação. Evito muitas manipulações algébricas rotineiras e tediosas com o Mathematica. Testo minhas conjecturas incompletas forçando brutamente pequenas instâncias no Matlab ou Python. Co-escrevi um artigo que é pura combinatória e esse é o trabalho que mais se beneficiou com a realização de extensas experiências com computadores para entender o que está acontecendo. Euler fez enormes tabelas de cálculos tediosos para ter uma ideia dos problemas. Devemos a ele usar nossas ferramentas para automatizar esse processo quando fazemos matemática.

Além disso, se você trabalhar com algoritmos e estruturas de dados, a programação fornecerá uma perspectiva insubstituível sobre questões de eficiência e usabilidade. Minha opinião aqui difere um pouco dos outros. Eu acho que aprender uma linguagem funcional para que você possa escrever provas desse tipo corretamente é uma perda de tempo (acho que é um ótimo ponto que as pessoas que têm experiência com uma linguagem fortemente tipada provavelmente tendem a escrever provas mais cuidadosamente estruturadas; apenas não pense que vale a pena fazer esse exercício). A programação funcional oculta questões de design de algoritmos e tempo de execução e enfatiza questões de lógica e semântica (e, é claro, aprender programação funcional é provavelmente uma obrigação e ocorrerá naturalmente se você estiver interessado em semântica lógica / PL). Similarmente, Eu acho que entrar nos detalhes OO de Java e C ++ também não é a maneira ideal de gastar seu tempo, pois o objetivo do OO é escrever código reutilizável modular. É o caminho a percorrer se você produzir código para outras pessoas usarem. Mas, se você quiser obter informações sobre eficiência e tempo de execução, se você se preocupa com algoritmos e estruturas de dados realmente eficientes, eu recomendo a sugestão de analisar o C. Ele permite que você fique perto da máquina enquanto fornece um nível razoável de abstração . Dessa forma, você terá uma idéia do que é rápido e lento, do que é uma estrutura de dados razoável etc. Mas, se você quiser obter informações sobre eficiência e tempo de execução, se você se preocupa com algoritmos e estruturas de dados realmente eficientes, eu recomendo a sugestão de analisar o C. Ele permite que você fique perto da máquina enquanto fornece um nível razoável de abstração . Dessa forma, você terá uma idéia do que é rápido e lento, do que é uma estrutura de dados razoável etc. Mas, se você quiser obter informações sobre eficiência e tempo de execução, se você se preocupa com algoritmos e estruturas de dados realmente eficientes, eu recomendo a sugestão de analisar o C. Ele permite que você fique perto da máquina enquanto fornece um nível razoável de abstração . Dessa forma, você terá uma idéia do que é rápido e lento, do que é uma estrutura de dados razoável etc.

Você pode ser um cientista da computação teórico bastante bem-sucedido sem programação. Para algumas pessoas, a programação é bastante difícil e, se você é um deles, não se desespere e mude de campo.

No entanto, para a maioria dos estudantes de graduação em matemática e ciências da computação, aprender a programar não é particularmente difícil e é uma habilidade muito útil. Você deve aprender uma linguagem de programação e, se gostar, deve tentar praticar o suficiente para se tornar razoavelmente competente. Então, quando chegar o ponto (e será) que será útil em sua pesquisa escrever um programa, você será capaz de fazê-lo.

Se você não aprender a programar agora, é bem provável que, quando você precise escrever um programa, não tenha tempo para aprender; portanto, talvez você não o escreva e acabe sendo menos eficaz em sua pesquisa. Embora não seja muito difícil conseguir que um aluno de graduação ou graduação faça isso por você, há muitas vezes em que é muito mais fácil e menos demorado fazê-lo sozinho, em vez de explicar o problema para eles.

Que idioma você deve aprender? Eu recomendaria uma linguagem orientada a objetos, já que essas são as mais usadas atualmente e suspeito que isso será mais verdadeiro no futuro. Talvez Python ou Java - ambos sejam linguagens orientadas a objetos e, embora sejam menos utilizados na prática do que C ++, minha impressão é que ambos são muito, muito mais fáceis de aprender. (Advertência: eu não conheço C ++, apesar de ter trabalhado no Bell Labs, então talvez eu esteja errado sobre isso.)

Há outra resposta que ninguém realmente trouxe. A programação pode realmente levar a uma teoria interessante. Muitos dos desenvolvimentos recentes em hash (principalmente hash de tabulação) são motivados não por preocupações teóricas em si, mas pelo fato de que os algoritmos teoricamente ótimos não são tão bons na prática. É claro que isso é algo que você não sabe, a menos que possa escrever código.

Mesmo no domínio dos algoritmos exponenciais de tempo exato, uma motivação está produzindo algoritmos que podem realmente funcionar. Os solucionadores SAT são o exemplo canônico disso.

Em resumo, a capacidade de codificar permite que você perceba deficiências e fraquezas no que pode parecer resultados teóricos ideais, e isso, por sua vez, abre novas direções de pesquisa teórica.

Três pontos:

1) Existe uma abordagem para a matemática chamada Matemática Experimental (veja também a Wikipedia: // Prova auxiliada por computador ) em que você usa programas de computador para investigar sobre padrões e estruturas de objetos, a fim de apresentar provas analíticas sobre esses objetos. Para essa abordagem, é melhor saber programar. Você pode ter certeza de que encontrará a necessidade dessa abordagem para provar declarações muito teóricas. Acredito que o esnobismo contra a programação muitas vezes acaba não sendo realmente útil na pesquisa da TCS.

2) Quando você aprende a programar, como subprodutos, aprende habilidades que são úteis no TCS. Um exemplo acima de tudo: descobri que pessoas com experiência em codificação tendem a checar mais suas provas. Ainda melhor, eles tendem a definir com muita frequência o tipo de objetos que estão considerando (ex .: "vamos considerar os operadores e ). Isso é bom para os leitores de um manuscrito Compiladores (e intérpretes) nos transformam em bons cientistas :) Para esse tipo de habilidade, sinto sugerir uma linguagem funcional fortemente tipada.B ∈ L ( Y , C $A \in L(X,Y)$$B \in L(Y,C)$

3) Quando você diz "programar", você também quer dizer " programa linear " ou " programa semidefinido "? :)

Obrigado Gopi por esta pergunta. Eu gostaria de estender as muitas respostas interessantes em outra dimensão que ainda não foi mencionada.

A pesquisa não é a única coisa que fazemos na universidade: se você quiser permanecer na academia, eventualmente terá que ensinar. Se você tiver sorte, terá que ministrar cursos bem distantes da sua área de especialização. Provavelmente, você receberá cursos com um componente substancial de programação. É aqui que até uma capacidade moderada de programar ajuda substancialmente: você será um professor muito melhor se souber programar. Em primeiro lugar, você ficará mais à vontade com o material, poderá responder melhor às perguntas dos alunos e entenderá as dificuldades que os alunos têm para aprender a programar, à medida que você mesmo experimentou esse processo de aprendizagem. Além disso, você pode produzir um melhor material didático. Por exemplo, você pode testar os exercícios de programação antes de entregá-los aos alunos,

Há uma dimensão pragmática adicional: o ensino envolve várias tarefas repetitivas que um programador qualificado pode automatizar, como criar rapidamente um site que os alunos podem usar para enviar os cursos e classificá-lo automaticamente (de acordo com o número de testes automatizados que o código passa).

A programação é uma boa maneira de melhorar sua compreensão de vários conceitos, mas também é um período de tempo perigoso.

Um argumento típico contra a programação é que isso faz você gastar tempo com detalhes sem importância; Um argumento típico para a programação é que ele faz com que você perceba que os detalhes que você acha que não são importantes são de fato importantes. Tornar-se bom em programação significa principalmente ser capaz de lidar com as partes sem importância rapidamente. Tornar-se bom leva muito tempo.

Quanto à linguagem de programação para aprender: "todos eles" é a minha resposta (explícita).

Estou atrasado para a festa, e todas essas são ótimas respostas, mas tenho outro motivo:

Visualização.

Sim, frequentemente você trabalha com coisas que não podem ser visualizadas, mas frequentemente trabalha com coisas que podem. Saber programar é indispensável para esta tarefa, e a visualização pode oferecer muitas informações sobre um problema.

Apenas um ponto rápido: saber programar me dá uma ferramenta adicional na pesquisa teórica. Quando eu tenho um algoritmo que acho que funcionará, se for fácil o suficiente, posso codificá-lo e verificar se ele realmente funciona. Se minha ideia (até) não funciona na prática, é pouco provável que funcione na teoria, e essa abordagem geralmente me impede de gastar uma quantidade enorme de tempo tentando provar algo que é falso.

Ninguém aqui abordou questões práticas sobre por que alguém que estuda o TCS deve aprender programação.

Se você está planejando fazer um doutorado em TCS em um departamento de Ciência da Computação, há uma boa chance de você precisar de alguns cursos não-Teóricos, e esses certamente serão muito intensivos em programação. Dependendo do programa em que você está, você também pode precisar de conhecimentos sobre assuntos não-Teóricos para passar nos exames de qualificação.

Quando você termina seu doutorado, a maioria das oportunidades de emprego para o TCS está na academia. Se você trabalha no meio acadêmico, é esperado que você ensine, e você pode ensinar uma classe de iniciação científica no ensino superior que será mais programação do que teoria. Mesmo se você estiver ministrando uma aula de teoria para estudantes de graduação, como, por exemplo, Algoritmos, você pode esperar que seus alunos saibam mais sobre programação do que teoria e, sem saber o que seus alunos sabem, será difícil para você preencher as lacunas na compreensão deles. . Estremeço com o pensamento de que os graduandos de CS sejam ensinados por alguém que não conhece programação!

Se você não se importa com essas preocupações práticas, provavelmente poderá fazer pesquisas sem realmente saber nada sobre programação. Certamente você tem muita companhia na comunidade do TCS, mas a milhagem variará dependendo da área exata da teoria em que você estiver trabalhando. Por exemplo, se você estiver fazendo pura teoria da complexidade computacional, provando limites mais baixos nas classes que ninguém possui já ouviu falar, é provável que a programação não lhe seja útil. Mas se você estiver fazendo algo mais algorítmico, sinto que ser capaz de escrever um bom código de trabalho limpo reforçará sua intuição, se nada mais.

Eu recomendo aprender C (não C ++). Pegue uma cópia da K&R e leia-a de frente para trás. C não possui muitos dos recursos sofisticados das linguagens modernas, mas possui sintaxe e semântica simples, mas elegantes, que você deve aprender por inteiro. No entanto, mesmo quando você entende a linguagem completamente, ainda é necessário dominar a escrita de um bom código elegante e livre de erros em C. No entanto, se você pode dominar a codificação em C, poderá dominar qualquer linguagem de programação que encontrar. Além disso, essa disciplina o ajudará a pensar como o hardware pensa, o que será benéfico ao projetar algoritmos.

Ideias como ponteiros são muito importantes para quem cria design de algoritmos, mas, infelizmente, linguagens como Java e Python as ocultam, então é por isso que não as recomendo como primeira linguagem para alguém com formação em matemática. OOP é mais importante para pessoas que precisam manter grandes projetos de software, não para quem está criando algoritmos.

Eu sugiro que você não espere o início do seu curso, pois a ciência da computação em qualquer nível envolve a implementação de algoritmos através de um computador para realizar / verificar / resolver qualquer teoria que você terá que enfrentar ao longo do curso, ESPECIALMENTE no seu nível.

Eu tive que programar no 10º ano (ensino médio) primeiro, e já sabia como usar uma linha de comando e isso realmente ajudou (isso é para mostrar como as habilidades de programação "básicas" são consideradas no CS).

O espanto de seus colegas é bem fundamentado, uma vez que pseudocódigo e algoritmos estão entre as primeiras coisas que é preciso aprender para programar.

No entanto, você não deve se perder completamente em seu próximo curso, pois pode usar suas habilidades matemáticas mais amplas (por conta própria) a seu favor para pular a programação orientada a objetos para aprender mais rapidamente uma linguagem de programação funcional.

• A programação funcional é MUITO orientada para a matemática, considerada mais difícil de aprender por seu conhecimento matemático necessário, considerada muito poderosa (em sua maneira "simples" e matemática de solucionar problemas difíceis por meios elegantes e "limpos").
• A orientação a objetos é boa quando você não deseja entender algoritmos subjacentes e princípios de implementação e simplesmente deseja "reutilizar" objetos já existentes.

Eu acho que você pode enfrentar o Haskell (geralmente não é o primeiro idioma) porque é puramente matemático, funcional e pode fazer basicamente o que você quiser. Aprender Haskell colocaria você em um nível em que você não precisaria aprender muito mais para acompanhar e até colocaria você em uma situação de controle e poder sobre seu curso. Se você gosta de estatística, aprender R é uma vantagem, mas não tanto quanto Haskell. Vi relatos de matemáticos declarando como eles ficaram surpresos com sua proximidade com a matemática e como ela adotou seu modo de pensar.

Além disso, um desafio que vale a pena enfrentar (para se acostumar rapidamente a um ambiente de programação) seria instalar e usar o Linux (o Ubuntu Linux fará). Confie em mim, você aprenderá muito jogando com ele ...

Esses conselhos são a melhor maneira que conheço de atualizar-se com rapidez e segurança para um matemático em ciência da computação. Além disso, a comunidade de código aberto é muito simpática e prestativa e, se você estiver emperrado, o IRC é a maneira mais direta de falar sobre qualquer assunto por meio de canais especializados (conecte-se no FreeNode). Lembre-se: perguntar é a única maneira de resolver perguntas, seja você mesmo, um fórum, um mecanismo de pesquisa ou em salas de chat.

Um exemplo de implementação em C ++ de um sistema de prova interativa é o seguinte artigo: Provas interativas no tempo ideal para avaliação de circuitos, de Justin Thaler. Está disponível em http://people.seas.harvard.edu/~jthaler/ . Parece ser um passo em direção ao objetivo de desenvolver uma implementação prática de sistemas de provas interativas de uso geral.

Papéis semelhantes e códigos-fonte relacionados aparecem no site mencionado acima.