Aula de dúvidas para prova presencial do curso de Licenciatura

Iniciei a gravação, então, hã, e vou compartilhar com vocês o gabarito da lista de exercícios preparatória para paraa avaliação, né? Eu já disponibilizei esse gabarito, mas ã eu acho que é um interessante pra gente conversar um pouco sobre a matéria, né? E deixa eu voltar aqui aqui pra gente conversar então sobre a matéria um pouquinho e ver se vocês têm alguma dúvida.

Ã, deixa eu ver se tá gravando tudo certo. Está. Então, eh, olá, boa noite.

Eu acabei de começar a gravação e vou, ã, conversar com você sobre a lista de exercícios e vai ficar gravado, então, eh, o que eu vou est eh conversando agora com vocês sobre a matéria. Então, eu disponibilizei uma lista de exercícios preparatório, então, paraa prova, né? Então, a primeira questão, ela perguntava ali para vocês citarem ao menos eh cinco problemas NP completos.

Que que tinha que tomar cuidado aqui? Eh, alguns problemas são problemas já de decisão, então eles são problemas NP completos porque eles têm eles pertencem à classe NP dos problemas que podem ser verificados em tempo polinomial e pertence à classe NP difícil, aonde tu tem a redução, né, de todos os problemas da classe NP para um problema já provado NP completo e de um problema já provado NP completo para ele. E os problemas que são de decisão, eles pertencem tanto a NP quanto a NP completo.

Os problemas de decisão difíceis, né? E então eles são NP completos. E tem problemas que a originalmente é um problema de otimização e aí ele seria apenas NP difícil porque ele não pode ter a verificação em ter polinomial.

Então, na hora que tu for escrever o nome do problema, quando é um problema que originalmente é de otimização, tu tem que acrescentar a palavra decisão. Então, se vocês olharem aqui, eu coloquei então soma de subconjuntos, que já é um problema de decisão. Então, ele é NP completo, porque é possível verificar uma possível solução em tempo polinomial.

O problema da mochila é um um problema originalmente de otimização. Então aqui a gente coloca problema da mochila de decisão. Conjunto independente também é um problema originalmente de otimização.

Então a versão de decisão NP completo, o clique de decisão, mesma questão, cicloano, que já é um problema de decisão, então ele já é NP completo. Cacheiro viajante versão decisão, né? e o TRAT, que já é um problema de decisão.

Então aqui tem alguns exemplos, né, de alguns problemas que foram mencionados na disciplina. Depois aqui eu peço para vocês marcarem a alternativa incorreta, né? Então ali diz assim: "Dado os três problemas A, B e C, sendo que A pertence a NP completo, sem qualquer informação adicional sobre B e C, se A tem uma redução em tempo polinomial para B e B tem uma redução em tempo polinomial para C, então podemos afirmar que C é NP completo.

Não. Por que que tá errado, pessoal? Porque a redução entre os problemas, ela nos permite afirmar que um problema é NP difícil.

Para ele ser NP completo, eu precisaria ter, além da verifica da redução em tempo polinomial a partir de um problema já provado difícil que tem nesse texto, eu precisaria informações de que a verificação do problema pode ser feita em tempo polinomial. Então eu peço ali para justificar a resposta, né? O que que seria uma justificativa?

Ah, essa é incorreta, porque eu posso apenas afirmar que o problema NP é difícil ou está incorreto, porque para afirmar que é um problema NP completo, eu precisaria também eh eu precisaria também da informação se o problema pode ser verificado em tempo polinomial, certo? As demais estão corretas, né? é o teorema de Q que estabelece que SAT é um problema NP completo.

Primeiro problema provado NP completo, né? Dado um problema NP completo conhecido A, se A reduz a B em tempo polinomial, então B é NP difícil. Exatamente o que eu disse.

Se um problema conhecidamente difícil, a gente mostra que qualquer instância dele pode virar uma instância do nosso problema, sínica que o nosso problema é pelo menos tão difícil quanto aquele outro. Pode ser inclusive mais difícil. Isso prova apenas de que o problema é NP difícil, certo?

Aí o limite superior da complexidade de um problema refere-se à complexidade do melhor algoritmo conhecido que o resolve, correto? E até hoje nunca foi apresentada uma verificação polinomial para o problema de otimização do cacheiro viajante. Isso é muito simples de entender, pessoal.

um problema que é difícil de se resolver quando tu pede a verificação se ele é um problema de otimização que tu quer o maior, o menor, o melhor, na decisão, no na no algoritmo de verificação, tu recebe como entrada a possível solução e a instância do problema, né, para verificar se aquela possível solução é válida para aquela instância num problema de otimização, tu teria que verificar que essa é a melhor solução. E para verificar que ela é a melhor solução, tu teria que resolver o problema. Então, por isso que os problemas difíceis de otimização, eles não pertencem à classe NP e são apenas NP difíceis, não completos.

Já a versão de decisão desse problema, ele é NP completo, porque a versão de decisão muda um pouco, né? Por exemplo, o cacheiro viajante, tu quer eh o menor caminho que passe por todas as cidades, exatamente uma vez e retorne à mesma cidade, eh o menor caminho, né, ou o melhor caminho do cacheiro viajante, que é o menor. Na versão de decisão, a pergunta é: existe um caminho de cacheira viajante de tamanho menor ou igual a K?

Aí isso tu consegue responder, porque é só tu verificar se é um caminho válido e ver o custo e testar se ele é menor que K. Aí tu consegue responder sim ou não em tempo polinomial, certo? Bom, vamos seguir marcar a incorreta de novo.

E a incorreta é existe na literatura uma redução polinomial do problema de decisão eh do problema de cobertura de vertice ao problema da árvore geradora mínima. Por que que é fácil de perceber que essa é incorreta? A árvore geradora mínima, a gente viu um algoritmo guloso que resolve o problema em tempo polinomial.

Se existisse uma redução da cobertura de vértices pro problema da árvore geradora mínima, eu estaria dizendo que a cobertura de vértice, qualquer instância vira alguma instância da cobertura mínima. Ã, desculpa, a cobertura diversa vira alguma instância da árvore geradora mínima. Como consigo resolver assim ter um polinomial?

significaria que eu conseguiria resolver o problema da cobertura de vértices em tempo polinomial. Como existe aquela sequência de reduções a partir de todos os problemas da classe NP viraram viram instâncias do problema SAT. Do SAT, qualquer instância SAT vira uma instância trs sat.

do tressat, qualquer instância tressat vira um problema da cobertura de vértices. E da cobertura de vértices, se eu conseguisse virar tudo instâncias da de um problema que é resolvido em tempo polinomial e as reduções são todas polinomiais, a classe P seria igual a NP. Porque qualquer problema NP eu transformaria no sák, transformaria no tress, que transformaria na cobertura diversa e transformaria nesse problema, né, que é resolvido em tempo polinomial.

Então todos os problemas seriam resolvidos na polinomial. Isso não é verdade, né? Então é bem fácil ver que isso não tá correto.

As demais a classes que estão corretas, a classe NP é composta pelos problemas que são verificáveis em tempo polinomial. Sim. Qualquer problema da classe P também tá na classe NP.

Sim, porque P é um subconjunto de NP. Qual que é o problema da classe NP completo? Também está na classe NP?

Sim, porque para ser NP completo tem que ser NP e tem que ser NP difícil. Se qualquer problema da classe NP completa puder ser resolvido em tempo polinomial, então todos da classe NP completo podem ser resolvidos em tempo polinomial. Sim, na verdade todos da classe NP poderiam, né, que inclui todos da classe CNP completo.

A próxima incorreta, todos os problemas da classe NP difícil também estão na classe NP completo. Falso. Por quê?

Justamente pelo que eu expliquei, eh tem problemas de otimização que são NP difíceis. E esses problemas não têm como ser verificados em tempo polinomial. As demais que estão corretas.

