View
34
Download
4
Category
Preview:
DESCRIPTION
UNIPÊ – Centro Universitário de João Pessoa Curso de Ciências da Computação. Teoria da Computação. MÁQUINAS UNIVERSAIS Fabrício Dias fabriciounipe@ig.com.br. Agenda. Algoritmo – Definições Máquina – Definições Máquina Universal Codificação de conjuntos estruturados e programas monolíticos - PowerPoint PPT Presentation
Citation preview
Teoria da ComputaçãoMÁQUINAS UNIVERSAIS
Fabrício Dias
fabriciounipe@ig.com.br
UNIPÊ – Centro Universitário de João PessoaCurso de Ciências da Computação
Agenda
Algoritmo – Definições Máquina – Definições Máquina Universal Codificação de conjuntos estruturados e
programas monolíticos Exemplos
Algoritmo
Termo usado intuitivamente para a solução de um problema
ProblemaProblema
SoluçãoSolução
ALGORITMOALGORITMO
4
Algoritmo
Solução de um problema: Descrição finita e não-ambígua; Passos discretos; Executáveis mecanicamente em um
tempo finito.
5
Algoritmo Limitações de tempo podem,
eventualmente, determinar se um algoritmo pode ou não ser utilizado na prática;
Entretanto, limitações de tempo não são restrições teóricas pois a inexistência de limitações não implica recursos ou descrições infinitas.
6
Algoritmo
Assim, recursos de tempo e de espaço devem ser “tanto
quanto necessários”.
7
Algoritmo Considerando que um algoritmo deve
possuir uma descrição finita, alguns tipos de dados podem não satisfazer tal condição, por exemplo os números irracionais O número
Assim, no que segue, o estudo é restrito aos algoritmos definidos sobre o conjunto dos números naturais.
8
Algoritmo
Algoritmos definidos sobre o conjunto dos números naturais. Qualquer conjunto contável pode ser
equivalente ao dos naturais, através de uma codificação.
Máquina
Conceito: Interpreta os programas de acordo com os dados
fornecidos; É capaz de interpretar um programa desde que
possua uma interpretação para cada operação ou teste que constitui o programa.
10
Máquina
O conceito de programa satisfaz à noção intuitiva de algoritmo;
Entretanto, é necessário definir a máquina a ser considerada;
Tal máquina deve ser suficientemente: Simples Poderosa
11
Máquina Simples:
Permite estudos de propriedades, sem a necessidade de considerar características não-relevantes;
Permite estabelecer conclusões gerais sobre a classe de funções computáveis;
Poderosa: Capaz de simular qualquer característica de
máquinas reais ou teóricas.
12
Máquina Universal
Se for possível representar qualquer algoritmo como um programa em uma máquina, então esta é denominada de máquina universal.
13
Máquina Universal
Evidências de que uma máquina é universal: Evidência Interna. Qualquer extensão das
capacidades da máquina universal não aumenta o seu poder computacional;
Evidência Externa. Outros modelos que definem a noção de algoritmo são, no máximo, computacionalmente equivalentes.
14
Codificação de conjuntos estruturados
Problema da codificação de conjuntos estruturados: onde elementos de tipos de dados
estruturados são representados como números naturais.
15
Codificação de conjuntos estruturados
Definição: para um dado conjunto estruturado X, a idéia básica é definir uma função injetora:
c: X →
ou seja, uma função tal que, para todo
x,y X, tem-se que:
se c(x) = c(y), então x=y
Neste caso, o número natural c(x) é a codificação do elemento estruturado x.
16
Exemplo 1 Codificação de n-Uplas Naturais
Suponha que é desejado codificar, de forma única, elementos de Nn como números naturais, ou seja, deseja-se uma função injetora:
c: Nn → N
17
Exemplo 1
Uma codificação simples é a seguinte:
a) pelo Teorema Fundamental da Aritmética, cada número natural é unicamente decomposto em seus fatores primos;
18
Exemplo 1
Uma codificação simples é a seguinte:
b) suponha que p1 = 2, p2 = 3, p3 = 5 e assim sucessivamente. Então, a codificação
c: Nn → N
definida como segue é unívoca (suponha (x1, x2, ..., xn) em Nn):
c(x1, x2, ..., xn) = p1x1 * p2
x2 * ... * pnxn
19
Exemplo 2 Codificação de Programas Monolíticos
Um programa monolítico pode ser codificado como um número natural.
Suponha um programa monolítico
P = (I, r) com n instruções rotuladas onde {F1, F2, ..., Ff} e {T1, T2, ..., Tt} são os correspondentes conjuntos de identificadores de operações e testes;
20
Exemplo 2 Codificação de Programas Monolíticos
Seja P' = (I, 1) como P, onde 1 é o rótulo inicial, e 0 o único rótulo final;
Assim, uma instrução rotulada pode ser de uma das duas seguintes formas:
a) Operação:
r1: faça Fk vá_para r2
b) Teste:
r1: se Tk então vá_para r2 senão vá_para r3
21
Exemplo 2 Codificação de Programas Monolíticos
Cada instrução rotulada pode ser denotada por uma quádrupla ordenada, onde a primeira componente identifica o tipo da instrução:
a) Operação (0):
r1: faça Fk vá_para r2
(0, k, r2, r2)
b) Teste (1):
r1: se Tk então vá_para r2 senão vá_para r3
(1, k, r2, r3)
22
Exemplo 2 Codificação de Programas Monolíticos
Usando a codificação, o programa monolítico P’, visto como quádruplas ordenadas pode ser codificado como segue: cada quádrupla (instrução rotulada) é
codificada como um número natural. Assim, o programa monolítico P’ com m instruções rotuladas pode ser visto como uma n-upla;
23
Exemplo 2 Codificação de Programas Monolíticos
por sua vez, a n-upla correspondente ao programa monolítico P’ é codificada como um número natural, usando a codificação.
24
Exemplo 2 Codificação de Programas Monolíticos
Suponha o número p = (2150)*(3105) Portanto, o programa possui duas instruções
rotuladas correspondentes aos números 150 e 105. Relativamente às decomposições em seus fatores primos, tem-se que: 150 = 21*31*52*70
105 = 20*31*51*71
25
Exemplo 2 Codificação de Programas Monolíticos
o que corresponde às quádrulas:
(1, 1, 2, 0) e (0, 1, 1, 1), que é o mesmo que:
1: se T1 então vá_para 2 senão vá_para 0
2: faça F1 vá_para 1
26
Exemplo Codificar o programa monolítico em um
único número natural P1. F->1, G->2.
1: faça F vá_para 22: se T então vá_para 3 senão vá_para 53: faça G vá_para 44: se T então vá_para 1 senão vá_para 05: faça F vá_para 66: se T então vá_para 7 senão vá_para 27: faça G vá_para 88: se T então vá_para 6 senão vá_para 0
27
Exemplo
1: faça F vá_para 2 (0, 1,2, 2)2: se T então vá_para 3 senão vá_para 5 (1, 1, 3, 5)3: faça G vá_para 4 (0, 2, 4, 4)4: se T então vá_para 1 senão vá_para 0 (1, 1, 1, 0)5: faça F vá_para 6 (0, 1, 6, 6) 6: se T então vá_para 7 senão vá_para 2 (1, 1, 7, 2)7: faça G vá_para 8 (0, 2, 8, 8)8: se T então vá_para 6 senão vá_para 0 (1, 1, 6, 0)
28
Exemplo
que correspondem aos seguintes números naturais:1: 20.31.52.72 = 36752: 21.31.53.75 = 126052503: 20.32.54.74 = 135056254: 21.31.51.70 = 305: 20.31.56.76 = 55147968756: 21.31.57.72 = 73507: 20.32.58.78 = 202668785200008: 21.31.56.70 = 93750
29
Exemplo Transformando o programa monolítico
em um número natural, temos que P1:
P1 = 23675 * 312605250 * 513505625
* 730 * 115514796875* 137350 * 1720266878520000 * 1993750
Dúvidas????
Recommended