Projeto e Análise de Algoritmos Lista 3

• Etapa 1 (Subestrutura de uma parentização ótima): para realizar a parentização ótima é necessário dividir a estrutura A em duas, a primeira parte vai de \(A_{i}...A_{k}\) e \(A_{k+1}...A_{j}\). Desta forma \(A_{i}...A_{k}\) e \(A_{k+1}...A_{j}\) ambas precisam serem ótimas para que \(A_{i}...A_{j}\) seja ótima.

• Etapa 2 (Solução recursiva): Seja m[i,j] o número mínimo de multiplicações escalares necessárias para calcular a matriz \(A_{i}...A_{j}\) (completa); o custo mínimo para calcular \(A_{1}...A_{n}\), seria, portanto, m[1, n]. Podemos definir m[i,j] recursivamente da maneira descrita a seguir:

  Se i = j, o subproblema é trivial, ou seja, não terá outra matriz para multiplicar a atual. Para obter a parentização ótima, é necessário termos que i < j. Assim podemos separar o produto, onde i <= k < j. Além disso, m[i,j] é igual ao custo mínimo para calcular os subprodutos \(A_{i}...A_{k}\) e \(A_{k+1}...A{j}\), somado com o custo de multiplicar essas duas matrizes.

  Dada a fórmula:

  

  Temos como caso base i = j e como caso recursivo i < j. Sabendo que m[i,j] deve armazenar o número mínimo de multiplicações, então em m[i,k] teremos o custo do cálculo das multiplicações de \(A_{i}...A_{k}\); en m[i,k] teremos o custo do cálculo das multiplicações de \(A_{k+1}...A_{j}\). \(P_{i-1}P_{k}P_{j}\) é o custo da multiplicação entre as duas matrizes \(A_{i}...A_{k}\) e \(A_{k+1}...A_{j}\), resultando no custo final pela soma total de \(A_{i}...A_{j}\).

• Etapa 3 (Cálculo dos custos ótimos): Teremos um vetor auxiliar para guardar as dimensões das matrizes, esse vetor possui n+1 posições indo de p[0..n]. Uma matriz \(A_{i}\) tem dimensão \(P_{i-1} \cdot P_{i}\). Além de um vetor auxiliar, teremos duas matrizes auxiliares: m[1..n, 1..n] para armazenar os custos de m[i,j] e s[1..n-1, 2..n] para armazenar o valor de k para obter o custo ótimo de m[i,j].

• Etapa 4 (Construção de uma solução ótima):

• Etapa 1 (Subestrutura de uma parentização ótima): sejam as sequências \(X = <x_{1}, x_{2}, ..., x_{m}>\) e \(Y = <y_{1}, y_{2}, ..., y_{n}>\) e seja \(Z = <z_{1}, z_{2}, ..., z_{l}>\) qualquer LCS de X e Y. As sequências são verificadas de trás para frente, do final para o início, assim:
  • 1) Se \(x_{m} = y_{n}\), então \(z_{l} = x_{m} = y_{n}\) e \(z_{l-1}\) será a LCS entre \(X_{m-1}\) e \(Y_{n-1}\). Então, o último caractere de X e Y faz parte da solução Z. portanto será reduzido em uma unidade.
  • 2) Se \(x_{m} \neq y_{n}\) e \(z_{l} \neq x_{m}\), então Z é uma LCS de \(X_{m-1}\) e Y. O \(z_{l}\) é diferente de \(x_{m}\), porém, ele pode ser igual ao \(y_{n}\). Assim, decrementamos o X para verificar se existe algum valor de X igual a Y para cair no caso (1).
  • 3) Se \(x_{m} \neq y_{n}\) e \(z_{l} \neq y_{n}\), então Z é uma LCS de X e \(Y_{n-1}\) realizando o processo inverso descrito no caso (2).