Segundo a literatura da área, o problema da satisfabilidade de cláusula boliana foi o primeiro problema da classe provada NP completo, um teorema de Cook, correto? Um problema A pertencente à classe NP, se ele possui um algoritmo de verificação em tempo polinomial, correto? Se A pode ser reduzido a B em tempo polinomial, então qualquer instância de A pode ser transformada numa instância de B.

Exatamente. Então, B é pelo menos tão difícil como A, quanto A. Então, é como se para resolver B eu tivesse que resolver A.

Se A é provado difícil, B também é difícil. Todo e qualquer problema NP completo pode ser verificado em tempo polinomial. Sim, porque NP completo implica em ser NP.

Se tu é NP, tu eh pode ser verificado em tempo polinomial. Depois pedia na questão cinco para enunciar a versão de decisão e de otimização, quando o problema for originalmente de otimização de uma série de problemas e dizer a que classe eles pertencem. Então aqui eu fiz uma divisão por classe, tá?

A classe P, a classe dos problemas podem ser resolvidos em tempo polinomial. O dois sat já é um problema de decisão. O círculo também.

Árvore de dura mínima é um exemplo de problema de otimização que é fácil. Então, a versão de otimização dele é fácil e é possível resolver em ter um polinomial. E aqui tem a versão de otimização de decisão.

Depois eu coloquei os problemas que pertencem à classe NP difícil ou NP completo. E coloquei ali a observação, ó, os problemas abaixos, né? Ele ele pertence à classe NP eh completo quando o problema for de decisão e NP difícil quando ele for de otimização.

Só tem versão decisão, NP completo. Cacheiro viajante otimização, NP difícil. Cachiro viajante, decisão, NP completo.

Cobertura de vértices, o clique também a versão de otimização NP difícil, versão de decisão, NP completo. O cicloano e o Tressat já são problemas de decisão, então eles são NP completos. Depois tem uma pergunta, dado um problema aqui, a que classe ele pertence?

Se ele possui um algoritmo polinomial que o resolve, pertence à classe P. Eh, depois ali de novo marcar em incorreta. Vamos ver o que que tem de errado nessa aqui.

Considere um problema A tal que A pode ser reduzido a B para um problema B pertencente à classe NP completo. Então, podemos concluir que A pertence a NP difícil, independente de ser ou não verificado em tempo polinomial. Isso aqui pode causar, hum, acho que é isso aí, né?

Porque eu só posso afirmar que é NP difícil ou não se tem a redução. Beleza? Mas tem uma questão aqui que tá muito errada.

Eu tenho que fazer redução de um problema difícil para o meu problema. Aqui eu tô dizendo que eu tô reduzindo um outro problema A para um problema difícil. Só que isso pode ser a parte fácil do problema difícil, entendeu?

Eu tô dizendo que o A é um pedacinho do B e que o B é difícil. Só que eu não posso não não posso afirmar que aquele pedacinho do B, o A, que esse pedacinho do B específico que é o A, que é a parte difícil do B, pode ser a parte fácil do B, tá? Então assim, para poder provar que um problema é NP difícil, tu tem que pegar um já provado difícil e mostrar que ele tá dentro desse meu problema que eu quero provar se é difícil, porque daí o meu é pelo menos tão difícil quanto ele.

As demais estão corretas, né? Então, considere um problema dado um conjunto de pontos e a distância entre cada parte de pontos encontre o menor ciclo que parta de um ponto aleatório qualquer, passe por todos os demais e retorne ao ponto de partida. E esse problema NP é difícil?

Sim, é o problema do cacharo viajante. A classe de problemas NP completo é formada pela interseção da classe NP e NP difícil. Sim, né?

Tem que ser NP e tem que ser NP difícil. quando tu é as duas coisas t NP completo. Se a versão de decisão do problema de cobertura de vértice pudesse resolvida em tempo polinomial, então P é igual a NP, correto?

Né? Então é o que eu expliquei por causa daquela sequência de reduções, né? Todos da classe NP poderiam ir fazendo as reduções polinomiais até chegar nesse que agora foi provado eh resolvido em tempo polinomial.

