Quão importante é saber programar para o TCS?

66

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?

Gopi
fonte
12
Você deveria ter programado alguns para escrever pseudo-código significativo, ou seja, definitivo e que reflete o tempo de execução. Os matemáticos geralmente não o fazem. Além disso, se você realmente deseja usar a teoria que desenvolve, é provável que tenha que implementar alguma coisa. Quanto aos idiomas, você provavelmente está melhor aprendendo algo funcional. C é bom para o desempenho, mas difícil de raciocinar e confuso em muitos aspectos. (Como você pode ver, YMMW)
Raphael
6
Concordo com "os matemáticos geralmente não fazem nada". Um teste simples para saber se um matemático que descreve um algoritmo realmente programou é perguntar "O que exatamente você quer dizer com 'Dado um X ...'?"
Jeffε
4
Programação, o que é isso? Teoremas são meus programas. Um procedimento de cozimento é diferente da arte de cozinhar. Desculpe, em mais de 20 anos não consigo ler nenhum código de programa. Na verdade, eu odeio essa bagunça "sendo realizada no PC". (Essa notação já está doente.) Euclides não pôde programar. No entanto, ele fez programas por séculos.
Stasys
6
@StasysJukna: Euclid era realmente um programador realmente péssimo. Ele não apenas nunca implementou seus algoritmos, como nunca os executou manualmente em casos de teste moderadamente complicados.
Jeffε
3
@ Jɛ ff E: Sim, Euclid era um programador de baixa qualidade, exatamente isso que eu queria dizer. Nós, no TCS, tendemos a não distinguir entre livros de culinária e arte de armar. Euclides poderia. Eu tenho um grande respeito pelas pessoas que podem programar. Mas não acho que esse recurso signifique "um CAN no TCS". Simplesmente não vai doer.
Stasys

Respostas:

55

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.

Tsuyoshi Ito
fonte
2
@SureshVenkat: De fato, se a programação é divertida, a pergunta "Qual a importância da programação?" Pode não ser muito relevante. Mas então a maior parte da minha resposta se tornará irrelevante. Que triste! :)
Tsuyoshi Ito
Eu não pensei no seu segundo argumento antes, na verdade, parece realmente uma boa idéia testar uma conjectura com um programa curto! Quanto à programação pode ser divertido, ao que parece, mas ainda tenho que ver todo o longo aprendizado de fim de semana =).
Gopi
@Gopi: Dito isto, muitas conjecturas não se encaixam nesse quadro de "teste com um programa simples". Por exemplo, geralmente não podemos testar comportamentos assintóticos (pelo menos por um programa simples). Mas quando você tem alguma conjectura que pode ser testada, um pouco de programação pode ser uma ferramenta poderosa. Quanto à diversão, sim, eu entendo. Eu simplesmente não queria ignorar o ponto de vista "divertido" listando apenas algumas motivações do ponto de vista de "utilidade".
Tsuyoshi Ito
3
As anotações de Knuth sobre uma aula de solução de problemas têm um exemplo maravilhoso da interação entre conjecturas e código (consulte o Problema 1): www-cs-faculty.stanford.edu/~knuth/papers/cs1055.pdf (particularmente gosto da imagem de alguém correndo para a sala de aula tendo uma pilha de folhas impressas)
Suresh Venkat
47

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.

Sasho Nikolov
fonte
10
"A programação funcional obscurece questões de design de algoritmos e tempo de execução e enfatiza questões de lógica e semântica". Combate palavras :)
Suresh Venkat
3
"A programação funcional obscurece questões de design de algoritmos e tempo de execução e enfatiza questões de lógica e semântica". É por isso que é uma boa escolha se você trabalha no lado lógico ou semântico do TCS. :)
Radu Grigore
5
Ahem.
Jeffε
3
@ Sasho: Todas as técnicas comuns ainda funcionam em linguagens funcionais. O único "problema" é que a programação funcional incentiva um estilo de programação e design de estrutura de dados com o qual as técnicas comuns de análise algorítmica estão sub-equipadas para lidar. (Por exemplo, qual é a grande-O de composição de função A operação é? Trivial , mas ele quebra completamente os pressupostos da complexidade assintótica - não há nenhuma métrica numérica simples de tamanho para uma entrada funcional.)
Neel Krishnaswami
3
@ShohoNikolov: Sempre que ensino uma aula de estruturas de dados de pós-graduação, realmente desejo poder supor que todos tenham alguma experiência em programação funcional. Em vez de passar três palestras de 90 minutos para explicar a persistência, eu poderia apenas dizer "Ei, você percebeu que suas estruturas de dados já fazem ISSO?"
Jeffε
33

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.)

Peter Shor
fonte
2
Eu vejo a verdade no seu terceiro parágrafo :).
Gopi
11
"No entanto, para a maioria das pessoas, aprender a programar não é particularmente difícil" - minha experiência me leva a discordar disso, mas a maioria das pessoas não é pesquisadora do TCS.
Max
2
Com o surgimento do Sage, é possível trabalhar com uma linguagem popular e agradável, como o Python, mantendo as bibliotecas matemáticas no estilo Mathematica / Maple / Matlab disponíveis instantaneamente.
András Salamon
11
O C ++ possui o sistema de tipo / metaprogramação mais avançado de qualquer linguagem de programação de uso geral convencional que eu já vi, exceto a família de linguagens Lisp. Portanto, se você gosta de teoria de tipos, design de linguagem ou teoria de compiladores, ou mais amplamente em semântica formal, convém se familiarizar com isso. Além do C ++, Java e C # são essenciais se você deseja fazer pesquisas em Ciência da Computação experimental ou se espera conseguir um emprego como programador ou engenheiro de software no setor. Python deve ser ensinado nas escolas secundárias: D
Antonio Valerio Miceli-Barone
4
@ AntonioValerioMiceli-Barone: Eu tenho que discordar, pelo menos em teoria dos tipos, design de linguagem, semântica formal e teoria da linguagem de programação (PLT) em geral: C ++ não é a linguagem a aprender para esses campos; TT e semântica formal se relacionam quase exclusivamente à programação funcional, enquanto a comunidade PL é mais diversificada, mas prefere linguagens mais elegantes que C ++. Haskell é a linguagem "mainstream" com o sistema de tipos mais avançado, seguido por Scala (menos avançado, um pouco mais mainstream). O C ++ possui recursos interessantes, mas é de nível muito baixo para o gosto moderno.
Blaisorblade 31/03
33

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.

Suresh Venkat
fonte
Sua resposta pode ajudar na pergunta sobre resultados empíricos no TCS .
Gopi
talvez, mas esse segmento há muito tempo morreu :)
Suresh Venkat
Na verdade, eu não olhei para a data, foi no último boletim que recebi, na seção "Maiores sucessos das semanas anteriores" =).
Gopi
18

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 )AL(X,Y)BL(Y,C)

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

Alessandro Cosentino
fonte
2
Ninguém que eu conheço usa "para programar" para "para programa linear" ou "para programa semidefinido". Você diria "construir / resolver um programa linear".
quer
2
@PeterShor ponto 3 não era sério
Alessandro Cosentino
3
E, claro, você também deve aprender a programar linear e a programar semidefinido ... ambas as habilidades úteis.
quer
3
+1 no ponto 2, na verdade, eu aprendi um pouco de OCaml quando era estudante de graduação, apesar de usá-lo apenas por um ano, tive o hábito de verificar os tipos de provas.
Gopi
4
Eu programo dinamicamente !
Jeffε
16

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).

Martin Berger
fonte
“Se você tiver sorte, terá que ministrar cursos bem distantes da sua área de especialização.” Isso tem sorte ...?
Tsuyoshi Ito
3
@ Tsuyoshi: Bem, isso força você a se familiarizar com uma nova área de assunto. No curto prazo, isso significa muito trabalho (que é amortizado a longo prazo, pois você provavelmente ensinará esse material mais de uma vez). Ao mesmo tempo, amplia consideravelmente seus horizontes intelectuais.
Martin Berger
@TsuyoshiIto: Sim!
Jeffε
13

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).

Radu GRIGore
fonte
2
Finalmente um argumento contra a programação :).
Gopi
11
@ Gopi, acho que a programação pode ser muito divertida e que o melhor entendimento que você ganha é muito importante. As outras respostas dão ótimos exemplos de como a programação ajuda a entender. Por isso, encorajo você a aprender programação e a não desistir, se a empresa parecer não pagar rapidamente.
Radu GRIGore #
6
Provar teoremas também é uma boa maneira de melhorar sua compreensão de vários conceitos, mas também é um período de tempo perigoso.
Jeffε
@ Jɛ ff E, minha opinião é preservada pela substituição [pseudocódigo-> prova no papel, código-> prova em um assistente de prova].
Radu GRIGore #
12

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.

John Moeller
fonte
3
Eu sei programar, e eu sou absolutamente sem esperança na visualização. Eu também suspeito que existem ferramentas que permitem visualizar as coisas sem fazer muita programação; se não houver, deve haver e talvez daqui a alguns anos.
quer
@ PeterShor: Porque você não usa C ++! (Brincadeirinha) #
93311 Tsuyoshi Ito
11
@ PeterShor: não estou me referindo a nenhum idioma ou ambiente específico; O MATLAB conta aqui. Mas saber programar pode obter visualizações que seriam incrivelmente inconvenientes. Por exemplo, o espaço de matrizes definidas bidimensionalmente positivas é tridimensional e eu queria visualizar uma família de construções nesse espaço. Eu tive que criar uma transformação e depois codificá-la para realmente ver meus objetos.
John Moeller
@ John ... você está certo, eu não acho que você poderia ter feito isso de outra maneira.
quer
7

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.

Lev Reyzin
fonte
Tsuyoshi Ito escreveu um argumento semelhante em sua resposta (segundo ponto :)).
Gopi
Opa, você está certa - eu perdi.
Lev Reyzin
5

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.

Marca
fonte
0

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.

Samuel Duclos
fonte
4
Não sei o quanto você está respondendo à pergunta original: não perguntei "como fazer", mas mais "para quê".
Gopi
0

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.

lgidwani
fonte
3
Você explicaria como este documento está relacionado à pergunta, ou seja, qual a importância de saber como programar para o TCS ?
scaaahu
Mesmo que fosse um exemplo de resultado teórico que se beneficiasse da programação, não responderia à pergunta original?
Jeremy
A pergunta pergunta se é necessário que um teórico da complexidade conheça a codificação. O artigo mencionado acima usa claramente resultados experimentais para complementar conceitos teóricos; isso requer codificação. De qualquer forma, levei muito tempo para encontrar um projeto de programação tão intimamente relacionado a um conceito central em ciência da computação teórica. Espero que este post seja útil para alguém em uma pesquisa semelhante.
Lgidwani