%\documentclass[dvips,12pt]{amsart}
\documentclass[pdftex,12pt]{amsart}
\usepackage{amsmath}
\usepackage[portuges]{babel}
\usepackage{enumerate}

\usepackage{hyperref}
\def\hbref#1#2#3{\href{#1#2}{#3}}

\def\crseurl{http://www.inf.ufes.br/~raulh/ufes/teaching/courses/lpii}

\def\cwurl{\crseurl/page/cw/0/}

\def\inmacros#1{\input{$HOME/tex/macros/#1}}

\inmacros{defport}
\inmacros{deflogic}
%\input{deflogic}
%\input{defseqs}
%\input{deftrees}
\title{Prova 0}

\author{Raul H.C. Lopes}
\def\radixsort{\emph{radix sort}}
\def\splitter{\emph{splitter}}
\def\quicksort{\emph{quick sort}}
\def\mergesort{\emph{merge sort}}
\def\prefsum{prefix sum}
\def\real{Real}


\def\scref#1{sc. \ref{#1}}
\def\exref#1{ex. \ref{ex:#1}}
\def\tabref#1{tab. \ref{tab:#1}}

\begin{document}

\maketitle

\section{Preliminares}
Este exerc\'{\i}cio tem o valor de prova parcial. Ele deve ser resolvido 
individualmente. Entregue sua solu\c{c}\~ao por escrito,
em folha de papel alma\c{c}o, devidamento identificada. 

Sua solu\c{c}\~ao deve ser entregue em minha sala at\'e quarta-feira, 10/08/05,
\`as 11 horas.

\section{Contexto}

\def\pl#1{\ensuremath\langle#1\rangle}
\def\sort#1{\ensuremath{tangle\ #1}}
\def\zip#1#2{\ensuremath{(#1\Join #2)}}
\def\tie#1#2{\ensuremath{(#1\mid #2)}}
\def\mm#1#2{\ensuremath{(#1\updownarrow #2)}}
\def\xPL{\textbf{PSeq}}

Uma \xPL\ de inteiros \'e uma seq\"u\^encia de $2^p$ inteiros, onde 
$p$ \'e um inteiro n\~ao negativo. Dada uma \xPL\ $S$, define-se:
\begin{itemize}
	\item $\zip pq = S$, $p$ e $q$ cont\^em os elementos de $S$, cujos
		\'ultimos bits de endere\c{c}o em $S$ s\~ao respectivamente
		zero e um.
	\item $\tie pq = S$, $p$ e $q$ cont\^em os elementos de $S$, cujos
		primeiros bits de endere\c{c}o em $S$ s\~ao respectivamente
		zero e um.
	\item $\pl x$ representa a \xPL\ de um \'unico elemento.
\end{itemize}

\def\xmin#1#2{\ensuremath{#1\downarrow#2}}
\def\xmax#1#2{\ensuremath{#1\uparrow#2}}

Considere que $\xmin ab$ \'e o m\'{\i}nimo de $a$ e $b$ e que 
$\xmax ab$ \'e o m\'aximo de $a$ e $b$.

\def\op#1#2{\ensuremath{#1\oplus #2}}

\begin{gather}
	\op{\pl x}{\pl y} = \pl{\op xy}\\
	\op{\zip pq}{\zip uv} = \zip{(\op pu)}{(\op qv)}\\
	\op{\tie pq}{\zip uv} = \tie{(\op pu)}{(\op qv)}\\
	\mm pq = \zip{(\xmin pq)}{(\xmax pq)}
\end{gather}


\section{As quest\~oes}
\begin{qst}
	Apresente uma defini\c{c}\~ao recursiva de um operador para c\'alculo
	das somas dos prefixos uma seq\"u\^encia de inteiros. 

	Prove a corre\c{c}\~ao do seu operador.
\end{qst}

\begin{qst}
	Defina operadores recursivos para c\'alculo de reverso e soma
	de prefixos sobre \xPL\ de inteiros.
\end{qst}

\def\bm#1#2{\ensuremath{#1\Updownarrow #2}}
Veja a defini\c{c}\~ao a seguir.
\begin{gather}
	\label{sort0}\sort{\pl x} = \pl x\\
	\label{sort1}\sort{\zip pq} = \bm{\sort p)}{(\sort q)}\\
	\bm{\pl x}{\pl y} = \mm{\pl x}{\pl y}\\
	\bm{\zip rs}{\zip uv} = \mm{(\bm rv)}{(\bm su)}
\end{gather}

\begin{qst}\label{sort}
	Dada uma \xPL\ $x$ sobre $\{0,1\}$, o que faz \sort x? Prove.
\end{qst}

\begin{qst}
	Qual seria a profundidade da computa\c{c}\~ao proposta na quest\~ao
	\ref{sort}?
\end{qst}

\begin{qst}
	Qual seria a complexidade de tempo e trabalho de uma implementa\c{c}\~ao
	paralela do algoritmo sugerido pelos axiomas \ref{sort0} e \ref{sort1}?
\end{qst}



	
\end{document}

