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

51

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.

András Salamon
fonte

Respostas:

34

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.

Aubrey da Cunha
fonte
8
Gosto que o seu exemplo use adição e multiplicação como exemplos. Parece que, de alguma forma, isso seria ainda menos intimidador para um leigo do que classificar ou procurar.
Lev Reyzin
Esta é uma maneira muito boa de chegar rapidamente ao cerne da questão, obrigado!
András Salamon
3
Eu dei o mesmo exemplo :) A reação que eu vi são pessoas negando, quase ficando com raiva de mim: "o que você quer dizer com não sabemos se a multiplicação é mais difícil do que a adição? É claro que sim ... você está brincando comigo? "
Sasho Nikolov
Eu realmente gosto desta resposta, mas não é o que faço! Eu trabalho em um campo completamente diferente, a saber, teoria dos tipos dependentes. Devo explicar "teoria A" vs "teoria B"?
Cody
39

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.

Ross Snider
fonte
11
E, para que conste, tive muita sorte em conseguir aproximar as pessoas de mim um pouco do assunto.
Ross Snider
11
Antes do fim efetivo da lista telefônica, isso poderia ter sido transformado em uma resposta rápida de duas frases. Existe um exemplo canônico de uma lista ordenada de acesso aleatório que todo mundo conhece?
András Salamon
Claro, András. O índice de um livro. Como alternativa, é claro que você pode optar por um novo baralho de cartas antes que ele seja embaralhado, o que obviamente permitiria que você considerasse o caso não ordenado.
Joe Fitzsimons
@ Joe: Eu encontro regularmente pessoas que não usaram livros didáticos com índices. Talvez se Harry Potter viesse com um índice ...
András Salamon 21/09
@ András: Acho que comi na faculdade com muita frequência! Certamente quase todos os livros escolares os possuem.
Joe Fitzsimons
21

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.)
Robin Kothari
fonte
pode haver apenas um Deus, supondo que vários deuses sejam logicamente inconsistentes, porque vários deuses terão diferentes níveis de atributos que contradizem o princípio de um Deus supremo (um deus sendo mais poderoso que outro deuses é bobo)
Mohammad Al-Turkistany
11
@ Williams, meu argumento é que o leigo ficará confuso com essas analogias .
Mohammad Al-Turkistany
10
embora eu realmente não deva, devo salientar que vários deuses são inconsistentes apenas sob a visão de que propriedades semelhantes a Deus formam uma ordem total. Se eles formam uma ordem parcial, é perfeitamente bom ter vários deuses. (Desculpe, Ryan)
Suresh Venkat
@Suresh, você está sugerindo que poderia haver dois deuses que não podemos dizer quem é mais poderoso? A relação binária aqui é ordem total. (desculpe, Ryan)
Mohammad Al-Turkistany
18

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.

András Salamon
fonte
20
Infelizmente, muitas pessoas que conheço pensam que os matemáticos seriam precisamente bons no cálculo de impostos ...
Lev Reyzin
11
Isso me lembra a famosa citação de Dijkstra - "A ciência da computação não é mais sobre computadores do que a astronomia é sobre telescópios".
Vinayak Pathak
2
Lez - Essas pessoas devem ser informadas sobre o Grothendiek Prime.
Vinayak Pathak
13
Aqui está outro, retirado de jondoda no Twitter: "Pedir a um cientista da computação para suporte técnico é como pedir a um botânico para cortar a grama". Este está ficando mais quente ...
Ryan Williams
4
Ryan, o corolário é que ambos podem facilmente realizar a tarefa, mas se ressentem de serem solicitados?
Joe Fitzsimons
16

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

Suresh Venkat
fonte
11

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.

Alex ten Brink
fonte
Este é realmente bom. De alguma forma eu não notei isso aqui antes.
Ryan Williams
Adorei o artigo!
Arnab #
8

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

philosodad
fonte
Ótimo, acho que esse é o tipo de resposta que iniciaria uma conversa interessante!
András Salamon
7

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.

Aaron Sterling
fonte
11
A maioria das pessoas que conheço pensaria que alguém tentando tornar a ficção científica real era um físico. Como você distingue?
András Salamon
2
Eu adoraria se um cientista experimental construísse algo que eu pensei. Por que tem que haver uma maneira de distinguir? Mas, para responder de qualquer maneira: penso em computadores microscópicos, enquanto os físicos pensam nas propriedades da matéria. Existe alguma diferença? Depende do que você gosta e do que enfatiza.
Aaron Sterling
Parece-me que isso explica o que é ciência da computação, mas não o que é ciência da computação teórica.
Zsbán Ambrus
6

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.

Andrej Bauer
fonte
2
por que "costumava ser"?
Suresh Venkat
11
Lembro-me de ouvir algo como: "CS para lógica / combinatória (TCS) é como física para geometria".
Kaveh
3
Suresh, acho que Andrej está afirmando isso: costumava ser que o estudo da física gerava uma grande fração dos problemas estudados pelos matemáticos, mas essa fração diminuiu ao longo dos anos (agora a matemática é muito mais ampla). Não sei o suficiente sobre a história da matemática para ter certeza de que isso é verdade, mas o que sei está de acordo com isso.
Ryan Williams
11
Eu não acho que essa analogia funcione, porque os leigos também não conhecem matemática e física.
Zsbán Ambrus
5

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

Michaël Cadilhac
fonte
5

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)

Arthur MILCHIOR
fonte
5

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

Rafael
fonte
4

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.

Vinayak Pathak
fonte
11
A única questão é a conversa sobre coisas que existem dentro do universo. Isso meio que torna a física mais do que a TCS. Afinal, o universo é um objeto finito, e uma grande parte do TCS lida com assintóticos.
Joe Fitzsimons
Hmm, esse é um bom argumento. Mas será que realmente usamos assintóticos porque queremos saber como nosso algoritmo se comportará em tamanhos de entrada maiores que o universo ou usamos a notação grande-Oh apenas para tornar nossos cálculos mais ou menos independentes?
Vinayak Pathak
Bem, certamente acho que coisas como decidir a computabilidade etc. vivem em um nível mais abstrato.
Joe Fitzsimons
4

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

Suresh Venkat
fonte
3
Na verdade, a Física Teórica, em vez da Mecânica Quântica, é o TCS da Física. Há muitas outras teorias físicas além da mecânica quântica (a relatividade geral clássica é o exemplo mais óbvio).
Joe Fitzsimons
O objetivo não é a precisão :)
Suresh Venkat
Mas então pode-se perguntar: "O que é ciência da computação?"
Vinayak Pathak
4

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.

Joshua Grochow
fonte
4

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).
Niel de Beaudrap
fonte
4

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

Daniel Apon
fonte
2

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?

Vinayak Pathak
fonte
2

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.

Charles Stewart
fonte
2

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.

Michael
fonte
0

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

Joe Fitzsimons
fonte
Certamente manteria a conversa em andamento!
András Salamon
11
Oh bom. Você pode me dizer como fazer o relógio parar de piscar 12:00?
Jeffε
11
Certamente, cobro a taxa de união habitual.
András Salamon
Eu sei que isso foi um pouco ridículo, mas, observando os votos negativos, eu o removerei felizmente se alguém tiver um problema sério com isso.
Joe Fitzsimons
11
Sem problemas! Eu estava preocupado que alguns teóricos da CS ou alguns técnicos de videocassete possam ter se ofendido.
Joe Fitzsimons