\documentclass[10pt]{article}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}

\pagestyle{empty}
\setlength{\textwidth}{16cm}
\setlength{\textheight}{22cm}
\setlength{\oddsidemargin}{0mm}
\setlength{\topmargin}{5mm}

\newcommand{\N}{\mbox{{\bf N}}}
\newcommand{\Z}{\mbox{{\bf Z}}}
\newcommand{\R}{\mbox{{\bf R}}}
\newcommand{\sse}{\Longleftrightarrow}
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
\newcommand{\ceil} [1]{\lceil{#1}\rceil}
\newcommand{\Oh}{\mathrm{O}}
\newcommand{\tdots}{\,.\,.\,} % in place of \ldots
\newcommand{\Ccal}{\mathcal{C}}

\def\risonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\smile$}}}$}}
\def\tristonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\frown$}}}$}}

\begin{document}

\begin{center}
{\large
{\bf 
MAC 5711 - Análise de Algoritmos \\
}
}
{\em Departamento de Ciência da Computação} \\
Segundo semestre de 2018 \\

\vspace{3mm}
{\large
{\bf Lista 7} 
}
\end{center}

\begin{enumerate}

%%% DIJK

    \item %pf
  Seja $s$ um vértice de um digrafo $G$ com custos positivos nos arcos.  Para
  cada vértice $v$ de $G$, seja $v.x$ o custo de \emph{algum} caminho de $s$
  a $v$ em $G$. Escreva um algoritmo eficiente que verifique se $v.x$, para
  todo $v$, é a distância de $s$ a $v$ em $G$. Explique porque seu algoritmo
  está correto.

    \item %pf
  Mostre que o algoritmo de Dijkstra pode produzir resultados errados se o
  digrafo tiver arcos de custo estritamente negativo.

    \item %sedg
  Escreva um algoritmo que recebe conjuntos $S$ e $T$ de vértices de um grafo
  e calcula a distância de $S$ a $T$, ou seja, o custo de um caminho de custo
  mínimo que começa em algum vértice em $S$ e termina em algum vértice em
  $T$. O algoritmo deve consumir o mesmo tempo de execução que o algoritmo de
  Dijkstra. Justifique que seu algoritmo está correto.  \emph{Dica:} Basta
  introduzir pequenas modificações no algoritmo de Dijkstra.

    \item %sedg
  Escreva um algoritmo que encontre um arco cuja remoção causa o maior aumento
  na distância de um vértice $s$ a um vértice $t$.

    \item %CLRS 24.3-3
  Suponha que trocamos a linha 4 do algoritmo do Dijkstra como segue
$$4. \quad \mbox{while} \ |Q| > 1$$ 
Isso faz com que a execução do laço execute $|V|-1$ vezes no lugar de $|V|$
vezes.  Será que o algoritmo continua correto?

  \item %CLRS 24.3-5
Dado um digrafo $G=(V,E)$ em que cada aresta $(u,v) \in E$ tem associado um
valor $r(u,v)$, que é um número real no intervalo $[0,1]$ que representa a
confiança de um canal de comunicação do vértice~$u$ até o vértice
$v$. Interpretamos $r(u,v)$ como a probabilidade de que o canal de $u$ a $v$
não falhe, e supomos que tais probabilidades são independentes. Dê um
algoritmo eficiente (mesmo tempo de execução que o de Dijkstra) que acha um
caminho mais confiável entre dois vértices dados.

  \item %CLRS 24.3-6
Seja $G=(V,E)$ um digrafo com pesos $w: E \rightarrow \{0,1,\ldots,W\}$ para
algum $W$.  Modifique o algoritmo de Dijkstra para que compute os caminhos
mínimos a partir de um vértice $s$ em tempo $\Oh(W|V|+|E|)$.

  \item %CLRS 24.3-7
Seja $G=(V,E)$ um digrafo com pesos inteiros
$w: E \rightarrow \{0,1,\ldots,W\}$ para algum $W$.  Modifique o algoritmo de
Dijkstra para que compute os caminhos mínimos a partir de um vértice $s$ em
tempo $\Oh((|V|+|E|)\lg{W})$. (\emph{Dica:} Quantas estimativas distintas de
caminhos mínimos podem existir em $V-S$ em cada iteração do algoritmo?)

%%% MST INTRO

  \item {\bf (CRLS Ex.~23.1-1)} Seja $e$ uma aresta de custo mínimo em um
grafo $G$ com custos nas arestas.  É verdade que $e$ pertence a alguma MST de
$G$?  É verdade que $e$ pertence a toda MST de $G$?

  \item %pf-sedgewick
Suponha que os custos das arestas de um grafo conexo são distintos dois a dois
(ou seja, não há duas arestas com o mesmo custo). Mostre que o grafo tem uma
única MST.

  \item %pf-sedgewick
Suponha que os custos das arestas de um grafo conexo são distintos dois a
dois. Seja $C$ um ciclo não trivial. É verdade que a aresta de custo mínimo em
$C$ pertence à (única) MST do grafo?


%%% PRIM-KRUSKAL
  \item %pf
Seja $G$ um grafo conexo com custos nas arestas. Uma aresta $e$ de $G$ é
crítica se o aumento do custo de $e$ faz com que o custo de uma MST de $G$
também aumente. Escreva uma função que determine todas as arestas críticas de
$G$ em tempo $\Oh(m\log{n})$

  \item %pf
Mostre que depois de cada execução da linha 6 do algoritmo de Prim tem-se
$u.\mathrm{key} < \infty$

  \item %kl-ta,
Suponha que temos um grafo $G$ com pesos nas arestas.  Verdadeiro ou falso:
Para qualquer MST~$T$ de~$G$, existe uma execução válida do algoritmo de
Kruskal que produz $T$ como saída?  Dê uma prova ou um contra-exemplo.

  \item %sd-wy
Seja $G$ um grafo conexo com custos nas arestas e seja $B$ um conjunto de
arestas de $G$.  Suponha que o grafo induzido por $B$ não tem
circuitos. Queremos encontrar uma subárvore geradora de custo mínimo dentre as
que contêm $B$.  Descreva um algoritmo eficiente para resolver o problema.

  \item {\bf (CRLS Ex.~23.2-4,5)} Suponha que todos os pesos num grafo com $n$
vértices são inteiros no intervalo de 1 até $n$.  Descreva como otimizar os
algoritmos de Kruskal e Prim nesta situação. O que acontece se os pesos são
inteiros no intervalo de 1 até $W$, onde esse valor é um inteiro dado, mas
arbitrário?

  \item %kl-ta
Dado um grafo com $n$ vértices, pesos distintos nas arestas, e no máximo $n+8$
arestas, dê um algoritmo com complexidade $\Oh(n)$ para achar uma MST.

\item Uma coleção $\Ccal$ de cláusulas sobre um conjunto $X$ de
  variáveis booleanas é uma \emph{tautologia} se toda atribuição a $X$
  satisfaz $\Ccal$. O problema \textsc{tautologia} consiste em, dado
  $X$ e $\Ccal$, decidir se $\Ccal$ é ou não uma tautologia. O
  problema \textsc{tautologia} está em NP? Está em coNP? Justifique
  suas respostas.
  
\item (difícil) O problema \textsc{2-sat} consiste na restrição de \textsc{sat}
  a instâncias $X$ e $\Ccal$ em que toda cláusula de $\Ccal$ tem
  exatamente dois literais. Mostre que o \textsc{2-sat} está em P, ou
  seja, descreva um algoritmo polinomial que resolva o \textsc{2-sat}.

\item Seja $G=(V,E)$ um grafo. Uma
  \emph{3-coloração} de $G$ é uma função $c:V \rightarrow \{1,2,3\}$ tal que
  $c(u) \neq c(v)$, para toda aresta $uv \in E$.

  Considere o 
\begin{quote}
  {\bf Problema {\sc 3-coloração}:} Dado um grafo, determinar se ele
  tem uma 3-coloração.
\end{quote}

  Mostre que o {\bf {\sc 3-coloração}} está em NP. 


\item Mostre que \textsc{2-coloração} está em P.
\item Mostre que o problema abaixo é NP-completo. 
\begin{quote}
  {\bf Problema {\sc partição}:} Dada uma coleção $S$ de números,
  decidir se existe uma subcoleção $S'$ de $S$ cuja soma é igual a soma dos
  números em $S \setminus S'$, ou seja, $$\sum_{x \in S} x = \sum_{x \not\in S} x.$$
\end{quote}

\item Mostre que o problema abaixo é NP-completo. 
\begin{quote}
  {\bf Problema {\sc mochila}:} Dado um número $W$, um número $V$, um número
  inteiro positivo $n$, uma coleção de números $w_1,\ldots,w_n$, e uma coleção
  de números $v_1,\ldots,v_n$, decidir se existe um subconjunto $S$ de
  $\{1,\ldots,n\}$ tal que $$\sum_{i \in S} w_i \leq W \mbox{\ \ \ e \ \ \ }
                             \sum_{i \in S} v_i \geq V.$$
\end{quote}

\end{enumerate}

\end{document}


%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
