\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 2016 \\
Horário: \parbox[t]{15cm}{Turma N: 3a. e 5a. 16:40 às 18:20h $-$ Sala 2008/ICEx} \\
Professor: Newton José Vieira \hfill sala 7328/Anexo U do ICEx \hfill 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. 
De forma alternativa ou complementar, o aluno poderá utilizar alguns dos livros referenciados a seguir.


\section{Bibliografia Adicional}

Algumas referências que tratam do item 1 do programa, referente ao conteúdo de matemática
discreta necessário para um bom acompanhamento do curso:
\begin{enumerate}
 \item Dean, N. {\em The Essence of Discrete Mathematics\/}, Prentice Hall, 1997.
 \item Grimaldi, R.P. {\em Discrete and Combinatorial Mathematics: An Applied Introduction\/},
       5th ed., Pearson, 2003.
 \item Rosen, K.H. {\em Discrete Mathematics and Its Applications\/},
       7th ed., McGraw-Hill, 2011. (Existe tradução pela McGraw-Hill da 6a ed., de 2009, com o
			 título \textit{Matemática Discreta e Suas Aplicações}.)
 \item Velleman, D.J. {\em How To Prove It\/}, 2nd ed., Cambridge University Press, 2006.
\end{enumerate}
Caso o aluno não domine algum tópico mencionado no item 1, com exceção de
linguagens formais, gramáticas e problemas de decisão, ele deverá
estudá-lo por conta própria, pois não haverá aula sobre o mesmo.

A seguinte lista de livros complementa o livro-texto e contém outras abordagens para os assuntos constantes dos itens 2 a 5 do programa, sendo que a maior parte deles pode ser consultada na biblioteca do ICEx (sala 4222):

\begin{enumerate}
 \item Greenlaw, R., Hoover, H.J. {\it Fundamentals of the Theory of Computation\/},
       Morgan Kauffmann, 1998.
 \item Hopcroft, J.E., Motwani, R., Ullman, J.D. {\it Introduction to Automata Theory,
       Languages and Computation\/}, 3rd ed., Addison-Wesley, 2006. (Existe tradução pela
			 Campus da 1a ed., de 2001, com o título \textit{Introdução à Teoria dos Autômatos,
			 Linguagens e Computação}.)
 \item Kelley, D. {\it Automata and Formal Languages: An Introduction\/}, Prentice-Hall, 1995.
 \item Kozen, D.C. {\it Automata and Computability\/}, Springer, 1997.
 \item Lawson, M.V., {\it Finite Automata\/}, Chapman \& Hall/CRC, 2004.
 \item Lewis, H.R., Papadimitriou, C.H. {\it Elements of the Theory of Computation\/}, 2nd ed.,
       Prentice-Hall, 2007.
 \item Linz, P., {\it An Introduction to Formal Languages and Automata\/}, 5th ed.,
       Jones and Bartlett, 2011.
 \item Martin, J.C. {\it Introduction to Languages and the Theory of Computation\/}, 4th ed.,
       McGraw-Hill, 2010.
 \item Menezes, P.B. {\it Linguagens Formais e Autômatos\/}, $6^{\mbox{\underline{a}}}$
       ed., Bookman, 2010.
 \item Moret, B.M. {\it The Theory of Computation\/}, Addison-Wesley, 1998.
 \item R\`ev\`esz, G.E. {\it Introduction to Formal Languages\/}, Dover, 2012.
 \item Sipser, M., {\it Introduction to Theory of Computation}, 3rd ed., Course Technology,
       2012. (Existe tradução pela Thomson da 2a ed., de 2007, com o título \textit{Introdução
			 à Teoria da Computação}.)
 \item Sudkamp, T.A. {\it Languages and Machines: An Introduction to the
       Theory of Computer Science\/}, 3rd ed., Pearson, 2005.
 \item Wood, D., {\it Theory of Computation}, John Wiley \& Sons, 1987.
\end{enumerate}
 
\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 à 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}
