\documentstyle[12pt]{artigo}
 
\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 1996
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Plano de Curso}
 
\section{Programa}
 
\begin{list}{\arabic{conta}}{\usecounter{conta}}
 \item Conceitos B\'asicos de Matem\'atica: conceitos b\'asicos de teoria dos
       conjuntos; rela\c c\~oes e fun\c c\~oes; defini\c c\~oes recursivas;
       conceitos b\'asicos de grafos; indu\c c\~ao matem\'atica.
 \item Linguagens Formais
 \begin{list}{\arabic{conta}.\arabic{conta2}}{\usecounter{conta2}}
  \item Linguagens regulares: express\~oes regulares; gram\'aticas regulares;
        aut\^omatos finitos; propriedades.
  \item Linguagens livres do contexto: gram\'aticas livres do contexto;
        aut\^omatos a pilha; propriedades.
  \item Linguagens sens\'{\i}veis ao contexto: gram\'aticas sens\'{\i}veis ao contexto;
        aut\^omatos lineares limitados; propriedades.
  \item Linguagens recursivamente enumer\'aveis: gram\'aticas irrestritas;
        m\'aquinas de Turing; linguagens recursivas; propriedades.
 \end{list}
 \item Decidibilidade: problemas de decis\~ao; tese de Church-Turing; o problema
       da parada m\'aquina de Turing universal; redutibilidade; exemplos de
       problemas indecid\'{\i}veis
\end{list}
 
\section{Bibliografia}
 
O programa ser\'a desenvolvido com base nos cap\'{\i}tulos 1 a 11 de:
 
\begin{itemize}
 \item Sudkamp, T.A. {\it Languages and Machines: An Introduction to the
  Theory of Computer Science\/}, Addison-Wesley, 1988.
\end{itemize}
 
A seguinte bibliografia cont\'em outras abordagens para os mesmos assuntos, e
exerc\'{\i}cios adicionais:
 
\begin{itemize}
 \item Aho, A.V., Ullman, J.D. {\it The Theory of Parsing, Translation and
 Compiling\/}, vol I: {\it Parsing\/}, Prentice-Hall, 1972.
 \item Denning, P.J., Dennis, J.B., Qualitz, J.E. {\it Machines, Languages and
 Computation\/}, Prentice-Hall, 1978.
 \item Hopcroft, J.E., Ullman, J.D. {\it Formal Languages and Their Relation
 to Automata\/}, Addison-Wesley, 1969.
 \item Hopcroft, J.E., Ullman, J.D. {\it Introduction to Automata Theory,
 Languages and Computation\/}, Addison-Wesley, 1979.
 \item Kelley, D. {\it Automata and Formal Languages: an introduction\/},
       Prentice-Hall, 1995.
 \item Lewis, H.R., Papadimitriou, C.H. {\it Elements of the Theory of
 Computation\/}, Prentice-Hall, 1981.
\end{itemize}
 
\section{Avalia\c{c}\~ao}
 
Ser\~{a}o distribu\'{\i}das 11 listas de exerc\'{\i}cios, cada lista relativa a um cap\'{\i}tulo
do livro texto. Cada lista vale 3 pontos, e pode ser feita por um grupo de, no
m\'{a}ximo, 2 alunos. Ser\~{a}o aplicadas 4 provas, a primeira valendo 13 pontos e as
restantes valaendo 18 pontos cada uma.
 
Seguem os assuntos cobertos por cada prova/lista de exerc\'{\i}cio, em termos dos
cap\'{\i}tulos do livro texto, assim como suas datas de realiza\c{c}\~{a}o/entrega
prov\'{a}veis:

\begin{center} 
\begin{tabular}{|c|c|c||c|l|c|c|} \hline
 Lista & Cap\'{\i}tulo & Entrega prov\'{a}vel & Prova & Cap\'{\i}tulos & Data prov\'{a}vel &
      Valor \\ \hline
  1    & 1    & 03/09 & 1    & 1, 2      & 03/09 & 13 \\
  2    & 2    & 03/09 & 2    & 3, 4, 5   & 26/09 & 18 \\ \cline{1-3}
  3    & 3    & 26/09 & 3    & 6, 7, 8   & 31/10 & 18 \\
  4    & 4    & 26/09 & 4    & 9, 10, 11 & 28/11 & 18 \\ \cline{4-7}
  5    & 5    & 26/09  \\ \cline{1-3}
  6    & 6    & 31/10  \\
  7    & 7    & 31/10  \\
  8    & 8    & 31/10  \\ \cline{1-3}
  9    & 9    & 28/11  \\ 
  10   & 10   & 28/11  \\ 
  11   & 11   & 28/11  \\ \cline{1-3}
\end{tabular}
\end{center}

%\end{document}

\section{Cronograma das Aulas}

\begin{tabular}{rcl}
 \multicolumn{1}{c}{\it Aula} & {\it Data} & \multicolumn{1}{c}{\it Assunto} \\
 01-02 & 13/08 & Apresenta\c{c}\~{a}o do plano de curso \\
 03-04 & 20/08 & 1.1, 1.2, 1.3 \\
 05-06 & 22/08 & 1.4, 1.5, 1.6 \\
 07-08 & 27/08 & 2 \\
 09-10 & 29/08 & Revis\~{a}o \\ \cline{2-3}
 11-12 & \multicolumn{1}{|c}{03/09} & \multicolumn{1}{l|}{Primeira prova}
  \\ \cline{2-3}
 13-14 & 05/09 & 3.1, 3.2, 3.3 \\
 15-16 & 10/09 & 3.4, 3.5, 3.6 \\
 17-18 & 12/09 & 4 \\
 19-20 & 17/09 & 5.1, 5.2, 5.3 \\
 21-22 & 19/09 & 5.4, 5.5, 5.6 \\
 23-24 & 24/09 & Revis\~{a}o \\ \cline{2-3}
 25-26 & \multicolumn{1}{|c}{26/09} & \multicolumn{1}{l|}{Segunda prova}
  \\ \cline{2-3}
 27-28 & 01/10 & 6.1, 6.2, 6.3 \\
 29-30 & 08/10 & 6.4, 6.5, 6.6 \\
 31-32 & 10/10 & 6.7, 6.8, 6.9 \\
 33-34 & 15/10 & 7.1, 7.2 \\
 35-36 & 17/10 & 7.3, 7.4 \\
 37-38 & 22/10 & 8.1, 8.2, 8.3 \\
 39-40 & 24/10 & 8.4, 8.5, 8.6 \\
 41-42 & 29/10 & Revis\~{a}o \\ \cline{2-3}
 43-44 & \multicolumn{1}{|c}{31/10} & \multicolumn{1}{l|}{Terceira prova}
  \\ \cline{2-3}
 45-46 & 05/11 & 9.1, 9.2, 9.3 \\
 47-48 & 07/11 & 9.4, 9.5, 9.6 \\
 49-50 & 12/11 & 10 \\
 51-52 & 14/11 & 11.1, 11.2, 11.3 \\
 53-54 & 19/11 & 11.4, 11.5, 11.6 \\
 55-56 & 21/11 & 11.7, 11.8 \\
 57-58 & 26/11 & Revis\~{a}o \\ \cline{2-3}
 59-60 & \multicolumn{1}{|c}{28/11} & \multicolumn{1}{l|}{Quarta prova}
  \\ \cline{2-3}
\end{tabular}
 
\end{document}
\endinput
\end
 
