matemática computacional pt3

Prévia do material em texto

MATEMÁTICA 
COMPUTACIONAL 
AULA 2 
 
 
 
 
 
 
 
 
 
 
 
Prof. Luis Gonzaga de Paulo 
 
 
2 
CONVERSA INICIAL 
Como já é de nosso conhecimento, a matemática é essencial à 
computação. Podemos até afirmar que computação e matemática são uma coisa 
só. E é por isso que nessa aula abordaremos questões que certamente 
despertam seu interesse, tais como a possibilidade de o computador cometer 
erros ou apresentar cálculos com resultados incorretos. Ou a possibilidade de 
validar os resultados obtidos pelos programas de computador, e também a 
capacidade de o computador manter em ordem e localizar as informações 
necessárias às nossas atividades. Vamos lá? 
Para responder a essas questões, trataremos de temas que são 
elementares à aplicação da matemática na computação, como os erros, a teoria 
dos conjuntos, os vetores e as matrizes, suas características principais e as 
operações que podemos realizar com eles. Também veremos elementos e 
estruturas matemáticas de grande importância para a computação, no que se 
refere ao tratamento de dados e ao estabelecimento de processos e fluxo de 
atividades para a solução de problemas. 
Saiba mais 
Para ampliar seus conhecimentos, leia: 
MACEDO, L. R. D., CASTANHEIRA, N. P., ROCHA, A. Tópicos de matemática 
aplicada. Curitiba: InterSaberes, 2013. cap. 2. 
TANEMBAUM, A. S. Organização estruturada de computadores. São Paulo: 
Pearson Prentice Hal, 2014. cap. 3 
TEMA 1 – ESTRUTURAS DE DADOS 
Nesse tema, vamos apresentar elementos matemáticos que têm vasto 
uso na computação, em especial na construção de estruturas de dados e em 
armazenamento, busca e recuperação de informações. 
1.1 Vetores 
Os elementos que denominamos vetores são listas de valores – 
conjuntos, ou arranjos – cujos elementos apresentam caraterísticas em comum. 
Os vetores têm seus elementos posicionados em sequência, e esses elementos 
são acessados usando-se uma chave, o índice do vetor. Os vetores integram 
os elementos de dados que são fundamentais para a resolução de problemas 
 
 
3 
por meio da organização dos dados em programas de computador. Vetores 
também representam segmentos de reta na geometria – uma sequência de 
pontos que forma a reta, sendo dessa forma um elemento gráfico. 
Em ambientes de computação, os vetores fazem parte das estruturas de 
dados homogêneas, por conter somente dados de um único tipo. Uma sequência 
de caracteres (cadeia ou string) é exemplo típico de um vetor que, na linguagem 
de programação C, por exemplo, é um tipo de dado – uma lista de caracteres. 
Nesses ambientes, os vetores são classificados como estruturas de dados 
lineares e estáticas. São compostos por um determinado número de elementos 
de um mesmo tipo ou com as mesmas características, sendo similares a outras 
estruturas de dados, como listas, filas, pilhas ou árvores. 
Nas linguagens de programação em geral, os vetores são tratados como 
variáveis múltiplas de uma única dimensão, as quais possibilitam acesso aos 
seus elementos de modo muito fácil e rápido. Entretanto, a inclusão ou exclusão 
de elementos intermediários é uma operação mais complexa, devendo ser 
bastante criteriosa para reduzir as operações de processamento e evitar a perda 
de dados. A Figura 1 a seguir apresenta dois vetores, um denominado Nome, 
com conteúdo alfanumérico, e outro denominado Idade, contendo apenas 
valores numéricos. 
Figura 1 – Vetores 
 
