Resumo cap 15 livro o advento do algoritmo

352 palavras 2 páginas
CENTRO UNIVERSITÁRIO TIRADENTES – UNIT
ENGENHARIA MECATRÔNICA – NOITE
Alexandre Ferreira, Aramis Ocrécio, Elielton Antônio, Jorge Henrique, Sandro
José, Walter Palhares.

O capitulo 14 apresenta o problema bastante conhecido na área da computação, o caixeiro do viajante. Partindo de Witten, Iowa, o problema de Waterman era visitar Wittless, Grainball City, Sab Sac, Amblot e
Waterloo apenas uma vez e terminar a viagem em Wapping Falls.
O aspecto do problema é puramente teórico, Waterman precisa determinar quantas rotas possíveis pode levá-lo de cidade em cidade. Se há n cidades, há n! rotas possíveis entre elas, logo, há 5.040 rotas possíveis de sete cidades, mas se faz necessário saber quais sõa as rotas reais, as que estão ao seu dispor.
Escrever um algoritmo para resolver o problema é muito fácil. O programa pode dar uma solução satisfatória para o problema de Waterman logo na primeira vez que pegar o nome de uma cidade, mas a relação entre rotas e cidades é perigosamente instável. À medida que cidades são acrescentadas ao quadro de Waterman, o número de rotas entre elas cresce desmedidamente. Esse é um problema de interesse excepicional para os teóricos da informática. Um problema que pode ser resolvido em tempo polinomial pertence ao que é chamado de classe de complexidade P; e pertence a ela se sua solução pode ser encontrada em um número finito de passos. Na classe de complexidade NP, por outro lado, estão os problemas cujas as soluções podem ser verificados, mas não necessariamente encontradas em tempo polinomial. O problema de Waterman claramente pertence a classe
NP.
É a relação entre P e NP que é de grande interesse conceitual e prático. Claramente, P denota problemas tratáveis do mundo, e NP os problemas que não são tratáveis; e o que os teóricos e todo o resto do mundo gostariam de saber é se existe algum metódo para reduzir problemas intratáveis àqueles que são tratáveis.

O que Leonard Adelman fez para apresentar uma solução ao problema, foi

Relacionados

  • livro algoritmo
    62619 palavras | 251 páginas
  • Inteligência artificial
    6161 palavras | 25 páginas
  • TCC - Geoprocessamento
    70741 palavras | 283 páginas
  • Computação movel
    75153 palavras | 301 páginas
  • Love and thuth
    2930 palavras | 12 páginas
  • Ambiente de Aprendizagem Moodle
    4213 palavras | 17 páginas
  • Sistema anti-grampo para telefonia fixa
    18210 palavras | 73 páginas
  • Ciencia da computação
    140878 palavras | 564 páginas
  • O que a internet tem feito com nossas mentes
    22971 palavras | 92 páginas
  • Teoria dos números
    139028 palavras | 557 páginas