E depois tem ali, né, meio repetido, mas tem ali embaixo, ó, a versão correta daquela afirmação que aparece algumas vezes, né? Então, dados três problemas A, B e C, sendo que A é difícil, a NP, né? O A é NP completo.

Sem qualquer informação sobre B e C, se esse problema é difícil, A pode ser reduzido ao problema B em polinomial e B pode ser reduzido a Copinomial. Então, eu posso afirmar que o CNP é difícil. Depois tem aqui uma questão, deixa eu ver, é a última de marcar verdadeira ou falso, tá?

Então, todo problema NP completo é NP difícil. Sim, esse é um pré-requisito tu ser para tu ser NP completo é tu ser NP difícil. Todo problema NP difícil NP completo.

Falso. Por quê? Porque os problemas NP completos são a um subconjunto dos NP difíceis para os quais eu tenho a verificação polinomial, certo?

Nem todos da classe NP difícil tem verificação polinomial. Por exemplo, aqueles de otimização que eu mencionei. Se um problema A possui verificação em tempo dois na N, então posso afirmar que ele pertence à classe NP completo.

Aí tem mais de uma justificativa aqui. Primeiro, somente com a informação da verificação, eu só poderia afirmar alguma coisa quanto a pertenceu ou não na classe NP. Então eu não posso afirmar que é NP completo, porque eu não poderia saber nada sobre NP difícil ou não.

E mesmo informação que foi dada aqui da verificação, tá dizendo que o problema tem uma verificação em tempo exponencial. Então eu não posso ã dizer que ele ele é NP, porque para ser NP tem que ser uma verificação polinomial. A próxima ali é a mesma que eu acabei de ler ali em cima, tá?

H, então tá correta, né? E a próxima. Se Q é um problema NP completo e P, um problema de solução verificável em tempo o de 2 na N log N, se eu tenho uma redução daquele problema Q, que é difícil pro P em tempoinomial, eu posso concluir que PNP é completo.

Aqui tem um detalhe sutil, né? Que que acontece? o eh a parte de afirmar que a NP difícil tá correta.

Eu tenho uma redução de um difícil para ele em tempo polinomial, porém a verificação é em tempo exponencial. Então eu só poderia afirmar que ele é NP difícil pela parte da que fala disso. Eu não posso afirmar que ele é NP, logo.

Eu não posso afirmar aquele NP completo. Depois, se um problema de decisão do cacheiro viajante for resolvido em tempo polinomial, então será possível provar que P é diferente de NP? Não vai ser provar possível provar que P igual NP.

E a última se já há um problema provado NP completo. Se um problema B possui verificação polinomial e uma redução com complexidade 4 na N, então eu posso concluir que NP é completo. Não, também tu poderia afirmar que é NP porque a verificação é polinomial, porém a redução é exponencial.

Então tu não pode afirmar que LP completo. Só poderia afirmar que é NP porque tu não tem a prova de que ele NP difícil. Bom, pessoal, essa lista ela faz um overview assim, né, sobre a parte teórica que a gente viu, sobre os problemas que a gente viu, a que classes eles pertencem, né, e a como provar, então, que um problema NP completo essa classe tão importante que a gente estudou.

Agora eu gostaria de falar um pouco sobre como é que vai ser a prova e como é que vai ser a recuperação para aqueles que ficarem em recuperação. Mas antes de passar para essa parte mais prática, na verdade eu vou perguntar se vocês têm alguma dúvida sobre a matéria. Uma coisa que eu vou mencionar, teve uma aula que foi sobre o primeiro problema NP completo, que é uma aula bem complicada, né, que é como foi é possível transformar qualquer máquina de touring e uma palavra de entrada numa numa instância do problema SAT, né?

H isso vocês não precisam se preocupar em em saber em detalhes como é que funciona. O que vocês precisam é entender a ideia, né? Como todo problema da classe NP pode ser resolvido por uma máquina de tour e não determinística de tempo polinomial.

