\documentclass[11pt,a4paper,reqno]{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc} % isso é quase redundante
\usepackage{textcomp}
\usepackage[T1]{fontenc}
\usepackage{ae}
\usepackage{aecompl}
%----------------------------
%\usepackage[colorlinks,bookmarks,linkcolor=black,citecolor=black]{hyperref}
\usepackage{hyperref}
\hypersetup{colorlinks=false}
\usepackage{srcltx}
\usepackage{fullpage}
\usepackage{setspace}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\def\@setaddresses{\par
  \nobreak \begingroup
\footnotesize
  \def\author##1{\nobreak\addvspace\bigskipamount}%
  \def\\{\unskip, \ignorespaces}%
  \interlinepenalty\@M
  \def\address##1##2{\begingroup
    \par\addvspace\bigskipamount\indent
    \@ifnotempty{##1}{(\ignorespaces##1\unskip) }%
    {\scshape\ignorespaces##2}\par\endgroup}%
  \def\curraddr##1##2{\begingroup
    \@ifnotempty{##2}{\nobreak\indent{\itshape Current address}%
      \@ifnotempty{##1}{, \ignorespaces##1\unskip}\/:\space
      ##2\par}\endgroup}%
  \def\email##1##2{\begingroup
    \@ifnotempty{##2}{\nobreak\indent{\itshape Endereço eletrônico}%
      \@ifnotempty{##1}{, \ignorespaces##1\unskip}\/:\space
      \ttfamily##2\par}\endgroup}%
  \def\urladdr##1##2{\begingroup
    \@ifnotempty{##2}{\nobreak\indent{\itshape URL}%
      \@ifnotempty{##1}{, \ignorespaces##1\unskip}\/:\space
      \ttfamily##2\par}\endgroup}%
  \addresses
  \endgroup
}
\makeatother

\def\({\left(}
\def\){\right)}
\def\<{\langle}
\def\>{\rangle}
\let\:\colon

\def\aa{{\mathtt A}}
\def\cc{{\mathtt C}}
\def\gg{{\mathtt G}}
\def\tt{{\mathtt T}}
\def\ZZ{{\mathbb Z}}
\def\RR{{\mathbb R}}
\def\FF{{\mathbb F}}
\let\:\colon
\def\bfx{\mathbf{x}}
\def\bfp{\mathbf{p}}
\def\Stanf{^\text{S}}

\def\Fat{\mathop{{\rm Fat}}\nolimits}

\usepackage{datetime}

\begin{document}
\onehalfspacing

\title[EP1 CCM128 1o.~semestre 2014]{%
  {\sl CCM128 Exercício-Programa 1}\\\medskip
  Genes}
\author{Y.~Kohayakawa}
\address{Instituto de Matemática e Estatística, Universidade de São Paulo, Rua
  do Matão 1010, 05508--090~São Paulo, SP}
\email{yoshi@ime.usp.br}

\def\datename{Versão de}
%\date{\today, \currenttime.  Versão preliminar} 
\date{\today, \currenttime}

\maketitle
%\thispagestyle{empty}
\footskip=25pt

\noindent\textbf{Data de entrega:}\quad 17/3/2014 (23:55)

\section{Introdução e definições básicas}
Este EP trata de processamento de cadeias de caracteres
(\textit{strings}).  Supomos fixo um \textit{alfabeto}~$\Sigma$, cujos
membros chamamos de \textit{letras} (um \textit{alfabeto} é
simplesmente um conjunto finito).  Nossas cadeias de caracteres, ou
\textit{palavras}, sobre~$\Sigma$ são sequências finitas de letras.  O
conjunto das palavras sobre~$\Sigma$ é denotado~$\Sigma^*$.  O
comprimento~$|s|$ de uma palavra~$s\in\Sigma^*$ é o número de letras
que a compõe.  Dadas duas palavras~$s$ e~$t\in\Sigma^*$, a
\textit{concatenação}~$st$ destas palavras é uma nova palavra
sobre~$\Sigma$; claramente~$|st|=|s|+|t|$.  A palavra vazia (aquela de
comprimento~$0$) é denotada por~$\lambda$.

\section{Genes}
\label{sec:genes}
Uma palavra~$f$ é um \textit{fator} de uma palavra~$s$ se~$s=s_1fs_2$
com~$s_1$ e~$s_2\in\Sigma^*$.  O conjunto dos fatores de uma
palavra~$s$ é denotado~$\Fat(s)$.  

No que segue, consideramos sempre~$\Sigma=\{\aa,\cc,\gg,\tt\}$.
Ademais, as palavras~$s=\aa\tt\gg$ e~$t=\tt\aa\gg$ terão papéis
especiais.  Seja dada uma palavra~$D\in\Sigma^*$.  Um \textit{gene}
em~$D$ é um fator~$g\neq\lambda$ de~$D$ de comprimento divisível
por~$3$ e tal que~$sgt\in\Fat(D)$.  Assim, um gene em~$D$ é um fator
de comprimento multiplo de~$3$, precedido de~$s=\aa\tt\gg$ e seguido
de~$t=\tt\aa\gg$.  Note que~$D$ pode conter um dado gene~$g$ em vários
locais diferentes.

\section{Seu programa}
\label{sec:}
Seu EP1 deve ter como entrada uma palavra~$D\in\Sigma^*$.  No modo
mais simples, seu programa deve ter como saída o número \textit{total}
de genes que~$D$ contém, contando com multiplicidade (se um dado gene
ocorre~$m$ vezes, este gene contribui com~$m$ nesse total).  Por
exemplo, na entrada 
\begin{verbatim}
CATGCTATAGATGTAGTAGAGCATGTAGCTAAGCTAGATGCTATAGATGAGCATGCTAG
\end{verbatim}
seu programa deve ter como saída o inteiro~$13$:
{\small
\begin{verbatim}
yoshi@renyi ~/TMP $ java-introcs GeneFindAll < ex.txt 
13
yoshi@renyi ~/TMP $ 
\end{verbatim}
} \noindent
(\verb|ex.txt| contém o exemplo acima).  Seu programa deve também ter
um modo, indicado pela opção \verb|-v|, em que ele imprime todos os
genes encontrados:
{\small
\begin{verbatim}
yoshi@renyi ~/TMP $ java-introcs GeneFindAll -v < ex.txt 
CTA
CTATAGATG
CTATAGATGTAG
CTATAGATGTAGTAGAGCATG
CTATAGATGTAGTAGAGCATGTAGCTAAGC
CTATAGATGTAGTAGAGCATGTAGCTAAGCTAGATGCTA
TAG
TAGTAGAGCATG
TAGTAGAGCATGTAGCTAAGC
TAGTAGAGCATGTAGCTAAGCTAGATGCTA
TAGCTAAGC
TAGCTAAGCTAGATGCTA
CTA
yoshi@renyi ~/TMP $ 
\end{verbatim}
}

\subsection*{Instâncias}
\label{sec:instancias}
Você deve supor que seu EP1 será tipicamente executado com
palavras~$D$ bastante longas (no modo padrão (sem \verb|-v|)).  Por
exemplo, $D$~poderia ser a sequência completa de nucleotídeos que
compõe um cromossomo de um organismo simples.  Por exemplo, veja o
cromossomo~III do \textit{C.~elegans} em
\url{http://www.ncbi.nlm.nih.gov/nuccore/NC_003281.10?report=fasta&log$=seqview}
(${}>\text{20MB}$).  (Ao visitar a URL acima, você perceberá que é
necessário remover mudanças de linha.)

\subsection*{Observações} Seguem algumas observações importantes.

\small
\begin{enumerate}
\item \textit{Este EP é estritamente individual}.  Programas
  semelhantes receberão nota~$0$.
\item Seja cuidadoso com sua programação (correção, documentação,
  apresentação, clareza de código, etc).  A correção não é baseada
  apenas na correção de seu programa.
\item Comparem entre vocês o desempenho de seus programas.
\item Entregue seu EP no Paca.
\item Não deixe de incluir em seu material um \textit{relatório} para
  discutir seu EP: faça quaisquer comentários que você achar
  interessante e inclua exemplos de execuções de seu programa.
  \textit{Quando mais o monitor vir as qualidades de seu programa,
    melhor será o seu humor e melhor será sua nota.}
\end{enumerate}

\subsubsection*{Observação final}  Enviem dúvidas para a lista de discussão da
disciplina.

%\bibliographystyle{abbrv}
%\bibliography{refs_Teach}

\end{document}

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