Teoria da computação aula_2

Prévia do material em texto

Teoria da Computação
Prof. Ms. Diego Daniel 
Duarte
Faculdades Anhanguera
Limeira - SP
Cronograma
Tópicos
 Relações e Funções (pag. 19)
 Tipos Especiais de Relações Binárias (pag. 
23)
 Alfabetos e Linguagens (pag. 54)
 Definições, Teoremas e Provas (pag. 36 – 
pag. 17 [Sipser])
Relações e Funções
 Uma função relaciona (mapeia) elementos de um 
conjunto (denominado domínio) sobre outro 
(denominado imagem)
f(A) = B
Domínio Imagem
Relações e funções
 Graficamente, podemos 
representar a relação entre 
os elementos de dois 
conjuntos finitos 
descriminando esses 
elementos e ligando cada 
elemento do domínio no seu 
representante da imagem, 
conforme ilustrado ao lado
1
2
3
4
5
6
7
A
B
C
D
E
F
G
Tipos Especiais de Relações Binárias
 Como representar 
graficamente a relação 
de uma função quando 
domínio e imagem são 
o mesmo conjunto?
Tipos Especiais de Relações Binárias
 Essa representação 
pode ser feita através 
de um grafo, no qual os 
vértices representam 
os elementos do 
conjunto e as arestas o 
relacionamento entre 
esses elementos
Limeira
Piracicaba Americana
Sumaré
Cosmópolis
Cordeirópolis
St. Bárbara
Alfabetos e Linguagens
 Informações são armazenadas na forma de 
cadeia se símbolos (bits geralmente)
 Compreender a processo sobre essas 
cadeias é fundamental para compreender o 
funcionamento computacional
Alfabetos e Linguagem
 Definições
– Alfabeto (Σ): conjunto finito de símbolos
 Exemplo: { a, b, ... , z }; { 0, 1, ... , 9 }
– Cadeia: sequência elementos contendo símbolos do 
alfabeto
 Exemplo: anhanguera; 2010
 Uma cadeia com nenhum elemento é chamada de cadeia 
vazia e é denotada por ε
– Comprimento (|w|): quantidade de símbolos de uma 
cadeia
 Exemplo: | anhanguera | = 10; | 2010 | = 4
 O comprimento de uma cadeia vazia é 0 (zero)
Alfabeto e Linguagem
 Operações sobre cadeias
– Concatenação (°): acrescenta o os símbolos da 
segunda cadeia no final da primeira
Exemplo: clara ° boia = claraboia
w ° ε = ε ° w = w
– Reverso (R): inverte a ordem dos símbolos da 
cadeixa
Exemplo: sametsisR = sistemas
Alfabetos e Linguagem
 Definições
– Subcadeia: parte de uma cadeia. v será uma 
subcadeia de w se w = xvy, no qual x e y podem 
ser ε
– Prefixo: parte inicial de uma cadeia. v será um 
prefixo de w se w = vy para um y qualquer
– Sufixo: parte final de uma cadeia. v será um 
sufixo de w se w = xv para um x qualquer
Alfabetos e Linguagens
 Linguagem: Conjunto de todas as possível 
cadeias de um alfabeto que atendam a 
determinadas propriedades
– Notação:
L = { w ∈ Σ* | w tenhas as propriedades P }
 Por se tratar de um conjunto, todas as 
considerações sobre conjuntos aplicam-se 
também sobre linguagens
Alfabetos e Linguagens
 Representações de Linguagens
– Expressões Regulares: simbologia para denotar 
os símbolos que podem ocorrer em uma cadeia.
 * : símbolos podem ocorrer 0 ou mais vezes
 + : símbolos podem ocorrer 1 ou mais vezes
 | : pode ocorrer o símbolo (ou sequência de símbolos) à 
esquerda ou à direta
– Exemplo:
 (ab)*b(a | b)+
Definições, Teoremas e Provas
 Definições
– Descrevem os objetos e noções a serem utilizadas
– Uma definição deve deixar claro o que constitui o objeto e o 
que não constitui
 Teorema
– Enunciado matemático demonstrado como verdadeiro
 Prova
– Enunciado lógico e convincente que, utilizando definições, 
garante que um teorema é verdadeiro
Definições, Teoremas e Provas
 Tipos de Prova
– Prova por Construção
Demonstra como construir um objeto que atendas às 
propriedades do teorema que se deseja provar
– Prova por Contradição
Supõe que um teorema é verdadeiro (ou falso) e 
demonstra, com base outros teoremas e/ou definições, 
que aquele objeto é, na verdade, falso (ou verdadeiro)
Definições, Teoremas e Provas
 Prova por Indução
– Demonstra que todos os elementos de um conjunto infinito 
atendem a uma propriedade específica
– Base da Indução: prova que a propriedade se aplica ao 
elemento de menor grau do conjunto (geralmente 0 ou 1)
– Passo da Indução: demonstra que, para cada i-ésimo 
elemento do conjunto, sendo i ≥ ao elemento de menor 
grau, se a propriedade é verdadeira para esse i-ésimo 
elemento também o será para o próximo (i + 1)
Definições, Teoremas e Provas
 Prova por Indução - Modelo
Base: Prove que P(0) é verdadeiro
Passo da Indução: Para cada i ≥ 0, suponha que P(i) é 
verdadeiro e use essa suposição para mostrar que P(i + 1) é 
verdadeiro
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17