se eu consigo transformar a a lógica das máquinas de touring em eh e a entrada, né, da palavra em uma instância do problema SAT, eu tô conseguindo eh mostrar como transformar qualquer instância e qualquer máquina, né, de qualquer máquina que resolve qualquer problema numa instância SAT. Então eu tô provando que qualquer problema da classe NP pode ser reduzido ao SAT, né? E e essa aula do primeiro problema NP completo, ela é importante entender isso, né?

E saber então que o primeiro problema eh provado NP completo foi o problema da estabilidade boliana, né? Que esse então foi ã e que depois disso, né? que esse foi o teorema de Cook e que depois disso, no ano seguinte, o Richard Carp começou a usar a seguinte lógica: se todos os problemas reduzem pro SAT, será que eu vou então usar o SAT para provar outros problemas?

E foi assim que ele foi encadeando a essa essas reduções entre os problemas, né? E provou diversos problemas como sendo NP complexos. Ã, mas de resto os demais slides, né?

A primeira aula ali, ela dá um overview sobre toda a matéria e depois a terceira aula ela fala sobre essas reduções entre problemas, né? Como é que funcionou as como é que funcionava essas reduções e e a diversos exemplos. Então, essa terceira área de todas, eu acho que é a mais hã tranquila no sentido de que tu tem menos cálculos para fazer, né?

é é mais teórica. Claro que se eu pedisse para vocês provarem um problema NP completo, vocês teriam que fazer um algoritmo de verificação em tempo polinomial. Então vocês precisariam conseguir eh eh fazer o pseudo código e fazer o cálculo da complexidade, mostrando que ele é polinomial.

Depois precisaria mostrar, explicar um problema já provado NP completo e mostrar que qualquer instância desse problema vira uma instância do outro através de um algoritmo de redução, onde tu tem entrada uma instância de um problema e a saída instância do outro e calcular a complexidade detalhada e mostrar que aquilo é polinomial para provar que um problema é NP completo, né? Mas eh na disciplina aqui eu já demonstrei para vocês as reduções, né? É uma coisa que vocês vão ter que hã que provar, né?

Eu já mostrei as provas para vocês. Bom, nós temos uma dúvida aqui. Precisa saber demonstrar as reduções?

Ã, não detalhadamente, mas tem que saber que as reduções existem. Talvez que um problema é reduzido a eh que existe a redução de um problema X para um problema Y, né? Mas detalhes das reduções ã eu não vou cobrar.

De qualquer forma, durante a prova vocês vão ter acesso ao moodle, né? Então, eh, vocês vão poder consultar o material sobre a prova, se é só sobre a área três, majoritariamente, né? Ã, pode ter alguma pergunta relacionada ao que foi visto nas demais áreas, mas o grande enfoque é na área três, tá?

Então assim, e é focado em classe de problemas, mas por que que essa parte tá na disciplina, né? Porque, por exemplo, o problema da mochila, o problema da mochila, ele tem um a mochila fracionária que tu consegue resolver em tempo polinomial com um algoritmo guloso. Mochila binária, tu consegue resolver através de um algoritmo de programação dinâmica de tempo pseudo polinomial, ou seja, não é polinomial, é um exponencial mais fácil, digamos assim.

E existe como fazer, como foi visto, tem a prova de que o problema da mochila pertence à classe NP completo, versão de decisão, versão de otimização, NP difícil. Então, coisas assim estão relacionadas a a tudo que a gente viu na disciplina, né? Mas o enfoque vai ser na área três.

O tipo de prova vai ser que nem a as listas de exercícios, é a múltipla escolha. Eh, lá no dia vocês vão fazer três provas, né, no Então, a o questionário ele vai ficar aberto no período de 3 horas, mas no momento em que vocês ingressarem no questionário, vocês têm uma hora para resolver. Isso foi conversado com a Congrade, tá?

Então, não é possível deixar mais tempo aberto porque tu estaria ocupando tempo das outras disciplinas. Então, para ser uma coisa uniforme, eh, foi decidido que vai ser dessa forma. Certo.

Quatro. Eh, são quatro provas. complexidade não foi.

