Informática Teórica
Engenharia da Computação
Teoria é importante para a prática

Ela provê ferramentas conceituais que os
praticantes usam em engenharia da computação.

Projetando uma nova linguagem de programação
para uma aplicacão especializada?
O que você aprender sobre gramáticas neste
curso irá bem a calhar.

Teoria é importante para a prática

Lidando com busca por cadeias e casamento de
padrões?

Lembre-se de autômatos finitos e expressões
regulares.
Teoria é importante para a prática

Lidando com busca por cadeias e casamento de
padrões?

Lembre-se de autômatos finitos e expressões
regulares.
Teoria é importante para a prática

Confrontado com um problema que parece
requerer mais tempo de computador do que você
pode suportar?

Pense no que você aprendeu sobre NP completude.
Teoria é importante para a prática

Os melhores projetos e aplicações de
computadores são concebidos com elegância em
mente.

Um curso teórico pode elevar seu sentido estético
e ajudá-lo a construir sistemas mais bonitos.
Teoria é importante para a prática




Finalmente, teoria é bom para você porque estudála expande sua mente.
Conhecimento técnico específico, embora útil
hoje, fica desatualizado em apenas uns poucos
anos.
Por outro lado as habilidades de pensar, exprimirse claramente e precisamente, para resolver
problemas, e saber quando você não resolveu um
problema.
Essas habilidades têm valor duradouro. Estudar
teoria treina você nessas áreas.
Teoria dos Autômatos



Lida com as definições e propriedades de
modelos matemáticos de computação.
Um modelo, chamado autômato finito, é usado em
processamento de texto, compiladores, e projeto
de hardware.
Um outro modelo, chamado gramática livre-docontexto, é usado em linguagens de programação
e inteligência artificial.
Teoria da Computação
Nosso curso


Três áreas centrais: autômatos, computabilidade e
complexidade.
Quais são as habilidades e limitações
fundamentais dos computadores?

O que faz alguns problemas computacionalmente
difíceis e outros fáceis? COMPLEXIDADE

Como separar os problemas que possuem solução
computacional daqueles que não possuem?
COMPUTABILIDADE
Teoria da Computação
Nosso curso

As teorias da complexidade e computabilidade
requerem uma definição precisa de um
computador.

A teoria dos autômatos introduz definições de
modelos matemáticos de computação.

Daí começamos o nosso curso estudando esses
modelos.
Teoria da Computação
Outros modelos
Só para sabermos:

Outros modelos de computação também foram
propostos.

-cálculo (Alonzo Church)
Funções recursivas  (Kurt Godel, Jacques


Herbrand)
Lógica combinatória (Moses Schonfinkel, Haskell
B. Curry)
Teoria da Computação
Contexto do que vamos começar a estudar
No curso iremos estudar os seguintes modelos de
computação:
Autômatos finitos
2. Autômatos com pilha
3. Máquinas de Turing
1.

1 e 2 possuem mémória finita ao passo que 3
possui memória ilimitada.
FERRAMENTAS MATEMÁTICAS

CONJUNTOS

Operações

Produto cartesiano

Conjunto das partes

SEQUÊCIAS E UPLAS
FERRAMENTAS MATEMÁTICAS

FUNÇÕES E RELAÇÕES

Domínio, contra-domínio e imagem

Argumentos e aridade

Função n-ária, unária, binária, etc.

Predicado ou propriedade

Relação n-ária, binária, etc.

Propriedades de uma relação

Relações de equivalência

GRAFOS
FERRAMENTAS MATEMÁTICAS

TEOREMAS

Métodos de Prova

Provas diretas

Provas por contradição

Provas por contrapositiva

Provas por indução matemática
FERRAMENTAS MATEMÁTICAS

CADEIAS E LINGUAGENS

Alfabeto

Conjunto finito não vazio de símbolos.

Notação:  ou 

Cadeias sobre um alfabeto

É uma sequência finita de símbolos daquele
alfabeto.

* é o conjunto de todas as cadeias sobre o
alfabeto 
FERRAMENTAS MATEMÁTICAS

CADEIAS E LINGUAGENS

Tamanho de uma cadeia w: |w|.

Cadeia vazia (de tamanho zero): 

Reverso de w: wR.
FERRAMENTAS MATEMÁTICAS

