Python per i laboratori

I laboratori del corso usano Python e il pacchetto Python-MIP. Del linguaggio serve però poco: saper scrivere un ciclo, costruire una lista o un dizionario con una comprensione, definire una funzione. Tutto ciò che compare nei modelli dei capitoli seguenti si riduce a queste poche costruzioni, e questo capitolo le raccoglie in un unico posto. Chi conosce già Python può saltare direttamente alla sezione sui dizionari, che è la struttura dati su cui si appoggiano quasi tutti i modelli, e al troubleshooting finale.

I blocchi di codice contrassegnati dal pulsante Run si eseguono direttamente nel browser: conviene modificarli e rilanciarli. Il codice che usa Python-MIP non è eseguibile nella pagina (il solver è un programma nativo) e compare come listato da leggere.

1. Notebook e Google Colab#

Un notebook (file .ipynb) è una sequenza di celle. Una cella contiene testo formattato in Markdown (con formule $\LaTeX$ come $\int_{\sqrt 2}^{\pi} x \sin(1/x)\,dx$) oppure codice Python. Una cella di codice si esegue con il pulsante Run o con Shift+Enter; il risultato compare subito sotto e resta lì finché non si rilancia la cella.

Nei laboratori i notebook si aprono su Google Colab: basta un account Google, si carica il file .ipynb e si lavora nel browser senza installare nulla. Ogni notebook dei lab comincia con due celle fisse, l’installazione del pacchetto e la sua importazione:

!pip install mip      # il punto esclamativo esegue un comando di shell dentro Colab
import mip

Il tempo di esecuzione compare a fianco di ogni cella; per le prime celle è zero perché non c’è nulla da calcolare.

2. Primi passi: variabili e stampa#

Una variabile si crea assegnandole un valore con =. Non c’è dichiarazione di tipo e non c’è punto e virgola a fine riga.

p1 = 987654321
p2 = 123456789
print(p1 + p2)
print(f"La somma di {p1} e {p2} è {p1 + p2}")

La seconda print usa una f-string: la f prima delle virgolette abilita la sostituzione delle espressioni fra parentesi graffe. Le f-string compaiono ovunque nei notebook per stampare soluzioni con un formato controllato, per esempio {obj:10.2f} stampa un numero su 10 caratteri con 2 decimali.

Gli operatori aritmetici sono quelli usuali, con tre aggiunte da ricordare: ** è la potenza (3**4 vale 81), // è la divisione intera e % è il resto della divisione (17 % 6 vale 5).

3. Controllo di flusso e funzioni#

L’esempio guida del Lab 0 è un test di primalità: $n$ è primo se nessun intero $k$ fra 2 e $\lfloor\sqrt n\rfloor$ lo divide. Non serve controllare divisori più grandi di $\sqrt n$, perché se $n = k \cdot q$ con $k > \sqrt n$ allora $q < \sqrt n$ è già stato controllato.

Algoritmo PrimeNumber
Input: n        Output: 1 se n è primo, 0 altrimenti
k = 2
finché k <= sqrt(n):
    se n è divisibile per k: restituisci 0
    incrementa k
restituisci 1

La traduzione in Python incapsula l’algoritmo in una funzione, introdotta da def, che restituisce True o False:

import math

def PrimeNumber(n):
    for k in range(2, math.floor(math.sqrt(n)) + 1):
        if n % k == 0:      # k divide n: resto zero
            return False
    return True

x = 42
if PrimeNumber(x):
    print(f"{x} è primo")
else:
    print(f"{x} non è primo")

Tre osservazioni, tutte fonti tipiche di errore.

• range esclude l’estremo destro. range(10) produce i numeri da 0 a 9, range(3, 10) da 3 a 9, range(3, 100, 7) da 3 a 100 a passi di 7. Per arrivare fino a $\lfloor\sqrt n\rfloor$ incluso serve quindi il + 1.

• L’indentazione è la sintassi. Non ci sono parentesi graffe né end: le righe consecutive con lo stesso rientro formano un blocco. I due frammenti seguenti fanno cose diverse: il primo stampa 0 42 1 42 2 42, il secondo 0 1 2 42.

  for i in range(3):
      print(i)
      print(42)
  
  for i in range(3):
      print(i)
  print(42)

• import math serve per le funzioni non elementari (sqrt, floor); le quattro operazioni, //, % e ** sono già nel linguaggio.

La prima versione dello stesso programma, nel notebook introduttivo, non usa il resto ma confronta divisione intera e divisione reale (n // k == n / k) e salva i divisori trovati in una lista, per poi stamparli tutti, compresi quelli maggiori di $\sqrt n$ ottenuti come n // d:

import math

n = 712515131
dividers = []
for k in range(2, 1 + math.floor(math.sqrt(n))):
    if n // k == n / k:
        dividers.append(k)

if dividers == []:
    print('Sì,', n, 'è primo')
else:
    print('No,', n, 'non è primo: è divisibile per',
          dividers + [n // d for d in reversed(dividers)])

import math
def PrimeNumber(n):
    for k in range(2, math.floor(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

primi = [i for i in range(2, 1001) if PrimeNumber(i)]
print(len(primi), "primi; gli ultimi cinque:", primi[-5:])

def fibonacci(quanti):
    fib = [1, 1]
    while len(fib) < quanti:
        fib.append(fib[-1] + fib[-2])
    return fib

print(fibonacci(30))

4. Liste#

Una lista è una sequenza ordinata e modificabile di oggetti, anche di tipo diverso: l = [1, 2, "hey!"]. Le operazioni che ricorrono nei lab:

• l.append(5) aggiunge un elemento in coda; l.extend([3, 4]) concatena un’altra lista; l1 + l2 produce la lista concatenata;
• gli indici partono da zero: l[0] è il primo elemento; gli indici negativi contano dalla fine, l[-1] è l’ultimo;
• len(l) è la lunghezza, max(l) e sum(l) il massimo e la somma;
• x in l vale True se x compare nella lista.

l = []
for i in range(50, 55):
    l.append(i)
print(l, "primo:", l[0], "ultimo:", l[-1])

l1 = ['Paris', 'Toulouse', 'Milano', 'Torino', 'Roma', 'Munich', 'Frankfurt', 'Edinburgh']
l2 = ['Madrid', 'Paris', 'Berlin', 'Roma', 'Bruxelles', 'Bern', 'Wien']
for city1 in l1:
    if city1 in l2:
        print(city1)          # le città presenti in entrambe le liste

5. List comprehension#

In matematica un insieme si definisce spesso per comprensione, per esempio $S = \{4i^3 : i = 3, 4, \ldots, 10\}$. Python permette la stessa scrittura in una riga:

S = [4*i**3 for i in range(3, 11)]
print(S)
print(S[0], S[3], S[7])

Il risultato è la lista [108, 256, 500, 864, 1372, 2048, 2916, 4000]. Attenzione: S è una lista, non un insieme, quindi ogni elemento ha una posizione, e la posizione non ha relazione con il valore di i che l’ha generato (S[3] è 864, prodotto da $i = 6$).

La comprensione accetta anche una condizione: da $S_1 = \{2, \ldots, 100\}$ si estrae l’insieme dei primi con

S1 = range(2, 101)
S2 = [i for i in S1 if PrimeNumber(i)]
print(S2)

(il notebook originale stampa P invece di S2, un refuso: la variabile definita si chiama S2).

Un piccolo esercizio del notebook chiede di calcolare $2^{1000}$: gli interi Python non hanno limite di dimensione, quindi 2**1000 si stampa senza problemi, un numero di 302 cifre.

6. Dizionari e tuple#

6.1 Dizionari#

Un dizionario associa a ogni chiave un valore. È la struttura più usata nei laboratori, perché le variabili e i vincoli di un modello sono indicizzati da insiemi che spesso non sono numeri consecutivi (coppie di nodi, nomi di prodotti).

age = {"John": 23, "Aysha": 15, "Malick": 44}
print(age["John"])

age['Mohit'] = 40      # nuova coppia chiave/valore
age['John'] = 25       # aggiornamento di un valore

print("chiavi:", age.keys())
print("valori:", age.values())
print("coppie:", age.items())
for i in age.keys():
    print(f"{i} ha {age[i]} anni")

Un dizionario vuoto è {}; d.keys(), d.values() e d.items() restituiscono rispettivamente le chiavi, i valori e le coppie, e permettono di iterare su tutto il contenuto. Come le liste, anche i dizionari si costruiscono per comprensione: {i: len(i) for i in names} associa a ogni nome la sua lunghezza.

L’esempio del notebook sulle popolazioni combina comprensione e filtro sulle chiavi:

population = {"Austria": 8901, "Belgium": 11493, "Denmark": 5823, "Finland": 5536,
              "France": 67287, "Germany": 83191, "Italy": 59258,
              "Netherlands": 17425, "Norway": 5368}

n_names = [country for country in population.keys() if 'n' in country]
n_pop = sum(population[country] for country in n_names)
print(f"Paesi con una 'n' nel nome: {n_names}")
print(f"Popolazione totale: {n_pop/1000} milioni")

population = {"Austria": 8901, "Belgium": 11493, "Denmark": 5823, "Finland": 5536,
              "France": 67287, "Germany": 83191, "Italy": 59258,
              "Netherlands": 17425, "Norway": 5368}
y_countries = [c for c in population if c[-1] == 'y']
print(y_countries, "media:", sum(population[c] for c in y_countries) / len(y_countries))
seven = [c for c in population if len(c) == 7]
print(seven, "massimo:", max(population[c] for c in seven))

6.2 Tuple#

Una tupla è una sequenza immutabile: t = (a1, a2, a3). Si accede agli elementi come in una lista (t[0]), ma non si può modificare un elemento dopo la creazione: t[2] = 8 produce un errore, mentre su una lista funziona.

a = [1, 2, 3, 4]
a[2] = 8
print("lista modificata:", a)

t = (1, 2, 3, 4)
try:
    t[2] = 8
except TypeError as e:
    print("tupla:", e)

Il motivo per cui le tuple contano nei lab è che possono fare da chiave di un dizionario, le liste no. Un dizionario come {(1,2): 12, (3,6): 2} associa coppie a numeri: è esattamente la forma delle variabili $x_{ij}$ indicizzate su archi di un grafo nel capitolo 2. L’esempio del notebook costruisce, per coppie $(x, y)$, le coordinate polari $\rho = \sqrt{x^2 + y^2}$ e $\theta = \arctan(y/x)$:

import math

S1 = [i for i in range(1, 10) if i % 3 == 0 or i % 7 == 0]    # divisibili per 3 o per 7
S2 = [i for i in range(1, 50) if i % 11 == 0 or i % 17 == 0]  # divisibili per 11 o per 17

polar = {(i, j): (math.sqrt(i**2 + j**2), math.atan(j/i)) for i in S1 for j in S2}
for k in polar.keys():
    print(f"coordinate polari di {k}: {polar[k]}")

La doppia for dentro la comprensione (for i in S1 for j in S2) enumera tutte le coppie: è il prodotto cartesiano $S_1 \times S_2$, la stessa costruzione con cui si genera l’insieme degli archi di un grafo.

def prime_factors(n):
    factors = []
    decomp = n
    i = 2
    while i <= decomp and i <= n:
        while decomp % i == 0:
            decomp = decomp / i
            if i not in factors:
                # TODO: aggiungere i a factors
        i += 1
    return factors

def prime_factors(n):
    factors = []
    decomp = n
    i = 2
    while i <= decomp and i <= n:
        while decomp % i == 0:
            decomp = decomp / i
            if i not in factors:
                factors.append(i)
        i += 1
    return factors

fattori = {n: prime_factors(n) for n in range(2, 101)}
print("57 ->", fattori[57], "   60 ->", fattori[60])

conteggio = {k: sum(1 for n in fattori if k in fattori[n]) for k in range(2, 51)}
print("7 ->", conteggio[7], "   2 ->", conteggio[2], "   47 ->", conteggio[47])

7. NumPy e Matplotlib#

Due moduli esterni compaiono nei lab sui grafi. NumPy offre i multiarray (vettori, matrici) con operazioni elemento per elemento e prodotto matriciale con @; Matplotlib disegna i grafici. Si importano con un alias per brevità.

import numpy as np

a = np.array([1, 2, 3, 4, 5])
b = np.array([10, 4, 0, 1, 2])
print('a + b =', a + b)
print('a * b =', a * b)              # prodotto elemento per elemento
print('prodotto scalare:', np.dot(a, b))

A = np.array([[2, 5, 3, 4], [5, 6, 8, 7], [1, 2, 8, 10]])   # matrice 3x4
v = np.array([7, 10, 0, 2])
print('A @ v =', A @ v)

Con np.random.random((k, 2)) si generano $k$ coppie di numeri casuali in $[0, 1)$; moltiplicando per 100 si ottengono punti in un quadrato di lato 100, la costruzione con cui il Lab 2 crea le istanze. Un grafico a dispersione dei punti si ottiene con plt.scatter(point[:,0], point[:,1]) seguito da plt.show(), dove point[:,0] seleziona la prima colonna.

8. Errori frequenti e troubleshooting#

La sezione conclusiva del primo notebook del Lab 1 raccoglie le cause più comuni di errore. Vale la pena conoscerle prima di scrivere il primo modello.

Indentazione. In un for, in un if o in una def il corpo deve essere rientrato in modo coerente. Danno errore sia un corpo non rientrato, sia due righe con rientro diverso nello stesso blocco:

for i in [1,2,3]:
print(i)                # errore: manca il rientro

if i==4:
    print('i is 4')
  print('deal with it') # errore: rientro incoerente

Il rientro consigliato è di 4 spazi.

Assegnamento e uguaglianza. = assegna, == confronta. if a = 4 è un errore di sintassi; a == 4 da solo è lecito ma non fa nulla (restituisce True o False). Questo distinguo torna nei vincoli dei modelli: un vincolo di uguaglianza si scrive con ==, mai con =.

Istruzioni su più righe. Una condizione lunga si spezza aggiungendo \ a fine riga, oppure lasciando aperta una parentesi: dentro parentesi non chiuse il ritorno a capo è libero. È il caso più frequente nei modelli, dove m.add_constr(...) occupa spesso due o tre righe.

if (i==3 or i==5 or
    i==7):
    print('i is prime')

Persistenza delle celle. È l’errore più insidioso perché non produce alcun messaggio. Il notebook lo illustra con un modello Python-MIP: si risolve $\max x_1 + x_2$ con il vincolo $2x_1 + x_2 \le 10$ e si ottiene $(0, 10)$. Poi, per «rilassare» il problema, si aggiunge in una nuova cella il vincolo $2x_1 + x_2 \le 20$ e si riottimizza:

m.add_constr(2*x1 + x2 <= 20)
m.optimize()
print('solution:', x1.x, ',', x2.x)      # ancora 0.0 , 10.0

La soluzione non cambia. Il modello ora ha due vincoli, quello vecchio e quello nuovo, e il più restrittivo continua a valere: add_constr aggiunge, non sostituisce. Per modificare un vincolo si torna nella cella che lo definisce, la si modifica e si rilanciano tutte le celle da lì in avanti; nel dubbio si riavvia il kernel e si esegue tutto dall’inizio.

Stile. Chi vuole verificare che il proprio codice segua lo standard può eseguire flake8 myprogram.py, che segnala ogni deviazione (di solito molte).

9. Riepilogo#

Elaborato dai tre notebook introduttivi del Lab 0 e dalla sezione «Miscellanea and troubleshooting» del Lab 1.