%\documentclass[dvips,12pt]{amsart}
\documentclass[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{Semin\'arios}
\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}
\def\xpaa{\emph{Projeto e An\'alise de Algoritmos}}
\def\CC{\emph{Ci\^encia da Computa\c c\~ao}}
\def\SC{\textbf{Senhor do Castelo}}

Como parte da avalia\c c\~ao da disciplina de \xpaa, voc\^e dever\'a
realizar um estudo do estado da arte em algum problema
relevante de \CC. Para tal, voc\^e escrever\'a um
artigo e apresentar\'a um semin\'ario sobre algum tema de sua escolha.
Os passos para realiza\c c\~ao deste trabalho s\~ao:
\begin{itemize}
	\item Escolher um tema de trabalho.

		Voc\^e pode escolher qualquer tema que considerar relevante em \CC,
		respeitando as restri\c c\~oes:
		\begin{itemize}
			\item O \SC\ acredita que o \'unico tipo de trabalho v\'alido em
				computa\c c\~ao passa pela constru\c c\~ao, valida\c c\~ao e
				an\'alise de programas. 
			\item O tema escolhido dever\'a passar pelo crivo do \SC\ e
				da turma: durante a avalia\c c\~ao final do seu trabalho,
				cada aluno emitir\'a uma nota para seu trabalho, que levar\'a
				em conta, entre outros, a relev\^ancia do assunto pesquisado.
		\end{itemize}

	\item Escolher uma metodologia de desenvolvimento.
	\item Desenvolver o trabalho de acordo com metodologia proposta.
	\item Escrever artigo e apresentar semin\'ario sobre o trabalho
		desenvolvido.
\end{itemize}

Voc\^e dever\'a  escolher uma metodologia de desenvolvimento do trabalho, 
baseada num dos seguintes enfoques:

\def\informal{\emph{informal}}
\begin{itemize}
	\item Enfoque te\'orico

		Fa\c ca uma apresenta\c c\~ao formal de seu problema e de sua 
		solu\c c\~ao e isso inclui:
		\begin{itemize}
			\item deriva\c c\~ao formal e corre\c c\~ao de melhor algoritmo para 
				solucionar o problema em quest\~ao;
			\item an\'alise matem\'atica de complexidade do algoritmo escolhido,
				inclu\'{\i}ndo, quando relevante, an\'alise de qualidade de
				solu\c c\~ao obtida.
		\end{itemize}

	\item Enfoque experimental

		Fa\c ca uma apresenta\c c\~ao {\informal} de seu problema e de sua
		solu\c c\~ao, seguido de rlato de experimento. Inclua, ao menos:
		\begin{itemize}
			\item Argumento \informal\ de corre\c c\~ao de melhor algoritmo
				para solucionar o problema em quest\~ao;
			\item An\'alise \informal\ de complexidade do algoritmo escolhido
				e da qualidade dos resultados esperados;
			\item Implementa\c c\~ao de seu algoritmo.
			\item An\'alise experimental exaustiva de sua implementa\c c\~ao,
				incluindo descri\c c\~ao da metodologia de teste.
		\end{itemize}
\end{itemize}

Este \'e um trabalho estritamente individual, o que significa que voc\^e
deve mostrar autonomia total em rela\c c\~ao a busca de fontes de pesquisa,
estudo de algoritmos, implementa\c c\~ao, escrita de artigo e quaisquer
outras atividades deste projeto.

\section{Temas sugeridos}

Seguem alguns temas sugeridos para semin\'ario:

\def\xmst{\'Arvore geradora m\'{\i}nima}
\def\atsp{\emph{TSP assim\'etrico}}
\def\gtsp{\emph{TSP geom\'etrico}}

\begin{itemize}
	\item Compress\~ao de dados:
		\begin{itemize}
			\item \emph{Predictive coding}
			\item Compress\~ao com perda
			\item Compress\~ao de \'{\i}ndices
		\end{itemize}
	\item Grafos e Otimiza\c c\~ao
		\begin{itemize}
			\item Algoritmos e estruturas de dados para o problema de \xmst.
			\item Compara\c c\~ao de heur\'{\i}sticas (algoritmos e estruturas
				de dados) para busca local no 
				problema do \atsp.
			\item Aproxima\c c\~ao arbitr\'aria no problema do \gtsp.
		\end{itemize}
	\item Geometria computacional
		\begin{itemize}
			\item Indexa\c c\~ao de imagens.
			\item Triangula\c c\~ao.
		\end{itemize}
	\item Algoritmos em hardware
		\begin{itemize}
			\item Ordena\c c\~ao.
			\item Complexidade de comunica\c c\~ao.
		\end{itemize}
\end{itemize}
 
\end{document}

