http://www.pedro.jmrezende.com.br/tc.htm

Teoria da Computação

Ciência da Computação - UnB
Prof.: A DESIGNAR

Semestre 2019.2: Terça e Quinta, 19:00 às 20:40h – Local: PJC BT 044
Mantenha-se em contato com esta página até o final do semestre.
Notas, prazos, tarefas, avisos, etc. serão divulgados aqui.

Esta página contém partes atualizadas periodicamente.
Primeira versão: 07.08.2019 - Ultima atualização: 11.12.2019
Menções finais

Material do curso

Índice

Apresentação
Objetivos
Programa
Metodologia
Avaliação
Datas, provas e pesos
Listas de Exercícios
Bibliografia

Apresentação

Essas questões são abordadas na disciplina Teoria da Computação. Ao longo do semestre, conheceremos as idéias formais que deram respostas às tres primeiras. Respostas cujos desdobramentos resultaram na Ciência da Computação, e por conseguinte na informática, que temos hoje. Quanto à última questão, nossa abordagem buscará respondê-la, com a colaboração dos alunos, também ao longo do semestre.

Objetivos

Estudaremos os modelos computacionais mais relevantes (autômatos, máquinas abstratas, gramáticas gerativas), seu poder expressivo ou computacional (computabilidade, decidibilidade), e relações importantes entre os mesmos (hierarquia de Chomski).  Também, as relações entre esses modelos e os processos produtivos na microeletrônica, no desenvolvimento de softwares, e na resolução de problemas computacionais (aplicações, complexidade), inclusive históricas (hipótese de Church-Turing). Para isso, precisamos aprender a ler (e entender) e a escrever em um formalismo capaz de permitir a formulação dos conceitos e a compreensão dos resultados. Estudaremos, pois, esses temas por meio deste formalismo. Começaremos com (uma rápida revisão d)o mínimo de linguagem matemática necessária para tal, coberta nos pre-requisitos desta disciplina.

Programa

A ementa oficial da disciplina é a seguinte


Metodologia

A bibliografia a ser seguida tem como referência o livro de Michael Sipser, "Introdução à Teoria da Computação", e/ou Hopcroft, Ullmand & Motwani, "Introdução à Teoria de Autômatos, Linguagens e Computação". As aulas expositivas seguirão o material preparado pelo professor anterior da disciplina, que seleciona e condensa tópicos cobertos por Sipser, não necessariamente na mesma ordem. O conteúdo de ambos os livros de referência é mais amplo do que o tempo e o contexo da disciplina nos permite cobrir, mas dele veremos o suficiente para cobrir quase toda a ementa.
As aulas terão como roteiro as transparências linkadas no segundo bullet do item “Material e Ferramentas de Referência” da Bibliografia (no final desta página), complementadas por conteúdo da Wikipedia (para os tópicos Máquina Universal de Turing, Hipótese de Church-Turing, Hierarquia de Chomski, e Teorema de Cook-Levin), além de exercícios com a ferramenta JFlap, linkada para download no quinto bullet do mesmo item da Bibliografia.

Para atividades fora de aula, serão passadas listas de exercícios (no próximo tópico desta página), pelo menos a primeira de entrega obrigatória (valendo nota). As demais listas, de entrega opcional, serão avaliadas caso, ao final do semestre, o aluno queira, com a média destas, arredondar a média de pontos da avaliação, em até dois décimos de ponto (escala 0 a 10). A 1ª lista, que será corrigida com comentários e devolvida antes da primeira prova. Esta lista cobre o mínimo em linguagem matemática necessária para abordarmos o programa da disciplina. Os comentários na correção desta 1ª lista visam, portanto, a permitir que o aluno possa balizar sua fluência nesse conteúdo básico presumido dos pré-requisitos, além de ter uma ideia de como serão avaliadas as provas (mas não do conteúdo das provas).

O professor estará disponível para atendimento aos alunos mediante agendamento por e-mail.

Avaliação

Aluno

Lista
obrigatória

Prova1

Prova2

Faltas
**

Menção

12/0066751

4.5

5.3

5.2


MM

15/0073208

7.5

8.1

6.1


MS

16/0166179

10.0

7.8

6.3


MS

18/0124684

2.5

8.3

6.3


MM




























Datas, Provas e Pesos -

Haverá duas provas escritas, a primeira no começo da nona semana do semestre letivo, em 10/10, cobrindo os itens 1) e 2) da ementa, e a segunda no final do semestre, em 10/12, cobrindo os itens 3) e 4).


Listas obrigatórias serão aceitas com atraso mediante redução na nota máxima. Não haverá prova de reposição.

Listas de Exercícios


1a. Lista de Exercícios (com exercícios do Sipser) - obrigatória para entrega a ser marcada ao final do tópico 1.

 Faça quatro das seguintes questões
 
 1.5.4- Mostre, com argumentos lógicos, que se A e B são conjuntos finitos quaisquer, então existem |B||A| funções com domínio em A e contradomínio em B. Determine quantas dessas funções são bijetoras. E quantas são sobrejetoras? 
 
 1.5.6- Mostre que em qualquer grupo de no mínimo duas pessoas, há pelo menos duas que têm o mesmo número de conhecidos dentro do grupo, considerando que a relação "conhecido de" é simétrica (use o princípio da correspondência).
 
 1.5.9- Um conjunto enumerável é um conjunto que pode ser domínio ou contradomínio de uma bijeção com os números naturais. Mostre o seguinte: Se soubermos que A é um conjunto não-enumerável, e B um subconjunto enumerável de A, então A - B (isto é, A sem os elementos de B) é também não-enumerável. (Sugestão: use argumento por contradição)

*-Considere a linguagem formal L = {0, 1}+. Se a cada cadeia de L associarmos o número natural que ela representa no sistema numérico posicional binário, tal associação descreve uma função de L em N (conjunto dos números naturais) que é sobrejetora, porém não é injetora. Descreva como obter um subconjunto de L por meio de duas operações envolvendo L e subconjuntos de L, sobre o qual a mesma função será também injetora (e portanto, bijetora). (Obs: as operações com linguagens formais estão descritas na lâmina 2 das transparências a4)
 
 1.6.2- O fecho transtitivo de uma relação R sobre A é a menor relação transtiva sobre A que contém R (tomando a definição de relação como subconjunto de um produto direto, "menor" significa minimal, isto é, qualquer subconjunto próprio dele deixa de satisfazer a propriedade que o define).
 Se  A = {a, b, c, d, e} e R = {(a,b), (a,c), (a,d) , (d,c), (c,e)}, descreva o fecho transitivo reflexivo R* (Se voce não se lembra como "completar" uma relação para obter o fecho, consulte um livro; se quiser, represente R* por um grafo dirigido, onde a aresta dirigida a->b representa (a,b) )
 
 1.6.5- Dê um exemplo de uma relação sobre um conjunto que não é reflexiva, mas seu fecho transitivo é reflexivo.

 2. *- Explique, usando argumentos lógicos e o lema do bombeamento, por que a linguagem L = {0n1n | n é número natural } não é regular, ou seja, não pode ser aceita por um automaton finito.

2a. Lista de Exercícios - cap. 2 - para antes da 1a. prova - opcional

Responda por completo os ítens da questão 2.4.8 do livro texto H.U.

2.4.8- As seguintes declarações são verdadeiras ou falsas? Explique sua resposta em cada caso (Para todas elas, é assumido um alfabeto S fixo).

a) Cada subconjunto de uma linguagem regular é regular;
b) Cada linguagem regular tem um subconjunto próprio (com pelo menos um elemento a menos) regular;
c) Se L é regular, então assim também é {xy tal que x pertence a L e y não pertence a L};
d) A linguagem {w tal que w = wR } é regular;
e) Se L é uma linguagem regular, assim também é a linguagem {w pertencente a L tal que wR também pertence a L}
f) Se C é um conjunto qualquer de linguagens regulares, então também é o conjunto formado pela união dessas linguagens
g) {wxwR onde x e w pertencem a S*} é regular.



3a. Lista de Exercícios - cap. 3 - para antes da 1a. prova - opcional

Responda os seguintes itens dos seguintes problemas do livro texto

3.5.1- Mostrar que as seguintes linguagens são livres de contexto.
a) {ambn onde m e n são números naturais distintos}.
b) {a,b}* - {anbn onde n é um número natural};
e) {w pertencente a {a,b}* tal que w=wR}


3.5.2- Mostrar que as seguintes linguagens não são livres de contexto.
c) {www tal que w pertence ao conjunto {a,b}* }.
d) {w pertencente a {a,b,c}* onde w tem números iguais de ocorrências de a, b e c};

4a. Lista de Exercícios (com matéria do Sipser) para antes da 2a. prova - opcional 

Quais modelos computacionais voce conheceu através desta matéria?
Desses modelos, quais admitem variantes?
Desses modelos, quais admitem mais de uma semântica (interpretação do funcionamento), quais não?
Dos que admitem mais de uma semântica, como você as descreveria?
Dos que admitem mais de uma variante, quais variantes alteram o poder expressivo do modelo, quais não?
A menos de variantes equivalentes, quais modelos/semânticas guardam relação de menor, maior, ou igual poder expressivo, citando exemplos se possível?
Como voce hierarquizaria essas relações, e como voce descreveria a hipótese que "fecharia" esta hierarquia no seu topo?
O que é o "problema da parada", e como vc descreveria sua importância para a teoria da computação?
O que são classes de complexidade computacional?
Quais dessas classes voce considera mais importantes, e por que?

Bibliografia

Material e Ferramentas de Referência:
Textos complementares:

Outros textos sobre o tema: