\documentclass[11pt,a4paper]{article}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

\usepackage{fullpage}
 
\newcounter{conta}

\begin{document}
 
\noindent Universidade Federal de Minas Gerais \\
{\it DCC129: Fundamentos da Teoria da Computação}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2015 \\
Horário: \parbox[t]{15cm}{Turma N: 3a. e 5a. 16:40 às 18:20h $-$ Sala 1024} \\
Professor: Newton José Vieira \hfill ICEx/sala 4023, www.dcc.ufmg.br/\verb+~+nvieira \\
{\bf\large Plano de Curso}

\section{Programa}
 
\begin{list}{\arabic{conta}}{\usecounter{conta}}
 \item Conceitos Preliminares: representação; prova de teoremas; conjuntos; relações; funções; conjuntos enumeráveis;
       definições recursivas; indução matemática; grafos; linguagens formais; gramáticas; problemas de decisão.
 \item Máquinas de Estados Finitos: alguns exemplos; autômatos finitos determinísticos; autômatos finitos não
       determinísticos; linguagens regulares: propriedades; máquinas de Mealy e de Moore; expressões regulares; gramáticas
			 regulares; linguagens regulares: conclusão.
 \item Autômatos de Pilha: uma introdução informal; autômatos de pilha determinísticos; autômatos de pilha não
       determinísticos; gramáticas livres do contexto; linguagens livres do contexto: propriedades.
 \item Máquinas de Turing: o que é máquina de Turing; algumas variações de máquinas de Turing; gramáticas e máquinas de
       Turing; propriedades das linguagens recursivamente enumeráveis e linguagens recursivas.
 \item Decidibilidade: a tese de Church-Turing; máquina de Turing universal; o problema da parada; redutibilidade; exemplos
       de problemas indecidíveis.
\end{list}

\section{Bibliografia}
 
O programa será desenvolvido com base no livro-texto:
\begin{itemize}
 \item Vieira, N.J. {\em Introdução aos Fundamentos da Computação: Linguagens e Máquinas}, Pioneira Thomson Learning
       (atualmente, CENGAGE), 2006.
\end{itemize}
%O livro pode ser encontrado na Livraria da UFMG situada na praça de serviços. 

A seguinte lista de livros contém outras abordagens para os assuntos constantes do programa, assim como exercí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 Anderson, J.A. {\it Automata Theory with Modern Applications\/}, Cambridge University Press, 2006.

 \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. (Há uma tradução publicada pela Campus em 2003.)

       \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ômatos\/}, $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 Rosa, J.L.G., {\it Linguagens Formais e Autômatos}, LTC, 2010.

       \label{Rosa}

 \item Rosenberg, A.L., {\it The Pillars of Computation Theory}, Springer, 2009.

       \label{Rosenberg}

 \item Sipser, M., {\it Introduction to Theory of Computation}, 2nd ed., Course
       Technology, 2005. (Há uma tradução 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á disponível na biblioteca do ICEx (sala 4222). Aos alunos que tenham uma menor maturidade matemática ou que desejem consultar um texto que tenha pretensões mais didáticas, recomenda-se qualquer um dos seguintes: \ref{Cohen}, \ref{Drobot}, \ref{Kelley}, \ref{Linz}, \ref{Martin}, \ref{Parkes}, \ref{Rosa}, \ref{Sipser} ou \ref{Sudkamp}. Especificamente sobre autômatos finitos, recomenda-se \ref{Lawson}. Por outro lado, para aqueles que desejem um texto com mais ``substância'', recomenda-se especialmente: \ref{Hopcroft}, \ref{Kozen}, \ref{Moret} ou \ref{Rosenberg}.

\section{Avaliação}

Serão distribuídas 3 listas de exercícios, valendo 10 pontos cada uma, e aplicadas 3 provas  valendo 24, 23 e 23 pontos.%Além disso, estarão disponíveis no Moodle alguns testes, para auto-avaliação, na medida em que a matéria for sendo coberta. Em tais testes, ao responder a uma pergunta, o aluno receberá uma indicação imediata se sua resposta está certa ou errada. O objetivo das listas preparatórias e dos testes é servir como auxílio ao aprendizado. Em cada prova irá cair no mínimo uma das questões de auto-avaliação e no mínimo um dos exercícios da lista preparatória respectiva.

Além das informações no Moodle, outras, como soluções de exercícios e provas de semestres anteriores, estarão disponiveis na página
\begin{center}
http://www.dcc.ufmg.br/\verb+~+nvieira
\end{center}
na entrada relativa \`a disciplina.

Para cada prova, será assumido que o aluno domina o assunto relativo aos capítulos anteriores aos marcados para a prova. Assim, na formulação das questões poderão ser utilizados conceitos e terminologias de assuntos cobertos em provas anteriores. 

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

De acordo com legislação da UFMG, a aprovação na disciplina está condicionada ao comparecimento de, no mínimo, 75\% da carga horária. O professor desta disciplina, em particular, só irá considerar pedidos de abonos de faltas no final do semestre, se o aluno tiver acumulado no mínimo 60 pontos. Assim, por exemplo, se o aluno tiver acumulado 59 pontos e tiver faltado a 26\% das aulas, ele será considerado infrequente e receberá o conceito F.

\end{document}
