\documentclass[12pt]{amsart}
\usepackage{amsmath}
\usepackage[latin1]{inputenc}
% uncomment next line to get pdf files with hyperlinks
%\usepackage[pdftex,bookmarks=true]{hyperref}

\usepackage{boxedminipage}
\input{defalgo.tex}
\usepackage{program}
\usepackage{epsf}
\input{defcode}
\input{defmath.tex}
\def\cao{\c c\~ao}
\def\cc{\c c}
\def\coes{\c c\~oes}
\def\ii{\'{\i}}
\def\stdin{\emph{stdin}}
\def\stdout{\emph{stdout}}
\def\sqn{seqüência}
\def\ibf#1{\item\textbf{#1}}
\def\clp{\ensuremath{\mathcal{P}}}
\def\clnp{\ensuremath{\mathcal{P}}}
\def\clnpc{\ensuremath{\mathcal{NP}}-complete}
\def\clnph{\ensuremath{\mathcal{NP}}-hard}
\def\clcnp{co-\ensuremath{\mathcal{NP}}}
\def\ta{\emph{Turing accpetable}}
\def\tm{\emph{TM}}
\def\ntm{\emph{NTM}}
\newtheorem{qst}{Questão}
\title{Exercícios: 1}

\author{Raul H.C. Lopes}

\begin{document}

\maketitle
\section{Introdu\cao}
A seguir você encontra  uma série de exercícios que você pode considerar
como ``treino coletivo'' para o grande e definitivo jogo que se aproxima. Você
encontrará aqui exercícios sobre os fundamentos de análise e corre\cao\ de
algoritmos e classes de complexidade. Importante: não existe (como não poderia 
haver)
a pretensão de cobrir tudo o que foi apresentado. Por outro lado, considero que muitos
destes exercícios você já resolveu como parte do seu estudo diário ao
longo do semestre: é até desrespeitoso em rela\cao\ à institui\cao\ em que
você estuda e, portanto, em rela\cao\ a você mesmo assumir que você vá
estudar a matéria toda nas próximas duas semanas. Em rela\cao\ ao grau de
dificuldade, lembre-se: você vai ser um mestre em Ciência da Computa\cao\ e
os alunos de Ciência da Computa\cao\ estudam exatamente esses tópico
em um curso de um semestre e fazem os mesmos trabalhos práticos que
você está fazendo. (Well... pelo menos, quando eu dou a disciplina.)
O que não quer dizer que esta disciplina seja trivial: é difícil. Mas, não 
impossível.

Aliás... Nossa prova fica marcada para o dia 15/04. O horário? Vocês 
determinam. Mas, se demorarem para decidir, eu determinarei. Infelizmente,
compromissos urgentes vão aparecendo.

BTW (ou aliás aliás?), eu não dou mais aulas este semestre.

\subsection{Notação}

  Assuma que:

  \begin{itemize}
    \item \clp, \clnp, \clnpc, \clnph, \clcnp\ denotam as classes de
problemas.
    \item \tm\ abrevia Máquina de Turing determinística.
    \item \ntm\ abrevia  Máquina de Turing não determinística.
    \item \emph{L é \ta} significa que existe \tm\ que aceita \emph{L}.
  \end{itemize}
\section{Ordena\cao}

\begin{qst}
Em rela\cao\ à ordena\cao\ de \sqn s apresente:
\begin{enumerate}
  \item condi\coes\ de corre\cao\ para um método de ordena\cao.
  \item algoritmos com argumento de corre\cao\ para cada método de ordena\cao\
estudado.
  \item estudo completo de complexidade para os algoritmos de cada método
de ordena\cao, abrangendo: melhor, pior caso e caso
médio, com respectivas rela\coes\ de recorrência, desenvolvimento e
fórmula fechada.
  \item distin\cao\ entre ordena\cao\ \emph{in-locus} e ordena\cao\ com 
constru\cao\
de nova \sqn.
  \item conceito de ordena\cao\ estável.
\end{enumerate}
\end{qst}

\section{Indexa\cao}
\begin{qst}
 \begin{enumerate}
 \item Apresente algoritmos para cria\cao\ de e pesquisa em árvores binárias e 
árvores B.
 \item Defina condi\coes\ de corre\cao\ para os algoritmos acima.
 \item Prove corre\cao\ dos algoritmos acima.
 \item Estude pior caso e melhor caso de pesquisa para as duas estruturas.
 \item Apresente ao menos duas representa\coes\ diferentes para nós de árvores
B e estude seus impactos na complexidade de pesquisa.
 \end{enumerate}

\end{qst}

\begin{qst}
  Prove todos os teoremas propostos em sala de aula para a árvore de sufixos
Ukkonen. 
\end{qst}

\section{Complexidade de problemas exponenciais}

\begin{qst}
  Desenvolva completamente o algoritmo de Kruskal para cálculo árvore
geradora mínima. Estabeleça os critérios de sua corre\cao. Prove sua corre\cao.
Estude sua complexidade.

\end{qst}

\begin{qst}
  Apresente e prove corre\cao\ de algoritmo para TSP euclideano que gere
caminho com peso equivalente a no máximo duas vezes o peso do melhor caminho.
\end{qst}

\section{Máquinas de Turing}

\begin{qst}
  \begin{enumerate}

    \item Defina formalmente \tm.
    \item Defina formalmente \ntm.
    \item Proponha \tm\ que aceite a linguagem $0^n1^n$.
    \item Proponha \tm\ que aceite a linguagem $ww^R$, onde $w^R$ denota o
reverso de $w$.
    \item Defina linguagem recursiva.
    \item Defina linguagem recursivamente enumerável.
  \end{enumerate}

\end{qst}

\begin{qst}
  Prove:
  \begin{enumerate}
    \item Se $L$ é recursiva então $\bar{L}$ também é.
    \item Se $L$ é a linguagem de uma \tm\ $M$ e $M$ tem tamanho polinomial,
então $\bar{L}$ é a linguagem de uma \tm\ de tamanho polinomial.
  \end{enumerate}
\end{qst}

\begin{qst}
  Apresente, justificando formalmente, 
uma linguagem que não é recusivamente enumerável.
\end{qst}

\begin{qst}
  Defina as seguintes classes de problema:
  \begin{enumerate}
    \item Classe \clp.
    \item Classe \clnp.
    \item Classe \clp.
    \item Classe \clnpc.
    \item Classe \clnph.
    \item Classe \clcnp.
  \end{enumerate}
\end{qst}

\begin{qst}
  Prove que o complemento de qualquer linguagem contida em \clp\ está em
\clp.
\end{qst}

\begin{qst}
  Seja $$L_0.L_1 = \{ uv \mid u\in L_0 \wedge v\in L_1\}$$
one $uv$ é a concatena\cao\ de $u$ com $v$.
  Prove que se $L_0,L_1 \in \clp$ então  $L_0.L_1 \in \clp$.
\end{qst}
\begin{qst}
  Seja \textbf{CSAT} o problema da satisfatibilidade de fórmulas do cálculo
proposicional construídas usando apenas variáveis proposicionais, conjun\cao,
disjun\cao\ e nega\cao, tais que a nega\cao\   só é usada para negar variaveis
proposicionais. Assumindo que \textbf{SAT} é \clnpc, prove que \textbf{CSAT}
também é.
\end{qst}


\bibliography{abbrev,analysis,formal,algorithms,program,string}

\bibliographystyle{amsplain}


\end{document}

