Funções

Prévia do material em texto

Aspectos Teóricos da Computação I
05 - Funções
Leonardo Jose Silvestre1
1Departamento de Computação e Eletrônica (DCEL)
Centro Universitário do Norte do Espírito Santo (CEUNES)
Universidade Federal do Espírito Santo(UFES)
Aspectos Teóricos da Computação I, 2014/2
DCEL (UFES) 05 - Funções ATCI 1 / 90
Funções Parciais e Totais
Função Parcial
Simplesmente relação funcional
Função Total ou Função
Relação funcional total
Portanto
Função parcial é relação
Função é função parcial (portanto, é relação)
Nem toda relação é função parcial (basta considerar uma relação
não-funcional)
Nem toda função parcial é uma função (basta considerar uma
função parcial não-total)
DCEL (UFES) 05 - Funções ATCI 2 / 90
Funções Parciais e Totais
Função Parcial
Simplesmente relação funcional
Função Total ou Função
Relação funcional total
Portanto
Função parcial é relação
Função é função parcial (portanto, é relação)
Nem toda relação é função parcial (basta considerar uma relação
não-funcional)
Nem toda função parcial é uma função (basta considerar uma
função parcial não-total)
DCEL (UFES) 05 - Funções ATCI 2 / 90
Funções Parciais e Totais
DCEL (UFES) 05 - Funções ATCI 3 / 90
Estudo das funções
Destacado do estudo das relações
Importante para a Matemática e Computação
Maioria das abordagens matemáticas é centrada no conceito de
função total
Em Computação, função parcial é tão ou mais importante que
função
Computablidade:
Noção mais fundamental em CC
Baseada em funções parciais
DCEL (UFES) 05 - Funções ATCI 4 / 90
Função Parcial
Definição
Função Parcial é uma relação funcional f ⊆ A× B
Portanto, função parcial é relação na qual cada elemento do
domínio está relacionado com, no máximo, um elemento do
contra-domínio
Notação
Função parcial f ⊆ A× B
f : A 9 B
ou, quando é claro que se trata de uma função parcial
f : A→ B
〈a,b〉 ∈ f
f (a) = b ou f 〈a〉 = b
DCEL (UFES) 05 - Funções ATCI 5 / 90
Termos alternativos para função parcial
Operação parcial
Mapeamento parcial
Transformação parcial
DCEL (UFES) 05 - Funções ATCI 6 / 90
Relações Funcionais - Exemplos
A = {a}, B = {a,b} e C = {0,1,2}
∅ : A→ B X
{〈0,a〉, 〈1,b〉} : C → B X
=: A→ B X
x2 : Z→ Z onde x2 = {〈x , y〉 ∈ Z2|y = x2} X
A× B : A→ B ×
<: C → C ×
DCEL (UFES) 05 - Funções ATCI 7 / 90
Função parcial como matriz ou grafo (endorrelação)
Matriz: no maximo um valor verdadeiro em cada linha
Grafo: no máximo uma aresta partindo de cada nodo
Função Parcial - Exemplo
⇒ Adição nos naturais: Operação ad: N× N→ N tal que
ad〈a,b〉 = a + b
Conjunto imagem?
⇒ Divisão nos reais. Operação div: R× R→ R tal que:
div〈x , y〉 = x/y
Conjunto imagem?
DCEL (UFES) 05 - Funções ATCI 8 / 90
Função Parcial Dual
Relação dual de uma função parcial não necessariamente é uma
função parcial (por quê?)
Relação Dual de Função Parcial - Exemplo
A = {0,1,2} e endofunção parcial f : A→ A tal que f = 〈0,2〉, 〈1,2〉
f op = 〈2,0〉, 〈2,1〉
f op é uma relação não funcional
DCEL (UFES) 05 - Funções ATCI 9 / 90
Função Parcial Dual
Lembre-se: conceito dual de funcional é injetora
Dual de função parcial é função parcial?
Deve ser injetora, ou seja
Relação dual de uma relação funcional e injetora é relação injetora
e funcional
Conclusão:
Relação dual de função parcial injetora é função parcial injetora.
DCEL (UFES) 05 - Funções ATCI 10 / 90
Relação Dual de Função Parcial - Exemplo
A = {a}, B = {a,b} e C = {0,1,2}. Duais são funções parciais?
∅ : A→ B X
=: A→ B X
{〈0,a〉, 〈1,b〉} : C → B X
x2 : Z→ Z onde x2 = {〈x , y〉 ∈ Z2 | y = x2} ×
DCEL (UFES) 05 - Funções ATCI 11 / 90
Composição de Funções Parciais
Composição de relações é relação, por definição
Composição de funções parciais é função parcial?
Basta mostrar que a composição de funcionais é funcional
Teorema: Composição de Funcionais é Funcional
R : A→ B e S : B → C relações funcionais
Então S ◦ R : A→ C é uma relação funcional
DCEL (UFES) 05 - Funções ATCI 12 / 90
Composição de Funcionais é Funcional - Prova
Suponha R : A→ B e S : B → C relações funcionais.
Então S ◦ R : A→ C é relação e basta provar que
(∀a ∈ A)(∀c1 ∈ C)(∀c2 ∈ C)(a(S ◦ R)c1 ∧ a(S ◦ R)c2 → c1 = c2)
Suponha a ∈ A, c1 ∈ C e c2 ∈ C tais que a (S ◦ R)c1 ∧ a(S ◦ R)c2
a (S ◦ R) c1 ∧ a (S ◦ R) c2 ⇒ (definição de composição)
(∃b1 ∈ B)(∃b2 ∈ B)(aRb1 ∧ a R b2 ∧ b1 S c1 ∧ b2 S c2)⇒ (R é funcional)
b1 = b2 ∧ b1 S c1 ∧ b2 S c2 ⇒ (S é funcional)
c1 = c2
Então (prova direta)
Logo, S ◦ R : A→ C é relação funcional
DCEL (UFES) 05 - Funções ATCI 13 / 90
Composição de Funções Parciais - Exemplo
f = {〈a,1〉, 〈c,5〉, 〈d ,5〉}
g = {〈1, x〉, 〈2, y〉, 〈4, y〉, 〈5, z〉}
g ◦ f = {〈a, x〉, 〈c, z〉, 〈d , z〉}
DCEL (UFES) 05 - Funções ATCI 14 / 90
Dualidade e Prova de Teoremas - Observação
Fato extremamente importante
Todo o resultado válido tambem é válido para o seu conceito dual
Prova é praticamente a mesma, respeitando as noções duais
Não é tão evidente na Teoria dos Conjuntos
Amplamente explorado na Teoria das Categorias
Noção de dualidade divide o trabalho pela metade, incluindo
definições e provas
DCEL (UFES) 05 - Funções ATCI 15 / 90
Dualidade
Por dualidade, composição de relações injetoras é uma relação
injetora
Composição de Injetoras é Injetora - Teorema
R : A→ B e S : B → C relações injetoras
Então S ◦ R : A→ C é uma relação injetora
Prova
Exercício: dualizar prova anterior
DCEL (UFES) 05 - Funções ATCI 16 / 90
Restrição
Para uma função parcial
Pode-se definir uma restrição, a partir de um subconjunto de seu
domínio
Operação (sobre funções)
Importante quando aplicada sobre sistemas
Uma das operações fundamentais da álgebra de processos
DCEL (UFES) 05 - Funções ATCI 17 / 90
Restrição do Domínio de uma Função Parcial
Definição
f : A→ B função parcial e A0 tal que A0 ⊆ A
Restrição do Domínio de f relativamente a A0
f \ A0 : A0 → B
é tal que
f \ A0 = f ∩ (A0 × B)
DCEL (UFES) 05 - Funções ATCI 18 / 90
Restrição do Domínio de uma Função Parcial
Exemplo
A = {1,2,3,4,5}, B = {x , y , z} e a função parcial f : A→ B
Para A0 = {3,4,5}, a função parcial f \ A0 : A0 → B
DCEL (UFES) 05 - Funções ATCI 19 / 90
Restrição do Domínio de uma Função Parcial - Exemplo
A = {a}, B = {a,b} e C = {0,1,2}
∅ : A→ B ∅ \ A = ∅ : A→ B
R = {〈0, a〉, 〈1, b〉} : C → B R \ {0} = {〈0, a〉} : {0} → B
idB = {〈a, a〉, 〈b, b〉} : B → B idB \ A = {〈a, a〉} : A→ B
x2 = {〈x , y〉 ∈ Z2 | y = x2} : Z→ Z x2 \ N = {〈x , y〉 ∈ N× Z | y = x2}: N→ Z
Restrição introduzida foi sobre o domínio: como seria sobre o
contra-domínio? Exercício
Restrição de sistemas: exemplificação em autômatos finitos
DCEL (UFES) 05 - Funções ATCI 20 / 90
Autômato Finito
Autômato Finito
Sistema de estados finitos
Modelo computacional do tipo sequencial muito comum
Usado em diversos estudos
Linguagens Formais, Compiladores
Semântica Formal, Teoria da Concorrência, . . .
Conceito de autômato finito introduzido (via exemplos)
Baseado em Linguagens Formais
Usados para verificar se (w - palavra, L - linguagem)
w ∈ L ou w /∈ L
DCEL (UFES) 05 - Funções ATCI 21 / 90
Autômato Finito
Modelo e Exemplo
Autômato Finito: máquina composta por
Fita
Unidade de Controle
Programa
Fita: dispositivo de entrada
Contém a informação a ser processada
Finita, dividida em células: cada célula armazena um símbolo
Símbolos: pertencem a um alfabeto de entrada
Não é possível gravar sobre a fita
DCEL (UFES) 05 - Funções ATCI 22 / 90
Autômato Finito
Autômato Finito: Modelo e Exemplo
Unidade de Controle: reflete o estado corrente
Estados
Número de estados: finito e predefinido
Unidade de Leitura
Inicialmente: cabeça na célula mais à esquerda da fita
Lê o símbolo de uma célula de cada vez
Após a leitura, move a cabeça umacélula para a direita
DCEL (UFES) 05 - Funções ATCI 23 / 90
Autômato Finito
Programa: função parcial
Comanda as leituras
Define o estado da máquina
Dependendo do estado corrente e símbolo lido, determina o novo
estado
DCEL (UFES) 05 - Funções ATCI 24 / 90
Autômato Finito
Autômato: aa ou bb como subpalavra
Nodos: estados; q0 - estado inicial; qf - estado final
Arcos: transições ou computações atômicas
Processamento: sucessiva aplicação de computações atômicas
DCEL (UFES) 05 - Funções ATCI 25 / 90
Autômato Finito
Autômato: aa ou bb como subpalavra
Linguagens Formais: o autômato pára (normalmente):
quando processar toda a entrada
aceita a entrada se parar em um estado final
DCEL (UFES) 05 - Funções ATCI 26 / 90
Autômato Finito
Autômato Finito como Função Parcial
Autômato finito definido como função parcial
No estado q0, ao ler a, assume o estado q1
No estado q0, ao ler b, assume o estado q2
〈〈q0,a〉,q1〉
〈〈q0,b〉,q2〉
DCEL (UFES) 05 - Funções ATCI 27 / 90
Autômato Finito
Autômato Finito como Função Parcial
Assim, em cada par ordenado da forma 〈〈q,a〉,p〉
Componentes:
Primeira: o par 〈 estado corrente, símbolo lido 〉
Segunda: novo estado
Função parcial:
δ : Q × Σ→ Q
Q - conjunto finito de estados Σ - alfabeto
〈〈q,a〉,p〉 é tal que δ(〈q,a〉) = p
DCEL (UFES) 05 - Funções ATCI 28 / 90
Autômato Finito
Autômato Finito como Função Parcial
Todos os pares que definem a função programa
Total? Injetora? Sobrejetora?
〈〈q0,a〉,q1〉 〈〈q1,a〉,qf 〉 〈〈q2,a〉,q1〉 〈〈qf ,a〉,qf 〉
〈〈q0,b〉,q2〉 〈〈q1,b〉,q2〉 〈〈q2,b〉,qf 〉 〈〈qf ,b〉,qf 〉
DCEL (UFES) 05 - Funções ATCI 29 / 90
Autômato Finito
Autômato Finito como Interface Homem × Máquina - Exemplo
δ : Q × Σ→ Q
Total? Injetora? Sobrejetora?
Q = {q0,q1,q2,q3,q4}
Σ = { moeda, tecla_doce, tecla_cigarro, tecla_refri, libera_doce,
libera_cigarro, libera_refri }
DCEL (UFES) 05 - Funções ATCI 30 / 90
Autômato Finito
Autômato Finito como Interface Homem × Máquina - Exemplo
DCEL (UFES) 05 - Funções ATCI 31 / 90
Autômato Finito
Restrição de um Autômato Finito
Cálculo de restrição de sistemas
Importante aplicação da operação de restrição de funções
parciais
Reuso de software: importante no estudo de Engenharia de
Software, Paradigma de Orientação a Objetos
DCEL (UFES) 05 - Funções ATCI 32 / 90
Autômato Finito
Restrição de Autômato Finito × Reuso de Software - Exemplo
Desejada uma nova máquina, sem as funções relacionadas com
cigarros
δ \Q × Σ0 : Q × Σ0 → Q
Σ0 = { moeda, tecla_doce, tecla_refri, libera_doce, libera_refri }
DCEL (UFES) 05 - Funções ATCI 33 / 90
Autômato Finito
Obs.: Manutenção de Software
Restrição de software pode facilmente ser implementada
Ferramenta automática de desenvolvimento/manutenção
Programador não altera o software
Realiza uma operação sobre este
Resultado desejado é garantido
Custo de manutenção de software:
Frequentemente é maior que o de desenvolvimento
Baixa confiabilidade de um software alterado (pelo programador)
Portanto, ferramentas automáticas de manutenção/reuso de
software são de fundamental importância
DCEL (UFES) 05 - Funções ATCI 34 / 90
Autômato Finito
Leitura Complementar
Autômatos finitos: memória finita e predefinida
Limitações sérias para solucionar problemas
Linguagens regulares: reconhecidas por autômatos finitos
Hierarquia de linguagens: classe dos problemas mais simples
Exemplo: parênteses balanceados - não existe autômato finito
DCEL (UFES) 05 - Funções ATCI 35 / 90
Autômato Finito
Leitura Complementar
Complexidade de algoritmos
Classe de algoritmos mais eficientes (tempo de processamento)
Qualquer autômato que solucione é igualmente eficiente
Qualquer solução é ótima
Implementação computacional de autômatos finitos: trivial
DCEL (UFES) 05 - Funções ATCI 36 / 90
Função Total
Função Total
Função (total)
Função parcial a qual é total
Herda conceitos e terminologias das relações e funções parciais
Definição: Função, Aplicação
Aplicação, Função Total ou simplesmente Função
Função parcial f : A→ B, a qual é total
Portanto, uma função (total) é uma função parcial definida para todos
os elementos do domínio
DCEL (UFES) 05 - Funções ATCI 37 / 90
Função Total
Função - Exemplos
A = {a}, B = {a,b} e C = {0,1,2}
=: A→ B X
idB : B → B X
x2 : Z→ Z onde x2 = {〈x , y〉 ∈ Z2 | y = x2} X
ad : N× N→ N tal que ad(a,b) = a + b X
∅ : ∅→ ∅ X
∅ : A→ B ×
{〈0,a〉, 〈1,b〉} : C → B ×
A× B : A→ B ×
<: C → C ×
div : R× R→ R tal que div(x , y) = x/y ×
Por que uma relação vazia é função e a outra não?
DCEL (UFES) 05 - Funções ATCI 38 / 90
Função Total
Função como matriz ou grafo (endorrelação)
Matriz: existe exatamente um valor verdadeiro em cada linha
Grafo: existe exatamente uma aresta partindo de cada nodo
No contexto das funções
Injetora coincide com monomorfismo
monomorfismo = injetora + total
Sobrejetora coincide com epimorfismo
epimorfismo = sobrejetora + funcional
Isomorfismo também é denominado de função bijetora
Como isomorfismo = monomorfismo + epimorfismo,
então bijetora = injetora + sobrejetora
DCEL (UFES) 05 - Funções ATCI 39 / 90
Função Total
Função Injetora, Sobrejetora e Bijetora - Exemplos
A = {a}, B = {a,b} e C = {0,1,2} e X um conjunto qualquer
=: A→ B injetora, não-sobrejetora
idX : X → B bijetora
x2 : Z→ Z não-injetora, não-sobrejetora
ad : N× N→ N epimorfismo, não-monomorfismo
∅ : ∅→ ∅ bijetora
{〈0,1〉, 〈1,2〉, 〈2,0〉} : C → C isomorfismo
R = {〈x , y〉 | y = sen x} não-monomorfismo, não-epimorfismo
DCEL (UFES) 05 - Funções ATCI 40 / 90
Função Total
Exemplos Importantes de Funções
Lembre: se Σ é alfabeto, então Σ∗ é conj. das palavras sobre Σ
Exemplo: para Σ = {a,b}
Σ∗ = {ε,a,b,aa,ab,ba,bb,aaa, . . .}
Função constante: qualquer valor do domínio resulta no mesmo valor
do contra-domínio
DCEL (UFES) 05 - Funções ATCI 41 / 90
Função Total
Função Constante - Definição
A e B conjuntos. Função constante em b ∈ B
constb : A→ B
para todo a ∈ A, constb(a) = b
Função Constante - Exemplos
A = {a} e Σ = {a,b} um alfabeto
const5 : R→ R const5 = {〈x ,5〉 ∈ R2}
palavra_vazia : Σ∗ → Σ∗ palavra_vazia = {〈w , ε〉 ∈ Σ∗ × Σ∗}
idA : A→ A
∅ : ∅→ ∅
DCEL (UFES) 05 - Funções ATCI 42 / 90
Função Total
Função Concatenação
Especialmente importante para Computação
Operação binária, definida sobre uma linguagem
Associa a cada par de palavras uma palavra formada pela
justaposição da primeira com a segunda
DCEL (UFES) 05 - Funções ATCI 43 / 90
Função Total
Função Concatenação - Definição
Σ = a,b um alfabeto
conc : Σ∗ × Σ∗ → Σ∗
para todo 〈u, v〉 ∈ Σ∗ × Σ∗, conc〈u, v〉 = uv
Concatenação - Exemplo
Σ = a,b
concatenação das palavras aba e bbb de Σ∗ resulta em
ababbb
palavra de Σ∗.
DCEL (UFES) 05 - Funções ATCI 44 / 90
Função Total
Importantes funções induzidas por relações ou operações sobre
conjuntos
Função Inclusão
Reflete a continência de conjuntos
Toda continência induz um função inclusão e vice-versa
Função projeção
Reflete a relação entre o produto cartesiano e os conjuntos originais
Função imersão
Reflete a relação a união disjunta e os conjuntos originais
Projeção e imersão: caracterizam a reversabilidade das operações
DCEL (UFES) 05 - Funções ATCI 45 / 90
Função Total
Função Inclusão - Definição
A e B conjuntos tais que A ⊆ B
incA,B : A ↪→ B ou simplesmente inc : A ↪→ B
para todo a ∈ A, inc(a) = a
Toda função inclusão é injetora
incA,B : A� B
(por quê?)
DCEL (UFES) 05 - Funções ATCI 46 / 90
Função Total
Função Inclusão × Continência
Vogais = { a, e, i, o, u } e Letras = { a, b, c,. . .,z }
Claramente, Vogais ⊆ Letras
incVogais,Letras : Vogais ↪→ Letras
DCEL (UFES) 05 - Funções ATCI 47 / 90
Função Total
Função Inclusão× Continência
As continências N ⊆ Z, Z ⊆ Q e Q ⊆ R induzem as funções inclusão
incN,Z : N� Z incZ,Q : Z� Q incQ,R : Q� R
Pode-se afirmar que existe a função de inclusão incN,R : N� R?
Generalizando: composição de funções inclusão é uma função
inclusão?
Já foi visto: reversabilidade do produto cartesiano: como pode ser
obtida?
DCEL (UFES) 05 - Funções ATCI 48 / 90
Função Total
Função Projeção - Definição
A e B conjuntos não-vazios e A× B o produto cartesiano
pi1 : A× B → A e pi2 : A× B → B
para todo 〈a,b〉 ∈ A× B
pi1〈a,b〉 = a e pi2〈a,b〉 = b
Recuperação dos operandos originais
A = {pi1〈a,b〉|〈a,b〉 ∈ A× B} primeiro operando
B = {pi2〈a,b〉|〈a,b〉 ∈ A× B} segundo operando
DCEL (UFES) 05 - Funções ATCI 49 / 90
Função Total
Função Projeção - Exemplo
A = {a,b} e B = {x , y} conjuntos e A× B o produto cartesiano
Funções projeção pi1 : A× B → A e pi2 : A× B → B
Toda função projeção é sobrejetora (por quê?)
DCEL (UFES) 05 - Funções ATCI 50 / 90
Função Total
Função Imersão - Definição
A e B conjuntos e A + B a união disjunta
q1 : A→ A + B e q2 : B → A + B
Para todo a ∈ A, tem-se que q1(a) = 〈a,0〉
Para todo b ∈ B, tem-se que q2(b) = 〈b,1〉
DCEL (UFES) 05 - Funções ATCI 51 / 90
Função Total
Função Imersão - Definição
A = {a,b} e B = {b, c}
A + B união disjunta
q1 : A→ A + B e q2 : B → A + B funções de imersão
Toda função imersão é injetora (por quê?).
DCEL (UFES) 05 - Funções ATCI 52 / 90
Função Total
Função Dual
Relação dual de uma função
Não necessariamente é uma função (por quê?)
Relação Dual de Função - Exemplo
f : {0,1,2} → {0,1} tal que f = {〈0,0〉, 〈1,1〉, 〈2,0〉}
f op = {〈0,0〉, 〈1,1〉, 〈0,2〉} não-funcional
g : {0,1} → {0,1,2} tal que g = {〈0,0〉, 〈1,1〉}
gop = {〈0,0〉, 〈1,1〉} não-total
Conjuntos correspondentes a g e gop são iguais
Por que g é função e gop não é função?
DCEL (UFES) 05 - Funções ATCI 53 / 90
Função Total
Função Dual
Condições para que dual de função seja função?
função = total + funcional
lembre-se: o dual de
total é sobrejetora
funcional é injetora
conclusão: sobrejetora + injetora, ou seja, bijetora
DCEL (UFES) 05 - Funções ATCI 54 / 90
Função Total
Relação Dual de Função - Exemplos
A = {a}, B = {a,b} e C = {0,1,2}. Duais são funções?
idB : B → B X
∅ : ∅→ ∅ X
{〈0,1〉, 〈1,2〉, 〈2,0〉} : C → C X
=: A→ B ×
ad : N× N→ N, tal que ad(a,b) = a + b ×
x2 : Z→ Z, onde x2 = {〈x , y〉 ∈ Z2 | y = x2} ×
R = {〈x , y〉 | y = sen x} ×
DCEL (UFES) 05 - Funções ATCI 55 / 90
Função Total
Composição de Funções
Composição de funções parciais é função parcial: já foi visto
Composição de funções é função? Basta provar que a
composições de relações totais é total
Teorema: Composição de Totais é Total
R : A→ B e S : B → C relações totais
Então S ◦ R : A→ C é total
DCEL (UFES) 05 - Funções ATCI 56 / 90
Função Total
Composição de Totais é Total - Prova
Suponha R : A→ B e S : B → C relações totais
Então S ◦ R : A→ C é relação
Basta provar que composição de totais é total
(∀a ∈ A)(∃c ∈ C)(a(S ◦ R)c)
De fato, suponha a ∈ A. Então:
a ∈ A⇒ R é total
(∃b ∈ B)(aRb)⇒ S é total
(∃b ∈ B)(∃c ∈ C)(aRb ∧ bSc)⇒ definição de composição
(∃c ∈ C)(a(S ◦ R)c)
Logo, S ◦ R : A→ C é uma relação total
DCEL (UFES) 05 - Funções ATCI 57 / 90
Função Total
Composição de Funções- Exemplo
f : A→ B, g : B → C e g ◦ f : A→ C
f = {〈a,1〉, 〈b,2〉, 〈c,5〉, 〈d ,5〉}
g = {〈1, x〉, 〈2, y〉, 〈3, y〉, 〈4, y〉, 〈5, z〉}
g ◦ f = {〈a, x〉, 〈b, y〉, 〈c, z〉, 〈d , z〉}
DCEL (UFES) 05 - Funções ATCI 58 / 90
Função Total
Por dualidade do Teorema da Composição de Totais
Composição de relações sobrejetoras é relação sobrejetora
Exercício: provar, “dualizando” a prova do teorema
Corolário: Composição de Sobrejetoras é Sobrejetora
R : A→ B e S : B → C relações sobrejetoras
Então S ◦ R : A→ C é sobrejetora
DCEL (UFES) 05 - Funções ATCI 59 / 90
Construções Matemáticas como Funções
Construções Matemáticas como Funções
Funções são frequentemente usadas para definir outras
construções matemáticas
Exemplos
Sequência
Multiconjunto
Conjunto indexado
Relação
DCEL (UFES) 05 - Funções ATCI 60 / 90
Construções Matemáticas como Funções
Relação como Função
Relação R : A→ B
R ⊆ A× B
Como todo subconjunto define uma função inclusão, qualquer relação
pode ser vista como
incR,A×B : R � A× B
Definição alternativa para relação
Na Matemática e na Computação
Usual definições alternativas equivalentes para uma mesma
construção
DCEL (UFES) 05 - Funções ATCI 61 / 90
Construções Matemáticas como Funções
Multiconjunto
Informalmente, um conjunto é
uma coleção, sem repetições e sem qualquer ordenação, de
objetos denominados elementos
Formalmente
uma coleção de zero ou mais objetos distintos, chamados
elementos do conjunto os quais não possuem qualquer
ordem associada
Característica fundamental
elementos distintos, não podem ser repetidos
DCEL (UFES) 05 - Funções ATCI 62 / 90
Construções Matemáticas como Funções
Multiconjuntos
Pela definição de igualdade de conjuntos
{1,2,3} = {3,3,3,2,2,1}
Multiconjuntos
Em alguns momentos é necessário tratar conjuntos com
repetições
Exemplo
União disjunta
Grafos
Na união disjunta, foi apresentada uma solução
Garante uma identidade única de cada elemento
Noção de “sobre-nome”
Vantagem: reversabilidade da operação
Multiconjunto: solução alternativa (não permite a reversabilidade)
DCEL (UFES) 05 - Funções ATCI 63 / 90
Construções Matemáticas como Funções
Grafo
Toda endorrelação pode ser vista como um grafo
Nem todo grafo é uma relação
Um motivo: grafos podem possuir arcos paralelos
Quais arcos são paralelos?
DCEL (UFES) 05 - Funções ATCI 64 / 90
Construções Matemáticas como Funções
Multiconjunto - Definição
X conjunto
Multiconjunto A de objetos de X é uma função
A : X → N
Notação
Como um conjunto, explicitando as repetições - destacando que
trata-se de um multiconjunto
DCEL (UFES) 05 - Funções ATCI 65 / 90
Construções Matemáticas como Funções
Multiconjunto - Exemplo
{1,2,3} 6= {3,3,3,2,2,1}
DCEL (UFES) 05 - Funções ATCI 66 / 90
Construções Matemáticas como Funções
Grafo com Arcos Paralelos - Exemplo
G = {〈A,B〉, 〈A,B〉, 〈B,B〉, 〈B,B〉, 〈B,B〉}
DCEL (UFES) 05 - Funções ATCI 67 / 90
Construções Matemáticas como Funções
Sequência
Termo sendo usado intuitivamente
Quando da definição de produto cartesiano
Noção mais formal de sequência (finita) ou de n-upla ordenada
Sequência de n componentes, denominada de n-upla
ordenada consiste de n objetos (não necessariamente
distintos) em uma ordem fixa
〈x1, x2, x3, . . . , xn〉 6= {x1, x2, x3, . . . , xn}
DCEL (UFES) 05 - Funções ATCI 68 / 90
Construções Matemáticas como Funções
Sequência Infinita, Sequência Finita - Definição
X conjunto
Sequência Infinita de X é uma função
x : N− {0} → X
Sequência Finita ou n-upla Ordenada com n componentes de objetos
de X é uma função
x : {1,2,3, . . . ,n} → X
DCEL (UFES) 05 - Funções ATCI 69 / 90
Construções Matemáticas como Funções
Palavra como Função - Exemplo
Σ = {a,b, c, . . . , z} alfabeto
Palavra casa como função (não-injetora)
casa : {1,2,3,4} → Σ
casa = {〈1, c〉, 〈2,a〉, 〈3, s〉, 〈4,a〉}
DCEL (UFES) 05 - Funções ATCI 70 / 90
Construções Matemáticas como Funções
Conjunto Indexado
uma variável do tipo arranjo é uma sequência finita de
variáveis, todas do mesmo tipo
Exemplo:
dados = array[1..10] of char
Corresponde à função:
dados : {1,2,3, . . . ,10} → X
X é um conjunto de variáveis do tipo char
Função dados é
Injetora?
Sobrejetora?
DCEL (UFES) 05 - Funções ATCI 71 / 90
Construções Matemáticas como Funções
Conjunto Indexado
dados : 1,2,3, . . . ,10→ X
Injetora: Cada componente de um arranjo é distinta
dados: 1,2,3, . . . ,10� X
No exemplo
dados(1) e dados(8) são variáveis do tipo char distintas
Correspondem às componentes dados[1] e dados[8]
Sobrejetora: Cada componente do arranjo é indexável por algum
índice
dados : 1,2,3, . . . ,10� X
Logo, a função é bijetora
dados : {1,2,3, . . . ,10} ↔ X
Generalização do raciocínio define conjunto indexado
DCEL (UFES) 05 - Funções ATCI 72 / 90
Construções Matemáticas como Funções
Conjunto Indexado - Definição
I e X conjuntos. Então, para uma função bijetora
f : I ↔ X
X é um Conjunto Indexado pelo conjunto I
Portanto, qualquer função bijetora define um conjunto indexado
Para f : I ↔ X
I - conjunto de índices
x ∈ X é genericamente denotado usando o seu índice i ∈ I
f (i) é denotado por xi
DCEL (UFES) 05 - Funções ATCI 73 / 90
Função de Hashing
Função de Hashing
Armazenamento e recuperação de informações
Eficiente: espaço de armazenamento e tempo de recuperação
Armazenamento e recuperação pode ser em
Tabela: variável do tipo arranjo
Arquivo de acesso direto: arquivo
Cada entrada/registro acessável diretamente
suponha que se trata de tabela
DCEL (UFES) 05 - Funções ATCI 74 / 90
Função de Hashing
Função de Hashing
Solução simples e eficiente
chave de identificação (exemplo, número de matrícula de alunos)
índice da tabela
se os valores para chave� número provável de entradas?
exemplo: cadastro de clientes de loja sendo CPF a chave
espaço de armazenamento excessivamente grande e esparso
Para uma tabela com poucas entradas
usando uma chave relativamente grande
como endereçar a correspondente entrada na tabela?
f : Chaves → {1,2,3, . . . ,n}
DCEL (UFES) 05 - Funções ATCI 75 / 90
Função de Hashing
Função de Hashing
Função para obter o endereço de instalação
Função de cálculo de endereço
Função de aleatorização
Função de randomização
Função de hashing
Função ideal
Injetora (por quê?)
No entanto, é difícil conseguir um monomorfismo
Funções de hashing geralmente geram colisões
Mesmo endereço a chaves diferentes
c1 6= c2 ∧ f (c1) = f (c2) colisão
DCEL (UFES) 05 - Funções ATCI 76 / 90
Função de Hashing
Função de Hashing - Exemplo
Chave: entre 0 e 1000
Tabela: entradas indexadas de 1 a 23
Função de hashing relativamente simples e razoavelmente
eficiente
f : {0,1, . . . ,1000} → {1,2, . . . ,23}f (c) = (c mod 23) + 1
Exemplo de cálculos e colisões:
DCEL (UFES) 05 - Funções ATCI 77 / 90
Função de Hashing
Função de Hashing
Como obter uma função de hashing injetora?
Métodos de tratamento de colisões
Política para a escolha de uma entrada disponível
Estudo das Estruturas de Dados
DCEL (UFES) 05 - Funções ATCI 78 / 90
Funções nas Linguagens de Programação
Funções nas Linguagens de Programação
Maioria das linguagens de programação manipula construções
similares ou baseadas nas funções matemáticas
Pascal: declaração function
Introduzida via exemplos
Permite implementar algumas funções matemáticas
DCEL (UFES) 05 - Funções ATCI 79 / 90
Funções nas Linguagens de Programação
Função em Pascal: Hashing - Exemplo
f (c) = (c mod 23) + 1
Declaração de dois tipos intervalos:
1 type in terv_0_1000 = 0. .1000
2 in terv_1_23 = 1 . .23
Declaração da função hashing f : {0,1, . . . ,1000} → {1,2, . . . ,23}
1 function hash ( c : interv_0_1000 ) : in terv_1_23 ;
2 begin
3 hash := ( c mod 23) + 1
4 end
DCEL (UFES) 05 - Funções ATCI 80 / 90
Funções nas Linguagens de Programação
Função em Pascal: Hashing - Exemplo
1 function hash ( c : interv_0_1000 ) : in terv_1_23 ;
Domínio da função
c do tipo interv_0_1000
Parâmetro formal
Contra-domínio da função
hash, do tipo interv_1_23
Contém valor resultante do cálculo da chamada da função
1 i f hash (766) = hash (237) then . . .
Exemplo de chamada da função
Valores 766 e 237: parâmetros atuais
Comando após a palavra then é executado?
DCEL (UFES) 05 - Funções ATCI 81 / 90
Funções nas Linguagens de Programação
Função em Pascal: EXOR (⊕) - Exemplo
Ou-Exclusivo denominado de EXOR (do inglês, exclusive or) - ⊕ usual
em Computação
p q p ⊕ q
V V F
V F V
F V V
F F F
DCEL (UFES) 05 - Funções ATCI 82 / 90
Funções nas Linguagens de Programação
Função em Pascal: EXOR (⊕) - Exemplo
EXOR pode ser reescrito, usando os conectivos usuais
p ⊕ q ⇔ (p ∧ ¬q) ∨ (¬p ∧ q)
Função em Pascal que implementa o conectivo ⊕
1 function exor ( p , q : boolean ) : boolean ;
2 begin
3 exor := ( p and not q ) or ( not p and q )
4 end
DCEL (UFES) 05 - Funções ATCI 83 / 90
Funções nas Linguagens de Programação
Função em Pascal: ⊕ - Exemplo
Um problema das funções em Pascal:
não permitem contra-domínio resultante de produto
cartesiano
Exemplo: equação polinomial do segundo grau
ax2 + bx + c = 0
fórmula de Baskara: duas raízes
função do tipo
baskara : R3 → R2
Solução mais adequada: linguagem de programação funcional
DCEL (UFES) 05 - Funções ATCI 84 / 90
Funções nas Linguagens de Programação
Função em Pascal: ⊕ - Exemplo
Um problema das funções em Pascal:
não permitem contra-domínio resultante de produto
cartesiano
Exemplo: equação polinomial do segundo grau
ax2 + bx + c = 0
fórmula de Baskara: duas raízes
função do tipo
baskara : R3 → R2
Solução mais adequada: linguagem de programação funcional
DCEL (UFES) 05 - Funções ATCI 84 / 90
Linguagem de Programação Funcional
Linguagem de Programação Funcional
Programação Funcional
Estilo de programação baseado em
Funções
Composição de funções (constituindo um programa)
Programa:
Expressão funcional é avaliada, em vez de comandos que são
executados
Linguagem de programação funcional:
Linguagem que suporta e encoraja este estilo programação
DCEL (UFES) 05 - Funções ATCI 85 / 90
Linguagem de Programação Funcional
Linguagem de Programação Funcional
Linguagem de programação funcional “pura”
Não possui variáveis, nem atribuições.
Linguagem de programação funcional é composta por:
Tipos primitivos de dados
Constantes de cada tipo primitivo
Operações: funções sobre os tipos primitivos
Construtores que permitem definir novos tipos e operações
DCEL (UFES) 05 - Funções ATCI 86 / 90
Linguagem de Programação Funcional
Haskell
Linguagem de programação funcional pura
Usa o conceito matemático de função
Mesmo valores do domínio (parâmetros atuais) resultam nos
mesmos valores do codomínio (mesmas saídas)
Portanto, resultado da aplicação de uma função, independente de
qualquer estado implícito do sistema
DCEL (UFES) 05 - Funções ATCI 87 / 90
Linguagem de Programação Funcional
Haskell - Exemplo
1 x = 1
Função constante: sempre retorna o valor 1
1 f x = x + 1
Função f: para o parâmetro x, retorna o valor x + 1
Contra-exemplo em Pascal (x variável integer)
1 function contador : integer ;
2 begin
3 x := x + 1;
4 contador := x
5 end
DCEL (UFES) 05 - Funções ATCI 88 / 90
Linguagem de Programação Funcional
Haskell - Exemplo
Exemplo em Haskell: ax2 + bx + c = 0
1 baskara a b c =
2 l e t de l t a = b∗b − 4∗a∗c
3 in ( (−b + s q r t ( de l t a ) ) / ( 2 ∗ a ) ,
4 (−b − s q r t ( de l t a ) ) / ( 2 ∗ a ) )
Para a, b e c, retorna o par ordenado correspondendo às raízes
let é usada para declarar delta
Acessível apenas no escopo da função baskara
DCEL (UFES) 05 - Funções ATCI 89 / 90
Linguagem de Programação Funcional
Haskell - Exemplo
Redução (avaliação) para os valores 1, -5 e 6
1 baskara 1 −5 6
2
3 l e t de l t a = (−5)∗(−5) − 4∗1∗6
4 in ( (5 + s q r t ( de l t a ) ) / ( 2 ∗ 1 ) ,
5 (5 − s q r t ( de l t a ) ) / ( 2 ∗ 1 ) )
6
7 l e t de l t a = 1
8 in ( (5 + s q r t ( de l t a ) ) / 2 ,
9 (5 − s q r t ( de l t a ) ) / 2 )
10
11 ( (5 + 1 ) / 2 ,
12 (5 − 1 ) /2 )
13
14 ( 3 , 2 )
DCEL (UFES) 05 - Funções ATCI 90 / 90
	Autômato FinitoFunção Total
	Construções Matemáticas como Funções
	Função de Hashing
	Funções nas Linguagens de Programação
	Linguagem de Programação Funcional