\documentclass[12pt,a4paper]{article}
 
\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 2001
 
\noindent Prof.: Newton Jos\'{e} Vieira \hfill Sala 4023/ICEx; e-mail: nvieira@dcc.ufmg.br
 
\noindent {\bf Plano de Curso}
 
\section{Programa}
 
\begin{list}{\arabic{conta}}{\usecounter{conta}}
 \item Conceitos Preliminares: representa\c c\~ao; prova de teoremas; conjuntos;
       rela\c c\~oes; fun\c c\~oes; conjuntos enumer\'aveis; defini\c c\~oes recursivas;
       indu\c c\~ao matem\'atica; grafos; linguagens formais; gram\'aticas; problemas de
       decis\~ao.
 \item M\'aquinas de Estado-Finito: alguns exemplos; aut\^omatos finitos
       determin\'{\i}sticos; aut\^omatos finitos n\~ao determin\'{\i}sticos; linguagens
       regulares: propriedades; m\'aquinas de Mealy e de Moore; express\~oes
       regulares; gram\'aticas regulares; linguagens regulares: conclus\~ao.
 \item Aut\^omatos com Pilha: uma introdu\c c\~ao informal; aut\^omatos com pilha
       determin\'{\i}sticos; aut\^omatos com pilha n\~ao determin\'{\i}sticos;
       gram\'aticas livres do contexto; linguagens livres do contexto: propriedades.
 \item M\'aquinas de Turing: o que \'e m\'aquina de Turing; algumas varia\c c\~oes
       de m\'aquinas de Turing; gram\'aticas e m\'aquinas de Turing; propriedades das
       linguagens recursivamente enumer\'aveis e linguagens recursivas.
 \item Decidibilidade: a tese de Church-Turing; m\'aquina de Turing universal; o
       problema da parada; redutibilidade; exemplos de problemas indecid\'{\i}veis.
\end{list}
 
\section{Bibliografia}
 
O programa ser\'a desenvolvido com base em uma apostila a ser distribu\'{\i}da
durante o semestre. Os cap\'{\i}tulos estar\~ao dispon\'{\i}veis em
\begin{center}
http://www.dcc.ufmg.br/\verb+~+nvieira
\end{center}
na entrada
\begin{center}
 Cursos de gradua\c c\~ao/Fundamentos da Teoria da Computa\c c\~ao/[2001/2]
\end{center}
na medida em que ficarem prontos, no formato PostScript.
Alternativamente, existir\'a uma vers\~ao em papel para os que preferirem tirar
fotoc\'opia.

A seguinte lista de livros cont\'em outras abordagens para os assuntos constantes do
programa, assim como exerc\'{\i}cios adicionais. Os livros mais avan\c cados ou que
demandem uma maior maturidade matem\'atica est\~ao marcados com asteriscos.

