\documentclass[12pt]{amsart}
\usepackage{amsmath}
\usepackage[latin1]{inputenc}
% uncomment next line to get pdf files with hyperlinks
%\usepackage[pdftex,bookmarks=true]{hyperref}

\usepackage{boxedminipage}
\input{defalgo.tex}
\usepackage{program}
\usepackage{epsf}
\input{defcode}
\input{defmath.tex}
\def\cao{\c c\~ao}
\def\cc{\c c}
\def\coes{\c c\~oes}
\def\ii{\'{\i}}
\def\stdin{\emph{stdin}}
\def\stdout{\emph{stdout}}
\def\sqn{seqüência}
\def\ibf#1{\item\textbf{#1}}
\title{Exercícios: 0}

\author{Raul H.C. Lopes}

\begin{document}

\maketitle
\section{Introdu\cao}
A lista a seguir apresenta uma série de exercícios que você pode considerar
como ``treino coletivo'' para os grandes jogos que se aproximam. Você
encontrará aqui exercícios sobre os fundamentos de análise e corre\cao\ de
algoritmos vistos até agora. Importante: não existe (como não poderia haver)
a pretensão de cobrir tudo o que foi apresentado.

\subsection{Notação}

  Assumindo que $P$ é um predicado

  \begin{equation*}
    [P] = 
    \begin{cases}
      1 \text{, if } P \\
      0 \text{, if } \neg P
    \end{cases}
  \end{equation*}


\section{Crescimento de funções}

\begin{enumerate}
  \item O que você entende por 
    \begin{itemize}
      \item $\inbigtheta{f(n)}{g(n)}$
      \item $\inbigo{f(n)}{g(n)}$
      \item $\inbigomega{f(n)}{g(n)}$
    \end{itemize}
  \item Por que escrever
\[ \inbigo{f(n)}{g(n)}\]
é mais adequado do que 
\[ f(n) = \bigo{f(n)} \] 
  \item Mostre as seguintes rela\coes\ são transitivas e reflexivas:
    \begin{itemize}
      \item $\inbigtheta{f(n)}{g(n)}$
      \item $\inbigo{f(n)}{g(n)}$
      \item $\inbigomega{f(n)}{g(n)}$
    \end{itemize}
  \item Prove a simetria  de \inbigtheta{f(n)}{g(n)}
  \item Dada soma
\[ s(n) = \sum_{\lele{0}{i}{d} a_i n^i} \]
prove:
\begin{enumerate}
  \item \[ \inbigo{s(n)}{n^k}\text{, when } k\ge d\]
  \item \[ \inbigomega{s(n)}{n^k}\text{, when } k\le d\]
  \item \[ \inbigtheta{s(n)}{n^k}\text{, when } k=d\]
\end{enumerate}
\item Prove que \[\inbigo{\log{n!}}{n\lg{n}}.\]

\end{enumerate}

\section{Somas e recorrências}
\begin{enumerate}
  \item Para cada uma das seguintes recorrências, faça:
    \begin{itemize}
      \item Escreva, se possível, a recorrência como somatória.
      \item Resolva a recorrência, encontrando uma fórmula fechada.

Não use indu\cao\ neste passo, nem métodos trivialoides como: \emph{guess
and prove}, olhar em uma referência, usar o \emph{Master method}, etc.
O objetivo é exercitar o desenvolvimento da recorrência. Lembre-se:
aplicar uma fórmula pronta até um colegial consegue. Melhor que isso é
desenvolver a fórmula.
      \item estabeleça claramente a restri\coes\ que devem ser satisfeitas
para sua fórmual ser válida;
      \item use indu\cao\ para provar a corre\cao\ de sua solu\cao.
    \end{itemize}
    \begin{enumerate}
      \item \begin{align*}
             U_0 & = a \\
             U_n & = b+U_{n-1}
            \end{align*}
      \item \begin{align*}
             U_0 & = a \\
             U_n & = b^n+U_{n-1}
            \end{align*}
      \item \begin{align*}
             U_0 & = a \\
             U_n & = c b^n+U_{n-1}
            \end{align*}
      \item \begin{align*}
             U_0 & = 0 \\
             U_n & = 2 U_{n-1} + 1
            \end{align*}
      \item \begin{align*}
             U_0 & = 0 \\
             U_n & = 3 U_{n-1} + 2
            \end{align*}
      \item \begin{align*}
             U_0 & = 0 \\
             U_n & = U_{n-1} + \log n
            \end{align*}

    \end{enumerate}

\item Resolva as seguintes somas:
  \begin{enumerate}
    \item \[\sum_{k=4}^0 a^k \]
    \item \[\sum_{i\le k < n} f(k)\text{, when } i=n\]
    \item \[\sum_{\lelt{0}{i}{n}} i[P(i)]\text{, onde } P(i) \text{ significa } i\text{ é par}\]
    \item \[\sum_{1\le k\le n} k^2\]
    \item \[\sum_{k=1}^{n} k2^k\]
    \item 
  \end{enumerate}

\end{enumerate}

\section{Complexidade em árvores}
\subsection{Árvores binárias}
Dada uma árvore binária $t$:
\begin{enumerate}
  \item Defina o grau de qualquer nó de $t$.
  \item Estabeleça o máximo de nós no nível $l$.
  \item Defina recorrência (e resolva-a) para o máximo de nós em
uma árvore com $k$ níveis.
  \item Estabeleça os números máximo e mínimo de níveis em
uma árvore com $n$ nós.
  \item Mostre que a busca pela versão ordenada de uma \sqn\ (ordena\cao\
por compara\cao) pode ser vista como uma busca em uma árvore binária 
de decisão.
  \item Quantas folhas teria a árvore de decisão do exercício anterior?
  \item Qual seria o número mínimo de níveis dessa árvores?
  \item Use essa árvore de decisão para achar o número mínimo de
compara\coes\ que qualquer algoritmo de ordena\cao\ por compara\cao\
de chaves deve realizar.
\end{enumerate}

\subsection{Árvores B}

Dada uma árvore B de ordem $m$, encontre (e prove):
\begin{enumerate}
  \item o número máximo de nós;
  \item o número mínimo de nós;
  \item o número máximo de níveis;
  \item o número mínimio de níveis.
\end{enumerate}

\section{Correção de algoritmos}

Os exercícios desta seção são pre-requisitos para quem pretende resolver
qualquer trabalho em \textbf{ACL2}: se você não consegue resolvê-los,
implemente seus trabalhos em C/C++/Ada.

\begin{enumerate}
\item Defina as invariantes das seguintes estruturas de dados:
\begin{enumerate}
  \item Stack.
  \item Fila (FIFO).
  \item Árvore binária.
  \item Árvore binária de pesquisa.
  \item Heap.
  \item Árvore B.
\end{enumerate}



\item Defina algoritmos recursivos para operar sobre naturais que usem apenas
opera\coes\ de incremento/decremento de $1$ e compara\cao\ com $0$.
\begin{itemize}
  \item Soma.
  \item Subtra\cao.
  \item Multiplica\cao.
  \item Divisão.
\end{itemize}

\item Defina invariantes que relacionam soma com subtra\cao\ e divisão com
multiplica\cao, prove-as usando ACL2.

\item Defina propriedades invariantes de uma concatena\cao\ de stacks.
\end{enumerate}

\bibliography{abbrev,analysis,formal,algorithms,program,string}

\bibliographystyle{amsplain}


\end{document}

