Exportar registro bibliográfico

Complexidade aleatoria de problemas computacionais (1992)

  • Authors:
  • Autor USP: MIYAMOTO, EDSON TADASHI - IME
  • Unidade: IME
  • Sigla do Departamento: MAC
  • Assunto: TEORIA DOS GRAFOS
  • Language: Português
  • Abstract: Nos 4 primeiros capitulos do trabalho, estudamos a complexidade computacional do reconhecimento de propriedades de grafos invariantes por isoformismos. Estudamos o problema para propriedades monotonicas nao-triviais de grafos. Sabe-se atualmente que a complexidade deterministica de pior caso dessas propriedades e 'OMEGA' ('N POT.2'), onde n e o numero de vertices dos grafos considerados. Existe entretanto uma conjectura de yao e karp de 1977 que diz que a complexidade aleatoria destas propriedades e tambem 'OMEGA' ('N POT.2'). Os resultados de yao e king sobre esta conjectura e o melhor limite inferior conhecido atualmente de 'OMEGA' ('N POT.4/3'), provado recentemente por p. Hajnal. Caso a conjectura de yao e karp venha a ser provada, pode-se por em duvida a eficacia de metodos probabilisticos aplicados a problemas computacionais. No ultimo capitulo apresentamos resultados de valiant e reischuk que comprovam que no caso do problema de selecao em paralelo do menor elemento de um conjunto, existe um algoritmo aleatorio que e assintoticamente mais eficiente do que qualquer algoritmo deterministico. Neste mesmo capitulo, apresentamos um resultado de alon e azar que prova que no caso de ordenacao de conjuntos com n elementos, usando algoritmos que utilizam mais de n processadores, a eficiencia de algoritmos aleatorios nao e melhor do que a de algoritmos deterministicos
  • Imprenta:
  • Data da defesa: 28.09.1992

  • How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      MIYAMOTO, Edson Tadashi; KOHAYAKAWA, Yoshiharu. Complexidade aleatoria de problemas computacionais. 1992.Universidade de São Paulo, São Paulo, 1992.
    • APA

      Miyamoto, E. T., & Kohayakawa, Y. (1992). Complexidade aleatoria de problemas computacionais. Universidade de São Paulo, São Paulo.
    • NLM

      Miyamoto ET, Kohayakawa Y. Complexidade aleatoria de problemas computacionais. 1992 ;
    • Vancouver

      Miyamoto ET, Kohayakawa Y. Complexidade aleatoria de problemas computacionais. 1992 ;

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

    Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2021