Complexidade aleatoria de problemas computacionais (1992)
- Autores:
- Autor USP: MIYAMOTO, EDSON TADASHI - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: TEORIA DOS GRAFOS
- Idioma: Português
- Resumo: 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
-
ABNT
MIYAMOTO, Edson Tadashi. Complexidade aleatoria de problemas computacionais. 1992. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 1992. Disponível em: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-003347/. Acesso em: 19 abr. 2024. -
APA
Miyamoto, E. T. (1992). Complexidade aleatoria de problemas computacionais (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-003347/ -
NLM
Miyamoto ET. Complexidade aleatoria de problemas computacionais [Internet]. 1992 ;[citado 2024 abr. 19 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-003347/ -
Vancouver
Miyamoto ET. Complexidade aleatoria de problemas computacionais [Internet]. 1992 ;[citado 2024 abr. 19 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-003347/
Como citar
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
