---

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

Criação: 25/06/2024

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