Descrição da mesa de jantar da ciência da computação teórica?

Muitas vezes me perguntam o que um cientista da computação teórico faz. Seria ótimo ter boas respostas a essa pergunta. Eu tendem a voltar ao jargão técnico e os olhos das pessoas geralmente brilham nesse momento.

O que faz um cientista da computação teórico, em termos que podem ser entendidos por pessoas que não são cientistas da computação?

Uma boa resposta deve ser ágil, precisa em espírito, sem parecer vaga ou banal. Para pontos de bônus, a resposta deve sugerir por que um cientista da computação teórico não é matemático nem praticante de TI.

Esta pergunta é inspirada na pergunta MO https://mathoverflow.net/questions/3559/colloquial-catchy-statements-encoding-serious-mathematics, embora a intenção seja diferente.

Minha resposta é geralmente: "Estudo por que alguns cálculos são difíceis de fazer". Como exemplo, eu normalmente comparo adição e multiplicação usando os métodos padrão da escola primária. Estes são cálculos que todos fizeram e que todos apreciam o valor de fazer rapidamente. Todos concordam que, para grandes números, a multiplicação é muito mais difícil que a adição. De fato, a maioria das pessoas sugere que o método da escola primária é o mais rápido possível. Então eu pergunto a eles o porquê. Como eles sabem que não há outra maneira de fazer a multiplicação tão fácil quanto a adição?

Quase todo mundo tem pelo menos alguma apreciação neste momento pela dificuldade de provar limites mais baixos (meu interesse particular), mesmo que eu não tenha usado esse termo. Dependendo do histórico e do interesse do público, posso mencionar que alguém encontrou uma maneira de multiplicar muito mais rápido que o método da escola primária (simplesmente a palavra "algoritmo" tende a atrair a atenção dos olhos), mas ainda mais lenta do que adicionar.

Eu dou às pessoas um exemplo concreto. Especificamente, muitas vezes motivo a teoria da complexidade com o mesmo problema ilustrativo (mas simples). Pergunto à minha audiência como eles instruiriam uma criança pequena a descobrir se o nome dele está em uma lista de nomes classificados alfabeticamente (e digo a eles que a criança leva três segundos para comparar um nome com outro). Geralmente, a pessoa / grupo cria uma abordagem ingênua e linear. Eu forço a conversa a recorrer ao algoritmo logarítmico (eu poderia usar uma palavra diferente do logaritmo), pedindo à pessoa algo melhor ou mencionando eu mesmo. Eu lhes mostro como dobrar o tamanho da lista adiciona apenas três segundos de trabalho para a criança com essa nova abordagem. E eu comparo isso diretamente com a versão linear, que agora parecerá totalmente boba.

Claro, eu trago de volta à terra. Digo a eles que a criança em questão geralmente é um computador, mas que poderia ser uma criança ou qualquer pessoa em geral. Que as perguntas que fazemos não são realmente sobre computadores, mas mais sobre a quantidade de espaço, tempo e informações necessárias para solucionar problemas. E motivo a análise da complexidade por analogia aos dois métodos diferentes para resolver o mesmo problema.

Quando chamo a atenção deles, trago os rebatedores pesados. Eu pergunto a eles "você pode provar que a solução logarítmica é a melhor que você pode esperar fazer ou pode encontrar algo melhor?" e pergunto a eles "existem problemas que nenhum processo (algoritmo) pode esperar resolver?" Fiquei surpreso com o modo como as pessoas tentam resolver essas questões quando não têm um histórico no TCS.

Gosto deste post de Scott Aaronson , que explica a teoria da complexidade como teologia quantitativa. Aqui está um trecho:

A teoria da complexidade computacional não é realmente, realmente, realmente sobre computadores. Os computadores desempenham o mesmo papel na complexidade que os relógios, trens e elevadores na relatividade. Eles são uma ótima maneira de ilustrar o ponto, provavelmente foram essenciais para descobrir o ponto, mas não são o ponto.

A melhor definição da teoria da complexidade que consigo pensar é que é teologia quantitativa: o estudo matemático de seres superinteligentes hipotéticos, como deuses. Suas preocupações incluem:

• Se um Deus ou deuses existissem, como eles poderiam se revelar aos mortais? (IP = PSPACE ou MIP = NEXP no caso politeísta.)

• Quais deuses são mais poderosos que outros deuses? (P ^NP vs. PP, SZK vs. QMA, BQP ^NP vs. NP ^BQP , etc. etc.)

• Poderia um Deus maravilhoso escolher conceder Sua onisciência a um mortal? (EXP vs. P / poli.)

• Oráculos podem ser confiáveis? (Os oráculos podem ser confiáveis?)

E claro:

• Os mortais poderiam se tornar divinos? (P vs. NP, BQP vs. NP.)

Um exemplo de resposta, que definitivamente pode ser melhorado:

Os cientistas teóricos da computação estudam computação em termos matemáticos. Eles podem consertar seu computador e os matemáticos podem calcular seus impostos.

Eu acho que uma excelente (não) resposta nesse sentido foi dada por Dijkstra (sempre uma boa fonte para recorrer a pronunciamentos rígidos e absolutistas :)).

Ciência da Computação não é mais sobre computadores do que astronomia é sobre telescópios. - EW Dijkstra

Eu realmente gosto da introdução ao problema de particionamento, conforme apresentado por Brian Hayes aqui .

Ele usa o problema de particionar um conjunto de crianças em equipes de igual capacidade total (supondo que você possa quantificar a capacidade de cada criança usando um número) e também explica o algoritmo guloso geralmente usado pelas crianças para resolver esse problema.

É um problema muito simples de entender, é fácil entender o algoritmo, surpreendente que seja (provavelmente) muito difícil em geral e embaraçoso que ainda não conseguimos provar o último bit.

Normalmente, respondo com algo do tipo: tento descobrir o que é possível fazer com um computador. Não é completamente preciso, mas é bem próximo, e geralmente as pessoas perguntam algo como "O que você quer dizer?" e posso referenciar algo específico, como TSP. Embora eu reformule o vendedor ambulante como, digamos, o problema de pular nas barras, o problema dos corretores de imóveis, o problema de muitas tarefas não há tempo suficiente ou o que parecer apropriado.

Por exemplo: "Bem, digamos que você precise comprar sapatos, compras e roupas, pegue um bolo, faça um corte de cabelo e faça outras tarefas antes do jantar. Seria ótimo se você pudesse colocar tudo isso no seu GPS e pode indicar em que ordem todas as suas tarefas serão feitas às 4 horas, mas se a lista de tarefas for longa o suficiente, não é possível, no momento, descobrir se você pode fazê-las por 4 em tudo , muito menos que ordem você precisa fazer-los, em qualquer quantidade razoável de tempo. Eu quero saber se é possível resolver esse problema rapidamente com um computador."

Quais são as melhores maneiras de resolver problemas e quais são difíceis de resolver? Há uma palavra em idiomas europeus - incluindo inglês! - "informática". A ciência da informação. Nos EUA, chamamos isso de ciência da computação teórica, por causa da forte indústria de computadores aqui, mas pensamos em resolver problemas sem computadores por um minuto. Considere o corpo humano. Resolve problemas de maneira quase milagrosa. A luz entra em nossos olhos e podemos ver coisas que reconhecemos . O som entra em nossos ouvidos e ouvimos palavras que entendemos . São problemas de informação com os quais resolvemos facilmente, milhares de vezes por dia, com os quais os melhores computadores do mundo ainda enfrentam problemas.

O processo de evolução levou milhões de anos para resolver esses problemas, usando uma estratégia de tentativa e erro e matando os infelizes. Imagine o que poderíamos realizar se adotássemos uma abordagem mais racional e investíssemos tanta criatividade humana nessa nova ciência da solução de problemas quanto investimos em geometria, teologia ou cálculo. O que faço é uma pequena parte desse investimento.

Em resposta à pergunta do leigo, "O que você faz?" Muitas vezes respondi: "Passo muito tempo olhando o espaço, descobrindo como tornar a ficção científica real". Depois, dou um exemplo específico de um projeto, explicado em algumas frases.

