\documentclass[12pt]{article}
\usepackage[portuges]{babel}
\usepackage[latin1]{inputenc}

\title{Projeto e Análise de Algoritmos}
\author{Raul H.C.Lopes}
\begin{document}
\maketitle

\section{Programa}

\begin{enumerate}
  \item Correção de programas em ACL2
  \begin{itemize}
    \item Funções aritméticas
    
    \item Listas
    
    \item Ordenação
    
    \item Árvores
  \end{itemize}
  \item Análise de algoritmos
  \begin{itemize}
    \item Crescimento de funções e notação assintótica
    
    \item Recorrências e somas
    
    \item Análise de pior caso e caso médio
  \end{itemize}
  \item Ordenação
  \begin{itemize}
    \item inserção
    
    \item troca
    
    \item seleção
    
    \item distribuição
  \end{itemize}
  \item Permutaçoes
  \begin{itemize}
    \item coeficientes binomiais
    
    \item funçoes geradoras
    
    \item permutações
  \end{itemize}
  \item Árvores
  \begin{itemize}
    \item Binárias
    
    \item B-trees
    
    \item Suffix trees and string matching
  \end{itemize}
  \item Heaps
  \begin{itemize}
    \item heapsort
  
    \item árvores de prioridade
  
    \item heaps binomiais
  \end{itemize}
  \item busca geométrica e em grafos
  \begin{itemize}
    \item range searching
    
    \item hulls
    
    \item árvores geradoras
    
    \item caminho mais curto
 
    \item busca em árvores
    
  \end{itemize}
  \item Teoria NP

\end{enumerate}

\section{Referências básicas}

\begin{itemize}
  \item Introduction to Algorithms
  
  \textit{T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein}
  
  \item The Art of Computer Programming: Vol. I, III
  
  \textit{D.E. Knuth}

  \item Analysis of Algorithms
  
  \textit{R. Sedgewick, P. Flajolet}
  
  \item Concrete Mathematics
  
  \textit{R.L.Graham,D.E. Knuth, O. Patashnik}
  
  \item An Introduction to Combinatorial Analysis
  
  \textit{J. Riordan}
  
  \item The Science of Programming
  
  \textit{D. Gries}

  \item A methodology of programming
  
  \textit{E. W. Dijkstra and W.H.J. Feijen}
  
  \item PVS  em \textbf{http://www.pvs.csl.sri.com}
  
  Manuais, tutoriais, artigos, provador.
  
  \item ACL2 em \textbf{tools/acl2.tar.gz}
  
  Manuais, tutoriais, artigos, provador.

\end{itemize}


\section{ Regras de Avaliação}
O processo de avaliação será realizado através de 2 provas (obrigatórias)
e 4 trabalhos (opcionais) de implementação. Estão definidas duas linhas
distintas de avaliação: teórica pura, mista.
\subsection{Avaliação téorica em complexidade e correção de programas}
O aluno pode optar por realizar dois trabalhos teóricos nas áreas
de: correçao de programas, usando as ferramentas \textbf{ACL2}, \textbf{PVS}
ou \textbf{Coq}, complexidade de algoritmos, exercício teórico, possivelmente,
usando \textbf{MuPAD} ou \textbf{Singular}.

Estes trabalhos substituem as duas provas, isso significando que o aluno
que optar por esta linha será avaliado exclusivamente pelos 2 trabalhos.

A nota final neste caso é dada pela média dos dois trabalhos.
\subsection{Avaliação mista  em complexidade e correção de programas}
O aluno que  optar por esta linha de avaliação deverá realizar obrigatoriamente
2 provas. Além disso, poderá opcionalmente implementar até 4 trabalhos 
práticos.

A nota final será dada pela seguinte fórmula
\[ \frac{((P_0+P_1)/2)*(10-t)+\sum_{0\le i<t}T_i}{10} \]
onde:
\begin{itemize}
  \item $t (0\le t < 5)$ é o número de trabalhos implementados pelo aluno;
  \item $P_0, P_1$ são as notas das provas $0$ e $1$;
  \item $T_i$, são as notas dos trabalhos.
\end{itemize}
\section{Datas das Provas }

\begin{enumerate}
  \item Prova 0
  \begin{enumerate}
    \item Data: 04/02/03
  \end{enumerate}
  \item Prova 1
  \begin{enumerate}
    \item Data: 25/03/03
  \end{enumerate}
\end{enumerate}

\section{ Trabalhos }

Primeiro trabalho prático e primeiro trabalho teórico nesta página, no próximo
dia 13/01.

\end{document}
