Professor, tenho uma pergunta: em qual classe de complexidade se encontra um trabalho que faz uso de processamento de imagens e classificação das mesmas? Mais especificamente o trabalho é sobre veículos autônomos e detecção de vias terrestres não pavimentadas, no caso preciso classifica-lo em uma dessas classes. Penso que seja um problema NP-Complete mas estou com dúvidas.
Como provar isso?
Desde já, muito obrigado!
3 года назад
Olá Wanderson, tudo bem? Se o seu algoritmo leva tempo exponencial para resolver o problema de visão computacional, temos indícios fortes de que ele é um problema NP-Completo, que é a classe de problemas que não tem soluçao em tempo polinomial. Mas como provar que meu problema é NP-Completo? Você tem que reduzir uma instância (exemplo) do seu problema a uma instância de um problema que já é notadamente NP-Completo. E também tem que fazer a volta que é pegar a instancia NP-Completa e retornar para a instância do seu problema. Se você fizer isso está provado. Obrigado por gostar do canal. Se você não for inscrito poderia se inscrever e ajudar o meu trabalho?
Professor olá tudo bem! Só uma pequena correção, no vídeo houve ligações entre os literais X2 com a sua negação, bem como o X3 com a sua negação, porém estas ligações não são permitidas.
4 года назад+4
Olá Giovane! Obrigado por corrigir. As vezes durante o vídeo fico um pouco nervoso... tímido sei lá. Você tá certo. Além disso, também foram muitas ligações para fazer... No vídeo não deu tempo de parar e verificar tudo. Gostaria de te pedir para se inscrever no canal se ainda não é inscrito e dê like e compartilha também para poder promover o canal. Me dá essa moral. Precisamos promover o máximo o canal para ajudar muito alunos.
Oi professor Adriano, eu não consegui entender no começo do vídeo quando foi explicado sobre os cliques o por quê de ser 4-cliques-2. Os outros eu entendi, mas esse fiquei com dúvida, não seria 2-cliques-2?
4 года назад+1
Oi Patrícia, são 4 cliques 2 mesmo. Cada para de 2 vértices que formam uma aresta é uma clique de tamanho 2. Qualquer dúvida estou a disposição.
Não tem 4-clique no grafo. Um clique é um subconjunto onde qualquer pares de vértices são adjacentes, ou seja ligados entre sim
3 года назад
Oi Diane, tudo bem? Tem razão. Obrigado por corrigir. Realmente não tem 4-clique no grafo de exemplo do começo do vídeo. Entretanto sua definição de clique está errada. A definição é: Cada dois vértices do subjconjunto que eu pegar esse dois tem que estar conectados por uma aresta. Ok? Essa é a definição certa. Se você não é inscrita no canal poderia se inscrever e fortalecer o meu trabalho?
Sensacional, o assunto mais complicado da ciência da computação explicado de forma muito clara!
Professor, tenho uma pergunta: em qual classe de complexidade se encontra um trabalho que faz uso de processamento de imagens e classificação das mesmas? Mais especificamente o trabalho é sobre veículos autônomos e detecção de vias terrestres não pavimentadas, no caso preciso classifica-lo em uma dessas classes. Penso que seja um problema NP-Complete mas estou com dúvidas.
Como provar isso?
Desde já, muito obrigado!
Olá Wanderson, tudo bem? Se o seu algoritmo leva tempo exponencial para resolver o problema de visão computacional, temos indícios fortes de que ele é um problema NP-Completo, que é a classe de problemas que não tem soluçao em tempo polinomial.
Mas como provar que meu problema é NP-Completo?
Você tem que reduzir uma instância (exemplo) do seu problema a uma instância de um problema que já é notadamente NP-Completo. E também tem que fazer a volta que é pegar a instancia NP-Completa e retornar para a instância do seu problema.
Se você fizer isso está provado.
Obrigado por gostar do canal. Se você não for inscrito poderia se inscrever e ajudar o meu trabalho?
Professor olá tudo bem!
Só uma pequena correção, no vídeo houve ligações entre os literais X2 com a sua negação, bem como o X3 com a sua negação, porém estas ligações não são permitidas.
Olá Giovane! Obrigado por corrigir. As vezes durante o vídeo fico um pouco nervoso... tímido sei lá. Você tá certo. Além disso, também foram muitas ligações para fazer... No vídeo não deu tempo de parar e verificar tudo. Gostaria de te pedir para se inscrever no canal se ainda não é inscrito e dê like e compartilha também para poder promover o canal. Me dá essa moral. Precisamos promover o máximo o canal para ajudar muito alunos.
Oi professor Adriano, eu não consegui entender no começo do vídeo quando foi explicado sobre os cliques o por quê de ser 4-cliques-2. Os outros eu entendi, mas esse fiquei com dúvida, não seria 2-cliques-2?
Oi Patrícia, são 4 cliques 2 mesmo. Cada para de 2 vértices que formam uma aresta é uma clique de tamanho 2. Qualquer dúvida estou a disposição.
Ah sim, obrigada.
Não tem 4-clique no grafo. Um clique é um subconjunto onde qualquer pares de vértices são adjacentes, ou seja ligados entre sim
Oi Diane, tudo bem? Tem razão. Obrigado por corrigir. Realmente não tem 4-clique no grafo de exemplo do começo do vídeo. Entretanto sua definição de clique está errada. A definição é: Cada dois vértices do subjconjunto que eu pegar esse dois tem que estar conectados por uma aresta. Ok? Essa é a definição certa.
Se você não é inscrita no canal poderia se inscrever e fortalecer o meu trabalho?