Capítulo 6 — Estruturas discretas

Mapa da aula

Aula 06 publicada. Mapa, exemplo, EX012.

flowchart TD
  N0["6.1 Conjuntos e relações"]
  N1["6.2 Lógica"]
  N2["6.3 Grafos"]
  N3["6.5 Atividade prática"]
  N4["Síntese do capítulo"]
  N0 --> N1 --> N2 --> N3 --> N4
  N4 --> EX["Exemplo resolvido"]
  EX --> Q["Exercício EX012"]

Desenho lógico

flowchart LR
  N0["6.1 Conjuntos e relações"]
  N1["6.2 Lógica"]
  N2["6.3 Grafos"]
  N3["6.5 Atividade prática"]
  N4["Síntese do capítulo"]
  N0 --> N1 --> N2 --> N3 --> N4 --> Q["EX012"]

[6.1 Conjuntos e relações]
    |
    v
[6.2 Lógica]
    |
    v
[6.3 Grafos]
    |
    v
[6.5 Atividade prática]
    |
    v
[Síntese do capítulo]
    |
    v
[Exemplo resolvido] --> [Exercício EX012]

Objetivos de aprendizagem e conexão

Depois deste capítulo, você consegue (1) usar conjuntos e operações de conjuntos para raciocinar sobre inventários e permissões; (2) escrever condições lógicas e conferi-las com tabelas-verdade; (3) modelar as dependências entre serviços como um grafo dirigido e calcular o que é afetado quando um nó falha; e (4) reconhecer quando uma verificação exaustiva é viável e quando o número de estados a torna impossível. O capítulo se apoia na programação do Capítulo 3 e prepara o Capítulo 13 (acesso), o Capítulo 22 (dependências) e o Capítulo 28 (análise de falhas).

6.1 Conjuntos e relações

Um conjunto é uma coleção de itens distintos. Os dispositivos da rede clínica formam um conjunto $C$; os dispositivos depois do fim do suporte formam um conjunto $U$; a sua interseção $C \cap U$ é o conjunto a isolar primeiro. A união $A \cup B$ reúne os itens de qualquer um dos dois; a diferença $A \setminus B$ mantém os itens de $A$ que não estão em $B$. O controle de acesso é raciocínio sobre conjuntos: as permissões efetivas de um usuário são a união das permissões dos seus papéis, e uma regra de segregação de funções diz que certos pares nunca podem estar ambos nessa união (Capítulo 13). Uma relação liga itens de dois conjuntos — "o usuário u tem o papel r", "o serviço s depende do serviço t". Muitas perguntas de segurança são perguntas sobre relações: quem alcança o quê, o que depende do quê.

6.2 Lógica

Uma proposição é verdadeira ou falsa. Combine proposições com e ($\wedge$), ou ($\vee$) e não ($\neg$). Uma regra como "um pagamento acima de £10.000 só é liberado se for criado por uma pessoa e aprovado por outra pessoa, ou se for uma transferência de emergência aprovada por dois diretores" é uma expressão lógica; escrevê-la formalmente expõe lacunas ("e se quem criou também for diretor?"). Uma tabela-verdade lista todas as combinações de entradas; com $n$ entradas, ela tem $2^n$ linhas. Para 4 entradas, são 16 linhas — fácil. Para 40 entradas, são cerca de $10^{12}$ linhas — impossível de conferir à mão, e é por isso que sistemas complexos precisam de estrutura, testes e argumentação, em vez de enumeração exaustiva. As leis de De Morgan — $\neg(A \wedge B) \equiv \neg A \vee \neg B$ — permitem reescrever condições de "não permitido" como condições de "permitido" e conferir que as duas dizem a mesma coisa.

6.3 Grafos

Um grafo é um conjunto de nós e arestas. Num grafo dirigido, as arestas têm direção; escrevemos $u \to v$ para dizer "$v$ depende de $u$". A partir de um nó que falhou, uma busca em largura visita todos os nós alcançáveis ao longo das arestas: esse conjunto é tudo o que pode ser afetado. O número de nós alcançáveis a partir de um nó é o seu alcance; nós com alcance alto são candidatos a proteção extra ou a redundância. Os grafos também expõem pontos únicos de falha: um nó cuja remoção desliga os serviços daquilo de que eles precisam. O artigo clássico de Rinaldi, Peerenboom e Kelly descreve as infraestruturas como interdependentes exatamente nesse sentido — física, cibernética, geográfica e logicamente (Rinaldi et al., 2001).

6.4 Exemplo resolvido e Laboratório 3: dependências do Calder County (sintético)

Este caso é sintético. A CRP desenhou um primeiro mapa de dependências: a subestação de energia alimenta as bombas de água, a alimentação da rede elétrica do hospital, a central de telecomunicações e a sinalização ferroviária; a central de telecomunicações transporta o despacho, os pagamentos com cartão, a telemetria da água e o arquivo de imagens em nuvem do hospital.