Em vetores como os da Figura 1, os elementos podem ser tratados 
individualmente, sendo referenciados pelo índice, ou seja, pela posição que 
ocupam no vetor: 
Nome [1] = João; Idade [1] = 35; 
Nome [2] = Maria; Idade [2] = 46; 
Nome [5] = Antônio; Idade [5] = 81; 
Vetores são bastante utilizados em programas de computadores nos 
quais operações de ordenação e busca de informação são recorrentes. 
 
 
4 
1.2 Matrizes 
Em computação as matrizes são um tipo de arranjo de vetores com duas 
ou mais dimensões, cujos dados contêm características comuns. Esses dados 
são organizados sequencialmente e, tal como os vetores, acessados por meio 
da chave – ou índice – da matriz. As matrizes também fazem parte das estruturas 
de dados essenciais para o tratamento de problemas matemáticos em ambientes 
computacionais, especialmente os de computação gráfica. 
As matrizes também são um tipo de estrutura de dados homogêneas, ou, 
como já dissemos, um tipo de arranjo de vetores, em que cada vetor corresponde 
à uma dimensão da matriz. A Figura 2 mostra uma matriz bidimensional, 
enquanto a Figura 3 apresenta uma matriz de três dimensões. 
Figura 2 – Uma matriz de duas dimensões 
 
 Os elementos dessa matriz podem ser referenciados da seguinte maneira: 
 Pessoa [1,1] = João Pessoa [1,2 ] = 35; 
 Pessoa [2,1] = Maria Pessoa [2,2] = 46 Pessoa [2,3] = Professora; 
 Pessoa [3,3] = Arquiteto; 
 Pessoa [5,1] = Antônio Pessoa [5,2] = 81; 
Figura 3 – Matriz de três dimensões 
 
 
 
 
5 
Tal qual os vetores, as matrizes compõem as chamadas estruturas de 
dados lineares e estáticas, podendo conter um número finito de elementos de 
determinado tipo, sejam letras, números ou sinais. Na maioria das linguagens de 
programação, as matrizes são consideradas variáveis de múltiplas dimensões, 
e o acesso aos elementos é feito por meio de índices – as chaves de acesso –, 
havendo um índice para cada dimensão da matriz. 
 As aplicações de planilhas de dados, como o Microsoft Excel, por 
exemplo, são a representação mais típica das matrizes. Também os elementos 
de imagens, tais como os desenhos, as fotografias e os filmes, são compostos 
por matrizes multidimensionais. A tela do computador que você está usando 
neste momento é uma matriz visível, na qual cada minúsculo ponto (ou pixel) 
representa um elemento com várias dimensões, tais como cor, posição e 
intensidade luminosa (brilho/contraste). 
1.3 Conjuntos 
 Os conjuntos são agrupamentos ou coleções de objetos – denominados 
elementos ou membros do conjunto –, cujas características são comuns entre si. 
Os conjuntos são geralmente representados por uma letra maiúscula, e os seus 
elementos são expressos entre chaves, tais como: 
 As vogais V = {A, E, I, O, U, a, e, i, o, u}; 
 Os estados da região sudeste S = {SP, RJ, MG, ES}; 
 Os dígitos do sistema binário de numeração D = {0, 1}. 
 Podemos também representar os conjuntos em sua forma gráfica com o 
diagrama de Venn, como mostrado na Figura 4. O diagrama de Venn contempla 
o conjunto dos números (e seus subconjuntos): Reais R, Irracionais I, Racionais 
Q, Inteiros Z, Naturais N. No caderno de exercícios da disciplina, são 
apresentadas as diversas operações com os conjuntos, além de problemas e 
soluções com o uso desses elementos. 
 
 
 
6 
Figura 4 – Diagrama de Venn 
 
TEMA 2 – ARITMÉTICA DE PONTO FLUTUANTE 
Como já vimos, os computadores são máquinas que trabalham com 
números. Nesse aspecto, os computadores superam a capacidade humana, 
tanto na quantidade quanto na velocidade. Isto porque podem manipular valores 
em grande escala, e o fazem com altíssimas velocidades. Entretanto, há um fator 
limitador: o tamanho, isto é, a quantidade de dígitos necessária para a 
representação desses valores. A maioria dos sistemas computacionais, 
linguagens de programação e softwares, delimitam a quantidade de dígitos que 
podem ser empregados para a representação desses valores. 
Tal como o número de dígitos de um display de calculadora, os sistemas 
computacionais empregam formatos definidos, com um número específico de 
dígitos para a representação dos números reais. Isso se deve ao fato de que a 
quantidade de bits utilizada pelo hardware é fixa, e deve haver uma 
compatibilização entre a quantidade e a representação numérica, de modo a 
evitar problemas com os cálculos, ou o aumento expressivo no tempo necessário 
para a realização dos cálculos. Para essa compatibilização, utilizamos o Sistema 
de Ponto Flutuante (ou de virgulaflutuante). Leia o capítulo 10 (Stallings, 2017), 
e use o caderno de exercícios para auxiliar seu aprendizado. 
 
 
7 
2.1 Sistema de ponto flutuante 
 Os computadores representam os números reais, com a Aritmética de 
Ponto Flutuante, formulada por F[β, t, -p, p], representando o sistema F do 
sistema de numeração de base β com a quantidade t de dígitos na mantissa – 
ou dígitos significativos, e limites de expoente de -p até p,. Os números desse 
sistema são então expressos no seguinte formato: 
 ± (0,𝒅𝟏𝒅𝟐 … 𝒅𝒕)β
𝒆
 
 No qual: 
 β é a base do sistema de numeração com o qual o computador opera 
(geralmente 2, ou binária, para a computação digital); 
 d é um dos dígitos da mantissa, cuja quantidade máxima é definida por t; 
 e representa o expoente, cujo intervalo é definido por p, variando de -p 
até p. 
 Por exemplo: Dado o sistema de representação F[10, 3, -5, 5], que 
significa β = 10, t = 3 e e ∈ [-5,5], temos então: 
 O menor número, em valores absolutos (m), é 0,001 x 10-5, ou seja, 10-8; 
 O maior número, em valores absolutos (M), é 0,999 x 105, ou seja, 99900. 
 Se usarmos esse sistema para representar um dado número, como por 
exemplo N = 227,68 ou seja, N = 0,22768 x 103, será representado como 0,227 
x 103 – caso a opção seja o truncamento ou corte – ou 0,228 x 103, caso a 
opção seja o arredondamento. 
2.2 Representação de Números Reais 
 Um número real é representado, como vimos, em um determinado 
sistema de numeração, com o formato específico desse sistema. A norma 
técnica IEEE 754 define os padrões que regem essa representação, o 
armazenamento e a realização de operações. O intuito é manter a 
compatibilidade entre os diversos ambientes computacionais, garantindo a 
portabilidade dos valores e evitando que diferentes formatos possam resultar em 
erros ou mesmo na impossibilidade da realização dos cálculos. Isto significa que 
temos dois conjuntos distintos de valores, denominados números de precisão 
 
 
8 
simples, com um tamanho de 32 bits, e precisão dupla, com um tamanho de 
64 bits. 
Tabela 1 – A precisão numérica definida pela norma IEEE 754 
 
A representação dos números reais em precisão simples fica como 
mostrado na figura 5, o que significa que podemos representar números no 
intervalo de 1,18 x 10-38 até 3,4 x 1038 aproximadamente, usando para isso sete 
casas decimais. 
Figura 5 – Representação dos números de precisão simples (32 bits) 
 
 Já a representação dos números reais em precisão dupla fica como 
mostra a Figura 6. Isso significa que podemos representar números no intervalo 
de 2,23 x 10-308 até 1,8 x 10308 aproximadamente, com dezesseis casas decimais. 
Figura 6 – Representação dos números de precisão dupla (64 bits) 
 
 
 