\begin{enumerate}
 \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 Floyd. R.M., Beigel, R. {\it The Language of Machines: An introduction to
       computability and formal languages\/}, Computer Science Press, 1994.
 \item Greenlaw, R., Hoover, H.J. {\it Fundamentals of the Theory of Computation\/},
       Morgan Kauffmann, 1998.
 \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 Hopcroft, J.E., Motwani, R., Ullman, J.D. {\it Introduction to Automata Theory,
       Languages, and Computation\/}, 2nd ed., Addison-Wesley, 2001.
 \item *Howie, J.M. {\it Automata and Languages\/}, Oxford University Press, 1991.
 \item Kelley, D. {\it Automata and Formal Languages: an introduction\/},
       Prentice-Hall, 1995.
 \item *Kozen, D.C. {\it Automata and Computability\/}, Springer, 1997.
 \item Lewis, H.R., Papadimitriou, C.H. {\it Elements of the Theory of
       Computation\/}, Prentice-Hall, 1981.
 \item Martin, J.C. {\it Introduction to Languages and the Theory of
       Computation\/}, McGraw-Hill, 1991.
 \item Menezes, P.B. {\it Linguagens Formais e Aut\^omatos\/}, $2^{\mbox{\underline{a}}}$
       ed., Sagra Luzzatto, 1998.
 \item *Moret, B.M. {\it The Theory of Computation\/}, Addison-Wesley, 1998.
 \item R\`ev\`esz, G.E. {\it Introduction to Formal Languages\/}, Dover, 1983.
 \item Sipser, M., {\it Introduction to Theory of Computation}, PWS Publishing
       Co., 1997.
 \item Sudkamp, T.A. {\it Languages and Machines: An Introduction to the
       Theory of Computer Science\/}, 2nd ed., Addison-Wesley, 1997.
 \item Taylor, R.G., {\it Models of Computation and Formal Languages\/}, Oxford University
       Press, 1998.
 \item Wood, D., {\it Theory of Computation}, John Wiley \& Sons, 1987.
\end{enumerate}
Grande parte destes livros est\'a dispon\'{\i}vel na biblioteca do ICEx (sala 4222).

\section{Avalia\c{c}\~ao}

Ser\~ao distribuidas 4 listas de exerc\'{\i}cios, valendo 10 pontos cada uma, e
ser\~ao aplicadas 4 provas, valendo 15 pontos cada uma.

A $i$-\'esima lista de exerc\'{\i}cios ser\'a distribu\'{\i}da antes da $i$-\'esima
prova (com bastante anteced\^encia). Tal lista constar\'a de exerc\'{\i}cios da apostila com
graus de dificuldade similares aos da prova que ser\'a aplicada em seguida.
Recomenda-se fortemente que os exerc\'{\i}cios das listas (melhor ainda, todos
os exerc\'{\i}cios da apostila) sejam resolvidos na medida em que a mat\'eria
correspondente for sendo coberta durante o curso.

As listas de exerc\'{\i}cios, assim como este Plano de Curso e outras informa\c c\~oes (como
solu\c c\~oes de exerc\'{\i}cios e provas de semestres anteriores), estar\~ao disponiveis na p\'agina
http://www.dcc.ufmg.br/\verb+~+nvieira, na entrada relativa \`a disciplina.

\end{document}
\section{Cronograma das Aulas}

\begin{tabular}{rcl}
 \multicolumn{1}{c}{\it Aula} & {\it Data} & \multicolumn{1}{c}{\it Assunto} \\
 01-02 & 06/08 & Apresenta\c{c}\~{a}o do plano de curso \\
 03-04 & 08/08 & 0.1, 0.2, 0.3 \\
 05-06 & 13/08 & 0.4, 0.5, 0.6 \\
 ---   & 15/08 & Feriado municipal: Assun\c c\~ao de N. Senhora \\
 07-08 & 20/08 & 0.7, 0.8, 0.9 \\
 09-10 & 22/08 & 0.10, 0.11, 0.12 \\ 
 11-12 & 27/08 & 1.1 \\
 13-14 & 29/08 & 1.2.1, 1.2.2 \\
 15-16 & 03/09 & 1.2.3 \\
 17-18 & 05/09 & 1.3.1, 1.3.2 \\
 19-20 & 10/09 & Prova (at\'e se\c c\~ao 1.2) \\
 21-22 & 12/09 & 1.3.3, 1.4.1, 1.4.2 \\
 23-24 & 17/09 & 1.5 \\
 25-26 & 19/09 & 1.6 \\
 27-28 & 24/09 & 1.7, 1.8 \\
 29-30 & 26/09 & 2.1, 2.2 \\
 31-32 & 01/10 & Prova (cap\'{\i}tulo 1)\\
 33-34 & 03/10 & 2.3 \\
 35-36 & 08/10 & 2.4.1, 2.4.2 \\
 37-38 & 10/10 & 2.4.3 \\
 ---   & 15/10 & Recesso: Comemora\c c\~ao dos dias do prof. e do FP \\
 39-40 & 17/10 & 2.4.4 \\
 41-42 & 22/10 & 2.5 \\
 43-44 & 24/10 & 3.1 \\
 45-46 & 29/10 & Prova (at\'e cap\'{\i}tulo 3) \\
 47-48 & 31/10 & 3.2 \\
 49-50 & 05/11 & 3.3, 3.4 \\
 51-52 & 07/11 & 4.1 \\
 53-54 & 12/11 & 4.2, 4.3 \\
 55-56 & 14/11 & 4.4, 4.5 \\
 57-58 & 19/11 & Revis\~{a}o \\
 59-60 & 21/11 & Prova (toda a mat\'eria) \\
\end{tabular}
 
\end{document}
\endinput
\end
 
