Esercitazione: Algebra lineare con Python

Contents

Esercitazione: Algebra lineare con Python#

Warning

Si ricorda che questa prima esercitazione è solo a scopo didattico. NON è richiesta la consegna di questa esercitazione, nè il suo contenuto sarà richiesto all’esame.

Siccome da qui in avanti lavoreremo costantemente con operazioni del tipo descritto sopra, lo scopo dell’esercitazione è solo quello di farvi prendere dimestichezza con questi metodi. Inoltre, cercare di ottimizzare gli algoritmi per massimizzare l’efficienza in un linguaggio come Python è, oltre che un attività “divertente”, un buon modo di imparare a ragionare che sarà sicuramente utile sia in futuro, che nel resto del corso.

Gli oggetti fondanti dell’algebra lineare sono, come avete visto, matrici e vettori, indicati in seguito con le lettere maiuscole dell’alfabeto latino (\(A\), \(B\), …) e con le lettere minuscole dell’alfabeto latino (\(v\), \(w\), …), rispettivamente.

Dal punto di vista pratico, i vettori non sono altro che array, mentre le matrici possono essere viste come degli array di array, dove ciascun elemento interno rappresenta gli elementi della matrice per righe (o per colonne).

La differenza principale tra i classici array e gli operatori di algebra lineare sono le operazioni tra essi. Ad esempio, la somma di due vettori di lunghezza uguale da come risultato un vettore della stessa lunghezza, con i valori ottenuti sommando elemento per elemento, mentre la somma di due array su Python li concatena, come abbiamo visto.

Similmente, esistono due prodotti possibili tra vettori e tra matrici e vettori: il prodotto “classico”, che corrisponde alla moltiplicazione elemento per elemento, e il prodotto riga-per-colonna. Si ricorda che in formule, questi si esprimono così:

siano \(v = (v_1, \dots, v_n)\), \(w = (w_1, \dots, w_n)\), \(A = (a_{i, j})_{i, j=1, \dots, m, n}\) due vettori ed una matrice. Allora:

\[ (v + w)_i = (v_i + w_i) \quad (v * w)_i = (v_i * w_i) \quad (Av)_i = \sum_{j=1}^n a_{i, j} v_j. \]

In questa esercitazione, si richiede di scrivere un piccolo pacchetto Python che implementa le principali funzioni di algebra lineare, senza utilizzare nessun pacchetto esterno se non le funzioni base di Python (quindi, senza utilizzare numpy).

In particolare, i vettori saranno rappresentati dalle liste, mentre le matrici saranno delle liste di liste, dove ciascuna lista interna rappresenta una riga (o una colonna) della matrice.

Le operazioni da implementare dovranno seguire le consuete regole di operazione tra vettori di algebra lineare, ad esempio una funzione somma(v, w) deve sommare i vettori v e w, elemento per elemento. Stessa cosa per la funzione prodotto_riga_per_colonna(A, v), che deve implementare il classico prodotto riga-per-colonna tra matrice e vettore (o, alternativamente, tra due vettori).

Quali operazioni implementare sono a discrezione dello studente. Si elenca qui sotto una serie di funzioni che possono essere implementate, a titolo di suggerimento:

  • somma(v, w)

  • differenza(v, w)

  • prodotto(v, w)

  • prodotto_riga_per_colonna(A, v)

  • prodotto_scalare(v, w)

  • prodotto_vettore_per_scalare(v, w)

  • potenza_prodotto_riga_per_colonna(A, p)

Oltre che delle funzioni di utilità, come ad esempio:

  • shape(v): che ritorna la shape del vettore/matrice in input

  • ndim(v): che ritorna 1 se v è un vettore, 2 se è una matrice

Testing#

Come abbiamo più volte ricordato, l’aspetto forse più importante quando si lavora con l’algebra lineare computazionale è l’efficienza. Infatti, è meno raro di quanto si pensa trovarsi a lavorare con vettori e matrici con milioni di elementi l’uno.

Si chiede quindi di testare l’efficienza del proprio codice utilizzando le funzioni contenute nella libreria time. Sotto un esempio di come utilizzare tale libereria per misirare l’efficienza di un codice.

import time

# Inizializzazione delle variabili
v = [0]*10_000

# Far partire il tempo
start_time = time.time()

# Eseguire operazioni varie
for i in range(10_000):
    v[i] += 1

# Misurare il tempo alla fine dell'esecuzione
end_time = time.time()

# Stampare il tempo
print(f"Tempo impiegato: {end_time - start_time}s")

Tempo impiegato: 0.0012390613555908203s

Come abbiamo visto, i cicli for e while in Python sono estremamente lenti.

Esistono però su Python vari modi per riuscire ad evitarli (o almeno, minimizzarne l’impatto sul costo computazionale). Quindi lo svolgimento dell’esercitazione sopra può essere fatta anche in vista dell’efficienza, cercando di sviluppare l’implementazione più efficiente possibile.

Ad esempio, prendere in considerazione operazioni come la list comprehension, operazioni built-in in Python, la pre-allocazione della memoria (inizializzando le variabili) per aumentare l’efficienza, nonché alcuni trick matematici che possono venire in mente per minimizzare il numero di operazioni e quindi massimizzare l’efficienza.

Contents