9 
2.3 Adição e subtração 
A adição e a subtração de números expressos em ponto flutuante repetem 
o processo para inteiros com expoente, porém é preciso atenção, como com 
qualquer operação cujos operadores utilizem expoentes. O processo pode ser 
descrito em três etapas: 
1. Comparamos a magnitude dos expoentes dos operadores e nivelamos 
esses expoentes, ajustando o do número de menor valor (alinhamento); 
2. Realizamos a operação (adição ou subtração); 
3. Ajustamos a mantissa e o expoente do número resultante 
(normalização). 
Para fixar esses passos, queremos realizar a soma de dois números 
binários expressos em aritmética de ponto flutuante: 
1,1100 x 24 + 1,1000 x 22 
Seguindo os passos descritos, teremos: 
1. Alinhamos os expoentes e a mantissa, ajustando os do menor valor: 
1,1000 x 22  0,0110 x 24 
2. Realizamos a soma dos dois números: 
1,1100 x 24 + 0,0110 x 24 = 10,0010 x 24 
3. Normalizamos o resultado, ajustando a mantissa e o expoente: 
10,0010 x 24  0,1000 x 26, assumindo que temos quatro casas decimais. 
2.4 Multiplicação 
O processo de multiplicação de números expressos em ponto flutuante é 
o mesmo utilizado para a multiplicação de números com expoentes: multiplicam-
se as bases e somam-se os expoentes. Nesse caso, a base é a mantissa. Então, 
se temos dois valores binários a e b, sendo a = ma x 2x e b= mb x 2y, teremos: 
a x b = (ma x mb) x 2x+y. Vejamos a seguinte operação como exemplo: 
1,000 x 2-2 x (-1,010 x 2-1) 
 
 
10 
1. Somamos os expoentes: 
(-2) + (-1) = -3 
2. Multiplicamos as mantissas: 
1,000 x (-1,010) = -1,010000 
3. Normalizamos o resultado, ajustando a mantissa e o expoente: 
-1,01000 x 2-3  -1,010 x 2-3, assumindo que temos três casas decimais. 
2.5 Divisão 
Assim como na multiplicação, o processo de divisão de números 
expressos em ponto flutuante é o mesmo utilizado para os demais números com 
expoentes: dividem-se as bases e subtraem-se os expoentes, lembrado que a 
base é a mantissa. Então, se tivermos que dividir dois valores binários a e b, 
sendo a = ma x 2x e b= mb x 2y, teremos: 
a  b = (ma  mb) x 2x-y. 
Vejamos a seguinte operação como exemplo: 
1,0000 x 2-2  (-1,0100 x 2-1) 
1. Subtraímos os expoentes: 
(-2) - (-1) = -2 + 1 = -1 
2. Dividimos as mantissas: 
1,0000  (--1,0100) = -0,11001100110011... (dízima) 
3. Normalizamos o resultado, ajustando a mantissa e o expoente: 
-0,110011 x 2-1, assumindo seis casas decimais, pois o resultado exigiria 
uma precisão muito maior. 
TEMA 3 – ERROS 
Como já vimos, operações aritméticas de ponto flutuante ou as de 
conversão entre sistemas podem resultar em erros. Estes erros são classificados 
em dois tipos básicos. Temos erros de precisão, decorrentes da limitação de 
dígitos usados para representar os valores – o número de dígitos é geralmente 
pré-definido em decorrência da utilização do sistema binário e da constituição do 
hardware. Este tipo de erro é comum em programação, no caso das variáveis 
utilizadas nos programas de computador. Por outro lado, a aproximação, o 
 
 
11 
arredondamento ou a ocorrência de dízimas periódicas geram os erros de 
exatidão, devido à interrupção abrupta ou forçada da representação. 
Existem grandes diferenças entre esses dois tipos de erros, e as 
implicações de ambos geram consequências distintas, em se tratando do 
ambiente computacional, mesmo que haja semelhanças. Por exemplo, os erros 
de truncamento, decorrentes do limite de precisão, prejudicam diretamente os 
números irracionais, tais como o número π (Pi), que expressamos normalmente 
com duas casas decimais, como 3,14. O valor 3,1415926 de Pi é usado na 
maioria dos cálculos, e é o padrão das calculadoras em geral, pois isso é 
satisfatório para a maioria dos cálculos. Já cálculos mais complexos, que 
requerem maior precisão, podem requerer a representação do Pi com até 
cinquenta e duas casas decimais: 
 
