%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Exercícios de MAC430 Algoritmos e Complexidade de Computação       %
% 2o. semestre de 2012                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <2012-10-01 16:57:54 yoshi>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,a4paper,reqno]{amsart}

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

%\usepackage{refcheck}
%\usepackage{srcltx}
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{hyperref}

\let\:=\colon
\let\epsilon=\varepsilon
\let\phi=\varphi
\def\e{{\rm e}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\dim{\mathop{\rm dim}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\im{\mathop{\rm im}\nolimits}
\def\bsigma{\bar\sigma}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
%\let\sim=\thicksim
\def\comp{^{\rm c}}

\def\inR{\mathrel{\in_{\text R}}} 

\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cC{\mathcal C}
\def\cD{\mathcal D}
\def\cE{\mathcal E}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cI{\mathcal I}
\def\cL{\mathcal L}
\def\cP{\mathcal P}
\def\cR{\mathcal R}
\def\cS{\mathcal S}
\def\cZ{\mathcal Z}

\def\barp{{\bar p}}

\def\Ave{\mathop{{\rm Ave}}\nolimits}
\def\Bi{\mathop{{\rm Bi}}\nolimits}
\def\Var{\mathop{{\rm Var}}\nolimits}
\def\Cov{\mathop{{\rm Cov}}\nolimits}
\def\dev{\mathop{{\rm dev}}\nolimits}
\def\og{\mathop{{\rm og}}\nolimits}
\def\diam{\mathop{{\rm diam}}\nolimits}

\def\EE{\mathop{\hbox{\hbox{${\mathbb E}$}}}\nolimits}
\def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits}
\def\FF{\mathop{\hbox{\raise.03ex\hbox{${\mathbb F}$}}}\nolimits}

\def\RP{\mathbf{RP}}
\def\BPP{\mathbf{BPP}}

\def\bfa{\textbf{a}}
\def\bfb{\textbf{b}}
\def\bff{\textbf{f}}
\def\bfx{\textbf{x}}
\def\bfy{\textbf{y}}
\def\bfX{\textbf{X}}
\def\bfdelta{\boldsymbol\delta}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother

\def\datedue#1{$\{$\textsl{Data de entrega}: #1$\}$}
\def\noduedate{$\{$\textsl{Exercício indicado}; \textsl{sem data de entrega}$\}$}
%\def\datedue#1{}
\def\sugestao#1{[\textit{Sugestão.} #1]}
\let\hint\sugestao
\def\observacao#1{[\textit{Observação.} #1]}

\begin{document}
\title[MAC430 Algoritmos e Complexidade]{%
  {\sl Exercícios}\\\medskip
  MAC430 Algoritmos e Complexidade de Computação\\\medskip
  2{\tiny o.} semestre de 2012}  
\date{Versão de \today}
\maketitle
\pagestyle{plain}
\footskip=25pt

\onehalfspace 

\noindent
\textbf{Instruções:}
\bgroup\small
\begin{enumerate}
\item Os problemas e exercícios com data de entrega devem ser
  resolvidos e entregues.  Estes exercícios farão parte de sua
  avaliação.
\item A entrega dos exercícios deve ser feita no começo da aula (as
  datas de entrega serão datas de aula).  

\item O monitor levará em conta não apenas a correção de sua solução,
  mas também a apresentação (soluções mal escritas valerão
  \textit{consideravelmente menos}).

\item Você deve fazer os demais problemas e exercícios, mas não é
  necessário entregar suas soluções.

\item Não deixe de atacar os desafios, mas eles podem resistir às suas
  investidas mais seriamente que os problemas.  

\item A entrega de soluções de problemas e desafios sem data de
  entrega pode contribuir em sua avaliação.

\end{enumerate}
\egroup

\bigskip
\noindent\textbf{Exercícios, problemas e desafios:}
\begin{enumerate}

\item\label{Q:1} Seja~$X$ um conjunto e denotemos
  por~$\cP^{<\infty}(X)$ o conjunto dos subconjuntos finitos de~$X$.
  Seja~$f\:\omega=\{0,1,2,\dots\}\to\cP^{<\infty}(X)$ uma função e
  suponha que, para todo~$n\in\omega$, existe uma
  função~$g_n\:n=\{0,\dots,n-1\}\to X$ tal que
  \begin{enumerate}
  \item[(\textit{a})]$g_n(i)\in f(i)$ para todo~$i\in n$ 
  \end{enumerate}
  e
  \begin{enumerate}
  \item[(\textit{b})]os $g_n(i)$ ($i\in n$) são todos distintos.
  \end{enumerate}
  Prove que existe uma função~$g\:\omega\to X$ tal que
  (\textit{a})~$g(i)\in f(i)$ para todo~$i\in\omega$ e (\textit{b})~os
  $g(i)$ ($i\in\omega$) são todos distintos.  Se removemos a hipótese
  de que~$f(i)$ é finito para todo~$i$, o resultado ainda vale?
  \datedue{7/8/2012}

\item (Problema) Prove a seguinte versão mais geral do
  Exercício~\ref{Q:1}.  Seja~$f\:Y\to\cP^{<\infty}(X)$ uma função e
  suponha que, para todo~$Z\subset Y$ com~$Z$ finito, existe uma
  função~$g_Z\:Z\to X$ tal que
  \begin{enumerate}
  \item[(\textit{a})]$g_Z(i)\in f(i)$ para todo~$i\in Z$ 
  \end{enumerate}
  e
  \begin{enumerate}
  \item[(\textit{b})]os $g_Z(i)$ ($i\in Z$) são todos distintos.
  \end{enumerate}
  Prove que existe uma função~$g\:Y\to X$ tal que
  (\textit{a})~$g(i)\in f(i)$ para todo~$y\in Y$ e (\textit{b})~os
  $g(i)$ ($i\in Y$) são todos distintos.  

\item Suponha que~$X$ e~$Y$ sejam conjuntos e suponha que existam
  funções injetoras~$f\:X\to Y$ e~$g\:Y\to X$.  Prove que existe uma
  bijeção~$h\:X\to Y$.  \datedue{7/8/2012}

\item\label{eq:F_twin} Sejam~$G$ e~$H$ dois grafos.  Suponha que~$G$
  seja isomorfo a um subgrafo de~$H$ e~$H$ seja isomorfo a um subgrafo
  de~$G$.  Mostre que, se os grafos~$G$ e~$H$ são finitos, então~$G$ é
  isomorfo a~$H$.  \datedue{9/8/2012}

\item Mostre que, se omitimos a hipótese de que~$G$ e~$H$ são grafos
  finitos no Exercício~\ref{eq:F_twin}, então a conclusão daquele
  exercício é falsa.  \datedue{9/8/2012}

\item Mostre que a linguagem~$L=\{0^k1^{2k}\:k\in\NN\}$ é
  decidível. \datedue{14/8/2012} 

\item\label{Q:YuVM} Um conjunto~$A\subset\ZZ$ é \textit{diofantino} se
  existe um natural~$n$ e um polinômio com coeficientes
  inteiros~$p(t,x_1,\dots,x_n)$ de~$n+1$ variáveis tal que
  $A=\{a\in\ZZ\:\text{existe }(r_1,\dots,r_n)\in\ZZ^n\text{ tal que
  }p(a,r_1,\dots,r_n)=0\}$.
  \begin{enumerate}
  \item[(\textit{i})]Prove que todo conjunto diofantino é
    Turing-reconhecível. 
  \item[(\textit{ii})]Matijasevi\v c provou que todo conjunto
    Turing-reconhecível~$A\subset\ZZ$ é diofantino.  Use o fato que
    existem conjuntos Turing-reconhecíveis~$A\subset\ZZ$ que não são
    decidíveis para deduzir que a resposta ao 10o.~Problema de Hilbert
    é negativa, isto é, que não existe um algoritmo que, dado um
    natural~$n$ e um polinômio com coeficientes
    inteiros~$q(x_1,\dots,x_n)$ com~$n$ variáveis, decide se
    existe~$(r_1,\dots,r_n)\in\ZZ^n$ tal que~$q(r_1,\dots,r_n)=0$.
  \end{enumerate} \datedue{16/8/2012}

\item(Continuação da Questão~\ref{Q:YuVM}) Seja~$P=\{2,3,5,7,\dots\}$
  o conjunto dos números primos.  Prove que existe um natural~$n$ e um
  polinômio de coeficientes inteiros~$q(x_1,\dots,x_n)$ tal que
  \begin{equation}
    \label{eq:1}
    P=\{q(r_1,\dots,r_n)>0\:(r_1,\dots,r_n)\in\NN^n\}.
  \end{equation}
  Isto é, os valores positivos que~$q$ assume, quando avaliado em
  argumentos naturais, é exatamente o conjunto dos números primos.
  \hint{Use o Teorema de Matijasevi\v c, enunciado na
    Questão~\ref{Q:YuVM}.  Considere o
    polinômio~$q(t,x_1,\dots,x_n)=(t+1)(1-p^2(t,x_1,\dots,x_n))-1$,
    onde~$p(t,x_1,\dots,x_n)$ é o polinômio na definição de conjuntos
    diofantinos.} \datedue{21/8/2012}

\item
  \begin{enumerate}
  \item[(\textit{i})]Elabore o conceito de \textit{máquina de Turing com infinitas
      fitas}.  A função de transição deve ser da forma
    \begin{equation}
      \label{eq:inf-tape-TM}
      \delta\:Q'\times\Gamma^*\to Q\times\Gamma^*\times\{L,R\}^*, 
    \end{equation}
    onde, como de usual, $Q'=Q\setminus\{q_{\rm ac},q_{\rm rej}\}$.
    Seja~$s=\gamma_1\dots\gamma_k\in\Gamma^*$.  O valor
    de~$\delta(q,s)$ diz qual deve ser a transição quando a máquina
    está no estado~$q$ e tem, sob a cabeça da $i$-ésima fita, a
    letra~$\gamma_i$ ($1\leq i\leq k$) e a $j$-ésima fita está vazia
    para todo~$j>k$.  Se~$\delta(q,s)=(q',s',m)$,
    então~$s'=\gamma_1'\dots\gamma_{k'}'$ e~$m=m_1\dots
    m_{k'}\in\{L,R\}^{k'}$ para algum~$k'\geq k$, a letra~$\gamma_i'$
    deve ser escrita na $i$-ésima fita, e a cabeça da $i$-ésima fita
    deve ser movida de acordo com~$m_i$ ($1\leq i\leq k'$).  Para
    responder essa questão, basta dizer sucintamente os detalhes que
    faltam ser especificados.
  \item[(\textit{ii})]Suas máquinas com infinitas fitas são
    equivalentes às MTs usuais?  (Naturalmente, prove sua afirmação.)
  \end{enumerate} \datedue{23/8/2012}

\item Considere o seguinte algoritmo não-determinístico (que aceita
  toda entrada).  {\singlespace\small\vspace{-3\jot}
  \begin{align*}
    A &= \text{``Dada entrada~$v\in\Sigma^*$:}\\
    &\qquad\qquad\text{\llap{\textbf{1.}}
      Mova a cabeça até encontrar um branco.}\\
    &\qquad\qquad\text{\llap{\textbf{2.}}
      Escolha, não-deterministicamente, uma palavra~$w\in\Sigma^*$ e
      escreva~$w$ na fita,}\\
    &\qquad\qquad\text{ imediatamente após~$v$.}\\
    &\qquad\qquad\text{\llap{\textbf{3.}}
      Aceite~$v$.''}\\
  \end{align*}
  }
  \begin{enumerate}\vspace{-3\jot}
  \item[(\textit{i})]O algoritmo~$A$ sempre pára?
  \item[(\textit{ii})]Defina uma máquina de Turing
    não-determinística~$N$ que executa~$A$.
  \item[(\textit{iii})]Sua máquina~$N$ sempre pára?  Isto é, é verdade
    que, para qualquer entrada~$v$, toda computação de~$N$ é finita?
  \item[(\textit{iv})]Sua resposta para~(\textit{iii}) depende de~$N$?
    Ou todas as máquinas~$N$ que executam~$A$ têm o mesmo
    comportamento?  (Como sempre, justifique sua resposta.)
  \end{enumerate}\datedue{23/8/2012}

\item Prove que a coleção das linguagens decidíveis é fechada pelas
  operações de (\textit{i})~união, (\textit{ii})~concatenação,
  (\textit{iii})~estrela, (\textit{iv})~complementação,
  (\textit{v})~interseção.  \noduedate

\item Prove que a coleção das linguagens Turing-reconhecíveis é
  fechada pelas operações de (\textit{i})~união,
  (\textit{ii})~concatenação, (\textit{iii})~estrela,
  (\textit{iv})~interseção, (\textit{v})~homomorfismo.  \noduedate

\item Seja~$\Sigma$ um alfabeto fixo, com as letras totalmente
  ordenadas por uma relação de ordem dada (por exemplo,
  $\Sigma=\{0,1\}$, com~$0<1$).  A \textit{ordem militar}
  em~$\Sigma^*$ ordena as palavras em~$\Sigma^*$ primeiro por
  comprimento e depois pela ordem lexicográfica induzida pela ordem
  em~$\Sigma$.  Prove que~$L\subset\Sigma$ é decidível se e só se
  existe um enumerador que enumera os membros de~$L$ em ordem militar.
  \noduedate

\item Prove que toda linguagem Turing-reconhecível~$L$ contém uma
  sublinguagem~$L'\subset L$ decidível com infinitas palavras.
  \datedue{30/8/2012} 

\item Seja~$L$ uma linguagem.  Prove que~$L$ é Turing-reconhecível se
  e só se existe uma linguagem decidível~$D$ tal que~$L=\{x\:\text{
    existe~$y$ tal que }(x,y)\in D\}$.  \sugestao{Use máquinas
    não-determinísticas (interprete~$y$ como uma computação de uma
    MTND com entrada~$x$ e~$D$ como uma MT que verifica a correção
    dessa computação).}  \datedue{11/9/2012}

\item Seja~$L$ uma linguagem que consiste de descrições de
  \textit{deciders}: $L=\{\<M_1\>,\<M_2\>,\dots\}$, onde todos
  os~$M_i$ são \textit{deciders}.  Prove que existe uma linguagem
  decidível~$D$ tal que~$D\neq L(M_i)$ para todo~$i$.
  \sugestao{Considere um enumerador para~$L$.}  \datedue{18/9/2012} 

\item Digamos que uma MT~$M$ tem a propriedade~$P$ se o comprimento de
  toda palavra que~$M$ aceita é um número primo.
  Seja~$L=\{\<M\>\:\text{$M$ tem a propriedade~$P$}\}$.
  \begin{enumerate}
  \item[(\textit{i})]Use o teorema de Rice para provar que~$L$ é
    indecidível.
  \item[(\textit{ii})]Dê uma prova direta de que~$L$ é indecidível
    (isto é, sem usar o teorema de Rice).
  \end{enumerate}\datedue{20/9/2012}

\def\leqm{\leq_{\mathrm m}}

\item Seja~$L$ uma linguagem Turing-reconhecível.  Prove que~$L\leqm
  A_{\mathrm{TM}}$.  \noduedate

\def\PCP{\mathop{{\rm PCP}}\nolimits}
\item\label{Q:PCP1} Fixe um alfabeto~$\Sigma$ com~$|\Sigma|\geq2$.
  Para todo inteiro~$k$, seja
  \begin{equation}
    \label{eq:PCP_k}
    \PCP_k=\left\{\left\{{t_1\brack b_1},\dots,{t_n\brack
          b_n}\right\}\in\PCP\:t_i,\,b_i\in\Sigma^*\text{ e }
      |t_i|,\,|b_i|\leq k\text{ para todo }i\right\}. 
  \end{equation}
  Assim, $\PCP_k$ contém as instâncias (positivas) de~$\PCP$ com todas
  as palavras~$t_i$ e~$b_i$ envolvidas de comprimento no máximo~$k$.
  \begin{enumerate}
  \item[(\textit{i})]Prove que~$\PCP_1$ é decidível.
  \item[(\textit{ii})]Prove que~$\PCP_k$ é decidível para
    todo~$k\geq1$.  (Como sempre, justifique sua resposta.)
  \item[(\textit{iii})]Existe uma máquina de Turing~$M$ tal que,
    quando executado com~$k$, tem como saída uma a descrição de uma
    máquina de Turing~$M_k$ que decide~$\PCP_k$?
  \end{enumerate}
  \datedue{4/10/2012}

\item Use a teoria vista em sala para desenvolver um programa em~C que
  imprime uma listagem de si próprio.  Ademais, produza seu programa
  de modo que ele tenha um comprimento, em bytes, que seja ou uma
  potência de~$2$, ou uma potência de~$3$, ou um número primo.
  \datedue{14/12/2012}

\item Escolha um dos problemas do capítulo sobre complexidade de tempo
  do Sipser (Capítulo~7) e resolva.  Escolha um problem
  `interessante'; uma boa escolha será `melhor apreciada'.  Soluções
  pouco originais não valerão muito (isto é, procure escolher
  problemas com soluções não-rotineiras).  Como sempre, não deixe de
  caprichar na escrita de sua solução.  \datedue{14/12/2012}

\item Escolha um dos problemas do capítulo sobre complexidade de
  espaço do Sipser (Capítulo~8) e resolva.  Escolha um problem
  `interessante'; uma boa escolha será `melhor apreciada'. Soluções
  pouco originais não valerão muito (isto é, procure escolher
  problemas com soluções não-rotineiras).  Como sempre, não deixe de
  caprichar na escrita de sua solução.  \datedue{14/12/2012}

\end{enumerate}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% eval: (auto-fill-mode t)
%%% eval: (LaTeX-math-mode)
%%% TeX-master: t
%%% End: