Chapter 6 — Discrete structures

Lesson map

Lesson 06 published. Map, example, EX016.

flowchart TD
  N0["Learning outcomes"]
  N1["6.1 Sets and policy"]
  N2["6.2 Graphs of reporting"]
  N3["Lab — Which staff cannot reach IT"]
  N4["6.3 Logic and gaps"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5
  N5 --> EX["Worked example"]
  EX --> Q["Exercise EX016"]

Logical drawing

flowchart LR
  N0["Learning outcomes"]
  N1["6.1 Sets and policy"]
  N2["6.2 Graphs of reporting"]
  N3["Lab — Which staff cannot reach IT"]
  N4["6.3 Logic and gaps"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX016"]

[Learning outcomes]
    |
    v
[6.1 Sets and policy]
    |
    v
[6.2 Graphs of reporting]
    |
    v
[Lab — Which staff cannot reach IT]
    |
    v
[6.3 Logic and gaps]
    |
    v
[Synthesis]
    |
    v
[Worked example] --> [Exercise EX016]

Learning outcomes

You will (1) use sets and logic to describe policy rules; (2) model reporting relationships as graphs; (3) find gaps in rules with simple logic.

6.1 Sets and policy

A set is a collection of distinct items. Nadia describes Ashcombe's staff as sets: counter staff, managers, IT staff and volunteers. A policy rule might say that only managers and IT staff may export member lists. In set terms, permitted exporters are the union of managers and IT staff. She checks the actual access list and finds that two volunteers belong to the set of exporters. Expressing rules as sets makes it easy to compare what the policy intends with what the system actually allows.

6.2 Graphs of reporting

A graph has nodes connected by edges. Nadia draws a graph in which staff are nodes and an edge shows whom each person would tell about a suspicious email. Most counter staff would tell their branch manager, who might or might not tell IT. Some branches have no path to IT at all. The lab finds which nodes cannot reach the IT node. A graph makes visible the routes by which warnings travel, and shows where a single absent manager could block an important report from reaching people able to act.

Lab — Which staff cannot reach IT

# Reporting graph: who can reach IT? (synthetic)
edges = {"IT": [], "Central-mgr": ["IT"], "Riverside-mgr": ["IT"], "Hill-mgr": ["Central-mgr"], "Quay-mgr": [], "Elm-mgr": []}
staff = {"Central": 20, "Riverside": 18, "Hill": 12, "Quay": 5, "Elm": 6}
for b in staff: edges[f"{b}-staff"] = [f"{b}-mgr"]
def reach(n, seen=None):
    seen = seen or set()
    if n == "IT": return True
    seen.add(n)
    return any(reach(m, seen) for m in edges[n] if m not in seen)
blocked = [b for b in staff if not reach(f"{b}-staff")]
print("branches without a route to IT:", blocked, "staff:", sum(staff[b] for b in blocked))

Run with python3 lab_graph.py. Verified output:

branches without a route to IT: ['Quay', 'Elm'] staff: 11

6.3 Logic and gaps

Nadia writes the visitor computer rule in logic: a session must end if the visitor leaves or if thirty minutes pass. She tests cases and finds a gap: if a visitor leaves without logging out and another sits down within thirty minutes, the session continues with the first visitor's email open. She proposes adding a rule that sessions end when the screen is idle for three minutes. Simple logic exposes cases that plain language hides, and testing rules against cases is a habit she will use throughout the course.

Worked example

Nadia uses sets to compare policy with access lists, a graph to find staff with no route to IT and logic to find a gap in visitor sessions.

Synthetic case. The data are synthetic.

Errors and limits

Real reporting routes are informal. Idle timeouts can annoy visitors.

Exercises

• EX016 — Union of sets. Which set union describes permitted exporters?
  Show marking criteria

  Rubric: 3 = managers and IT staff;; 2 = union;; 1 = volunteers;; 0 = none.
• EX017 — Unreachable staff. How many staff could not reach IT in the lab?
  Show marking criteria

  Rubric: 3 = 11, at Quay and Elm;; 2 = 11;; 1 = vague;; 0 = none.
• EX018 — Session gap. What gap did the logic test reveal?
  Show marking criteria

  Rubric: 3 = a new visitor inherits an open session;; 2 = inherit;; 1 = vague;; 0 = none.

Synthesis

Sets, graphs and logic expose differences between intended and actual rules and routes.

Continue studying — chapter 06 of 40

← Chapter 05 (draft) · Course chapter index · Chapter 07 (draft) →