Download - Matematica Discreta Para BCC
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 1
Matemtica Discreta paraCincia da Computao
P. Blauth Menezes
Departamento de Informtica Terica
Instituto de Informtica / UFRGS
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 2
Matemtica Discreta para Cincia da Computao
P. Blauth Menezes
1 Introduo e Conceitos Bsicos2 Lgica e Tcnicas de Demonstrao3 lgebra de Conjuntos4 Relaes5 Funes Parciais e Totais6 Endorrelaes, Ordenao e Equivalncia7 Cardinalidade de Conjuntos8 Induo e Recurso9 lgebras e Homomorfismos10 Reticulados e lgebra Booleana11 Concluses
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 3
8 Induo e Recurso
8.1 Princpio da Induo Matemtica8.2 Prova Indutiva8.3 Segundo Princpio da Induo Matemtica8.4 Definio Indutiva8.5 Expresses Regulares8.6 Computaes de um Autmato Finito8.7 Leitura Complementar: Gramtica e BNF8.8 Recurso8.9 Leitura Complementar: Funes Recursivas
Parciais
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 4
8 Induo e Recurso
8.1 Princpio da Induo Matemtica
Princpio da Induo Matemtica
tcnica para lidar com tipos de dados que tm uma relao de boa-ordem
Relao de Boa-Ordem todo conjunto no-vazio de elementos do tipo de dado tem um elemento mnimo segundo esta relao de ordem exemplo: N
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 5
Dada uma boa ordem
pode-se aplicar induo para provar propriedades que valem para todo elemento
Por simplicidade
tipo de dados considerado: N ou qq outro conjunto isomorfo a N
Exemplo simples que ilustra o Princpio da InduoMatemtica
efeito domin
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 6
Efeito Domin
ao derrrubar a primeira pea todas as demais peas sero derrubadas em cadeia
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 7
Para estar certo que ocorrer primeira pea derrubada (direo das demais) (1) se qq pea est suficientemente prxima da seguinte, ento, ao ser
derrubada, far com que a seguinte tambm seja derrubada (2)
Ento por (1), a primeira pea derrubada por (2), a segunda pea derrubada por (2), a terceira pea derrubada e assim sucessivamente
Portanto, para i to grande quanto se queira i-sima pea derrubada
Logo, para qq n n-sima pea derrubada
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 8
Princpio da Induo Matemtica
pode ser resumido como
se o incio correto e se coisa alguma pode dar errada,ento sempre ser correto
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 9
Def: Princpio da Induo Matemticap(n) uma proposio sobre M = {n N n m e m N }Princpio da Induo Matemtica
p(m) verdadeira para qq k M, p(k) p(k + 1) ento, para qq n N, p(n) verdadeira
Base de induo p(m)
Hiptese de induo p(k)
Passo de induo p(k) p(k + 1)
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 10
Na definio
forma mais tradicional denominada de Primeiro Princpio da Induo Matemtica formulaes alternativas: adiante
Duas aplicaes da Induo Matemtica destacam-se
Prova Indutiva ou Prova por Induo tcnica de demonstrao comum na CC & Informtica no do domnio da lgica pura
Definio Indutiva ou Definio Recursiva comum na CC & Informtica j usada anteriormente de forma informal
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 11
Recurso
conceito prximo ao de induo e presente na grande maioria daslinguagens de programao o de recurso.
Exemplos de construes baseadas em induo erecurso e de especial interesse para CC e Informtica
Computaes de um autmato finito Gramticas de Chomsky e a Forma de Backus Naur (ou BNF) Expresses Regulares Funes Recursivas Parciais ou Funes Recursivas de Kleene
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 12
8 Induo e Recurso
8.1 Princpio da Induo Matemtica8.2 Prova Indutiva8.3 Segundo Princpio da Induo Matemtica8.4 Definio Indutiva8.5 Expresses Regulares8.6 Computaes de um Autmato Finito8.7 Leitura Complementar: Gramtica e BNF8.8 Recurso8.9 Leitura Complementar: Funes Recursivas
Parciais
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 13
8.2 Prova Indutiva
Prova Indutiva ou Prova por Induo
tcnica de demonstrao baseada no Princpio da Induo Matemtica no do domnio da lgica pura
limita-se a confirmar se p(n) correta
Demonstrao por induo
demonstrar a base de induo p(m) fixado um k
supor verdadeira a hiptese de induo p(k) demonstrar o passo de induo p(k) p(k + 1)
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 14
Exp: Prova por Induo - p(n): n < 2n
para qq n N, tem-se que n < 2n
Base de Induo. k = 00 < 1 = 20
Hiptese de Induo. Suponha que, para k Np(k): k < 2k verdadeira
Passo de Induo. Prova para p(k + 1): k + 1 < 2k+1
k + 1 < hiptese de induo 2k + 1 2k + 2k = 2 * 2k = 2k+1
Logo, para qq n N, tem-se que n < n2
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 15
Exp: Prova por Induo - p(n): 2n < n!
para qualquer n N, se n > 3, ento 2n < n!
Base de Induo. k = 442 = 16 < 24 = 4!
Hiptese de Induo. Suponha para k > 3p(k): 2k < k! verdadeira
Passo de Induo. Prova para p(k + 1): 2k+1 < (k + 1)!
2k+1 = 2 * 2k < hiptese de induo 2 * k! < (k + 1) * k! = (k + 1)!
Logo, para qq n N, se n > 3, ento 2n < n!
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 16
Exp: Prova por Induo - 1 + 2 + + n = (n2 + n)/2para qualquer n N, tem-se que1 + 2 + + n = (n2 + n)/2
Base de Induo. k = 0(02 + 0)/2 = (0 + 0)/2 = 0/2 = 0
Hiptese de Induo. Suponha para k Np(k): 1 + 2 + + k = (k2 + k)/2 verdadeira
Passo de Induo. p(k+1): 1+2++k+(k+1) = ((k+1)2+k+1)/2 1 + 2 + + k + (k + 1) = (1 + 2 + + k) + (k + 1) = pela hiptese de induo (k2 + k)/2 + (k + 1) = (k2 + k)/2 + (2k + 2)/2 = (k2 + k + 2k + 2)/2 = ((k2 + 2k + 1) + (k + 1))/2 = ((k + 1)2 + (k + 1))/2
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 17
Exp: Prova por Induo - #2A = 2#AFoi afirmado que
se o cardinal de um conjunto A n ento o cardinal de 2A 2n, o que justifica a notao 2A.
Teorema (verso limitada a conjuntos finitos)
para qq conjunto finito A, se #A = n, ento tem-se que #2A = 2n
Considere o seguinte exemplo motivacional:
P() = { } P({ a }) = { , { a } } P({ a, b }) = { , { a }, { b }, { a, b } } P({ a, b, c }) =
{ , { a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c } }
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 18
Observe P({ a, b }) e P({ a, b, c }) (por exemplo)
metade dos elementos de P({ a, b, c }) corresponde a P({ a, b })
P({ a, b, c }) = P({ a, b }) { { c }, { a, c }, { b, c }, { a, b, c } }
outra metade de P({ a, b, c }) corresponde a P({ a, b }),adicionando-se c a cada conjunto
P({ a, b, c }) = P({ a, b }) { { c }, { a } { c }, { b } { c }, { a, b } { c } }
Ou seja, #P({ a, b, c }) possui o dobro de elementos de #P({ a, b })
cada elemento adicionado a um conjunto duplica o cardinal docorrespondente conjunto das partes
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 19
Base de Induo. Seja k = 0 (#A = 0). Ento A =
P() = { }
p(0) verdadeira pois
#P() = 1 = 20 = 2#
Hiptese de Induo. Suponha que, para algum k N (#A = k)
p(k): #P(A) = 2#A verdadeira
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 20
Passo de Induo. p(k + 1). Sem perda de generalidade, suponha osseguintes conjuntos (conjuntos com o mesmo cardinal so isomorfos)
A = { 1, 2, 3, , k } B = { 1, 2, 3, , k, k + 1 }
Por hiptese de induo #P(A) = 2k
P(A) so todos subconjuntos de B que no possuem o elemento k + 1
demais subconjuntos B so aqueles que contm o elemento k + 1 a unio de cada conjunto de P(A) com { k + 1 } resultando em outros 2k conjuntos
#P(B) = 2k + 2k = 2k+1
Logo, para qq conjunto finito A, se #A = n, ento tem-se que #2A = 2n
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 21
8 Induo e Recurso
8.1 Princpio da Induo Matemtica8.2 Prova Indutiva8.3 Segundo Princpio da Induo Matemtica8.4 Definio Indutiva8.5 Expresses Regulares8.6 Computaes de um Autmato Finito8.7 Leitura Complementar: Gramtica e BNF8.8 Recurso8.9 Leitura Complementar: Funes Recursivas
Parciais
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 22
8.3 Segundo Princpio da InduoMatemtica
Freqentemente conveniente trabalhar com outrasformulaes do Princpio da Induo Matemtica
Primeiro Princpio da Induo Matemtica princpio introduzido
Segundo Princpio da Induo Matemtica formulao especialmente importante considera no apenas o resultado anterior p(k) mas todos os
anteriores para concluir p(k + 1)
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 23
Lembrando
Def: (Primeiro) Princpio da Induo Matemticap(n) uma proposio sobre M = {n N n m e m N }Princpio da Induo Matemtica
p(m) verdadeira para qq k M, p(k) p(k + 1) ento, para qq n N, p(n) verdadeira
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 24
Def: Segundo Princpio da Induo MatemticaSeja p(n) proposio sobre M = {n N n m e m N }.
Primeira Verso.
p(m) verdadeira para qq k M: p(m) p(m + 1) p(k) p(k + 1) ento, para qq n N, p(n) verdadeira
Segunda Verso. Suponha t N
p(m), p(m + 1),,p(m + t), so verdadeiras; para qq k M tq k m + t: p(m) p(m + 1) p(k) p(k + 1) ento, para qq n N, p(n) verdadeira
Segunda verso: prova os t primeiros casos em separado para verificara base de induo
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 25
Aplicao usual do Segundo Princpio
definio e prova de propriedades de expresses frmulas rvores, etc.
razo pela qual freqentemente denominado de induo em estrutura induo estruturada
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 26
Exp: Segundo Princpio: Proposio Lgica
Suponha que p uma proposio lgica a qual contmexclusivamente os conetivos lgicos , e . Se o valor verdade
de todos os tomos de p V, ento o valor verdade de p V
Uma prova por induo (no nmero de tomos, primeira verso):
Base de Induo. Seja k = 1
p um tomo portanto, por hiptese, p V
Hiptese de Induo. Suponha que, para algum k N, e para qq u Ntal que u k
se o nmero de tomos de p u, ento o valor verdade de p V
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 27
Passo de Induo. Seja p uma proposio com k + 1 tomos
p pode ser reescrita (q e r possuem individualmente no mximo ktomos e, conjuntamente, k + 1 tomos): q r q r q r
por hiptese de induo q e r so V portanto, em qualquer dos casos, p V
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 28
Exp: Segundo Princpio: Postagem
Qualquer valor de postagem igual ou maior que 12 reais pode serformado usando exclusivamente selos de 4 e de 5 reais
Uma prova por induo (no nmero de selos, segunda verso):
Base de Induo. Seja k { 12, 13, 14, 15 }
12 reais: 3 selos de 4 13 reais: 2 selos de 4 e 1 selo de 5 14 reais: 1 selo de 4 e 2 selos de 5 15 reais: 3 selos de 5
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 29
Hiptese de Induo. Suponha que, para algum k N, e para qq u Ntal que 15 u k
se o valor u, ento pode ser formado usando selos de 4 e 5
Passo de Induo. Seja uma postagem cujo valor k + 1 reais
tal postagem pode ser formada usando uma postagem de k - 3 reais mais um selo de 4 reais
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 30
8 Induo e Recurso
8.1 Princpio da Induo Matemtica8.2 Prova Indutiva8.3 Segundo Princpio da Induo Matemtica8.4 Definio Indutiva8.5 Expresses Regulares8.6 Computaes de um Autmato Finito8.7 Leitura Complementar: Gramtica e BNF8.8 Recurso8.9 Leitura Complementar: Funes Recursivas
Parciais
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 31
8.4 Definio Indutiva
Princpio da induo Matemtica
pode ser usado em definies
Definio Indutiva ou Definio Recursiva
Base de induo explicita os casos elementares (os mais simples)
Passo de induo/recurso demais casos so definidos em termos dos anteriores
Definio Indutiva ja foi usado informalmente
Fecho transitivo
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 32
Exp: Definio Indutiva Fecho TransitivoEndorrelao R: A A. Fecho Transitivo
Se a, b R, ento a, b R+ (1)
Se a, b R+ e b, c R+, ento a, c R+ (2)
Os nicos elementos de R+ so os construdos como acima (3)
(1) base de induo
(2) passo de induo (hiptese?)
(3) garante que, de fato, definio indutiva (3) pode ser omitido (subentendido)
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 33
Exp: Def. Indutiva Conjunto de Todas as PalavrasAlfabeto = { a, b }
* = { , a, b, aa, ab, ba, bb, aaa, }
Base de Induo. * qq x , tem-se que x *
Passo de Induo. se u e v so palavras de *, ento a concatenao u v palavra de *
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 34
Exp: Definio Indutiva Frmula LgicaSimplificada, no incluindo quantificadores, variveis, etc.
Base de Induo qq proposio atmica (incluindos V e F) frmula
Passo de Induo. Se q e r so frmulas ento tambm so frmulas
(q) (q r) (q r) (q r) (q r)
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 35
Exp: Definio Indutiva Princpio da Induo MatIlustrao da relao entre o Princpio da Induo e a definio indutiva
definio indutiva (no nmero de conetivos) de frmula lgicausando o Segundo Princpio
Base de Induo. Seja k = 0 qq proposio atmica (incluindo V e F) uma frmula;
Hiptese de Induo. Suponha que, para algum k N, e para qq i Ntal que i k
se p uma frmula com i conetivos, ento p uma frmula lgica
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 36
Passo de Induo. Seja p uma frmula com k + 1 conetivos
p pode ser reescrita q e r so frmulas e possuem conjuntamente k conetivos
(q) (q r) (q r) (q r) (q r)
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 37
8 Induo e Recurso
8.1 Princpio da Induo Matemtica8.2 Prova Indutiva8.3 Segundo Princpio da Induo Matemtica8.4 Definio Indutiva8.5 Expresses Regulares8.6 Computaes de um Autmato Finito8.7 Leitura Complementar: Gramtica e BNF8.8 Recurso8.9 Leitura Complementar: Funes Recursivas
Parciais
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 38
8.5 Expresses Regulares
Autmato Finito
j introduzido especialmente importante
define a classe das linguagens regulares possui diversas aplicaes na Computao e Informtica
Expresses Regulares
alternativa para definir linguagens regulares
definio indutiva que segue Segundo Princpio da Induo Matemtica (segunda verso)
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 39
Def: Expresso Regular (ER) sobre um alfabeto
Base de Induo. ER e denota a linguagem vazia ER e denota a linguagem { } qq smbolo x ER e denota a linguagem { x }
Passo de Induo. Se r e s so ER e denotam as ling. R e S, ento
Unio. (r + s) ER e denota a linguagem R S
Concatenao. (rs) ER e denota a linguagem
R S = { uv u R e v S }
Concatenao Sucessiva. (r*) ER e denota a linguagem R*
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 40
Exp: Expresso RegularOmisso de parnteses em uma ER usual
concatenao sucessiva: precedncia sobre concatenao e unio concatenao: precedncia sobre unio
ER Linguagem Representada
aa somente a palavra aaba* todas palavras iniciam por b seguido por 0 ou mais a(a + b)* todas as palavras sobre { a, b }(a + b)*aa(a + b)* todas as palavras contendo aa como subpalavraa*ba*ba* todas as palavras contendo exatamente dois b(a + b)*(aa + bb) todas as palavras que terminam com aa ou bb(a + )(b + ba)* todas as palavras sem dois a consecutivos
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 41
8 Induo e Recurso
8.1 Princpio da Induo Matemtica8.2 Prova Indutiva8.3 Segundo Princpio da Induo Matemtica8.4 Definio Indutiva8.5 Expresses Regulares8.6 Computaes de um Autmato Finito8.7 Leitura Complementar: Gramtica e BNF8.8 Recurso8.9 Leitura Complementar: Funes Recursivas
Parciais
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 42
8.6 Computaes de um AutmatoFinito
Exemplos de modelos computacionais introduzidos
Rede de Petri, definida como uma relao Autmato Finito, definido como uma funo parcial
Definidos sintaticamente
definies formais de sua forma
Semntica ??
interpretao do funcionamento ou processamento introduzida textualmente, de forma informal
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 43
Autmato Finito
processamento de um Autmato Finito a sucessiva aplicao decomputaes atmicas (transies)
q 0
q 1 q 2
a b
b
a
a,b
a bq f
q f
q 1
q 0
a b b a
q 2
q f
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 44
Programa de um Autmato Finito: funo parcial
: Q Q
(q, a) = p no estado q, ao ler o smbolo a, assume o estado p
Para dar semntica sintaxe de um Autmato Finito
estender a definio da funo programa argumento: um estado e uma palavra
definida indutivamente
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 45
Funo Programa Estendida
base de induo: entrada vazia (palavra vazia) permanece no mesmo estado
passo de induo: entrada no-vazia (palavra no-vazia) processa o primeiro smbolo da entrada, usando mesmo raciocnio sucessivamente ao resto da palavra
Funo Programa Estendida definio formal
: Q * Q
(q, ) = q (q, aw) = ((q, a), w)
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 46
Exp: Funo Programa Estendida
q 0
q 1 q 2
a b
b
a
a,b
a bq f
q f
q 1
q 0
a b b a
q 2
q f
(q0, abba) = ((q0, a), bba) = (q1, bba) = ((q1, b), ba) = (q2, ba) = ((q2, b), a) = (qf, a) = ((qf, a), ) = (qf, ) = qf
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 47
8 Induo e Recurso
8.1 Princpio da Induo Matemtica8.2 Prova Indutiva8.3 Segundo Princpio da Induo Matemtica8.4 Definio Indutiva8.5 Expresses Regulares8.6 Computaes de um Autmato Finito8.7 Leitura Complementar: Gramtica e BNF8.8 Recurso8.9 Leitura Complementar: Funes Recursivas
Parciais
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 48
8.7 Gramtica e BNF
Gramticas de Chomsky
formalismo universalmente aceito e usado em Computao eInformtica e outras reas
Linguagens Formais definio e estudo das propriedades das linguagens
Teoria da Computao limites da solucionabilidade de problemas e propriedades
Linguagens Naturais linguagens como o portugus
Sistemas Biolgicos simulao do desenvolvimento de sistemas vivos
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 49
Prova-se: gramtica equivalente a Mq. de Turing
poder computacional
Hiptese de Church
qq funo computvel pode ser especificada por uma gramtica gramtica: aceita como definio formal de algoritmo
Gramticas em Computao e Informtica
especialmente importantes para definir a sintaxe de linguagens Pascal, C, definidas usando gramticas
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 50
8 Induo e Recurso
8.1 Princpio da Induo Matemtica8.2 Prova Indutiva8.3 Segundo Princpio da Induo Matemtica8.4 Definio Indutiva8.5 Expresses Regulares8.6 Computaes de um Autmato Finito8.7 Leitura Complementar: Gramtica e BNF
8.7.1 Gramtica8.7.2 BNF
8.8 Recurso8.9 Leitura Compl.: Funes Recursivas Parciais
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 51
8.7.1 Gramtica
Gramtica , basicamente
conjunto finito de regras aplicadas sucessivamente, geram palavras
Gerao de palavra
indutivamente definida
Linguagem
conjunto de todas as palavras geradas forma finita de expressar sintaxe de linguagens eventualmente
infinitas
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 52
Gramticas para linguagens naturais ???
mesmas
Definio de Semntica ???
podem ser usadas gramticas
em geral, so usados outros tipos de formalismos
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 53
Def: GramticaGramtica de Chomsky ou simplesmente Gramtica
V - conjunto finito de smbolos variveis ou no-terminais
T - conjunto finito de smbolos terminais disjunto de V
P: (V T)+ (V T)* relao finita P finito regra de produo: par da relao
S - elemento distinguido de V smbolo inicial ou varivel inicial
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 54
Notao
regra de produo ,
grupo de regras da forma 1, 2, ..., n
1 2 n
Regras de produo
definem as condies de gerao das palavras da linguagem
Derivao
aplicao de uma regra de produo par de uma relao
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 55
Def: Relao de DerivaoG gramtica tq P: (V T)+ (V T)* e S o smbolo inicialDerivao um par da Relao de Derivao
: (V T)+ (V T)* , da relao denotado de forma infixada
Relao indutivamente definida
qq regra S de P, ento S derivao
qq derivao se regra de P ento
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 56
Def: Linguagem Gerada (por uma Gramtica)G gramtica tq S smbolo inicialLinguagem Gerada pela gramtica G
Linguagem(G) = { w T* S + w }
+ denota o fecho transitivo da relao de derivao
portanto: palavra de uma linguagem no pode conter variveis
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 57
Exp: Gramtica e Derivao - Nmeros NaturaisGramtica G
V = { N, D }, sendo que N o smbolo inicial T = { 0, 1, 2,, 9 } P contm as regras
N D N DN D 0 1 9
Derivao de 243 (existe mais alguma gerao?)
N DN 2N 2DN 24N 24D 243
Distingue zeros esquerda:123 0123
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 58
Interpretao indutiva
Base de Induo todo dgito um natural
Passo de Induo Se n um natural ento a concatenao de n com qq dgito tambm natural
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 59
Exp: Gramtica e Derivao - Expresso AritmticaGramtica G
V = { E }, sendo que E o smbolo inicial T = { +, , (, ), x } P contm as regras (interpretao indutiva?)
E E+E E EE E (E) E x
(x + x)x Linguagem(G) ???E E E (E) E (E + E) E
(x + E) E (x + x) E (x + x) x
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 60
8 Induo e Recurso
8.1 Princpio da Induo Matemtica8.2 Prova Indutiva8.3 Segundo Princpio da Induo Matemtica8.4 Definio Indutiva8.5 Expresses Regulares8.6 Computaes de um Autmato Finito8.7 Leitura Complementar: Gramtica e BNF
8.7.1 Gramtica8.7.2 BNF
8.8 Recurso8.9 Leitura Compl.: Funes Recursivas Parciais
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 61
8.7.2 BNF
Forma de Backus Naur ou simplesmente BNF
(do ingls, Backus Naur Form)
BNF
variveis so delimitas por e por
palavras no-delimitas: smbolos terminais
representao de uma regra de produo ,
::=
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 62
Exp: BNF - Identificador em Pascal
BNF - ident o smbolo inicial
ident ::= letra identletra identdgito letra ::= a b z dgito ::= 0 1 9
Base de Induo
toda letra um identificador
Passo de Induo
se S identificador ento a concatenao de S com qq letra/dgito identificador
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 63
8 Induo e Recurso
8.1 Princpio da Induo Matemtica8.2 Prova Indutiva8.3 Segundo Princpio da Induo Matemtica8.4 Definio Indutiva8.5 Expresses Regulares8.6 Computaes de um Autmato Finito8.7 Leitura Complementar: Gramtica e BNF8.8 Recurso8.9 Leitura Complementar: Funes Recursivas
Parciais
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 64
8.8 Recurso
Recurso
conceito prximo ao de induo
presente na grande maioria das linguagens de programao
Inspirado nas Funes Recursivas de Kleene
equivalente: Mquina de Turing e Gramtica de Chomsky
Hiptese de Church qq algoritmo pode ser expresso usando recursividade
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 65
Induo Recurso
qq definio indutiva pode ser simulada por recurso
nem toda recurso possui uma correspondente definio indutiva no necessariamente respeita a boa ordem da induo
recomendvel programar recurso respeitando os princpios dadefinio indutiva garante que o programa pra e atinge o resultado esperado
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 66
Exemplo importante para o entendimento da recurso
Exp: Definio Indutiva FatorialFatorial n!
n! = 1, se n = 0 n! = n * (n - 1) * (n - 2) * 1, se n > 0
Para n > 0
n * (n 1)! sendo que (n 1)! = (n - 1) * (n - 2) * 1
Da mesma forma, (n 1)!
(n 1) * (n - 2) !, sendo que (n 2)! = (n - 2) * (n - 3) * 1e assim sucessivamente
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 67
Base de Induo
0! = 1
Passo de Induo
n! = n * (n 1)!
Fatorial de 4
4! = 4 * (4 1)! = 4 * 3! = passo de induo 4 * 3 * (3 1)! = 4 * 3 * 2! = passo de induo 4 * 3 * 2 * (2 1)! = 4 * 3 * 2 * 1! = passo de induo 4 * 3 * 2 * 1 * (1 1)! = 4 * 3 * 2 * 1 * 0! = base de induo 4 * 3 * 2 * 1 * 1 = 24
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 68
Exp: Funo Recursiva em Pascal Fatorial
function fatorial(n: integer): integer;beginif n = 0then fatorial := 1else fatorial := n * fatorial(n 1)end
Exp: Funo recursiva em Haskell Fatorial
fatorial(0) = 1fatorial(n) = n * fatorial(n 1)
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 69
Nem toda programao recursiva corresponde a umadefinio indutiva
Exp: Funo Recursiva
function ciclo_infinito(x: real): real;beginciclo_infinito := x * ciclo_infinito(x)end
no corresponde a noo de boa ordem no caracteriza definio indutiva
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 70
Obs: Eficincia da RecursoProcessamento de recurso em linguagens imperativas: C, Pascal
considervel demanda do recurso memria
recurso expressa certos programas de forma mais elegante mas no muito recomendado
recurso escrita de forma iterativa (while, for) em geral, mais eficiente
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 71
Obs: Eficincia da Recurso
Recurso em Linguagens funcionais, como Haskell
tcnica padro de aplicar uma operao sucessivamente
base da maioria dos programas funcionais
Otimizaes no-usadas em linguagens imperativas
estudo de tais tcnica no detalhado
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 72
8 Induo e Recurso
8.1 Princpio da Induo Matemtica8.2 Prova Indutiva8.3 Segundo Princpio da Induo Matemtica8.4 Definio Indutiva8.5 Expresses Regulares8.6 Computaes de um Autmato Finito8.7 Leitura Complementar: Gramtica e BNF8.8 Recurso8.9 Leitura Complementar: Funes Recursivas
Parciais
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 73
Matemtica Discreta para Cincia da Computao
P. Blauth Menezes
1 Introduo e Conceitos Bsicos2 Lgica e Tcnicas de Demonstrao3 lgebra de Conjuntos4 Relaes5 Funes Parciais e Totais6 Endorrelaes, Ordenao e Equivalncia7 Cardinalidade de Conjuntos8 Induo e Recurso9 lgebras e Homomorfismos10 Reticulados e lgebra Booleana11 Concluses
-
Matemtica Discreta para Cincia da Computao - P. Blauth Menezes 74
Matemtica Discreta paraCincia da Computao
P. Blauth Menezes
Departamento de Informtica Terica
Instituto de Informtica / UFRGS