\documentclass[12pt]{amsart}
\usepackage[portuges]{babel}
\usepackage{boxedminipage}
\usepackage[latin1]{inputenc}
% uncomment next line to get pdf files with hyperlinks
%\usepackage[pdftex,bookmarks=true]{hyperref}
%\input{defmath}
\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\acl{\textbf{ACL2}}
\newtheorem{qst}{Questão}
\title{Estruturas de Dados \\
Prova 0 \\ Business as Usual}

\author{Raul H.C. Lopes}


\begin{document}

\maketitle
\section{Introdu\cao}

Esta prova foi elaborada para ser resolvida em uma hora. 
A prova deve ser resolvida individualmente, sendo permitida consulta a notas de 
aula. Todas as questões têm o mesmo peso.

\section{As questões}

\begin{qst}
Seja $\mathcal{P}.S$ o conjunto de todos os subconjuntos de $S$ e $\#S$, 
o n\'umero
de elementos de $S$. Prove que $\mathcal{P}.S = 2^{\#S}$. 
\textsl{Dica: Qualquer
subconjunto de um conjunto de $n$ elementos pode ser representado por
uma \sqn\ de $n$ booleanos, cada um indicando se determinado elemento do 
conjunto original 
ocorre
ou n\~ao no subconjunto em quest\~ao.}
\end{qst}

\begin{qst}
Veja a fun\cao\ a seguir.

\begin{verbatim}
   gcd (m,n) = if m < n
               then gcd(m,n-m)
               else if m > n 
               then gcd(m-n,n)
               else m
\end{verbatim}

Prove que, se $a$ e $b$ s\~ao inteiros maiores do que zero, $gdc(a,b)$ 
termina e produz o maior divisor comum de $a$ e $b$.

\end{qst}


\begin{qst}
Considere a defini\cao\ a seguir.

\begin{align*}
  F_0 = & 0 \\
  F_1 = & 1 \\
  F_n = & F_{n-1}+F_{n-2}, \text{ para } n>1 
\end{align*}

Prove que, para todo $n$ inteiro ($n \geq 0$), $F_n < 2^n$. 
\end{qst}

\vfill

\section{...I'll say when it's the end!} 
\begin{quote}
  ... and Aunt Sally she come in, and when we got back se was standing on top
of the bed raising Cain, and the rats was doing what they could to keep off
the dull times for her.
\end{quote}


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

\bibliographystyle{amsplain}


\end{document}

