\documentclass[11pt,a4paper]{article}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
 
\newcounter{conta}

\begin{document}
 
\noindent Universidade Federal de Minas Gerais \\
{\it DCC129: Fundamentos da Teoria da Computa\c{c}\~ao} $-$ Turmas B e E 
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2009 \\
Hor\'ario: \parbox[t]{15cm}{3a. e 5a. 11:10 \`as 12:50h $-$ Sala 2010 }
Professor: Newton Jos\'{e} Vieira \hfill ICEx/sala 4023, www.dcc.ufmg.br/\verb+~+nvieira \\
{\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 Estados Finitos: 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 de Pilha: uma introdu\c c\~ao informal; aut\^omatos de pilha
       determin\'{\i}sticos; aut\^omatos de 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 no livro-texto:
\begin{itemize}
 \item Vieira, N.J. {\em Introdu\c c\~ao aos Fundamentos da Computa\c c\~ao:
       Linguagens e M\'aquinas},
       Pioneira Thomson Learning, 2006.
\end{itemize}
O livro pode ser encontrado na Livraria da UFMG situada na pra\c{c}a de servi\c{c}os. Ele pode
tamb\'em ser encontrado em qualquer boa livraria do ramo, incluindo Cultura (www.livrariacultura.com.br),
Saraiva (www.livrariasaraiva.com.br), Siciliano (www.siciliano.com.br) e
Submarino (www.submarino.com.br).

A seguinte lista de livros cont\'em outras abordagens para os assuntos constantes do
programa, assim como exerc\'{\i}cios adicionais.

\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 Cohen, D.I.A., {\it Introduction to Computer Theory\/}, John Wiley \& Sons,
       1991.

       \label{Cohen}

 \item Denning, P.J., Dennis, J.B., Qualitz, J.E. {\it Machines, Languages and
       Computation\/}, Prentice-Hall, 1978.

 \item Drobot, V., Dennis, J.B., Qualitz, J.E. {\it Formal Languages and Automata
       Theory\/}, Computer Science Press, 1989.

       \label{Drobot}

 \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\/}, 3rd ed., Addison-Wesley, 2006.

       \label{Hopcroft}

 \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.

       \label{Kelley}

 \item Kozen, D.C. {\it Automata and Computability\/}, Springer, 1997.

       \label{Kozen}

 \item Lawson, M.V., {\it Finite Automata\/}, Chapman \& Hall/CRC, 2004.

       \label{Lawson}

 \item Lewis, H.R., Papadimitriou, C.H. {\it Elements of the Theory of
       Computation\/}, Prentice-Hall, 1981.

 \item Linz, P., {\it An Introduction to Formal Languages and Automata\/}, 2nd ed.,
       Jones and Bartlett, 1997.

       \label{Linz}

 \item Martin, J.C. {\it Introduction to Languages and the Theory of
       Computation\/}, 3rd ed., McGraw-Hill, 2002.

       \label{Martin}

 \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.

       \label{Moret}

 \item Parkes, A.P. {\it Introduction to Languages, Machines and Logic: Computable
       Languages, Abstract Machines and Formal Logic\/}, Springer-Verlag, 2002.

       \label{Parkes}

 \item R\`ev\`esz, G.E. {\it Introduction to Formal Languages\/}, Dover, 1983.

 \item Rodger, S.H., {\it JFLAP: An Interactive Formal Languages and Automata Package},
       Jones \& Bartlett, 2006.

 \item Sipser, M., {\it Introduction to Theory of Computation}, 2nd ed., Course
       Technology, 2005. (H\'a uma tradu\c{c}\~ao publicada pela Thomson (que
       mudou o nome para Cengage) em 2007.)

       \label{Sipser}

 \item Sudkamp, T.A. {\it Languages and Machines: An Introduction to the
       Theory of Computer Science\/}, 2nd ed., Addison-Wesley, 1997.

       \label{Sudkamp}

 \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).
Aos alunos que tenham uma menor maturidade matem\'atica ou que desejem consultar
um texto que tenha pretens\~oes mais did\'aticas, recomenda-se qualquer um dos
seguintes: \ref{Cohen}, \ref{Drobot}, \ref{Kelley}, \ref{Linz}, \ref{Martin},
\ref{Parkes}, \ref{Sipser} ou \ref{Sudkamp}. Especificamente sobre aut\^omatos finitos,
recomenda-se \ref{Lawson}. Por outro lado, para aqueles que desejem
um texto com mais ``subst\^ancia'', recomenda-se especialmente: \ref{Hopcroft},
\ref{Kozen} ou \ref{Moret}.

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

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

Recomenda-se fortemente que os exerc\'{\i}cios da apostila no final de cada
se\c c\~ao sejam resolvidos na medida em que a mat\'eria correspondente for sendo
coberta durante o curso.

Os 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
\begin{center}
http://www.dcc.ufmg.br/\verb+~+nvieira
\end{center}
na entrada relativa \`a disciplina.

Para cada prova, ser\'a assumido que o aluno domina o assunto relativo aos
cap\'{\i}tulos anteriores aos marcados para a prova. Assim, na formula\c c\~ao
das quest\~oes poder\~ao ser utilizados conceitos e terminologias de
assuntos cobertos em provas anteriores. 

Durante as aulas poder\~ao ser propostos outros exerc\'{\i}cios, provas ou
quaisquer outros tipos de atividades valendo pontos extra ou para
substituir itens da avalia\c c\~ao normal. {\bf No entanto, o professor n\~ao
vai se preocupar em divulgar para alunos faltosos quaisquer atividades destas!}

De acordo com legisla\c c\~ao da UFMG, a aprova\c c\~ao na disciplina est\'a
condicionada ao comparecimento de, no m\'{\i}nimo, 75\% da carga hor\'aria. O
professor desta disciplina, em particular, s\'o ir\'a considerar pedidos de
abonos de faltas no final do semestre, se o aluno tiver acumulado no m\'{\i}nimo
60 pontos. Assim, por exemplo, se o aluno tiver acumulado 59 pontos e tiver
faltado a 30\% das aulas, ele ser\'a considerado infreq\"uente e receber\'a o
conceito F.

\end{document}
