\documentclass[11pt]{article}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}

\pagestyle{empty}
\setlength{\textwidth}{16cm}
\setlength{\textheight}{24cm}
\setlength{\oddsidemargin}{0cm}
\setlength{\topmargin}{-1cm}

\newcommand{\N}{\mbox{{\bf N}}}
\newcommand{\Z}{\mbox{{\bf Z}}}
\newcommand{\R}{\mbox{{\bf R}}}
\newcommand{\sse}{\Longleftrightarrow}
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
\newcommand{\ceil} [1]{\lceil{#1}\rceil}


\def\risonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\smile$}}}$}}
\def\tristonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\frown$}}}$}}

\begin{document}

\begin{center}
{\large
{\bf 
MAC 5711 - Análise de Algoritmos \\
}
}
{\em Departamento de Ciência da Computação} \\
Segundo semestre de 2002 \\

\vspace{5mm}
{\large
{\bf Lista 2} \\
% (Valor: 40 pontos)\footnote{Você só precisa entregar as questões
% que tem valor marcado, mac claro que deve fazer todos \risonho} \\
}
\vspace{5mm}
% Devolução: 17 de março de 1999
\end{center}

\vspace{5mm}

\begin{enumerate}
  
\item Sejam $n \in \Z$ e $x \in \R$. Prove que
\begin{enumerate}
  \item $\floor{x} < n    \sse x < n;    \    n < \ceil{x} \sse n < x$.
  \item $n \leq \floor{x} \sse n \leq x; \ \ceil{x} \leq n \sse x \leq n$.
  \item $\floor{x} = n \sse x-1 < n \leq x \sse n \leq x < n+1$.
  \item $\ceil{x} = n  \sse x \leq n < x+1 \sse n-1 < x \leq n$.
  \item $\floor{-x} = - \ceil{x}$.
\end{enumerate}

\item Mostre que $\floor{x} + \floor{y} \leq \floor{x+y}$, com igualdade se e
  somente se (sse) $x+y-1 < \floor{x} + \floor{y}$. Encontre uma fórmula
  análoga para $\ceil{\ }$.

\item Mostre que se $x \in \R$, $m, n \in \Z$ e $n > 0$, então  
$ \left\lfloor\frac{x+m}{n}\right\rfloor = 
  \left\lfloor\frac{\floor{x}+m}{n}\right\rfloor.$

\item Para inteiros $n, m$, simplifique \\
(a) $\left\lfloor \frac{n+m}{2} \right \rfloor + 
     \left\lfloor \frac{n-m+1}{2} \right \rfloor$ \hspace{3cm}
(b) $\left\lceil \frac{n+m}{2} \right \rceil + 
     \left\lceil  \frac{n-m+1}{2} \right \rceil$.

\item Dê exemplos de funções $f, g: \N \rightarrow \N$ estritamente
  crescentes, tais que nem $f(n) = O(g(n))$ nem $g(n) = O(f(n))$.

\item Prove que, para todas funções $f, g: \N \rightarrow \N$,
\begin{enumerate}
  \item $af(n)+b = O(f(n))$ \ \ ($a, b$ constantes).
  \item $O(f(n)) + O(f(n)) = O(f(n))$.
  \item $O(O(f(n))) = O(f(n))$.
  \item $O(f(n)) O(g(n)) = O(f(n)g(n))$.
  \item $O(f(n)g(n)) = f(n) O(g(n))$.
\end{enumerate}

\item Prove que \\
(a) $\sum_{i=1}^{n} i^k$ é $\Theta(n^{k+1})$  \hspace{3cm} 
(b) $\sum_{i=1}^{n} \frac{i}{2^i} \leq 2$.

\item Suponha que $f: \N \rightarrow \N$ e $k \in \N$ são
  tais que $e^{f(n)} = O(n^k)$. Mostre que $f(n) = O(\log n)$.

\end{enumerate}

\end{document}

