Perguntas decorrentes de aplicações da ciência da computação teórica em outras áreas da pesquisa / prática em ciência da computação ou outros assuntos.
Para demonstrar a importância dos algoritmos (por exemplo, para estudantes e professores que não fazem teoria ou são de campos totalmente diferentes), às vezes é útil ter à mão uma lista de exemplos em que os algoritmos principais foram implantados em setores comerciais, governamentais, ou software...
Para o problema de vazão máxima , parece haver um número de algoritmos muito sofisticados, com pelo menos um desenvolvido recentemente no ano passado. O fluxo máximo de Orlin no tempo O (mn) ou melhor fornece um algoritmo que roda em O (VE). Por outro lado, os algoritmos que eu normalmente vejo...
O estudo da ecologia e da evolução está se tornando cada vez mais matemático, mas a maioria das ferramentas teóricas parece vir da física. No entanto, em muitos casos, os problemas têm uma natureza muito discreta (veja, por exemplo, SLBS00 ) e podem se beneficiar da perspectiva da ciência da...
Eu não sou um teórico da ciência da computação, mas acho que esse problema do mundo real pertence aqui. O problema Minha empresa possui várias unidades em todo o país. Oferecemos aos funcionários a possibilidade de trabalhar em outra unidade. Mas há uma condição: o número total de trabalhadores...
Eu tenho trabalhado na introdução de alguns resultados da complexidade computacional na biologia teórica, especialmente evolução e ecologia , com o objetivo de ser interessante / útil para os biólogos. Uma das maiores dificuldades que enfrentei é justificar a utilidade da análise de pior caso...
Ultimamente, comecei a procurar algoritmos de aproximação para problemas difíceis de NP e estava pensando nas razões teóricas para estudá-los. (A questão não é para ser inflamatória - estou apenas curiosa). Alguma teoria verdadeiramente bela saiu do estudo dos algoritmos de aproximação - a conexão...
Houve pesquisas para implementar construções de extratores aleatórios? Parece que as provas do extrator fazem uso do Big-Oh, deixando a possibilidade de grandes constantes ocultas, tornando as implementações programáticas potencialmente irrealistas. Algum contexto: estou interessado em usar...
Eu gostaria de dar uma palestra em matemática sobre o sistema de controle de revisão do git . Agora é amplamente utilizado em matemática e também na indústria de ciência da computação. Por exemplo, a comunidade HoTT (Homotopy Type Theory) a utiliza e é o sistema para edição colaborativa de arquivos...
Ao tentar convencer economistas da relevância da teoria da complexidade impressa, existe uma referência padrão a ser citada? Estou familiarizado com o post de Noam Nisan , a pesquisa de Tim Roughgarden e o capítulo 11 do ensaio de Scott Aaronson . Essas postagens são acessíveis aos cientistas da...
Vamos supor que construímos um computador quântico universal. Exceto por questões relacionadas à segurança (criptografia, privacidade, ...) quais problemas atuais do mundo real podem se beneficiar com o uso? Estou interessado em ambos: problemas atualmente insolúveis para uma entrada...
Eu fiz essa pergunta no Stack Overflow há um tempo atrás: Problema: a venda de Bob . Alguém sugeriu postar a pergunta aqui também. Alguém já fez uma pergunta relacionada a esse problema aqui - subfloresta de peso mínimo de determinada cardinalidade - mas, pelo que entendi, não me ajuda com o meu...
Quais são alguns problemas do mundo real que foram resolvidos usando um algoritmo genético? Qual é o problema? Qual é o teste de aptidão utilizado para resolver este
O conceito de um esquema de compartilhamento secreto é frequentemente atribuído a Shamir (A. Shamir, Como compartilhar um segredo , Comm. ACM, 22 (1979), pp. 612-613.) E Blakey (GR Blakey, Salvaguardando chaves criptográficas , em Proc. NCC, volume 48, 1979, pp. 313-317.). A idéia geral é que...
Considere o seguinte problema, Dado um conjunto de números positivos { a 1 , … , a n } em que k ≥ 3 é uma constante, queremos particionar o conjunto em m subconjuntos de tamanho k, para que o produto da soma de cada subconjunto é maximizado.n=kmn=kmn = k m{a1,…,an}{a1,…,an}\{ a_1, \dots, a_n...
x1,…,xnx1,…,xnx_1, \ldots, x_nR2R2\mathbb{R}^2∥xi−xj∥2‖xi−xj‖2\|x_i - x_j\|^22323\frac 2 32323\frac 2 3 O pior exemplo que consigo encontrar é 3 pontos em um triângulo equilátero, que atinge o 2323\frac 2 3 . Observe que uma divisão aleatória produziria 1212\frac 1 2 , mas parece intuitivamente...
Estou procurando uma estrutura de dados altamente eficiente para armazenamento de dados semelhante à seguinte. Tags de identificação Pedido1 Pedido2 -------------------------- 1 1,2 1 1 2 2,5 2 3 3 1,7 4 7 4 6 3 0 Eu preciso ser capaz de consultar essa estrutura de tal forma a que ele iria me...
Estou interessado nas propriedades combinatórias das redes sociais como gráficos. As pessoas analisaram coisas como a distribuição dos graus, o coeficiente de agrupamento e a compressibilidade desses gráficos. Uma pergunta básica é: esses gráficos geralmente são bons gráficos de expansão? Alguém...
Seja x=(x1,…,xn)x=(x1,…,xn)x=(x_1,\dots,x_n) um vetor de variáveis booleanas. Sejam C,DC,DC,D dois circuitos booleanos em xxx . Diga que CCC é semelhante a DDD se: Pr[C(x)≠D(x)]Pr[C(x)≠D(x)]\Pr[C(x) \ne D(x)]{ 0 , 1 } nxxx{0,1}n{0,1}n\{0,1\}^n C,DC,DC,D diferem na distância de edição do gráfico...
Eu sou um estudante de CS. Fizemos teoria dos grafos em um curso. Achei interessante. Quais são as reais aplicações da teoria dos grafos no campo da ciência da computação? Por exemplo, descobri que alguns conceitos na teoria dos grafos podem ser usados para projetar redes. Quais são outras...
Esta pergunta foi motivada por uma pergunta no stackoverflow . Suponha que você está dado uma árvore enraizada (ou seja, há uma raiz e nós ter filhos, etc.) em n nós (rotulados 1 , 2 , ... , n ).TTTnnn1,2,…,n1,2,…,n1, 2, \dots, n Cada vértice tem um peso inteiro não negativo associado: w i...