Precisões maiores são obtidas com algoritmos computacionais 
específicos, e já se tem realizado o cálculo de Pi com dezenas de trilhões de 
dígitos. Esses erros podem ser expressos de duas maneiras: na forma absoluta 
ou na forma relativa (em percentual), como veremos a seguir. 
3.1 Erro absoluto 
O erro absoluto é a diferença entre o valor real e a forma na qual foi 
expresso. Calculamos o erro absoluto pela seguinte fórmula: 
𝑬𝑨𝒙 = x - �̅� 
Tomando o exemplo dado do valor de Pi, sendo x o valor de Pì com oito 
casas decimais e �̅� o valor de Pi com dois decimais, então temos: 
3,1415926 - 3.14 = 0,0015926 
É claro que isso é apenas um exemplo, pois o valor real de Pi é algo ainda 
desconhecido. 
 
 
 
12 
3.2 Erro relativo 
O erro relativo é a razão entre o erro absoluto EA e o valor real x, isto é: 
𝑬𝑹𝒙 = 
𝑬𝑨𝒙
𝒙 
 
Ou também: 
𝑬𝑹𝒙 = 
 𝐱 − �̅�
𝐱 
 
Com os valores do exemplo dado: 
𝑬𝑹𝒙 = 
3,1415926 − 3.14
3,1415926
 → 𝑬𝑹𝒙 = 5 x 10
-4 ou 0,05% 
3.3 Exceções 
Nos ambientes computacionais, as operações com ponto flutuante podem 
resultar em interrupção do processamento, o que não é algo esperado. Essas 
operações são decorrentes basicamente de cinco tipos de operações – ou 
exceções: 
1. O overflow é um resultado apresentadoquando é gerado um resultado 
infinito ou muito além da capacidade de representação do sistema. 
2. O underflow ocorre quando é obtido um resultado zero após um 
arredondamento de um valor diferente de zero, ou seja, um valor muito 
menor do que a capacidade de representação do sistema. 
3. A divisão por zero geralmente é o resultado de um cálculo com um 
underflow ou valor pouco significativo para o sistema. Uma divisão por 
zero não possibilita qualquer solução matemática. 
4. Um resultado inexato, apesar de ser algo que pode acontecer com 
relativa frequência, pode resultar tanto de um cálculo que gere overflow 
quanto de arredondamentos. Geralmente, essas ocorrências não geram 
uma interrupção do processo, porém podem, caso façam parte de um 
processo recorrente ou recursivo, se transformar em algo mais crítico, e 
por isso pode ser tratado como uma exceção. 
5. Um número inválido é o resultado de uma operação que não pode ser 
considerado um número, conhecido pela sigla em inglês NaN – Not a 
 
 
13 
Number, como por exemplo a raiz quadrada de um número negativo, uma 
divisão de zero por zero ou de infinito por infinito. 
3.4 Cancelamento catastrófico 
Figura 7 – Cancelamento catastrófico 
 
O cancelamento catastrófico é o nome que se dá ao efeito que ocorre 
quando um cálculo atinge o épsilon ε do sistema computacional. O épsilon do 
sistema é o menor número que, somado a 1, resulta em um número diferente de 
1; ou seja, não é arredondado. O épsilon representa a precisão aritmética relativa 
da máquina, e é consequência da precisão finita da aritmética de ponto flutuante. 
TEMA 4 – ELEMENTOS MATEMÁTICOS COMPUTACIONAIS 
Alguns elementos matemáticos são de grande importância para 
determinadas tarefas, seja a resolução de problemas ou a implementação de 
funcionalidades específicas por meio de programas de computador. Os grafos e 
as árvores são dois desses elementos, dos quais trataremos neste tema. 
4.1 Grafos 
A estrutura gráfica utilizada em matemática para apresentar as relações 
entre os elementos ou objetos de um conjunto é denominada grafo. Grafos são 
expressos na forma de equação como G (V,A), na qual são representados seus 
dois elementos: os vértices e as arestas. Os elementos do conjunto – ou 
componentes, objetos – são representados por círculos ou pontos e 
denominados vértices. Já as relações, ligações, dependências ou “caminhos” 
entre os vértices são representados por segmentos de reta ou linhas, as arestas, 
como nos mostra a Figura 8. 
 
 
14 
Figura 8 – A representação de um Grafo 
 
