Fundamentos de Matemática Discreta com Python¶
Matemática Discreta¶
A matemática é uma ciência fundamental para qualquer formação ligada à computação, à informática e, em nosso caso, à ciência e análise de dados. Porém, a característica distintiva da matemática realizada pelas máquinas é a finitude. Isto é, enquanto a matemática tradicional que aprendemos é capaz de lidar com quantidades infinitas e incontáveis, as máquinas possuem limitações em suas capacidades, seja em armazenamento, seja em memória. Embora tais capacidades sejam expansíveis de alguma forma, devemos compreender que os recursos computacionais são finitos.
Chamamos de Matemática Discreta (ou Álgebra Abstrata) a área da Matemática que lida com objetos discretos, a saber, conjuntos, sequencias, listas, coleções ou quaisquer entidades contáveis. Por exemplo, diz-se que o conjunto dos números reais é incontável, ou não enumerável, pelo fato de não conseguirmos obter um paralelo entre seus elementos e o conjunto dos números naturais. Em outras palavras, não podemos determinar o número de elementos do conjunto R. Por outro lado, isto não acontece com uma variedade de outros conjuntos que podemos encontrar na vida real. Observemos os exemplos:
O conjunto das vogais da língua portuguesa;
O conjunto dos times de futebol brasileiros da série A em 2020;
O conjunto de nomes das estações do ano;
O conjunto das personagens que formam o quarteto principal do filme Os Pinguins de Madagascar e;
O conjunto dos números pares positivos menores ou iguais a dez.
Cada conjunto desses possui um número finito de elementos. Isto quer dizer que são contáveis, ou enumeráveis. Podemos defini-los, em linguagem matemática, por meio da extensão, quando listamos seus elementos, ou por meio da compreensão, quando usamos uma propriedade que distingue seus elementos. Ao longo do ensino básico, você já deparou com isto. Vamos apenas relembrar.
Reescritos por extensão, esses conjuntos, em ordem, são lidos como:
{a,e,i,o,u}
{Atlético-PR,…,Bahia,Botafogo,…,Coritiba,…,Fortaleza,…,Internacional,…,São Paulo,Sport,Vasco}
{Primavera,Verão,Outono,Inverno}
{Capitão,Kowalski,Recruta,Rico}
{2,4,6,8,10}
Já por compreensão, poderiam ser lidos como:
{c∈A;c é vogal}
{t∈T;t é da Série A}
{x;x é uma estação do ano}
{p;p é personagem do quarteto principal do filme Os Pinguins de Madagascar}
{e;e é estação do ano}
{n∈Z|n=2k∧2≤n≤10∧k∈Z}
Por livre conveniência, chamamos de A o conjunto de todas as letras de nosso alfabeto e de T o conjunto de todos os times de futebol do Brasil. Adicionalmente, vale ressaltar que poderíamos usar diferentes formas de denotá-los por compreensão além dessas. Tal liberdade de escolha, desde que coerente, transmite exatamente o caráter abstrato que a Matemática Discreta possui.
Estruturas de dados em Python para lidar com objetos discretos¶
A linguagem oferece diversos objetos para operarmos com quantidades discretas em formas de sequencias, listas ou coleções. De forma genérica, você pode interpretá-las como “conjuntos” que contém zero ou mais elementos. Um conjunto com zero elementos é chamado de vazio. Em Python, também temos meios para representar o “vazio” também, como veremos adiante.
As principais estruturas que aprenderemos serão:
list
: estrutura cujo conteúdo é modificável e o tamanho variável. Listas são caracterizadas por mutabilidade e variabilidade. Objetoslist
são definidos por um par de colchetes e vírgulas que separam seus elementos:[., ., ... ,.]
.tuple
: estrutura cujo conteúdo não é modificável e o tamanho fixado. Tuplas são caracterizadas por imutabilidade e invariabilidade. Objetostuple
são definidos por um par de colchetes e vírgulas que separam seus elementos:(., ., ... ,.)
.dict
: estruturas contendo uma coleção de pares do tipo chave-valor. Dicionários são caracterizados por arrays associativos (tabelas hash). Objetosdict
são definidos por um par de chaves e agrupamentos do tipo'chave':valor
(key:value), separados por vírgula:{'chave1':valor1, 'chave2':valor2, ... ,'chaven':valorn}
. As chaves (keys) são do tipostr
, ao passo que os valores podem ser de tipos arbitrários.set
: estruturas similares adict
, porém não possuem chaves e contêm objetos únicos. Conjuntos são caracterizadas por unicidade de elementos. Objetosset
são definidos por um par de chaves e vírgulas que separam seus elementos:{., ., ... ,.}
.
Listas¶
Estruturas list
formam uma coleção de objetos arbitrários e podem ser criadas de modo sequenciado com operadores de pertencimento ou por expressões geradoras, visto que são estruturas iteráveis.
Listas por geração¶
Exemplo: crie uma lista dos primeiros 100 inteiros não-negativos.
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]
Exemplo: crie o conjunto {x∈Z;−20≤x<10}
Exemplo: crie o conjunto {x∈Z;−20≤x≤10}
Adicionando e removendo elementos¶
Há vários métodos aplicáveis para adicionar e remover elementos em listas.
Adição por apensamento¶
Adiciona elementos por concatenação no final da lista.
Adição por extensão¶
Para incluir elementos através de um objeto iterável, sequenciável, usamos extend
.
Iteração e indexação¶
A iteração sobre uma lista é o processo de “passear” por seus elementos de modo sequenciado. Ao fornecermos o índice (posição) de seus elementos, podemos indexá-los.
Em Python, a indexação de listas começa a partir de 0
e termina em n - 1
, onde n
é o tamanho da lista.
Por exemplo, analise a seguinte correspondência:
posição:{p=0,p=1,…,p=n−1}
elementos na lista:[x1,x2,…,xn]
Quer dizer, o primeiro elemento, x1 está na posição 0, p=0, ao passo que o último elemento, xn, está na posição n−1, p=n−1. Logo, se escolhermos uma variável chamada p que assume o valor 0, 1, …, n−1, mediante a posição (ordenada) do elemento na lista, diremos que p é um iterador, os inteiros de 0 a n−1 são os índices e n é o tamanho da lista.
Esta mesma idéia é aplicável a qualquer coleção, sequencia ou objeto iterável.
Remoção por índice¶
Suponha que tivéssemos criado a lista:
Como 5 não é par, não deveria estar na lista. Para excluírmos um elemento em uma posição específica, usamos pop
passando o índice onde o elemento está.
Adição por índice¶
Nesta lista, podemos pensar em incluir 4 entre 2 e 6. Para isto, usamos insert(posicao,valor)
, para valor
na posicao
desejada.
Apagar conteúdo da lista¶
Podemos apagar o conteúdo inteiro da lista com clear
.
Podemos contar o número de elementos da lista com len
.
Outros métodos de lista¶
Conte repetições de elementos na lista com count
.
Localize a posição de um elemento com index
.
Remova a primeira aparição do elemento com remove
.
Faça uma reflexão (“flip”) in-place (sem criar nova lista) da lista com reverse
.
Ordene a lista de maneira in-place (sem criar nova lista) com sort
.
Concatenação de listas¶
Listas são concatenadas (“somadas”) com +
. Caso já possua listas definidas, use extend
.
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-23-3b000c9317b9> in <module>
----> 1 ['Flamengo', 'Botafogo'] + 'Fluminense' # erro: 'Fluminense' não é list
TypeError: can only concatenate list (not "str") to list
Fatiamento de listas¶
O fatiamento (“slicing”) permite que selecionemos partes da lista através do modelo start:stop
, em que start
é um índice incluído na iteração, e stop
não.
Omissão de start
e stop
¶
Modo reverso¶
Elementos alternados com step
¶
Podemos usar um dois pontos duplo (::
) para dar um “passo” de alternância.
Mutabilidade de listas¶
Podemos alterar o conteúdo de elementos diretamente por indexação.
O teste de identidade é False
, mas o teste de igualdade é True
.
Exemplo: Escreva uma função que calcule a área, perímetro, comprimento da diagonal, raio, perímetro e área do círculo inscrito, e armazene os resultados em uma lista.
# usaremos matemática simbólica
from sympy import symbols
from math import pi
# símbolos
B, H = symbols('B H',positive=True)
def propriedades_retangulo(B,H):
'''
A função assume que a base B
é maior do que a altura H. Senão,
as propriedades do círculo inscrito
não serão determinadas.
'''
d = (B**2 + H**2)**(1/2) # comprimento da diagonal
r = d/2 # raio do círculo inscrito
return [B*H, 2*(B+H), d, d/2, 2*pi*r, pi*(r)**2]
# lista de objetos símbolos
propriedades_retangulo(B,H)
Formatação de strings¶
Os valores na lista acima poderiam ser impressos de uma maneira mais legível. Até o momento, estivemos habituados em imprimir valores passando-s à função print
. Entretanto, a Python nos oferece uma ampla gama de recursos para formatar strings. Veremos mais detalhes sobre templating e formatação de strings mais à frente no curso. Por enquanto, vamos ver como podemos imprimir melhor os float
anteriores.
O template a seguir usa a função format
para substituição de valores indexados.
Nota: Para ajuda plena sobre formatação, consultar:
# considere R: retângulo; C: círculo inscrito
res = propriedades_retangulo(B,H) # resultado
props = ['Área de R',
'Perímetro de R',
'Diagonal de R',
'Raio de C',
'Perímetro de C',
'Área de C'
] # propriedades
# template
templ = '{0:s} = {1:.2f}\n\
{2:s} = {3:.3f}\n\
{4:s} = {5:.4f}\n\
{6:s} = {7:.5f}\n\
{8:s} = {9:.6f}\n\
{10:s} = {11:.7f}'.format(props[0],res[0],\
props[1],res[1],\
props[2],res[2],\
props[3],res[3],\
props[4],res[4],\
props[5],res[5])
# impressão formatada
print(templ)
Como interpretar o que fizemos?¶
{0:s}
formata o primeiro argumento deformat
, o qual éprops[0]
, comostr
(s
).{1:.2f}
formata o segundo argumento deformat
, o qual éres[0]
, comofloat
(f
) com duas casas decimais (.2
).{3:.3f}
formata o quarto argumento deformat
, o qual éres[1]
, comofloat
(f
) com três casas decimais (.3
).
A partir daí, percebe-se que um template {X:.Yf}
diz para formatar o argumento X
como float
com Y
casas decimais, ao passo que o template {X:s}
diz para formatar o argumento X
como str
.
Além disso, temos:
\n
, que significa “newline”, isto é, uma quebra da linha.\
, que é um caracter de escape para continuidade da instrução na linha seguinte. No exemplo em tela, o template criado é do tipo multi-line.
Nota: a contrabarra em \n
também é um caracter de escape e não um caracter literal. Isto é, para imprimir uma contrabarra literalmente, é necessário fazer \\
. Vejamos exemplos de literais a seguir.
Exemplos de impressão de caracteres literais¶
f-strings¶
Temos uma maneira bastante interessante de criar templates usando f-strings, que foi introduzida a partir da versão Python 3.6. Com f-strings a substituição é imediata.
Estilos de formatação¶
Veja um comparativo de estilos:
Exemplo: Considere o conjunto: V = {c∈A;c é vogal}. Crie a concatenação de todos os elementos com f-string.
Veremos à frente meios mais elegantes de fazer coisas similares.
Controle de fluxo: laço for
¶
Em Python, podemos realizar iterar por uma coleção ou iterador usando laços. Introduziremos aqui o laço for
. Em Python, o bloco padrão para este laço é dado por:
Acima, valor
é um iterador.
Compreensão de lista¶
Usando for
, a criação de listas torna-se bastante facilitada.
Exemplo: crie a lista dos primeiros 10 quadrados perfeitos.
A operação acima equivale a:
Exemplo: crie a PA: an=3+6(n−1),1≤n≤10
Exemplo: se X={1,2,3} e Y={4,5,6}, cria a “soma” X+Y elemento a elemento.
Exemplo: se X={1,2,3} e Y={4,5,6}, cria o “produto” X∗Y elemento a elemento.
Tuplas¶
Tuplas são são sequencias imutáveis de tamanho fixo. Em Matemática, uma tupla é uma sequência ordenada de elementos. Em geral, o termo n−upla (“ênupla”) é usado para se referir a uma tupla com n elementos.
Por exemplo, tuplas de um único elemento são chamadas de “singleton” ou “mônada”. Tuplas de dois elementos são os conhecidos “pares ordenados”. Com três elementos, chamamos de “trio” ou “tripleta”, e assim por diante.
Em Python, tuplas são criadas naturalmente sequenciando elementos.
Tuplas são acessíveis por indexação.
Se na tupla houver uma lista, a lista é modificável.
Tuplas também são concatenáveis com +
.
Desempacotamento de tuplas¶
enumerate
¶
Podemos controlar índice e valor ao iterar em uma sequencia.
Exemplo: Construa o produto cartesiano
Dicionários¶
Dicionários, ou especificamente, objetos dict
, possuem extrema versatilidade e são muito poderosos. Criamos um dict
por diversas formas. A mais simples é usar chaves e pares explícitos.
Os pares chave-valor incorporam quaisquer tipos de dados.
Acesso a conteúdo¶
Para acessar o conteúdo de uma chave, indexamos pelo seu nome.
Exemplo: construindo soma e multiplicação especial.
Inserção de conteúdo¶
Alteração de conteúdo¶
Deleção de conteúdo com del
e pop
¶
Combinando dicionários¶
Usamos update
para combinar dicionários. Este método possui um resultado similar a extend
, usado em listas.
Dicionários a partir de sequencias¶
Podemos criar dicionários a partir de sequencias existentes usando zip
.
Visto que um dict
é composto de várias tuplas de 2, podemos criar um de maneira ainda mais simples.
Controle de fluxo: condicionais if
, elif
e else
¶
Em Python, como na maioria das linguagens, o operador if
(“se”) serve para tratar situações quando um bloco de instruções de código precisa ser executado apenas se uma dada condição estabelecida for avaliada como verdadeira. Um bloco condicional é escrito da seguinte forma:
Este bloco diz basicamente o seguinte: “faça algo se a condição for verdadeira”. Vejamos alguns exemplos.
A condição pode ser formada de diversas formas desde que possa ser avaliada como True
ou False
.
A estrutura condicional pode ser ampliada com um ou mais elif
(“ou se”) e com else
(senão). Cada elif
, uma redução de else if, irá testar uma condição adicional se a condição relativa a if
for False
. Se alguma delas for testada como True
, o bloco de código correspondende será executado. Caso contrário, a decisão do interpretador será executar o bloco que acompanhará else
.
Exemplo: teste da tricotomia. Verificar se um número é >, < ou =0.
Exemplo: Considere o conjunto de classificações sanguíneas ABO (+/-)
Se em um experimento aleatório, n pessoas (n≥500) diferentes entrassem por um hospital em um único dia, qual seria a probabilidade de p entre as n pessoas serem classificadas como um(a) doador(a) universal (sangue O-) naquele dia? Em seguida, estime a probabilidade das demais.
# 'randint' gera inteiros aleatoriamente
from random import randint
# número de pessoas
n = 500
# associa inteiros 0-7 ao tipo sanguíneo
tipos = [i for i in range(0,8)]
sangue = dict(zip(tipos,['A+','A-','B+','B-','AB+','AB-','O+','O-']))
# primeira pessoa
i = randint(0,8)
# grupo sanguíneo
s = []
# repete n vezes
for _ in range(0,n):
if i == 0:
s.append(0)
elif i == 1:
s.append(1)
elif i == 2:
s.append(2)
elif i == 3:
s.append(3)
elif i == 4:
s.append(4)
elif i == 5:
s.append(5)
elif i == 6:
s.append(6)
else:
s.append(7)
i = randint(0,7) # nova pessoa
# calcula a probabilidade do tipo p em %.
# Seria necessário definir uma lambda?
prob = lambda p: p/n*100
# armazena probabilidades no dict P
P = {}
for tipo in tipos:
P[tipo] = prob(s.count(tipo))
if sangue[tipo] == 'O-':
print('A probabilidade de ser doador universal é de {0:.2f}%.'.format(P[tipo]))
else:
print('A probabilidade de ser {0:s} é de {1:.2f}%.'.format(sangue[tipo],P[tipo]))
A probabilidade de ser A+ é de 10.80%.
A probabilidade de ser A- é de 14.00%.
A probabilidade de ser B+ é de 15.00%.
A probabilidade de ser B- é de 12.80%.
A probabilidade de ser AB+ é de 12.80%.
A probabilidade de ser AB- é de 13.60%.
A probabilidade de ser O+ é de 11.00%.
A probabilidade de ser doador universal é de 10.00%.
Conjuntos¶
As estruturas set
(conjunto) são úteis para realizar operações com conjuntos.
União de conjuntos¶
Considere os seguintes conjuntos.
Atualização de conjuntos (união)¶
A união in-place de dois conjuntos pode ser feita com update
.
A atualização da união possui a seguinte forma alternativa com |=
.
Interseção de conjuntos¶
Atualização de conjuntos (interseção)¶
A interseção in-place de dois conjuntos pode ser feita com intersection_update
.
A atualização da interseção possui a seguinte forma alternativa com &=
.
Diferença entre conjuntos¶
Atualização de conjuntos (diferença)¶
A interseção in-place de dois conjuntos pode ser feita com difference_update
.
A atualização da diferença possui a seguinte forma alternativa com -=
.
Adição ou remoção de elementos¶
Reinicialização de um conjunto (vazio)¶
Podemos remover todos os elementos de um conjunto com clear
, deixando-o em um estado vazio.
Diferença simétrica¶
A diferença simétrica entre dois conjuntos A e B é dada pela união dos complementares relativos:
Logo, em A△B estarão todos os elementos que pertencem a A ou a B mas não aqueles que são comuns a ambos.
Nota: os complementares relativos A∖B e B∖A aqui podem ser interpretados como A−B e B−A. Os símbolos ∖ e − em conjuntos podem ter sentidos diferentes em alguns contextos.
Atualização de conjuntos (diferença simétrica)¶
A diferença simétrica in-place de dois conjuntos pode ser feita com symmetric_difference_update
.
Continência¶
Podemos verificar se um conjunto A é subconjunto de (está contido em) outro conjunto B (A⊆B) ou se B é um superconjunto para (contém) A (B⊇A) com issubset
e issuperset
.
Subconjuntos e subconjuntos próprios¶
Podemos usar operadores de comparação entre conjuntos para verificar continência.
A⊆B: A é subconjunto de B
A⊂B: A é subconjunto próprio de B (A possui elementos que não estão em B)
Disjunção¶
Dois conjuntos são disjuntos se sua interseção é vazia. Podemos verificar a disjunção com isdisjoint
Igualdade entre conjuntos¶
Dois conjuntos são iguais se contém os mesmos elementos.
Compreensão de conjunto¶
Podemos usar for
para criar conjuntos de maneira esperta do mesmo modo que as compreensões de lista e de dicionários. Neste caso, o funcionamento é como list
, porém, em vez de colchetes, usamos chaves.
Sobrecarga de operadores¶
Em Python, podemos realizar alguns procedimentos úteis para laços de repetição.
Exemplo: verifique se a soma das probabilidades no dict
P
do experimento aleatório é realmente 100%.
De modo mais Pythônico:
Ou ainda:
Controle de fluxo: laço while
¶
O condicional while
permite que um bloco de código seja repetidamente executado até que uma dada condição seja avaliada como False
, ou o laço seja explicitamente terminado com a keyword break
.
Em laços while
, é muito comum usar uma linha de atualização da condição usando sobrecarga de operadores.
A instrução é como segue:
Repeti 100 vezes e x = 0.7314327009999998. Contando...
Repeti 200 vezes e x = 0.5139224009999996. Contando...
Repeti 300 vezes e x = 0.3444721009999996. Contando...
Repeti 400 vezes e x = 0.2170818009999996. Contando...
Repeti 500 vezes e x = 0.12575150099999965. Contando...
Repeti 600 vezes e x = 0.06448120099999974. Contando...
Repeti 700 vezes e x = 0.02727090099999983. Contando...
Repeti 800 vezes e x = 0.008120600999999913. Contando...
Repeti 900 vezes e x = 0.0010303009999999755. Contando...
Repeti 1000 vezes e x = 9.999999999973564e-10. Contando...
x = -6.8435572439409775e-46
from math import sin,pi
x = 1.0
i = 1
while x**3 > 0:
if i % 100 == 0: # imprime apenas a cada 1000 repetições
print(f'Repeti {i} vezes e x = {x**3}. Contando...')
if i == 500:
print(f'Repeti demais. Vou parar.')
break # execução interrompida aqui
x -= 1e-3 # atualiza o decremento
i += 1 # contagem de repetição
print(f'x = {x**3}')
Repeti 100 vezes e x = 0.7314327009999998. Contando...
Repeti 200 vezes e x = 0.5139224009999996. Contando...
Repeti 300 vezes e x = 0.3444721009999996. Contando...
Repeti 400 vezes e x = 0.2170818009999996. Contando...
Repeti 500 vezes e x = 0.12575150099999965. Contando...
Repeti demais. Vou parar.
x = 0.12575150099999965
Exemplo: construa seu próprio gerador de números aleatórios para o problema da entrada de pessoas no hospital.
Exemplo: verifique se a soma das probabilidades no dict
P
do experimento aleatório é realmente 100%.
map
¶
A função map
serve para construir uma função que será aplicada a todos os elementos de uma sequencia. Seu uso é da seguinte forma:
No exemplo anterior, as entradas do usuário são armazenadas como str
, isto é, ‘2’, ‘3’ e ‘4’. Para que elas sejam convertidas para int
, nós executamos um casting em todos os elementos da sequencia usando map
.
A interpretação é a seguinte: para todo x
pertencente a sequencia
, aplique funcao(x)
. Porém, para se obter o resultado desejado, devemos ainda aplicar list
sobre o map
.
Observe que a resposta de map
não é human-readable. Para lermos o que queremos, fazemos:
Podemos substituir funcao
por uma função anônima. Assim, suponha que você quisesse enviezar os valores de entrada somando 1 a cada número. Poderíamos fazer isso como:
filter
¶
Podemos aplicar também como uma espécie de “filtro” para valores usando a função filter
. No caso anterior, digamos que valores acima de 7 sejam inseridos erroneamente no gerador de números (lembre-se que no sistema sanguíneo ABO, consideramos um dict
cujo valor das chaves é no máximo 7). Podemos, ainda assim, filtrar a lista para coletar apenas valores menores do que 7. Para tanto, definimos uma função lambda
com este propósito.
Exemplos com maior complexidade¶
Exemplo: Podemos escrever outro gerador de forma mais complexa. Estude este caso (pouco Pythônico).
Exemplo: Associando arbitrariamente o identificador de uma pessoa a um tipo sanguíneo com compreensão de dict
.