Eu vou até confirmar aqui. ele e a gente teve uma reunião de todos os professores que que ministr acho aqui o WhatsApp para E a gente teve uma reunião, os três professores, das três provas e a prova vai das 9 ao meio-dia. Eu vou questionar, tá?

E se houver eh a confirmação disso, eu abro o questionário por 4 horas e tal. Mas eh eu eu não sei eh a gente teve a reunião e foi essa a orientação que passaram. É o professor isso é para todos, será?

Ou se é só para ti, hein? Ou talvez ele se reun estranho. Tá, eu tô mandando aqui.

Sim. é múltipla escolha no sentido que tu vai escolher uma delas, né? Eh, [Música] não é, a professora tá dizendo que sim, que são são que a que ela tem duas disciplinas, mas eu vou até olhar porque Deixa eu ver se ele mandou aqui.

Ele falou na reunião, tá? Então vamos aguardar, mas ele confirmando eu abro o questionário pelo período que ele me me confirmar. Eu tô confusa aqui.

Deixa eu ver o que que eu botei lá no questionário. Depois eu vou parar aqui de compartilhar a tela com vocês, porque a gente já falou sobre essa parte. Vou tentar acessar o Moodle para verificar essa questão.

Daqui a pouco eu tô equivocada e já tá tudo configurado certinho, mas eu saí pensando. Deixa eu ver. Meio dia até tá até o meio-dia.

Pois é. Eu acho que teve alguma coisa que se Então o que tá marcado com vocês é até a uma. Sim.

Tá. E eu já vou alterar isso agora e depois confirmo ali com ele. Mas é, tá até o meio-dia.

Vamos botar até às 13, então. Tá, obrigado por terem avisado. Eh, na reunião a gente tava em três professores e falou em em nove ao meio-dia, que seriam três provas e tal, que no outro semestre eram quatro, enfim.

Mas acho que foi um equívoco, mas tá resolvido já. Então vai ficar aberto das 9 a 1 e vocês vão ter uma hora para resolver no momento que vocês ingressarem na prova. E a prova vai ser estilo as listas de exercícios.

Então, eh, vocês vão vai ter um enunciado e aí vão ter as opções, vocês escolhem uma, tá? Acho que são 10 questões, tá bem tranquilo de fazer nesse tempo. Mais alguma dúvida, pessoal?

Não, eu não tenho isso, mas essa lista de exercício, por exemplo, que eu corrigi hoje, ela é bem bem tranquila assim para vocês usarem como como material de preparação, ouvir de novo as aulas, né? Eh, por questões de tempo, eu diria, por exemplo, que eu vi aquela aula sobre o primeiro problema NP completo. Se tiver que não ouvir uma, não ouvir aquela, no sentido de que vocês têm que ter a ideia mais geral e ela é bem detalhada, né?

Hã, eu vou compartilhar de novo com vocês aqui para mostrar o plano de ensino, pra gente falar um pouco sobre a recuperação. Talvez não seja necessário, né? Mas caso seja necessário, o que tem definido no como recuperação é que quem ficar abaixo de seis vai ter que realizar uma atividade de recuperação, tá?

Então essa atividade de recuperação eu vou definir ainda como será, se vai ser um outro questionário, eh se vai ser um trabalho, né? Mas não vai ser prova presencial. Tá?

Eu não sei se outros professores já mencionaram isso para vocês. Eh, e aí, claro, quem fizer a recuperação, mesmo que tire 10, vai ficar no máximo com conceito C, OK? Acima de seis, 60% tem que acertar para passar.

Mas muitos estão super bem de nota e e essa parte da disciplina de todas, eu imagino que para vocês deve ter sido a mais tranquila, né? Porque é mais teórica, né? Ã, então eu acho que vocês não vão ter problema.

Ã, mais alguma dúvida, pessoal? O peso da prova é 50%. Sim, aqui, ó, no plano de ensino, opa, se vocês forem ver, ó, é 025 o questionário 1, 025 o questionário 2 e 05 a prova.

Mais alguma dúvida, pessoal? acontece. Oi, acho que aconteceu alguma coisa.

Eu caí, mas voltei.