%\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}
\inmacros{defseqs}

\def\course{Projeto e An\'alise Algoritmos}
\def\thisdoc{Lista $\mathcal{PC}_0$}
\title{\course\\ \thisdoc}



\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\loop{\emph{loop}}

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

\begin{document}

\maketitle

\section{Introdu\c{c}\~ao}
Resolva os seguintes exerc\'{\i}cios individualmente. Use-os como 
treinamento para os testes individuais que ser\~ao realizados em
sala de aula.

\section{Os exerc\'{\i}cios}
Cada um dos exerc\'{\i}cios a seguir demanda calcular um programa.
Apresente claramente os seguintes itens:
\begin{itemize}
	\item estado final do seu programa;
	\item invariante do \loop, justificando sua deriva\c c\~ao;
	\item guardas do \loop;
	\item condi\c c\~oes de progresso;
	\item vari\'avel derivada;
	\item programa n\~ao recursivo, usando a linguagem de Dijkstra;
	\item prova de corre\c c\~ao do seu programa.
\end{itemize}

\begin{ex}
	Calcular o m\'aximo divisor comum de dois inteiros n\~ao negativos.
\end{ex}

\begin{ex}
	Determinar uma aproxima\c c\~ao para a raiz quadrada de um inteiro n\~ao 
	negativo.
\end{ex}

\begin{ex}
	Determinar a maior pot\^encia de dois que \'e menor do que um inteiro 
	dado.
\end{ex}

\begin{ex}
	Dada uma seq\"u\^encia de inteiros $S$ e um inteiro $x\in S$, determine
	a posi\c c\~ao de $x$ em $S$.
\end{ex}

\begin{ex}
	Dada uma seq\"u\^encia ordenada 
	de inteiros $S$ e um inteiro $x\in S$, determine
	eficientemente a posi\c c\~ao de $x$ em $S$.
\end{ex}

\begin{ex}
	Determine o reverso de uma lista.
\end{ex}

\begin{ex}
	Dado um inteiro positivo, determine a sua representa\c c\~ao bin\'aria.
\end{ex}

\begin{ex}
	Dada uma \'arvore bin\'aria, determine o n\'umero de folhas da mesma.
\end{ex}

\begin{ex}
	Dada uma \'arvore bin\'aria, calcule uma seq\"u\^encia com a visita\c c\~ao
	\emph{inordem} dos seus n\'os. 
\end{ex}

\begin{ex}\label{ex:horner}
	Dada uma seq\"u\^encia de inteiros, coeficientes de um polin\^omio
	$\bnd{+}{i}{\lelt0in}{a_i x}$, e o valor de $x$, calcule eficientemente o
	valor de $x$.
\end{ex}

\begin{ex}
   Resolva \exref{horner} em m\'aquina PRAM.
\end{ex}

\begin{ex}
	Calcule os primeiros $1000$ valores da seq\"u\^encia definida pelos
	axiomas:
	\begin{enumerate}
		\item $1\in S$.
		\item Se $x\in S$, $2x\in S, 3x\in S, 5x \in S$.
		\item Fecho.
	\end{enumerate}
\end{ex}

\begin{ex}
	\'Arvore Geradora m\'{\i}nima de um grafo, usando a invariante do algoritmo
	de Prim.
\end{ex}

\begin{ex}
	\'Arvore Geradora m\'{\i}nima de um grafo, usando a invariante do algoritmo
	de Boru\v{v}ka.
\end{ex}

\end{document}

