%\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{Avalia\c{c}\~ao Final}

\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 final. Ele avalia todo o conte\'udo do
semestre. Voc\^e deve entregar sua pr\'opria solu\c{c}\~ao por escrito,
em folha de papel alma\c{c}o, devidamento identificado. Voc\^e pode discutir
suas solu\c{c}\~oes com seus colegas, mas deve submeter sua pr\'opria
solu\c{c}\~ao.

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

\section{Contexto}
\def\pram{\textbf{PRAM}}
\def\bigo#1{\ensuremath{\mathcal{O}(#1)}}
Os algoritmos a seguir devem ser apresentados considerando execu\c{c}\~ao 
em uma m\'aquina \pram: n\'umero polinomial de processadores, com acesso
simult\^aneo em
\bigo(1) a qualquer posi\c{c}\~ao de mem\'oria. Interessam-nos:
\begin{itemize}
	\item A corre\c{c}\~ao dos algorimos.
	\item O tempo execu\c{c}\~a o, que deve ser entendido como o n\'umero 
		de transi\c{c}\~oes (passos) paralelas.
	\item O trabalho executado, que deve ser considerado como o tempo
		multiplicado pelo n\ 'umero de processadores.
\end{itemize}

\def\erew{\textbf{EREW PRAM}}

Uma varia\c{c}\~ao interessante da m\'aquina \pram\ \'e a 
\erew, que  \'e uma \pram\ em que o acesso simult\^aneo de mais de um processador
a uma mesma posi\c{c}\~ao de mem\'oria \'e feito de forma serializada.

\def\NC{\textbf{NC}}

Um importante conceito em computa\c{c}\~ao paralela \'e o da classe 
\NC\ de problemas: problemas com solu\c{c}\~oes em m\'aquina PRAM, que usam
n\'umero polinomial de processadores e demandam tempo polilogar\'{\i}tmico.


\section{As quest\~oes}
\def\speedup{\emph{speedup}}

\begin{qst}
	o \speedup\ de um algoritmo paralelo $A$ para resolver um problema
	$P$ em $p$ processadores 
	\'e a divis\~ao do tempo do melhor algoritmo
	seq\"u\^encial que resolve $P$ pelo
	tempo de $A$ executado com $p$ processadores.

	Comente a afirma\c{c}\~ao: \textbf{Um algoritmo eficiente para 
	resolver $P$ em $p$ processadores apresenta  \speedup\
	superior a $p$.}
\end{qst}

\def\xNC{classe \textbf{NC}}
\begin{qst}
	Moste que o problema do c\'alculo das soma dos sufixos de uma
	seq\"u\^encia de inteiros pertence \`a \xNC e que ele pode ser resolvido
	por um algoritmo paralelo com trabalho igual ao do melhor algoritmo
	sequencial.
	
\end{qst}

\begin{qst}
	Descreva um algoritmo paralelo eficiente para calcular o valor
	de um polin\^omio
	$$\sum_{\lele0in}a_ix^i$$
	dados os valores de $x$ e $a_i$.

	Calcule a complexidade de tempo e trabalho do seu algoritmo e justifique
	porque ele \'e eficiente.
\end{qst}

\begin{qst}
	Descreva um algoritmo paralelo eficiente para 
	para realizar o \emph{broadcast} de um valor contido na posi\c{c}\~ao
	inicial de array para todas as outras prosi\c{c}\~oes,
	assumindo ele deve executar em uma \erew. 
	Calcule a complexidade de tempo e trabalho do seu algoritmo e justifique
	porque ele \'e eficiente.
	
\end{qst}

\begin{qst}
	Descreva um algoritmo para determinar se um conjunto de inteiros tem 
	um subconjunto, cujo somat\'orio \'e $k$, sendo este um inteiro dado.

        Calcule a complexidade de tempo e trabalho do seu algoritmo.

	Situe o problema dado em uma classe de complexidade.
\end{qst}

\begin{qst}
	Descreva um algoritmo paralelo eficiente para ordena\c{c}\~ao de 
	inteiros.
	Calcule a complexidade de tempo e trabalho do seu algoritmo e justifique
	porque ele \'e eficiente. Discute poss\'{\i}veis dificuldades de 
	implement\'a-lo.


\end{qst}


\end{document}

