Aqui está uma pergunta da "faixa B", se é que alguma vez houve. Resumo: a primeira coisa que penso quando tento dar uma semântica a programas não determinísticos resulta em uma semântica em que não posso provar coisas sobre loops que terminam apenas de forma não determinística. Certamente alguém...
Alguém pode me apontar a referência para a não definibilidade do módulo de continuidade funcional no PCF? \ newcommand {\ bool} {\ mathsf {bool}}\newcommand{\N}{\mathbb{N}} \newcommand{\bool}{\mathsf{bool}} Andrej Bauer escreveu um post muito bom no blog explorando alguns dos problemas com mais...
Minha pergunta é sobre a equivalência da segurança de várias funções unidirecionais candidatas que podem ser construídas com base na dureza da fatoração. Assumindo o problema de FACTORING: [Dado para números primos aleatórios P , Q < 2 n , encontre P , Q. ]N= PQN=PQN = PQP, Q <...
Dado um gráfico misto G=(V,E,A)G=(V,E,A)G=(V,E,A) com as arestas EEE e arcos AAA , encontre uma correspondência em EEE que minimize o número de arcos em G/MG/MG/M , onde G/MG/MG/M é obtido de GGG contratando vértices correspondentes e removendo arcos paralelos. (A versão de decisão) deste problema...
Quero começar a aprender sobre a codificação de rede: http://en.wikipedia.org/wiki/Network_coding Você conhece alguma boa pesquisa (por exemplo, pesquisas e tutoriais do IEEE) sobre os assuntos acima. Encontrei alguns cursos universitários no google, mas gostaria de receber recomendações de...
Existem vagas para recém-formados ou mestres com um histórico de pesquisa para trabalhar como pesquisador antes de se comprometerem com o doutorado? O TCS tem uma cultura de cargos de pós-doutorado para que os recém-formados em doutorado façam pesquisas antes de tentar se candidatar a uma vaga...
Digamos que temos um poliedro na forma padrão: A x = bx ≥ 0UMAx=bx≥0 0\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*} Existem métodos conhecidos para encontrar um hiperplano que divide o poliedro de uma maneira que o número...
Katz e Lindell mencionam em seu livro que o LFSR tem sido horrível como base para geradores pseudo-aleatórios e defendem que eles não são mais usados (bem, eles também recomendam que as pessoas usem cifras de bloco em vez de cifras de fluxo). Mas vejo, por exemplo, que uma das cifras do portfólio...
Suponha que seja uma linguagem booleana, de seqüências finitas acima de { 0 , 1 } . Seja L n o número de strings em L com comprimento n . Para uma função d ( n ) dos números inteiros positivos aos números reais positivos, L tem densidade superior d ( n ) se L n ≤ 2 n d ( n ) para todo n...
Um idioma está na classe se houver dois idiomas e modo queLLLDPDPDPL1∈NPL1∈NPL1 \in NPL2∈coNPL2∈coNPL2 \in coNPL=L1∩L2L=L1∩L2L = L1 \cap L2 Um problema canônico de completo é SAT-UNSAT: dadas duas expressões 3-CNF, e , é verdade que é satisfatório eDPDPDPFFFGGGFFFGGG não é? Também se sabe que o...
Estou diante de um dilema bastante difícil: - Eu havia completado a M.Tech no CS há 2 anos, completando minha dissertação na área de testes VLSI. Enquanto eu gostei do meu trabalho, não quero voltar a fazer meu doutorado nisso - tenho muita vontade de seguir um curso teórico (em algoritmos de...
Estou procurando o texto completo do resultado da camarilha de Moon and Moser de 1965, On Cliques in Graphs (existem gráficos com um número máximo de cliques exponenciais em ). O paywall da minha universidade não tem acesso ao diário específico. (De fato, a visualização fornece as primeiras frases...
Ouvi muitas vezes dizer que você não pode escrever um programa para detectar bugs em um navegador da Web, processador de texto ou sistema operacional, por causa do Teorema de Rice: qualquer propriedade semântica para uma linguagem completa de Turing é indecidível. No entanto, não sei até que...
Contexto: Consideramos apenas dígitos. Deixe CYCLE ser a linguagem dos gráficos com um ciclo; é um problema NL-completo. Seja HASEDGE o idioma dos gráficos com pelo menos uma aresta. Em seguida, trivialmente, não é mais NL, enquanto permanece assim.CICLO ∪ ¯ HASEDGECICLO ∪...
Estou procurando notas de aula disponíveis on-line ou outros recursos que ofereçam uma boa introdução à programação paralela, assim como o analógico paralelo de classes básicas em ciência da computação. Meu foco é o seguinte: enquanto sou capaz de falar sobre dividir e conquistar, algoritmos...
Existe um algoritmo de tempo polinomial para encontrar - se houver - uma aranha de abrangência de um determinado gráfico ? Uma aranha é uma árvore com no máximo um nó com grau maior que 2: eu sei que várias condições de grau em G (essencialmente, graus de nó suficientemente grandes) garantem a...
No livro de Arora-Barak, na definição de funções construtivas no tempo, diz-se que o uso de funções que não são construtíveis no tempo pode levar a "resultados anômalos". Alguém tem um exemplo desse "resultado anômalo"? Ouvi, em particular, que podem existir funções tais que o teorema da hierarquia...
Dado um conjunto de pontos em um espaço cartesiano 3D, estou procurando um algoritmo que classifique esses pontos, de modo que a distância euclidiana mínima entre dois pontos consecutivos seja maximizada. Também seria benéfico se o algoritmo tivesse uma tendência a uma distância euclidiana média...
Não tenho certeza se a área correta, mas aqui vai. Inicio um doutorado em Gerenciamento de Confiança e Reputação em redes de Comunicações (muita teoria de grafos, análise probabilística, etc.) e tenho muita leitura pela frente. Alguém pode aconselhar as melhores maneiras de gerenciar a leitura...
Eu tenho 400 bolas, nas quais 100 são vermelhas, 40 são amarelas, 50 são verdes, 60 são azuis, 70 são roxas, 80 são pretas. (bolas da mesma cor são idênticas) eu preciso de um algoritmo de embaralhamento eficiente, para que, após embaralhar, as bolas estejam em uma lista e Quaisquer 3 bolas...