\documentclass[12pt]{article}
\usepackage{isolatin1}
\usepackage{epsf}
\usepackage{fullpage}
\usepackage{color}

\thispagestyle{empty}

\begin{document}
\thispagestyle{empty}

%\color{red}
\mbox{}

\bigskip

\begin{center}
\large\bf
MO640 - Biologia Computacional\\

\bigskip

Prova Individual - 30/05/2005
\end{center}

\bigskip

\bigskip

\bigskip

\paragraph{Questão 1} (Valor 3,0) 
Considerando o problema da distância de reversão com sinais, classifique as afirmações abaixo como verdadeiras ou falsas:
\begin{enumerate}
\item
uma componente boa pode ser um super-obstáculo
\item
uma componente pode ser ao mesmo tempo um super-obstáculo e um obstáculo simples
\item
uma componente ruim pode ser um não-obstáculo, um obstáculo simples ou um super-obstáculo
\item
não é possível ter uma permutação onde haja exatamente duas componentes ruins, e tal que ambas sejam super-obstáculos
\end{enumerate}


\paragraph{Questão 2} (Valor 2,0) 
Considerando o problema de distância de transposição de prefixos, sem sinais, exiba uma permutação fácil, diferente da identidade, que se inicie com ``1'', ou então dê um argumento explicando porque tal permutação não existe.


\paragraph{Questão 3} (Valor 3,0)
Encontre uma seqüência ótima de reversões com sinal que ordene a permutação abaixo.  Justifique porque você acredita que sua seqüência seja ótima.
\[
   [-2, 1, -3, 4, -8, 6, 7, -5].
\]


\paragraph{Questão 4} (Valor 2,0)
Encontre a seqüência de transposições sem sinal mais curta que você conseguir que ordene a permutação abaixo.
\[
   [3, 2, 1, 6, 5, 4].
\]

\end{document}