A ciência da computação teórica é para a ciência da computação o que a matemática costumava ser para a física.

Normalmente, dou a seguinte resposta, embora focada na teoria da complexidade: "Estudo os limites, em termos de espaço e tempo, para que um problema seja resolvido. Os problemas incluem: encontrar o caminho mais curto no mapa ou ganhar um jogo de xadrez".

Geralmente dou o problema de fatoração como exemplo; Peço primeiro o número que divide 15; geralmente as pessoas podem responder 3, 5 e se divertir perguntando se 1 e 15 são a resposta correta. Então eu dou um número enorme (mais de 10 dígitos) e pergunto se eles podem me dizer quais são os divisores; e explico que, mesmo para os cientistas da computação, essa é uma pergunta realmente difícil.

Então, se eu tiver tempo, tento explicar que a questão é descobrir como resolver esse problema ou provar que sempre levará muito tempo (uma noção que sabemos exatamente como definir). E então uma pequena palavra de criptografia, para explicar por que ela é usada, e uma palavra sobre quanto tempo leva a equipe de cientistas a quebrar a chave do número com centenas de dígitos (eu evito falar em bits porque as pessoas parecem saber melhor o que é um dígito)

A questão colocada é realmente difícil, pois a maioria das pessoas não tem idéia do que os cientistas da computação em geral fazem. Isso é muito diferente de outras disciplinas.

Eu gosto de usar a seguinte analogia: (T) CS é para computadores o que é física para CD-players (ou seja, o laser). Isso realmente funciona muito bem, porque a maioria das pessoas tem uma idéia do que um físico lida, seja correto ou não.

Exemplos mais específicos incluem coisas com as quais as pessoas podem se relacionar

• Correspondência de seqüência de caracteres (abordagem ingênua lenta versus experiência diária de pesquisa rápida no Word, Navegador, ...)
• Problema de caminho mais curto (conforme usado em sistemas de navegação)
• Agendamento (dependendo do grau de nerdidade do outro, consulte processos de negócios ou agendamento na CPU)

Eu explicaria então que, enquanto as pessoas do PCS cuidam de uma rápida implementação ou boa integração em sistemas complexos, as pessoas do TCS se perguntam o que é possível e provam coisas que fornecem conhecimentos / técnicas seguros e reutilizáveis ​​para o PCS usar.

Você também pode usar a frustração das pessoas em relação aos computadores ("Não faz o que eu quero!"). Você pode salientar que o (T) CS trata de como expressar as coisas de uma maneira que os computadores possam entender e processar eficientemente (referindo-se a sintaxe, semântica, estruturas de dados, algoritmos).

Quando alguém lhe faz uma pergunta, você pode respondê-la diretamente ou dar a ele um procedimento passo a passo a seguir e uma prova de que, se as etapas forem seguidas com precisão, a resposta será obtida dentro de um período de tempo razoável. Dado que os passos em si não são muito complicados e podem ser executados rapidamente por uma entidade capaz de existir neste universo, que tipos de perguntas exibem tais procedimentos? Eu acho que esse é o assunto da Ciência da Computação Teórica.

Minha resposta usual, que não é rápida, mas é garantida para interromper a conversa (bônus!), É "como a teoria quântica é o núcleo matemático da física, o TCS é o núcleo matemático da ciência da computação".

Estudamos os limites da computação. Com que rapidez você pode resolver um determinado problema computacional? Quanto tempo é necessário para resolvê-lo, independentemente da solução que você tenta? Depois, dou a eles esses exemplos (que são fáceis de explicar para a maioria dos leigos - e, de fato, muitos leigos têm experiência direta com eles - demonstram algumas propriedades dos problemas de PN-completos e realmente têm a ver com salvar vidas).

Obviamente, as pessoas (inclusive eu) podem brincar dizendo que eu ignorei outros recursos importantes, como espaço, aleatoriedade ou até quantum. Mas quando você tem apenas 2 minutos para contar a alguém sobre um campo inteiro, algumas coisas ficam de fora.