CADEIAS E LINGUAGENS

Operação de concatenação de cadeias.

Essa opereção pega duas cadeias x e y e forma
uma nova colocando y após x.

A cadeia xy é chamada de concatenação de x e y.

Em geral xy é diferente de yx
FERRAMENTAS MATEMÁTICAS

CADEIAS E LINGUAGENS

Concatenação de cadeias: algumas propriedades

Associativa: (xy)z = x(yz)

A cadeia  é a identidade: x = x = x

|xy| = |x| + |y|
FERRAMENTAS MATEMÁTICAS

CADEIAS E LINGUAGENS

Concatenação de x com si própria: xK.

Exemplo: (ab)3 = ababab
(ab)0 = 

Definição recursiva para xk:

x0 = 

xn+1 = xnx

Linguagem: conjunto de cadeias
Autômatos Finitos

É um dos modelos computacionais que
estudaremos.

Porém com uma quantidade extremamente
limitada de memória.
O que um computador pode fazer com uma
memória tão pequena?
Na verdade, interagimos com tais computadores o
tempo todo, pois eles residem no coração de
vários dispositivos eletromecânicos.


Autômatos Finitos

O controlador para uma porta automática é um
exemplo de tal dispositivo.
 As lavadoras de louça/roupa, termômetros
eletrônicos, relógios digitais, calculadoras e
máquinas de venda automática....
 Os autômatos também são chamados de máquinas
de estados finitos.
Autômatos Finitos: exemplo
Controlador para uma porta automática de entrada
Sinal de entrada
Estado
Nenhum
Frente
Atrás
Ambos
Fechado
Fechado
Aberto
Fechado
Fechado
Aberto
Fechado
Aberto
Aberto
Aberto
Esse controlador é um computador com apenas 1 bit de memória,
capaz de registrar em quais dos dois estados o controlador está.
Autômatos Finitos

Controladores para diversos aparelhos domésticos,
como lavadora de pratos e termostatos eletrônicos,
assim como peças de relógios digitais e
calculadoras, são exemplos adicionais de
computadores com memória limitada.

O projeto requer que se tenha em mente a
metodologia e terminologia de autômatos finitos.
Autômatos Finitos

Ao começar a descrever a teoria matemática de
autômatos finitos, fazemos isso no nível abstrato,
sem referˆência a qualquer aplicação específica.

A seguir vamos ver alguns exemplos usando um
diagrama de estados e identificar os conceitos de:
estado inicial, estado de aceitação ou final,
transição.
Autômatos Finitos

Uma máquina M1 que recebe cadeias de bits como
entrada e aceita somente aquelas que começam
com um ou mais zeros seguidos de um ou mais 1’s
apenas.
Autômatos Finitos

O autômato recebe os símbolos da cadeia de entrada
um por um da esquerda para a direita.
 Após ler cada símbolo, M1 move de um estado para
outro ao longo da transição que tem aquele símbolo
como seu rótulo.
 Quando ele lê o último símbolo, M1 produz sua saída.
 A saída é aceite se M1 está agora no estado de
aceitação e rejeite se ele não está.
Autômatos Finitos

Um AF M2 que recebe cadeias de bits e aceita
aquelas que possuem 10 como subcadeia
Autômatos Finitos
0
q0
M2
1
1
q1
0
q3
0,1
Autômatos Finitos
M3
q0
0
1
0
1
L(M3)={w | w termina em 1}
q1
Autômatos Finitos
M4
1
1
0
q0
q1
0
L(M4)={w | w é a cadeia vazia  ou termina em 0}
Autômatos Finitos
a
M5
q0
b
a
q2
q1
b
b
a
a
b
q3
q4
b
a
L(M5)={w | w começa e termina no mesmo símbolo}
Autômatos Finitos
a
q0
b
q1
a
b
q2
a
q3
b
a,b
Os estados q1 e q2 servem para “memorizar’’ o símbolo anterior.
Esse AF aceita as cadeias sobre o alfabeto {a,b} que possuem aa
ou bb como subcadeias.
Autômatos Finitos
q0
0
1
q1
1
0
1,0
q3
Esse AF aceita qualquer cadeia binárias que termina com o símbolo 1 ou
que termina com um número par de 0s seguindo o último 1.