Funções em Matemática Discreta e Programação

Matemática Discreta Ângelo Magno de Jesus Funções Motivação Funções são a base para estruturação de códigos de programas portanto são de extrema importância para a Ciência da Computação Praticamente todas as linguagens de programação utilizam funções Há linguagens de programação orientadas a funções que são ditas linguagens funcionais A linguagem Haskell é um exemplo Funções Relação funcional Relação Total Uma relação binária R A B é uma relação total se e somente se a Ab BaRb Em outras palavras temos que para uma relação ser total todos os elementos do conjunto origem devem estar relacionados a algum elemento do conjunto destino O domínio de definição é o próprio conjunto A Funções Função é uma relação Funcional e Total Ou seja Cada elemento do conjunto origem deve estar relacionado a no máximo um elemento do conjunto destino Todos os elementos do conjunto origem devem estar relacionados a algum elemento do conjunto destino Exemplos Funções Exemplos relação relação função função Funções Função Injetora Uma função R A B é uma função injetora se e somente se Em outra palavras temos que para uma função ser injetora cada elemento do conjunto destino deve estar relacionado a no máximo um elemento do conjunto origem Funções Função Injetora Ex Funções Função Injetora Ex não sim Funções Função Injetora fx x 3 é injetora fx x² 1 é injetora Funções Função sobrejetora Uma função R AB é sobrejetora se e somente se Em outras palavras temos que para uma função ser sobrejetora todos os elementos do conjunto destino devem estar relacionados a algum elemento do conjunto origem O conjunto imagem é o próprio conjunto B Funções Função sobrejetora ex 0 Funções Função sobrejetora ex sim não 0 Funções Função sobrejetora fx x 2 é sobrejetora fx x³ Obs Domínio e Imagem são números inteiros fx x par x 1 x ímpar 0 É sobrejetora Funções Função Bijetora Função que é simultaneamente Injetora e Sobrejetora Recursividade Funções Recursivas Aplicação A recursividade está presente na natureza e até mesmo na música No desenvolvimento de software algoritmos as funções recursivas são de extrema importância Funções Recursivas São funções que invocam a si mesmas Recursão Ver Recursão Funções Recursivas As funções recursivas normalmente consistem nos passos Passos recursivos uma ou mais etapas onde a função chama a si mesma Passos base caso base onde a se encerra a recursão caso contrário a função entrará em um loop infinito Funções Recursivas Floco de neve recursão de 1 a 6 Funções Recursivas Exemplo fatorial 1 se n 0 n fatn 1 se x 0 fatn caso base caso recursivo fat0 1 fatn n fatn 1 Simplificando Funções Recursivas Exemplo fatorial Funções Recursivas Exemplo fatorial Funções Recursivas Exemplo fatorial Funções Recursivas Exemplo fatorial Funções Recursivas Exemplo fatorial Funções Recursivas Exemplo fatorial Funções Recursivas Exemplo fatorial Funções Recursivas Exemplo fatorial Funções Recursivas Número de Fibonacci Funções Recursivas Número de Fibonacci Homenagem ao Matemático Italiano Leonardo de Pisa 1170 1250 que era conhecido como Fibonacci Sendo considerado um dos maiores matemáticos do período medieval Seu livro de 1202 intitulado Liber Abaci introduziu a sequência na matemática da Europa Ocidental A sequência de Fibonacci tem aplicações na análise de mercados financeiros na ciência da computação e na teoria dos jogos Também aparece em configurações biológicas Funções Recursivas Número de Fibonacci 0 se n 0 1 se n 1 fibn 1 fibn 2 outros casos fibn fib0 0 fib1 1 fibn fibn 1 fibn2 Simplificando Funções Recursivas Ex Fazer fib5 Funções Recursivas Exercícios Criar pilha de recursão fatorial6 Dada a definição 0 se x 3 n fn 3 outros casos fx Criar pilha de recursão f10 Referências Matemática Discreta Márcia Rodrigues Notare Universidade de Caxias do Sul Centro de Ciências Exatas e Tecnologia Departamento de Informática Discrete Mathematics Using a Computer Cordelia Hall John ODonnel Fundamentos Matemáticos para Ciência da Computação Judith Gersting Wikipédia Enciclopédia Livre