Se você quiser dar uma olhada no passado, lembre ao público que "computador" costumava se referir a uma pessoa cuja profissão era calcular as coisas . (E se você quiser violar alguns estereótipos de gênero que eles possam ter, pode salientar que esses também eram frequentemente mulheres.)

Você pode obter várias coisas ao mesmo tempo:

• faça um argumento convincente de que "ciência da computação" pode ser algo além de estudar "computadores";
• ressalte que as pessoas que estão computando precisam de algumas regras para realizar sua tarefa (especialmente em uma sala cheia de "computadores" realizando tarefas especializadas - complexidade e paralelização da comunicação, alguém?), e isso é verdade para as máquinas;
• descrever que "ciência da computação" é encontrar maneiras eficazes de resolver problemas que envolvem "computação" nesse sentido;
• coloque a questão de que o que exatamente está fazendo a computação não é tão importante quanto os recursos de que eles precisam (como tempo e espaço disponível).

Eu sempre começo apontando-os para um vídeo ou artigo criativo e intencionalmente irreverente que explica um conceito técnico em um nível intuitivo. Aqui está um bom exemplo: Rabiscar em matemática: espirais, Fibonacci e ser uma planta

Depois que eles entendem o conceito (e esperamos ter nos divertido um pouco), tento generalizar o que eles aprenderam sobre algo sobre o TCS. Por exemplo, o vídeo acima pode levar a uma explicação básica de algoritmos ou computação como um processo recursivo - "algo que gera uma estrutura complexa a partir de algumas regras simples". O pessoal da TCS, então, apenas estuda que tipos de regras produzem que tipos de estrutura!

A partir daí, geralmente é fácil passar do TCS geral para o que você faz de domínio específico. :)

Seguindo a sugestão de Ross Snider, de começar com um exemplo específico, também se pode explicar diretamente a questão P vs NP. Pode-se descrever essa pergunta para um leigo como se a verificação de uma solução é comprovadamente mais fácil do que realmente encontrar uma, ou é verdade que sempre que podemos verificar uma solução, também podemos encontrá-la?

Aqui está o meu:

A ciência da computação não é apenas ciência, há muita engenharia nela, mas a parte científica é sobre a compreensão da computação. E uma computação é um processo físico que gera informações de maneira ordenada. Na ciência da computação teórica, achamos que precisamos de matemática relativamente sofisticada para entender a computação.

Isso nos leva a falar sobre computação em biologia, o papel da lógica na ciência da computação, etc.

Talvez alguém possa dizer isso

um cientista da computação teórico estuda problemas realmente muito difíceis relacionados à ciência da computação.

O cientista não usa o computador enquanto é criativo, mas pensa muito em rabiscar fórmulas e desenhos peculiares no papel e, ocasionalmente, passear. Assim, a praticabilidade imediata não é a coisa mais importante, é mais como um artista que explora e tenta entender os mistérios deste mundo.

Pode-se mencionar coisas que contam com algumas soluções elegantes de teóricos, como computador, internet, mecanismos de busca, banco seguro, filmes em 3D, seqüenciamento de DNA etc. algumas delas podem ser vistas pela primeira vez em várias décadas.

Pela minha experiência, muitas pessoas têm um momento da AHA em que percebem que a ciência da computação e a teoria em especial são tão ricas em questões e problemas interessantes para estudar. Muitos dos quais podem ser descritos em um nível alto! Esta é uma lista do Prof. Wikipedia (via SIGACT), escolha seus favoritos: algoritmos, estruturas de dados, teoria da complexidade computacional, computação distribuída, computação paralela, VLSI, aprendizado de máquina, biologia computacional, geometria computacional, geometria computacional, teoria da informação, criptografia, computação quântica , teoria dos números computacionais e álgebra, semântica e verificação de programas, teoria dos autômatos e estudo da aleatoriedade.

O que faz um cientista da computação teórico, em termos que podem ser entendidos por pessoas que não são cientistas da computação?

Praticamente o mesmo que um técnico de conserto de videocassete. Ambos consideram como obter o melhor desempenho das máquinas que lêem e gravam informações em pedaços extremamente longos de fita.

Isso pode ser um pouco mais doloroso do que o que você estava procurando ...