• Etapa 2 (Solução recursiva): Podemos expressar o comprimento de uma LCS por: O caso base é quando não possui letras na sequência, sendo assim, i = 0 ou j = 0 retornando 0. Se i,j > 0 e \(`x_{i} = y_{j}\), então é armazenado o comprimento da resposta na posição c[i-1,j-1] + 1. Se i,j > 0 e \(x_{i} \neq y_{j}\), então armazenamos o maior comprimento entre c[i,j-1] e c[i-1,j].

• Etapa 3 (Cálculo dos custos ótimos): Considerando duas sequências de caracteres X e Y, utilizaremos duas tabelas: c[1…m, 1…n] para guardar os valores de c[i,j] dado que c[i,j] é responsável por armazenar o maior comprimento da sequência. e b[1…m,1…n] onde b[i,j] aponta para a entrada da tabela correspondente à solução ótima do subproblema, em outras palavras, ele guarda uma “seta” que irá nos guiar pela matriz b e mostrará quais são as letras que formará a solução.

• Etapa 4 (Construção de uma solução ótima): Começamos em b[m,n] a percorrer a matriz seguindo as setas, sempre que encontrarmos a seta para diagonal na entrada b[i,j] ela implica que \(x_{i} = x_{j}\) do qual é um elemento da LCS. Os elementos da LCS são encontrados em ordem inversa por esse método.

Suponha que tenhamos um conjunto \(S = {a_{1},a_{2},...,a_{n}}\) de n atividades propostas que desejam usar um recurso (ex.: uma sala) que só pode ser utilizado por uma única atividade por vez. Cada atividade \(a_{i}\) tem um tempo de início \(s_{i}\) e um tempo de término \(f_{i}\), onde 0 <= si < fi < infinito. Se selecionada, a atividade \(a_{i}\) ocorre durante o intervalo de tempo meio aberto \([s_{i}, f_{i})\). As atividades \(a_{i}\) e \(a_{j}\) são compatíveis se os intervalos \([s_{i}, f_{i})\) e \([s_{j}, f_{j})\) não se sobrepõem. Isto é, \(a_{i}\) e \(a_{j}\) são compatíveis se \(s_{i}\) > \(f_{j}\) e \(s_{j}\) >= \(f_{i}\).

• Matriz de adjacências:

typedef struct grafo {
  int V;
  int E ;
  int **adj;   
} Grafo;

• Lista de adjacências:

typedef struct vertice {
  int no;
  struct vertice *prox;
} Vertice;


typedef struct grafo {
  int V;
  int E;
  Vertice *adj;
} Grafo;

Qualquer subárvore de uma MST também é uma MST.

• 1) Escolher um vértice arbitrário e inicializar a MST como vazia e o conjunto de vértices visitados contendo apenas o vértice inicial.
• 2) Enquanto a MST não conter todos os vértices do grafo, selecione a aresta de menor custo que conecta um vértice a um vértice não visitado e adicione na MST. Essa aresta de menor custo, também conhecida como aresta leve, é dada pela técnica do corte, também visando não formar ciclos.
• 3) Repetir o passo (2) até que a MST contenha todos os vértices do grafo.
• 4) Retorna a saída da MST.

Começamos mostrando que T não possui ciclos, assim, basta mostrar que nenhuma aresta escolhida pelo algoritmo forma um ciclo. Note que, se começarmos a percorrer o ciclo C cada vez que passamos por uma das arestas que atravessa o corte, nós mudamos de parte, e só nesse caso mudamos de parte. Ao definir o corte, separamos o grafo em duas partes: os vértices e arestas que estão dentro do corte dos que não estão. Assim, após atravessarmos o corte C um número impar de vezes, estamos numa parte diferente da que começamos. Como um ciclo tem que fechar, precisamos atravessar um número par de arestas para voltar ao começo.

• Corolário - Aresta Solitária: Se E é uma única aresta atravessando um certo corte, então não pode pertencer a um ciclo.
• Lema - Travessia Par: Se um corte (A, B) atravessa um ciclo C qualquer, então C tem um número par de arestas atravessando o corte. Então, se E estivesse em um ciclo, pelo lema, ao menos mais uma aresta também precisaria atravessar o corte (A,B).

Agora, mostraremos que T é geradora e alcança todos os vértices de G.

• Lema: Arestas na Fronteira: Um grafo não é conexo se e somente se existe um corte (A, B) que não é atravessado por arestas.
• Lema: Corte Vazio: Um grafo é conexo se e somente se não existir um corte vazio em G.

Prova(Volta): Com base no lema de arestas na fronteira e supondo que existe um corte (A,B) sem arestas, tal que \(u \epsilon A\) e \(v \epsilon B\). Basta verificar que não existe caminho de u até V, caso contrário, teriamos uma aresta atravessando (A,B), portanto o grafo é desconexo.

Prova(Ida): Com base no lema de arestas na fronteira e supondo que o grafo não é conexo. Seja A o conjunto de todos os vértices alcançados a partir de V. Seja B = V \ A. Note que \(u \epsilon B\) (não existe caminho entre u e V para ser alcançado). Assim (A,B) é um corte sem arestas cruzando sua fronteira. Sabendo que G=(V,E) é conexo usando o lema do corte vazio, concluímos que ele não possui qualquer corte (A,B) sem arestas. Portanto, o algoritmo nunca vai parar no meio de uma iteração.

Assim, mostramos que T tem custo mínimo pela propriedade do corte, pois, toda aresta escolhida pelo algoritmo é a mais barata de um corte e, pela propriedade, ela deve estar na MST.

• 1) Seleciona o menor valor do grafo e o armazena no conjunto de soluções.
• 2) Busca pelos menores valores que não estão no conjunto de soluções, ou seja, as arestas que não foram verificadas e verifica se não formam ciclo. Se não tiver ciclo e buscar o menor valor então a aresta é adicionada no conjunto de soluções.
• 3) Repetir o passo 2 até alcançar todos os vértices.
• 4) Retorna a saída da MST.

A entrada do algoritmo de Dijkstra é um grafo ponderado com um vértice inicial especificado. O grafo é representado por uma matriz de adjacência, onde cada entrada indica o peso da aresta entre dois vértices. O vértice inicial é especificado como um inteiro que representa o seu índice na matriz de adjacência.

A saída do algoritmo de Dijkstra é uma lista de vértices que representa o caminho mais curto do vértice inicial a todos os outros vértices do grafo.

• 1) Inicialização: atribui 0 a origem e cria o conjunto de vértices vazio.
• 2) Seleção do nó não visitado com a menor distância e atualização dos valores
• 3) Repetir o passo 2 até alcançar o nó objetivo.

• Classe P: Problemas que podem ser resolvidos em tempo polinomial.
• Classe NP: Problema que são verificaveis em tempo polinomial. Qualquer problema P está em NP, visto que, se um problema está em P, podemos resolvê-lo em tempo polinomial mesmo sem ter certificado. Os problemas da classe NP não possuem solução P.
• Classe NP-Completo: Iguais ao NP, porém, todos os problemas NP podem ser reduzidos a eles.
• NP-Difícil: Todos os problemas NP-Completo podem ser reduzidos a ele, porém, sem verificação em tempo polinomial.
• Circuito Hamiltoniano: O problerma do circuito hamiltoniano é um problema relacionado aos caminhos hamiltonianos em grafos. Um caminho hamiltoniano é um caminho que permite passar por todos vértices de um grafo G, não repetindo nenhum, ou seja, passar por todas uma só vez. O objetivo é encontrar um ciclo hamiltoniano, que é um ciclo que visita cada vértice exatamente uma vez, exceto o início e o fim.
• Reduções: As reduções são usadas para transformar um problema em outro problema, da forma que a solução do segundo problema possa ser usada para resolver o primeiro.

\(SAT \alpha CLIQUE\)

Satisfabilidade: Dada uma fórmula booleana, existe uma atribuição de valores às suas variáveis que a torne verdadeira. A formula deve estar na forma normal conjuntiva ou disjuntiva - clausulas definidas apenas com o operador \(\wedge\) e \(\vee\).

Ex.: Existe uma combinação de valores booleanos para que \(x_{1}, x_{2}, x_{3}\) na expressão \((x_{1} \vee \sim x_{2}) \wedge (x_{1} \vee x_{3}) \wedge (\sim x_{1} \vee x_{2})\) seja verdadeira?

A ideia é construir um grafo a partir da formula booleana em tempo polinomial tal que: \(instância_{A} \rightarrow instância_{B}\). Seja K o número de cláusulas (expressões entre parênteses), para cada elemento na fórmula (qualquer \(x_{i}\) ou \(\sim x_{i}\)) crie um vértice (se o mesmo elemento aparecer mais de uma vez, cada cópia resulta em um vértice).

Para cada par de elementos em clausulas diferentes que podem ser verdadeiras ao mesmo tempo, adicionamos uma aresta a eles. Assim:

SAT: \(x_{1} \wedge (\sim x_{1} \vee x_{2} \vee \sim x_{3}) \wedge x_{3}\)

Passos do CLIQUE:

• 1) Adicionar a quantidade de vértices relacionadas a quantidade de variáveis da fórmula (pondendo repetir). No caso temos \(x_{1}, \sim x_{1}, x_{2}, \sim x_{3}, x_{3}\) totalizando 5 vértices.

• 2) Em seguida, adicionamos uma aresta nos vértices que podem ser verdadeiros entre si para cada um dos vértices da fórmula e para cada cláusula, ou seja, adicionamos arestas nos vértices que não formam uma contradição, aplicando em cada cláusula, como é o caso de \(\sim x_{1} \wedge x_{1}\) (é contradição com a variável sendo comparada com ela mesma só que negada).

No exemplo acima, \(x_{2}\) não é comparado com \(\sim x_{3}\) pois eles pertencem a mesma cláusula, a comparação deve ser feita em cláusulas diferentes.

Com isso, podemos nos pertguntas: toda resposta no CLIQUE é verdadeira no SAT e toda resposta falsa no CLIQUE também é falsa no SAT? No exemplo acima dado o número de cláusulas K=3, podemos afimar que como o SAT é NP-Completo o CLIQUE também é.

\(Ciclo Hamiltoniano (CH) \alpha TSP\)

O caixeiro viajante é um problema que tenta determinar a menor rota para percorrer uma série de cidades visitadas uma única vez cada uma.

Considere o grafo G=(V,E) sendo uma instância do CH, nós precisamos construir então uma instância do TSP a partir dele.

Temos então um caminho hamiltoniano h = 1->2->3->4->5->1.

Para criar e formar um TSP precisamos construir um grafo completo G’(V,E’).parte

Assim:

Em seguida, definimos uma função C, dada por:

Assim, dado C uma função que mapeia tanto E’ quanto E, mostramos que o grafo G tem um ciclo hamiltoniano se e somente se existe um grafo G’ com peso máximo ‘0’ que é isomorfo a um grafo G. Com isso, pela definição do CH podemos concluir que o TSP é NP-Completo.

\(Cob.Vert. (CV) \alpha Conj.Ind. (CI)\)

Uma cobertura de vértices é o conjunto mínimo de vértices que cobrem todas as arestas do grafo.

Um conjunto independente é um conjunto de vértices que não possui arestas ligando-se diretamente.

No grafo acima, temos que uma das coberturas de vértices é CI = {A,C} e outra CI2 = {D, B}. Também temos como cobertura de vértices CV = {A, E, C} e outra CV2 = {B, D, E}.

Para provar que a CV é NP-Completo primeiro precisamos mostrar que o problema está na classe NP basta apresentar um algoritmo não deterministico que execute em tempo polinomial para resolver o problema. Outra maneira é encontrar um algoritmo determinista polinomial que verifica que uma dada solução é valida. Em seguida precisamos provar que CV está em NP-Completo, basta reduzir um problema existe do conjunto NP-Completo ao problema CV.