 
 
\documentstyle[12pt]{artigo}
 
\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\noindent P\'os-Gradua\c{c}\~ao 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 1993
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Plano de Curso}
 
\section{Ementa}
 
Classifica\c{c}\~ao e propriedades das gram\'aticas, aut\^omatos e linguagens
formais. Decidibilidade. Computabilidade.
 
\section{Programa}
 
\begin{list}{\arabic{conta}}{\usecounter{conta}}
 \item Conceitos B\'asicos de Matem\'atica
 \begin{list}{\arabic{conta}.\arabic{conta2}}{\usecounter{conta2}}
  \item Conceitos B\'asicos de Teoria dos Conjuntos
  \item Rela\c c\~oes e fun\c c\~oes
  \item Defini\c c\~oes recursivas
  \item Conceitos b\'asicos de grafos
  \item Indu\c c\~ao matem\'atica
 \end{list}
 \item Linguagens Formais
 \begin{list}{\arabic{conta}.\arabic{conta2}}{\usecounter{conta2}}
  \item Linguagens regulares
  \begin{itemize}
   \item express\~oes regulares
   \item gram\'aticas regulares
   \item aut\^omatos finitos
   \item propriedades
  \end{itemize}
  \item Linguagens livres do contexto
  \begin{itemize}
   \item gram\'aticas livres do contexto
   \item aut\^omatos a pilha
   \item propriedades
  \end{itemize}
  \item Linguagens sens\'{\i}veis ao contexto
  \begin{itemize}
   \item gram\'aticas sens\'{\i}veis ao contexto
   \item aut\^omatos lineares limitados
   \item propriedades
  \end{itemize}
  \item Linguagens recursivamente enumer\'aveis
  \begin{itemize}
   \item gram\'aticas irrestritas
   \item m\'aquinas de Turing
   \item linguagens recursivas
   \item propriedades
  \end{itemize}
 \end{list}
 \item Decidibilidade e Computabilidade
 \begin{list}{\arabic{conta}.\arabic{conta2}}{\usecounter{conta2}}
  \item Decidibilidade
  \begin{itemize}
   \item problemas de decis\~ao
   \item tese de Church-Turing
   \item o problema da parada
   \item m\'aquina de Turing universal
   \item redutibilidade
   \item exemplos de problemas indecid\'{\i}veis
  \end{itemize}
  \item Computa\c c\~ao num\'erica
  \begin{itemize}
   \item computa\c c\~ao de fun\c c\~oes
   \item computa\c c\~ao num\'erica
   \item composi\c c\~ao de fun\c c\~oes
   \item fun\c c\~oes n\~ao comput\'aveis
  \end{itemize}
 \end{list}
\end{list}
 
\section{Bibliografia}
 
O programa ser\'a desenvolvido com base nos cap\'{\i}tulos 1 a 12 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 Lewis, H.R., Papadimitriou, C.H. {\it Elements of the Theory of
 Computation\/}, Prentice-Hall, 1981.
\end{itemize}
 
\section{Avalia\c{c}\~ao}
 
Ser\~ao aplicadas 4 provas de 25 pontos cada uma.
 
\end{document}
\endinput
\end
 