Os grafos que têm suas arestas direcionadas são denominados grafos 
orientados (ou ainda grafos dirigidos, direcionados ou dígrafos). Um vértice 
pode ser ligado a ele próprio, formando um laço ou loop. As arestas podem 
conter rótulos de identificação, de peso ou valor numérico. Um grafo G é um 
grafo dirigido G = (V, A), tal que V = {A, B, C, D, E, F, G} e A = {(A,B), (B,C), 
(B,D), (B,E), (C,E), (D,E), (E,F), (G,D)}, como mostrado na Figura 9. Neste 
exemplo, é possível identificar rotas ou fluxos entre os vértices, traçando 
caminhos entre eles. 
Figura 9 – Um grafo dirigido 
 
Em um outro caso, temos um grafo não dirigido G = (V, A), representando 
as fronteiras entre alguns países da América do Sul, em que V = {Argentina, 
Bolívia, Brasil, Chile, Paraguai, Uruguai} e A = {(Argentina, Bolívia), 
(Argentina, Brasil), (Argentina, Chile), (Argentina, Paraguai), (Argentina, 
Uruguai), (Bolívia, Brasil), (Bolívia, Chile), (Bolívia, Paraguai), (Brasil, 
Paraguai), (Brasil, Uruguai)}, o que nos mostra a Figura 10. 
E nesse outro caso, mostrado na Figura 11, um grafo dirigido rotulado G 
= (V, N, A), tal que V = {a, b, c, d, e, f} e A = {(a,9,b), (a,4,b), (b,3,b), (b,6,e), 
(d,7,a), (d,7,e), (e,8,d), (e,5,f)}. Note que foram acrescentados valores que 
 
 
15 
identificam as arestas, e que há um vértice c para o qual não há nenhuma 
ligação, além de um loop no vértice b. 
Figura 101 – Um grafo não dirigido 
 
A representação de um grafo finito com n vértices pode ser feita por uma 
matriz de adjacência. Essa matriz tem as dimensões definidas pelo número de 
vértices (n-por-n), e o valor na linha i e coluna j fornece o número de arestas 
que conectam o i-ésimo ao j-ésimo vértices. 
Figura 11 – Um Grafo dirigido rotulado 
 
 A Figura 12 abaixo apresenta uma matriz de adjacência e o respectivo 
grafo. 
Figura 12 – Uma matriz de adjacência com o respectivo grafo 
 
 
 
16 
Importante: 
 Em um dígrafo, contemplamos os graus de saída (o número de arestas 
saindo de um vértice) e de entrada (o número de arestas entrando em um 
vértice); 
 O grau de um vértice de um dígrafo é igual à soma dos graus de saída e 
de entrada. 
4.2 Árvores 
Uma árvore é um grafo conexo, aquele no qual sempre existe uma 
aresta entre dois quaisquer de seus vértices, e que é também acíclico, isto é, 
não existem ciclos ou loops. As árvores correspondem a uma das mais 
importantes estruturas de dados não lineares da computação. 
Com relação à definição de árvores, podemos afirmar que nem todo grafo 
é uma árvore, mas que toda árvore é um grafo. Além disso, é um grafo 
bipartido, isto é, apresenta pelo menos dois níveis. Toda árvore também é um 
grafo planar, que é representado em um plano, em apenas duas dimensões. 
Por outro lado, todo grafo conexo inclui ao menos uma árvore de extensão 
associada a si, composta de todos os seus vértices e de algumas de suas 
arestas. 
Para considerarmos um grafo G com n vértices como uma árvore, 
devemos verificar se esse grafo: 
 É conexo, e há um único caminho entre dois vértices quaisquer; deixará 
de ser conexo se qualquer aresta for removida; 
 É acíclico, tem n – 1 arestas, e ao se incluir uma nova aresta fecha-se 
