\documentclass[12pt]{article}

\usepackage{sbc-template}

\usepackage{graphicx,url}

\usepackage[brazil]{babel}
%\usepackage[latin1]{inputenc}
\usepackage[utf8]{inputenc}
\sloppy

\title{Problema da Seleção de Atividades}
\author{Fagner O. Bernardo , Victor H. Vidigal}

\address{Instituto de Ciências Exatas e Biológicas - ICEB -- Universidade Federal de Ouro Preto (UFOP)\\
\nextinstitute
  Departamento de Computação -- DECOM
}

\begin{document}

\maketitle

\begin{abstract}
  This paper will address the problem of activity selection. This problem consists in determining a solution set so that it is possible to get the largest number of activities that a resource can share from the time an activity is performed does not interfere with the time the other is performed. Three solution proposals will be presented, each one with specific characteristics and performance and their respective results.
\end{abstract}

\begin{resumo}
 Este trabalho abordará o problema de seleção de atividades. Este problema consiste em determinar um conjunto solução, de modo que seja possível obter o maior número de atividades que poderão compartilhar um recurso desde o tempo de realização de uma atividade não interfira no tempo de realização da outra. Serão apresentadas três propostas de solução, cada qual com características e desempenho específicos e seus respectivos resultados.
\end{resumo}

\section{Introdução} \label{sec:firstpage}{
	Este trabalho foi realizado para demonstrar diferentes formas de se obter conjunto solução para o problema de seleção de atividades. Este problema possui características particulares que devem ser respeitadas para que se possa obter um conjunto solução consistente. A descrição do problema é a seguinte:
	Existe um conjunto S de n atividades em que cada atividade Si possui um tempo pré-determinado para iniciar e para finalizar. O prazo de duração de cada atividade é contado em horas completas e representado dentro do intervalo de 24 horas. Deve-se obter um conjunto solução com o maior número possível de atividades mutuamente compatíveis, ou seja, o tempo de término da atividade anterior não deve ser superior ao tempo de início da atividade seguinte.
	Respeitadas as restrições deste problema, o trabalho apresentará propostas de solução capazes de gerar um conjunto com uma solução ótima para o problema de seleção de atividades.
}
\section{Objetivos}{
	Este trabalho tem como objetivo realizar a implementação de algoritmos baseados em três métodos capazes de lidar com o problema de seleção de atividades e apresentar uma solução que seja considerada ótima, ou seja, aquela que maximize a quantidade de atividades que possam ser realizadas dentro do intervalo de tempo de 24h.
	\begin{itemize}
		\item{
			O método da Escolha Guloso, que realiza uma escolha gulosa das possíveis soluções, ou seja, escolhendo aquelas que parecerem promissoras, sem avaliar diferentes combinações de atividades dentre todas as atividades disponíveis;
		}
		\item{
			O método Backtracking, que tem por objetivo a utilização da busca exaustiva na geração de todas as soluções que forem consistentes, ou seja, aquelas que não violem nenhuma restrição imposta pelo problema.
		}
	 	\item{
	 		O método Programação Dinâmica, que tem como diretriz o armazenamento temporário de informações referente às combinações de atividades que possam gerar um conjunto solução máximo e utilizando estas informações para obter o melhor conjunto solução possível.
	 	}
	\end{itemize}
}


\section{Organização do trabalho}{
	Para a realização deste trabalho, será realizada uma pesquisa bibliográfica em fontes que oferecem informações sobre os métodos aplicados, afim de identificar e entender todos os aspectos relacionados ao problema e aos métodos utilizados, para que se possa verificar a pertinência e a eficiência de cada um dos três na resolução do problema.
	Em seguida, se iniciará o desenvolvimento do algoritmo de cada método proposto mediante análise da particularidade do problema.
	Após a implementação dos algoritmos, serão realizados testes de desempenho dos três métodos para que seja possível realizar uma análise do desempenho e capacidade de cada um deles gerar uma solução ótima para o problema proposto.
}

\section{Descrição dos métodos e análises de complexidade}
{
	\subsection{Escolha Gulosa}{
		O primeiro método utilizado foi a escolha gulosa. A escolha gulosa é também conhecida como método míope, ou seja, ele faz a escolha óbvia em cada etapa da execução em que ele tenha que realizar uma escolha. Este algoritmo realiza a escolha conforme o critério que lhe foi definido, que pode ser o critério de maximização ou minimização de um resultado. A cada escolha realizada o algoritmo deve resolver um novo subproblema originado da escolha anterior. Para determinado cenário de problema a escolha gulosa é capaz de gerar a melhor solução.
		No algoritmo implementado, a escolha gulosa age em um vetor de atividades, que foi previamente ordenado de forma crescente segundo o critério de término de atividade. Desta forma a primeira atividade do vetor ordenado já é inserida no conjunto solução, pois é garantido que ela é a atividade que terminará antes de qualquer outra atividade presente no vetor.
		Tendo esta primeira atividade como referência, a escolha gulosa verifica o valor que representa a hora de término dela e usa-o como referência para procurar a próxima atividade com tempo de início que seja igual ou maior o tempo de término da atividade que já está na solução. Assim que encontra uma atividade com as características desejadas, o algoritmo a insere no conjunto solução e usa a hora de término desta nova atividade para procurar a próxima. O algoritmo repete este procedimento até que todas as atividades do vetor de atividades tenham sido verificadas.
		O algoritmo realiza esta tarefa por meio de chamadas recursivas, ou seja, a partir da primeira atividade inserida no conjunto solução e que se tornou a referência para a busca de uma nova atividade, é realizada uma nova chamada (recursiva) da função que procura por outra atividade até que todas as atividades tenham sido verificadas.
	}
	\subsubsection{Análise de complexidade}{

	}
	\subsection{Backtracking}{
		O segundo método utilizado foi o backtracking. O backtracking utiliza o conceito da busca exaustiva em árvore binária de profundidade. Significa que o algoritmo utiliza a força bruta e expande todas as combinações possíveis de atividades até chegar nas folhas da árvore utilizando chamadas recursivas. Cada nó gera uma solução, cada folha gera uma solução completa.
		A expansão da árvore ocorre da esquerda para a direita a cada chamada recursiva, desta forma é possível identificar a melhor combinação de atividades mutuamente compatíveis e inseri-las no conjunto solução. O backtracking visa buscar soluções que sejam completas e consistentes. Sempre que o algoritmo encontra uma solução melhor que a solução anterior ela se torna a nova solução ideal substituindo a anterior, que deixa de existir.
		O que diferencia o backtracking da busca exaustiva é o fato de que ele realiza podas em ramificações da árvore que violam as restrições impostas ao problema à medida que ela está sendo construída, a cada chamada recursiva, e não irá mais procurar soluções naquela ramificação, pode-se dizer então, que o backtracking elimina soluções inconsistentes. Assim, o backtracking fica conhecido como busca exaustiva inteligente.
	}
	\subsubsection{Análise de complexidade}{

	}
	\subsection{Programação dinâmica}{
		O segundo método a ser implementado é a programação dinâmica. A programação dinâmica pode ser implementada de forma recursiva, semelhante ao backtracking ou de forma iterativa.
		Ela utiliza o conceito da memorização, significa que o algoritmo armazena as informações geradas durante a sua execução em uma tabela ou outra estrutura de dados e se for necessário calcular novamente algum valor que ele já calculou antes basta simplesmente recupera a informação previamente armazenada, evitando o retrabalho e otimizando o seu tempo de execução.
		A programação dinâmica é mais utilizada em problemas de otimização, desta forma as premissas do algoritmo são: caracterizar a estrutura de uma solução ótima, definir recursivamente o valor de uma solução ótima, computar o valor da solução ótima e construir a solução ótima por meio da informação armazenada.
	}
	\subsubsection{Análise de complexidade}{

	}
}

\section{Metodologia}{
	\subsection{Avaliação experimental}{
		Para verificar a eficiência e, por consequência, a viabilidade da utilização de cada um dos três métodos apresentados, os algoritmos serão submetidos a testes experimentais. Os testes serão úteis como objeto de observação e avaliação do desempenho individual de cada método implementado.
	}

	\subsection{Descrição dos experimentos}{
		Cada algoritmo será submetido a um teste de desempenho. Para cada algoritmo serão fornecidas instâncias do problema de valores 30, 50, 75 e 100. Cada algoritmo executará estas instâncias dez vezes, para que seja possível realizar um estudo estatístico do desempenho reduzindo a margem de erro.
		No geral, não é necessário fornecer valores de instâncias maiores, no entanto, o estudo de complexidade da escolha gulosa nos mostra que o algoritmo se comportaria bem com instancias muito maiores, mesmo que o valor limite da solução ótima seja 23 atividades mutuamente compatíveis.
		O algoritmo backtracking será submetido a uma instância de 150 atividades para que seja possível consolidar as suposições mediante sua análise de complexidade.
		A programação dinâmica... (arrumar uma instancia maiorzinha p ela tbm).
	}
	\subsection{Configuração dos experimentos}{
		Antes do início da execução de cada instância do problema, será gerado um arquivo com valores aleatórios que representarão a hora de início e de término de cada atividade. Assim que oum método for executado, o arquivo será lido e as instâncias serão armazenadas em memória principal (memória RAM). Em seguida o método irá ser executado para avaliar aquela instância persente na memória da máquina.
		Após o término da execução de cada instância, será apresentado o tempo total utilizado pelo algoritmo e uma lista contendo a solução ótima para aquela instância, ou seja, contendo todas as atividades que são mutuamente compatíveis.
	}
	\subsection{Métricas de avaliação}{
		O desempenho de cada método desenvolvido é baseado na análise da complexidade do algoritmo, no conceito por trás da implementação, no sistema operacional utilizado e nas características do hardware, pois o algoritmo pode sofrer alteração em seu desempenho conforme o sistema operacional e o desempenho do hardware.
	}
}
\section{Resultados}{
	Esta sessão é dedicada à apresentação dos resultados obtidos nos testes realizados. Os resultados a serem apresentados estão relacionados ao valor de cada instância utilizada como parâmetro na execução dos testes, seguida do caso particular testado para cada algoritmo.

	\subsection{Escolha gulosa}{
		A escolha gulosa foi o método que obteve o melhor desempenho dentre os três métodos apresentados. Este método foi capaz de lidar de forma muito satisfatória com as instâncias de referência e com o caso particular de uma instância que continha 1 milhão de atividades.
	}
	\subsection{Programação dinâmica}{
		A programação dinâmica...
	}
	\subsection{Backtracking}{
		O backtracking foi o algoritmo que teve o pior desempenho dentre todos, ele demonstrou possuir um desempenho satisfatório para instâncias de até 75 elementos. Quando o valor das instâncias era superior a este, foi possível notar que o tempo de execução do algoritmo aumentou consideravelmente.
	}
}
\section{Conslusão}{
	Durante o estudo bibliográfico que objetivava a coleta de informações inerentes ao desenvolvimento deste trabalho, foi possível perceber que cada metodologia analisada possui um objetivo relacionado à questões de decisão, que é o problema em questão, e questões de otimização. Desta forma foi possível identificar previamente qual estratégia utilizada seria a mais pertinente para este problema, ou seja, qual delas seria capaz de fornecer uma resposta satisfatória em um intervalo de tempo pré-estabelecido.
	Dada a característica do problema a escolha gulosa foi o método que garantiu um resultado satisfatório com o menor tempo, portanto este é, sem dúvida, o método mais recomendado para resolver este problema, podendo ser escolhido sem receio de que não irá gerar uma solução ótima.
	A realização deste trabalho foi importante pois mostrou que o método mais complexo ou mais sofisticado nem sempre é o melhor. É fundamental entender as características e particularidades de cada problema que se deseja resolver e projetar a solução mais adequada a ele, de modo a proporcionar a melhor utilização dos recursos empregados e do tempo dedicado na tarefa
}

\section{Referências}

S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani. Algorithms. McGraw-Hill, 2006.\\\\
Departamento de Computação da universidade Federal de Ouro Preto. Moodle, material de aula. Disponível em: http://www.decom2.ufop.br/moodle/login/index.php. Acesso em: 22 de 03 de 2017.

%\bibliographystyle{sbc}
%\bibliography{sbc-template}

\end{document}