---

Área de concentração: 55134 - Ciências de Computação e Matemática Computacional

Criação: 22/11/2018

Nº de créditos: 12

Carga horária:

Teórica Por semana	Prática Por semana	Estudos Por semana	Duração	Total
4	0	8	15 Semanas	180 Horas

Docentes responsáveis:

Diego Raphael Amancio
João Luis Garcia Rosa
Moacir Antonelli Ponti
Thiago Alexandre Salgueiro Pardo

Objetivos:

Apresentar ao aluno conceitos fundamentais das disciplinas de Teoria da Computação (teoria das
linguagens formais e autômatos, teoria da computabilidade e teoria da complexidade). Capacitar o
aluno a compreender e utilizar estes conceitos.

Justificativa:

O estudo destes aspectos fundamentais da ciência da computação deve auxiliar na formação da base
teórica necessária às demais disciplinas do curso.

Conteúdo:

Linguagens Regulares: Autômatos finitos determinísticos e não-determinísticos; expressões regulares; técnicas para identificar e descrever linguagens regulares; técnicas para mostrar que uma linguagem não é regular; propriedades de tais linguagens. Linguagens Livres de Contexto: Gramáticas Livres de Contexto; derivações; árvores de derivação; ambiguidade; autômatos de pilha; propriedades de tais linguagens; técnicas para mostrar que uma linguagem não é livre de contexto. Linguagens Sensíveis ao Contexto e Linguagens Recursivamente Enumeráveis: Máquinas de Turing; definições básicas e sua relação com a noção de um algoritmo/programa. Poder das Máquinas de Turing e Tese de Church-Turing. Indecidibilidade: máquinas de Turing Universais; Limitações sobre a nossa habilidade de computar; problemas indecidíveis. Teoria de Complexidade: Complexidade de Tempo, Complexidade de Espaço, Intratabilidade.

Forma de avaliação:

Média ponderada entre provas e projetos.

Observação:

Nenhuma.

Bibliografia:

Fundamentais:
SIPSER, M. Introduction to the Theory of Computation. PWS, 2a ed, 1997.
HOPCROFT, M. & ULLMAN Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2001.
DIVÉRIO & MENEZES Teoria da Computação – Máquinas Universais e Computabilidade. Série Livros Didáticos 5, IF
UFRGS, 2. ed., 2000, Sagra Luzzatto.
MENEZES, P.B. Linguagens Formais e Autômatos, Série Livros Didáticos 3, IF UFRGS, 4. ed., 2001, Sagra
Luzzatto.
ROSA, J.L.G. (2010). Linguagens Formais e Autômatos. LTC.
Complementares (se houver):
HAREL, D. Algorithmics – The Spirit of Computing. Addison-Wesley, 2. ed., 1992.
GAREY & JOHNSON Computers and Intractability – a guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979.
CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L. Introduction to Algorithms. The Mit Press. 1. ed., 1990.
TOSCANI & VELOSO Complexidade de Algoritmos, Série Livros Didáticos 13, IF UFRGS, 1. ed., 2001, Sagra
Luzzatto.