um novo ciclo. 
Se um determinado vértice da árvore é escolhido como especial, a árvore 
é denominada enraizada, e o vértice escolhido é denominado raiz. Uma árvore 
livre é aquela que não tem raiz. O número máximo de arestas – ou ramos – em 
um vértice – ou elemento – é chamado de ordem ou grau, e a máxima sequência 
de vértices de grau um ou maior define a quantidade de níveis de uma árvore. 
 
 
17 
4.3 Árvore binária 
A árvore binária é o tipo de árvore que a computação mais utiliza, e é 
definida como um grafo acíclico, conexo, dirigido. Cada nó tem grau (ou ordem) 
menos ou igual a. Cada ramo da árvore é um vértice dirigido, sem peso, que 
chega ao próximo (sucessor ou filho) a partir do seu anterior (antecessor ou pai), 
formando uma hierarquia, e fazendo com que só exista um único caminho entre 
dois nós distintos. 
Figura 13 – Uma árvore binária 
 
A implementação de uma árvore binária na programação de 
computadores geralmente usa uma função recursiva, tanto para a construção da 
árvore quanto para o acesso e a modificação dos elementos. A recursão é 
utilizada frequentemente nas operações com árvores binárias; a construção e 
ordenação de listas para a busca binária é uma das principais aplicações das 
árvores binárias. 
Figura 14 – Árvore binária com acesso EDR 
 
 
 
18 
Os percursos possíveis em uma árvore binária são a leitura em pré-ordem, 
em ordem e em pós-ordem. Em “pré-Ordem” (ou RED = raiz, esquerda, direita) 
é acessado um nó raiz, depois seu sucessor da esquerda e em seguida o da 
direita. No acesso “em ordem” (In-Order ou ERD = esquerda, raiz, direita) é 
acessada uma folhada esquerda, sua raiz (ou predecessor), e depois o nó da 
direita. Já no acesso em “pós-ordem” (ou EDR = esquerda, direita, raiz), o acesso 
inicia-se pelo nó da esquerda, desloca-se para o da direita e então segue à raiz 
deles. A Figura 14 apresenta uma árvore binária com o acesso em pré-ordem 
(RED): F,B,A,D,C,E,G,I,H. Nessa mesma árvore, podemos ter o acesso em pós-
ordem (EDR): A,C,E,D,B,H,I,G,F ou em ordem (ERD): A,B,C,D,E,F,G,H,I. 
TEMA 5 – CONTAGEM 
O processo de contar coisas e eventos é muito importante. Amaioria dos 
problemas que tratamos na matemática, na computação e em outras áreas, 
implica contar objetos de conjuntos. Entretanto, esse processo nem sempre é 
fácil, e por isso vamos abordar métodos de contagem para determinados 
conjuntos, de modo a aprender a pensar os problemas do ponto de vista 
quantitativo. Neste tema, vamos ver como o pensamento quantitativo é útil para 
analisarmos problemas discretos, especialmente na área da computação. Uma 
pesquisa sobre análise combinatória ajudará você a entender e aprofundar seus 
conhecimentos sobre técnicas específicas de contagem, e entender por que 
essas técnicas são importantes no estudo de processos discretos. 
Existe um princípio, denominado princípio fundamental da contagem, 
ou também princípio multiplicativo, que estabelece o seguinte: “quando um 
evento é composto por n etapas sucessivas e independentes, de tal modo que 
as possibilidades da primeira etapa é x e as possibilidades da segunda etapa é 
y, resulta no número total de possibilidades de o evento ocorrer, dado pelo 
produto (x) . (y)” (Gouveia, 2019). 
 Podemos então resumir esse princípio como sendo a multiplicação das 
possíveis opções pela quantidade de elementos possíveis. Para auxiliar no 
processo de contagem, podemos lançar mão de arranjos, permutações e 
combinações. 
 
 
19 
5.1 Arranjo 
Os arranjos são subconjuntos nos quais a ordem e a natureza fazem a 
diferença. Considerando um conjunto de n elementos, organizados em 
subconjuntos de p elementos, sendo p ≤ n, utilizamos a seguinte fórmula para o 
arranjo: 
An,p =
𝒏!
(𝒏−𝒑)!
 