# Lab 3 - cross-sector dependency closure on a directed graph (synthetic Calder County, offline)
from collections import deque
# edge u -> v means "v depends on u"
DEPENDS = {
    "grid-substation-N": ["water-pumps", "hospital-main", "telecom-exchange", "rail-signalling"],
    "telecom-exchange": ["dispatch-cad", "card-payments", "water-telemetry", "hospital-pacs-cloud"],
    "water-pumps": ["hospital-water"],
    "water-telemetry": ["water-pumps"],
    "dispatch-cad": ["ambulance-dispatch"],
    "hospital-main": [],
    "card-payments": ["fuel-retail"],
    "rail-signalling": [], "hospital-water": [], "hospital-pacs-cloud": [],
    "ambulance-dispatch": [], "fuel-retail": [],
}
def affected(start):
    seen, q = {start}, deque([start])
    while q:
        for v in DEPENDS.get(q.popleft(), []):
            if v not in seen:
                seen.add(v); q.append(v)
    return sorted(seen - {start})
for node in ("grid-substation-N", "telecom-exchange", "water-telemetry"):
    a = affected(node)
    print(f"{node}: {len(a)} affected -> {', '.join(a)}")
fan = sorted(((len(affected(n)), n) for n in DEPENDS), reverse=True)[:3]
print("highest reach:", fan)

Saída esperada:

grid-substation-N: 11 affected -> ambulance-dispatch, card-payments, dispatch-cad, fuel-retail, hospital-main, hospital-pacs-cloud, hospital-water, rail-signalling, telecom-exchange, water-pumps, water-telemetry
telecom-exchange: 8 affected -> ambulance-dispatch, card-payments, dispatch-cad, fuel-retail, hospital-pacs-cloud, hospital-water, water-pumps, water-telemetry
water-telemetry: 2 affected -> hospital-water, water-pumps
highest reach: [(11, 'grid-substation-N'), (8, 'telecom-exchange'), (2, 'water-telemetry')]

Leia o resultado com cuidado. O grafo diz pode ser afetado, e não vai falhar: ele ignora energia de reserva, armazenamento e operação manual. Isso é deliberado — o primeiro mapa encontra onde olhar; o Capítulo 22 acrescenta o tempo e a autonomia da reserva. Ele também revela uma escolha de modelagem: aqui, as bombas de água dependem da telemetria só se não puderem funcionar localmente. Cada aresta é uma afirmação que alguém deveria conseguir justificar.

6.5 Atividade prática

Acrescente uma aresta que você acha que falta (por exemplo, a água do hospital depende da estação de tratamento, que depende da subestação) e um caminho alternativo (uma segunda central de telecomunicações). Recalcule o alcance. Escreva três frases sobre o que a mudança mostra e o que não mostra.

Acrescentar "estação de tratamento → água do hospital" e "subestação → estação de tratamento" eleva ainda mais o alcance da subestação, enquanto uma segunda central não retira nada da simples contagem de alcançabilidade: a busca continua marcando todo nó que um caminho consegue alcançar. Essa é a limitação que o EX012 pede que você explique, e é o motivo para escrever as dependências do tipo E e do tipo OU de formas diferentes.

6.6 Erros comuns e limites

• Confundir a direção das arestas ("depende de" versus "fornece"); escreva a convenção no topo de todo diagrama.
• Tratar a alcançabilidade como certeza de falha.
• Construir um grafo a partir da visão de uma única organização: outros operadores conhecem dependências que você não conhece.
• Tentar enumerar espaços de estados exponencialmente grandes.

No Laboratório 3, a linha de convenção edge u -> v means "v depends on u" é o que torna legível o alcance de 11 nós da subestação; invertida, a mesma lista afirmaria que a subestação depende da venda de combustível. Alcance de 11 significa exposição, e não falha, já que o hospital tem 72 horas de autonomia de gerador. O mapa é a primeira visão da CRP e não tem o que os engenheiros da CW e da CPN sabem. E o argumento da tabela-verdade escala no sentido contrário: 40 entradas binárias dão cerca de um trilhão de linhas.

Exercícios — capítulo 6

EX011 — Conjuntos para triagem. Objetivo: usar operações de conjuntos. Entradas: C = {INF-01, INF-02, IMG-01, IMG-02, ADM-02}; U = {INF-02, IMG-01, IMG-02, LAB-01, ADM-02}; K (dispositivos com uma falha sabidamente explorada) = {IMG-01, ADM-02}. Etapas: calcule $C \cap U$, $(C \cap U) \cap K$ e $U \setminus C$; diga sobre qual conjunto você agiria primeiro e por quê. Evidência esperada: três conjuntos e um motivo. Rubrica: 3 = tudo correto e prioridade para $(C \cap U) \cap K$ = {IMG-01, ADM-02}; 2 = um erro; 1 = dois erros; 0 = nada.

EX012 — Um caminho alternativo. Objetivo: ver como a redundância muda o alcance. Entradas: Laboratório 3. Etapas: modele que o dispatch-cad também pode usar um enlace por satélite independente da central, de modo que perder só a central já não para o despacho. Explique por que uma busca simples de alcançabilidade não consegue expressar isso e proponha uma mudança de modelagem. Evidência esperada: explicação e proposta. Rubrica: 3 = reconhece a dependência OU (precisa de qualquer um de vários fornecedores) versus a dependência E, propõe nós que exigem todas/qualquer das entradas; 2 = só reconhece o problema; 1 = edita as arestas de forma incorreta; 0 = nada.

Síntese do capítulo

Os conjuntos descrevem inventários e permissões; a lógica torna as regras exatas e verificáveis; os grafos tornam as dependências visíveis e calculáveis. Cada modelo responde a uma pergunta mais estreita do que parece: a alcançabilidade mostra exposição, e não falha, e a verificação exaustiva só funciona enquanto o espaço de estados é pequeno.