%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Time-stamp: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass[reqno]{amsart} %% Escrevendo em português: \usepackage[brazil]{babel} \usepackage[latin1]{inputenc} %---------------------------- %\usepackage{refcheck} \usepackage{srcltx} \usepackage{fullpage} %\usepackage{doublespace} \usepackage{setspace} \let\:=\colon \let\epsilon=\varepsilon \def\e{{\rm e}} \def\dist{\mathop{\rm dist}\nolimits} \def\supp{\mathop{\rm supp}\nolimits} \def\ex{\mathop{\rm ex}\nolimits} \def\bsigma{\bar\sigma} \def\RR{\mathbb R} \def\NN{\mathbb N} \def\ZZ{\mathbb Z} \def\llfloor{\left\lfloor} \def\rrfloor{\right\rfloor} \def\llceil{\left\lceil} \def\rrceil{\right\rceil} \def\({\left(} \def\){\right)} \def\<{\langle} \def\>{\rangle} %\let\sim=\thicksim \newcommand{\tdots}{\,.\,.\,} % in place of \ldots \newcommand{\larr}{\leftarrow} \newcommand{\phentao}{\phantom{então}} \newcommand{\phsenao}{\phantom{senão}} \newcommand{\x}{\hspace*{3ex}} % era 4ex \newcommand{\xx}{\hspace*{6ex}} \newcommand{\xxx}{\hspace*{9ex}} \newcommand{\xxxx}{\hspace*{12ex}} \newcommand{\xxxxx}{\hspace*{15ex}} \newcommand{\xxxxxx}{\hspace*{18ex}} \newlength{\tsts} \settowidth{\tsts}{9} \newcommand{\ts}{\hspace{\tsts}} \newcommand{\RM}{\textrm} \newenvironment{pseudoc} {\begin{list}% {}% {% \sffamily% \setlength{\partopsep}{1ex}% \setlength{\topsep}{1ex}% \setlength{\leftmargin}{\parindent}% \setlength{\parsep}{0.5ex}% }% \item}% {\end{list}% } \newenvironment{pseudocode}% {\begin{pseudoc}% \textbf{\textrm{Algoritmo}}\hspace{0.7ex}\ignorespaces% }% {\end{pseudoc}} \def\inR{\mathrel{\in_{\text R}}} \def\cA{\mathcal A} \def\cB{\mathcal B} \def\cC{\mathcal C} \def\cD{\mathcal D} \def\cF{\mathcal F} \def\cG{\mathcal G} \def\cH{\mathcal H} \def\cI{\mathcal I} \def\cL{\mathcal L} \def\cP{\mathcal P} \def\cR{\mathcal R} \def\cS{\mathcal S} \def\barp{{\bar p}} \def\prof{\mathop{{\rm prof}}\nolimits} \def\Bi{\mathop{{\rm Bi}}\nolimits} \def\Var{\mathop{{\rm Var}}\nolimits} \def\Cov{\mathop{{\rm Cov}}\nolimits} \def\dev{\mathop{{\rm dev}}\nolimits} \def\og{\mathop{{\rm og}}\nolimits} \def\EE{\mathop{\hbox{\hbox{${\mathbb E}$}}}\nolimits} \def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits} \def\FF{\mathop{\hbox{\raise.03ex\hbox{${\mathbb F}$}}}\nolimits} \def\RP{\mathbf{RP}} \def\BPP{\mathbf{BPP}} \def\bfx{\textbf{x}} \def\bfy{\textbf{y}} \makeatletter \renewcommand{\labelenumi}{\theenumi.} \makeatother \def\datedue#1{$\{$\textsl{Data de entrega}: #1$\}$} \def\sugestao#1{[\textit{Sugestão.} #1]} \def\observacao#1{[\textit{Observação.} #1]} \begin{document}\onehalfspace \title[MAC0122 Algoritmos]{Prova de Recuperação de Princípios de Desenvolvimento de Algoritmos\\2{\tiny o.} semestre de 2006} %\date{Versão de \today} \maketitle \footskip=20pt \noindent {\bf Instruções:} \begin{enumerate}\small \item Não destaque as folhas do caderno de soluções. \item A prova pode ser feita a lápis. Cuidado com a legibilidade. %\item Há~$3$ questões na prova. Verifique antes de começar a prova %se o seu caderno de questões está completo. \item Não é permitido o uso de folhas avulsas para rascunho. %\item Nas questões que envolvem elaboração de programas, coloque %comentários suficientes para que o programa seja facilmente %compreendido. \item Não é necessário apagar rascunhos no caderno de soluções. \item Asserções imprecisas valem pouco. Justifique suas asserções (dentro do razoável). Seja claro e objetivo. %\item \textbf{IMPORTANTE:} \textbf{Faça no máximo 3 questões.} \end{enumerate} \bigskip \begin{enumerate} %\thispagestyle{empty} \item{}[3 pontos] \begin{enumerate} \item[(\textit{i})] Descreva precisamente o algoritmo de ordenação \textit{mergesort} (ordenação por intercalação). \item[(\textit{ii})] Quanto tempo demora o \textit{mergesort} para ordenar um vetor de inteiros com~$n$ entradas? Justifique sua resposta cuidadosamente. \item[(\textit{iii})] Descreva precisamente o algoritmo de ordenação \textit{quicksort}. \item[(\textit{iv})] Quanto tempo demora o \textit{quicksort} para ordenar um vetor de inteiros com~$n$ entradas? Justifique sua resposta cuidadosamente. \end{enumerate} \item{}[3 pontos] Nesta disciplina, estudamos \textit{tabelas de símbolos}: estruturas de dados para armazenar \textit{itens} que admitem as operações de inserção e busca de itens por \textit{chaves}, entre outras. \begin{enumerate} \item[(\textit{i})] Descreva precisamente como implementar uma tabela de símbolos usando \textit{árvores binárias de busca} (ABBs). \item[(\textit{ii})] Discuta as características principais de desempenho de tabelas de símbolos implementadas com ABBs (por exemplo, quanto tempo demora tipicamente a inserção de um item em uma tal tabela, supondo que há na tabela~$n$ itens?). Justifique sua resposta cuidadosamente, explicitando as hipóteses em sua análise. \item[(\textit{iii})] Descreva precisamente como implementar uma tabela de símbolos usando \textit{tabelas de hashing}. \item[(\textit{iv})] Discuta as características principais de desempenho de tabelas de símbolos implementadas com tabelas de hashing (por exemplo, quanto tempo demora tipicamente a inserção de um item em uma tal tabela, supondo que há na tabela~$n$ itens?). Justifique sua resposta cuidadosamente, explicitando as hipóteses em sua análise. \end{enumerate} %\pagebreak \bigskip \item{}[4 pontos] Descreva o projeto de um programa que recebe uma cadeia de caracteres~$T$ como entrada e devolve o trecho repetido mais comprido neste texto. Por exemplo, se o texto de entrada for \texttt{aacabcabcbabcbabac}, então a saída de seu programa deve ser \texttt{abcbab}. Faça uma descrição cuidadosa de seu projeto de programa: descreva a estrutura de dados a ser usada e dê os protótipos das funções principais, com uma descrição de o que estas funções devem fazer e como elas poderiam ser implementadas (não esqueça do \texttt{main()}). O seu projeto deve supor que a entrada~$T$ pode ser grande; por exemplo, $T$~poderia um livro todo. Um programa implementado de acordo com o seu projeto deve ser tal que \begin{enumerate} \item[(\textit{i})] sob hipóteses razoáveis, ele leva tempo basicamente não muito maior que proporcional a $n\log n$, onde~$n$ é o número de caracteres em~$T$, \item[(\textit{ii})] ele gasta uma quantidade de memória proporcional ao número de caracteres em~$T$. \end{enumerate} Você deve argumentar por que o programa teria estas propriedades (em particular, você deve explicitar as hipóteses que você usa em sua análise). % \sugestao{Um \textit{sufixo} de uma cadeia de caracteres~$T$ é um `segmento % final' dela. Os sufixos de \texttt{abcde} são \texttt{abcde}, % \texttt{bcde}, \texttt{cde}, \texttt{de}, \texttt{e}, e a cadeia vazia, % com~$0$ caracteres ($6$~sufixos no total). Considere os sufixos de~$T$.} %\bigskip %\item{}[4 pontos] \end{enumerate} \endgroup \end{document} % Local Variables: % mode: latex % eval: (Portug-mode) % TeX-master: t % End: