%\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}
\title{Exerc\'{\i}cio Extra}

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

\begin{document}

\maketitle

\section{Preliminares}
Este exerc\'{\i}cio poder\'a ser usado para melhorar sua nota na disciplina
de processamento paralelo. As regras s\~ao:
\begin{itemize}
	\item O exerc\'{\i}cio \'e estritamente individual.
	\item O exerc\'{\i}cio deve ser submetido at\'e 12/09.
	\item Alunos que n\'ao fizeram o trabalho do curso e fizerem este
		exerc\'{\i}cio estar\~ao aprovados com nota cinco.
	\item Ter\~ao suas notas corrigidas para $9.2$ alunos que:
		\begin{itemize}
			\item conclu\'{\i}ram ao menos parcialmente o trabalho
				do curso.
			\item conseguirem at\'e o dia 12/09 ajustar dois dos
				exerc\'{\i}cios do trabalho do curso para
				atender \`as condi\c{c}\~oes definidas abaixo.
			\item completarem todos os programas deste
				exerc\'{\i}cio extra.
		\end{itemize}
	\item Ter\~ao suas notas corrigidas para $10$ alunos que:
		\begin{itemize}
			\item conclu\'{\i}ram ao menos parcialmente o 
				trabalho do curso;
			\item apresentarem at\'e 12/09 os exerc\'{\i}cios
				do trabalho do curso atendendo \`as
				condi\c{c}\~oes definidas abaixo.
			\item completarem todos os progrmas deste
				exer\c{c}\'{\i}cio extra.
		\end{itemize}
\end{itemize}

As condi\c{c}\~oes referidas acima dizem respeito a apresentar vers\~oes dos
seguintes programas que executem com quatro processadores, dentro das 
restri\c{c}\~oes de tempo:
\begin{itemize} 
	\item vishkin  para lista de $2^{16}$ n\'os em $480$
		segundos.
	\item bitonic para $2^{12}$ em $30$
		segundos.
	\item merge para $2^{24}$ itens em $120$
		segundos.
\end{itemize}
				
Se suas implementa\c{c}\~oes j\'a atendem a tais restri\c{c}\~oes, voc\^e n\~ao 
precisa trabalhar nelas. Se seus n\~ao atendem \'as
restri\c{c}\~oes, voc\^e pode corrigi-los.

\section{Os exerc\'{\i}cios extras}

\begin{ex}
	Implemente um programa paralelo para multiplica\c{c}\~ao de matrizes
	quadradas. Use um dos algoritmos de:
	\begin{itemize}
		\item \href{http://www.math.ruu.nl/people/bisselin/pub22.ps.gz}{Bisseling}
		\item \href{http://citeseer.ist.psu.edu/10233.html}{Bisseling e
			McColl}
		\item
			\href{http://www.springerlink.com/media/N1DR7RWQQQDQTWXHDR02/Contributions/9/H/V/A/9HVAFCD65B6NWJUQ.pdf}{Bisseling e
			McColl}, vis\'{\i}vel apenas de dentro da UFES.
	\end{itemize}

	Seu programa receber\'a como \'unico argumento da linha de
	comando o n\'umero de linhas das matrizes. Ele receber\'a do \stdin\
	os elementos das duas matrizes, seguindo a ordem:
	\begin{itemize}
		\item  os elementos da primeira matriz vir\~ao antes dos
			elementos da segunda matriz.
		\item um elemento por linha de \stdin.
		\item todas as colunas da linha $i$ antes das colunas da linha
			$i+1$.
	\end{itemize}
\end{ex}

\begin{ex}
	Implemente um programa paralelo para encontrar a solu\c{c}\~ao mais
	curta para o n-puzzle, definido em sala.

	Seu programa receber\'a como \'unico argumento da linha de
	comando o n\'umero de linhas da matriz. Ele receber\'a do \stdin\
	os elementos da matriz, seguindo a ordem:
	\begin{itemize}
		\item um elemento por linha de \stdin.
		\item todas as colunas da linha $i$ antes das colunas da linha
			$i+1$.
	\end{itemize}

\end{ex}

\end{document}

