Funções Parciais e Representações Numéricas

FUNÇÕES PARCIAIS f Wm Wn Σk 12k W Σk W ℕ Funções Parciais f A B f A B B A x4 x1 y1 y2 x2 x3 y3 y4 x y f x y f y y f é uma relação f é unívoca x A y B fx y f é total Domínio Domain Imagem Range Conjunto de Partida Conjunto de Chegada Computador ou Formalismo Entrada Saída Programa Função Parcial Computador ou Formalismo Funções Parciais Recursivas Linguagem de Programação PL Máquinas de Registradores Ilimitados Máquinas de Registrador Único Máquina de Turing Algoritmos Rotulados de Markov 2 1 3 4 5 6 Modelos teóricos que levaram a construção dos computadores reais O que é um número 101 é um número Representação Numérica 101 100 0 1 101 1 52 0 51 1 50 Na base 10 Na base 5 101 1 102 0 101 1 100 Na base 2 26 em decimal 101 1 22 0 21 1 20 5 em decimal Representação Numérica Quanto é 725 na base 4 725 4 181 1 4 45 1 4 11 1 4 2 3 4 0 2 23111 725 2 44 3 43 1 42 1 41 1 40 Representação Numérica Quanto é 725 na base 5 725 5 145 0 5 29 0 5 5 4 5 1 0 5 0 1 10400 725 1 54 0 53 4 52 0 51 0 50 Representação Numérica Quanto é 725 na base 16 725 16 45 5 16 2 13 16 0 2 2D5 725 2 162 13 161 5 160 D 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 A B C D E F Hexa Decimal O que é um número O que significa 2 Cardinalidade A B bijeção cdA cdB Cardinalidade A PU A B f A B total e bijetiva U universo das ovelhas Equivalência Função Total Bijetiva 2 x y x y U x y Classe de conjuntos PU Partição de PU com a equivalência U PU a b c a b c ab ac bc abc 0 1 2 3 Representação Indoarábica Decimal D 3 13 Representação nÁdica Σn 12n y 225 em Σ5 Exemplos z 225 em Σ7 x 225 em Σ10 Vantagem Cada número tem apenas UMA representação em Wn nÁdica para Indoarábica νx νσk σ1σ0 k i0 σi ni σk nk σ1 n σ0 y 225 em Σ5 y 2 52 2 51 5 50 50 10 5 65 Qual valor de y na representação decimal Exemplo nÁdica para Indoarábica νx νσk σ1σ0 k i0 σi ni σk nk σ1 n σ0 z 225 em Σ7 νz 2 72 2 71 5 70 98 14 5 117 Qual valor de x na representação decimal Exemplo nÁdica para Indoarábica νx νσk σ1σ0 k i0 σi ni σk nk σ1 n σ0 w 231 em Σ4 Exemplo ν231 2 42 3 4 1 45 ν231 Representação 1ádica 1i 1j 1ij palavra de comprimento m em Σ1 Operações nádicas νz νx νy νz νx νy νz νxνy νz νx νy νz νx νy νx νy Indoarábica para nÁdica η2x Exemplo x 101 101 Base 2 2 50 1 2 24 2 2 11 2 2 5 1 2 2 1 2 0 2 211221 Σ2 12 Indoarábica para nÁdica η5x Exemplo x 101 101 Base 5 5 20 1 5 3 5 5 0 3 351 Σ5 12345 Indoarábica para nÁdica η10x Exemplo x 101 101 Base 10 10 10 1 10 0 A A1 Σ10 123456789A Indoarábica para nÁdica η10x Exemplo x 100 100 Base 10 10 9 A 10 0 9 9A Σ10 123456789A Indoarábica para nÁdica η16x Exemplo x 101 101 Base 16 16 6 5 16 0 6 65 Indoarábica para nÁdica η16x Exemplo x 256 256 Base 16 16 16 15 16 0 15 FG Σ16 123456789A B C D E F G G F ν η ν η IdD η ν IdA Indução Método para definir funções e provar teoremas Indução Princípio 1 Seja x x A x 1 A 0 A A W A W Se Então Indução Princípio 2 Seja x 0 y xy A x A 0 A A W A W Se Então Indução Princípio 3 Seja x W σ Σ x A x σ A 0 A A W A W Se Então