\documentclass[11pt]{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc} % isso é quase redundante
\usepackage{textcomp}
%\usepackage[T1]{fontenc}
%----------------------------
\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother

\def\ZZ{{\mathbb Z}}
\def\FF{{\mathbb F}}

\begin{document}
\title{Exercício Programa 1}
\maketitle
\thispagestyle{empty}

\noindent\textbf{Data de entrega:}\quad 10/10/2003

\subsection*{Aritmética modulo~$p$}
Seja~$p$ um número primo.  No que segue, escrevemos~$\ZZ/p\ZZ$ para o
conjunto~$\{0,1,\dots,p-1\}$.  Podemos definir operações de soma e produto
em~$\ZZ/p\ZZ$ da seguinte forma: dados~$a$ e~$b\in\ZZ/p\ZZ$, podemos
definir~$a+b\in\ZZ/p\ZZ$ como sendo
$$
(a+b)\pmod p,
$$
isto é, o resto da divisão de~$a+b$ por~$p$ (naturalmente, aqui entendemos
por~$a+b$ a soma usual de inteiros).  Analogamente, podemos
definir~$ab\in\ZZ/p\ZZ$ como sendo
$$
(ab)\pmod p,
$$
isto é, o resto da divisão de~$ab$ por~$p$ (aqui, $ab$~denota o produto usual
de inteiros). 

Às vezes, ao fazermos contas em~$\ZZ/p\ZZ$, é conveniente identificarmos
inteiros fora do conjunto~$\{0,1,\dots,p-1\}$ com elementos desse conjunto.  A
regra é simples: dado qualquer~$n$ inteiro, identificamos~$n$ com~$n\pmod p$,
o resto da divisão de~$n$ por~$p$.  Por exemplo, para~$p=7$, temos~$7=0$,
$8=1$, e~$13=-1$.

\subsubsection*{Exemplos}  Suponha que~$p=5$.  Então, em~$\ZZ/p\ZZ=\ZZ/5\ZZ$, temos
$2+4=1$ e~$2\times 4=3$.  Em~$\ZZ/2\ZZ$ (isto é, $p=2$), temos~$1+1=0$
e~$1\times0=0$.

\subsection*{Aritmética de polinômios} Consideraremos agora polinômios na
variável (ou indeterminada)~$x$, com coeficientes inteiros.  Usualmente, o
conjunto de tais polinômios é denotado por~$\ZZ[x]$.  Você conhece as
operações de soma e produto de tais polinômios.  

Suponha agora que temos um número primo~$p$ fixo.  Podemos agora passar a
considerar os coeficientes dos nossos polinômios como elementos
de~$\ZZ/p\ZZ$.  Por exemplo, se~$p=3$, então os polinômios
$$
4x^3+8x+1,\quad x^{10}+1,\quad\text{e}\quad5x^2-x+1 
$$
de~$\ZZ[x]$ podem ser entedidos, respectivamente, como os polinômios
$$
x^3+2x+1,\quad x^{10}+1,\quad\text{e}\quad-x^2-x+1 
$$
em~$(\ZZ/3\ZZ)[x]$.  Naturalmente, podemos tambem definir a soma e produto de
polinômios com coeficientes em~$\ZZ/p\ZZ$ de forma natural.

\subsubsection*{Exemplos}  Suponha que~$p=3$.  Então, em~$(\ZZ/3\ZZ)[x]$, temos 
$$
(x^3+2x+1)+(x^{10}+1)+(-x^2-x+1)=x^{10}+x^3-x^2+x
$$
e
$$
(x+1)(2x-1)=2x^2+x-1,\quad(x+1)^5=x^5-x^4+x^3+x^2-x+1.
$$

\subsection*{Os cálculos} Neste exercício, você deve calcular (isto é, expandir)
os seguintes polinômios:
\begin{enumerate}
\item Em~$(\ZZ/2\ZZ)[x]$:
  $$
  (1+x)^3,\quad(1+x)^4,\quad(1+x)^{15},\quad(1+x)^{16},
  $$
  e
  $$
  (x^4+x+1)^{15}.
  $$

\item
    Em~$(\ZZ/3\ZZ)[x]$:
    $$
    (x^4+x^3+x^2-x-1)^{80}.
    $$

\item\textbf{(Item revisado!)}
 Em~$(\ZZ/7\ZZ)[x]$:
  $$
  (x^4-x^3-x^2-2x-2)^{2400},\quad(x^4-3x^3+5x^2+2x+3)^{2400}.
  $$
  Em vez de imprimir estes polinômios em sua saída (a saída seria muito
  extensa), escreva seu programa de forma que o usuário pode examinar o
  coeficiente de~$x^k$ para qualquer~$k$.  Use seu programa para determinar o
  coeficiente de~$x^k$ para todo~$k\leq20$ e para~$k=9487$, $k=9485$,
  e~$k=9370$. 
\end{enumerate}

\subsection*{Estratégia} Naturalmente, o que você deve fazer é escrever várias
funções em~C que manipulam polinômios com coeficientes em~$\ZZ/p\ZZ$.  Para
tanto, você vai achar conveniente implementar, inicialmente, funções para
calcular somas e produtos em~$\ZZ/p\ZZ$.  Feito isto, a sua tarefa é escrever
funções para fazer cálculos com polinômios em~$(\ZZ/p\ZZ)[x]$.

Você deve, \textit{obrigatoriamente}, representar os polinômios em seu
programa como listas ligadas, com as células representando os monômios, isto
é, parcelas como~$3x^5$ (a informação contida na célula correspondente a este
monômio seria o par de inteiros~$(3,5)$).  Fica a seu critério escolher que
tipo de lista ligada usar (linear, circular, com ou sem cabeça, etc).  Faça um
boa escolha!

\textbf{Note que este EP tem uma continuação!!!}

\subsection*{}\textbf{Observações}

\small
\begin{enumerate}
\item \textit{Este EP é estritamente individual}.  Exercícios semelhantes
  receberão nota~$0$.
\item Seja cuidadoso com sua programação (correção, documentação,
  apresentação, clareza do código, etc), dando especial atenção a suas
  estruturas de dados.  A correção será feita levando isso em conta.
\item Comparem entre vocês o desempenho de seus programas.
\item Entregue o seu EP através do sistema PANDA.
\item Não deixe de incluir em seu código um \textit{relatório} para discutir
  seu EP: discuta as estruturas de dados usadas, os algoritmos usados, etc.
  \textit{Se você escrever claramente como funciona seu EP, o monitor terá
    pouca dificuldade em corrigi-lo, e assim você terá uma nota mais alta.}
  (Se o monitor sofrer para entender seu código, você pode imaginar o humor
  dele ao atribuir sua nota.)
\end{enumerate}

\subsubsection*{Observação final}  Enviem dúvidas para a lista de discussão da
disciplina.

\end{document}

% Local Variables: 
% mode: latex
% eval: (Portug-mode)
% TeX-master: t
% End: 