Para uma melhor compreensão, considere uma associação de escritores 
com 40 membros, cuja diretoria é composta por quatro deles, que ocupam os 
cargos de presidente, vice-presidente, secretário e vice-secretário. De quantas 
formas é possível organizar a composição dessa diretoria? Para responder, 
vejamos: 
n = 40, p = 4  A40,4 =
40!
(40−4)!
 = 
40.39.38.37.36!
36!
 = 40x39x38x37 = 2.193.360 
Portanto, podemos ter 2.193.360 diferentes composições de diretoria 
nessa associação. É importante ressaltar que a ordem faz diferença, pois um 
membro poderá ocupar qualquer um dos cargos, tomando parte em diferentes 
composições com os mesmos escritores! 
5.2 Permutação 
A permutação nada mais é do que um caso específico de arranjo, no qual 
o número de elementos do conjunto (n) é igual ao número total de elementos. 
Isso resulta em que o denominador, na fórmula do arranjo, seja igual a uma 
unidade (1). A consequência é que a permutação é representada pela seguinte 
fórmula: 
Pn=n! 
Como exemplo de permutação, imagine um veículo que comporta seis 
passageiros, no qual viajarão seis pessoas. Nesse caso, as pessoas irão ocupar 
os lugares em determinada ordem, e o número de pessoas é igual ao número de 
assentos. Então usamos a permutação para calcular de quantas formas os 
passageiros poderão se acomodar no veículo: 
P6 = 6! = 6.5.4.3.2.1 = 720 
 
 
20 
Então existem 720 diferentes formas de acomodar esses passageiros no 
veículo. 
5.3 Combinação 
Diferentemente dos arranjos, as combinações são subconjuntos para os 
quais a ordem dos elementos não importa, porém, a sua natureza, sim. Deste 
modo, para obtermos uma combinação simples de n elementos combinados p a 
p, sendo (p≤ n), recorremos à seguinte fórmula: 
Cn,p =
𝒏!
𝒑!(𝒏−𝒑)!
 
Usando o exemplo do arranjo, consideremos que na mesma associação 
de escritores há um conselho composto de três membros, todos com a mesma 
função. Nesse caso, a ordem não importa, e por isso usaremos a combinação 
para calcular quantas formações desse conselho são possíveis: 
n = 40, p = 3  C40,3 =
40!
3!(40−3)!
 = 
40.39.38..37!
3!37!
 = 
40.39.38
3.2.1
 = 9.880 
Assim concluímos, que há 9.880 formações possíveis. 
FINALIZANDO 
O conhecimento e o uso dos elementos e métodos matemáticos aqui 
apresentados é de fundamental importância para a computação. 
Recomendamos que você pesquise e faça os exercícios desta aula, que constam 
do Caderno de Exercício e nas atividades práticas da disciplina. 
 
 
 
21 
REFERÊNCIAS 
GOUVEIA, R. Análise combinatória. Toda Matéria, 14 maio 2019. Disponível 
em: <https://www.todamateria.com.br/analise-combinatoria/>. Acesso em: 13 
jun. 2019. 
LEITE, A. E., CASTANHEIRA, N. P. Teoria dos números e teoria dos 
conjuntos. Curitiba: InterSaberes, 2014. 
MACEDO, L. R. D., CASTANHEIRA, N. P., ROCHA, A. Tópicos de matemática 
aplicada. Curitiba: InterSaberes, 2013. 
SPERANDIO, D. et al. Cálculo numérico. São Paulo: Pearson Education do 
Brasil, 2014. 
STALLINGS, W. Arquitetura e organização de computadores. 10. ed. São 
Paulo: Pearson Education do Brasil, 2017. 
TANEMBAUM, A. S. Organização estruturada de computadores. São Paulo: 
Pearson Prentice Hal, 2014.