Lezione 09 · Complessità computazionale e progettazione dei programmi¶

Due programmi possono dare lo stesso risultato ma impiegare tempi molto diversi: uno risponde in un istante, l'altro in mille anni. La complessità computazionale serve a prevedere questo comportamento prima di eseguire il programma. Nella seconda parte vedrai come si progetta un programma in modo ordinato, così da renderlo leggibile, corretto e facile da modificare.

Calcolabilità e trattabilità¶

Un problema è risolvibile se esiste una Macchina di Turing (un modello teorico di calcolatore) che fornisce la soluzione in un tempo finito. È trattabile se esiste un algoritmo che arriva alla soluzione in tempi e con un consumo di memoria accettabili. Ricordi la Torre di Hanoi della lezione 08? È risolvibile ma non trattabile.

La complessità computazionale studia i costi di esecuzione di un algoritmo (tempo e memoria) e come crescono al crescere della dimensione del problema. La trattabilità dipende proprio dalla complessità.

Tipi e misure di complessità¶

Ci sono due tipi di complessità, legati tra loro:

• complessità spaziale: quanta memoria serve per i dati dell'algoritmo;
• complessità temporale: quanto tempo serve per produrre la soluzione. Oggi è la più studiata, perché i calcolatori hanno in genere molta memoria.

Le misure possono essere:

• statiche: dipendono solo dalla struttura dell'algoritmo (ad esempio il numero di istruzioni scritte), non dai dati di input;
• dinamiche: dipendono dalla struttura e dai dati di input. Ricordano le sequenze dinamiche della lezione 08.

Complessità e dati di input¶

Il primo fattore che incide sul tempo è la quantità di dati. Per questo il tempo di esecuzione si scrive come una funzione f(n) della dimensione n dell'input. Ad esempio, un algoritmo ha tempo n² se il tempo cresce come il quadrato della dimensione dell'input: se n raddoppia, il tempo diventa circa quattro volte più grande.

La dimensione da sola però non basta: il tempo dipende anche da come sono fatti i dati. Valori diversi possono far prendere all'algoritmo strade diverse. Per questo si studiano tre casi:

Complessità asintotica¶

Quando si analizza un algoritmo interessa come cresce il tempo per n molto grande. Si guarda l'ordine di grandezza di f(n) e si trascurano le operazioni poco importanti, concentrandosi su quelle predominanti. Questa è la complessità asintotica: dipende solo dall'algoritmo. La complessità esatta, invece, dipende da tanti fattori (il calcolatore, il linguaggio, …).

Se due algoritmi risolvono lo stesso problema con complessità f(n) e g(n), e f(n) è asintoticamente inferiore a g(n), allora esiste una dimensione n₀ oltre la quale il primo algoritmo è sempre più veloce del secondo.

Le complessità più diffuse¶

Dalla più trattabile alla meno trattabile:

Guarda quanto crescono in fretta:

Con n = 100 un algoritmo esponenziale richiederebbe circa 10³⁰ passi: anche a un miliardo di passi al secondo, servirebbero miliardi di miliardi di anni.

n = int(input('Dimensione n: '))

passi_lineare = 0
for i in range(n):            # un ciclo: cresce come n
    passi_lineare = passi_lineare + 1

passi_quadratica = 0
for i in range(n):            # due cicli annidati: cresce come n²
    for j in range(n):
        passi_quadratica = passi_quadratica + 1

passi_log = 0
k = n
while k > 1:                  # dimezzo ogni volta: cresce come log n
    k = k // 2
    passi_log = passi_log + 1

print('logaritmica:', passi_log)
print('lineare:    ', passi_lineare)
print('quadratica: ', passi_quadratica)
print('esponenziale (2**n):', 2 ** n)

Prova con 10, 100 e 1000 e confronta come crescono i numeri.

Esempio: trovare il minimo¶

Problema: trovare il minimo m in un insieme di n numeri {x₁, x₂, …, xₙ}.

Algoritmo:

1. prendi x₁ come primo candidato: m = x₁;
2. confronta m con x₂, …, xₙ;
3. ogni volta che trovi un xᵢ < m, aggiorna m = xᵢ;
4. alla fine m è il minimo.

Si fanno n − 1 confronti, che per n grande è praticamente n: la complessità è f(n) = n (lineare). Il tempo è direttamente proporzionale alla dimensione dei dati.

Esempio: ordinamento per selezione (selection sort)¶

Problema: disporre in ordine crescente n numeri {x₁, x₂, …, xₙ}.

Algoritmo: per ogni indice i = 1, 2, …, n − 1:

1. trova il minimo m nel sottoinsieme {xᵢ, xᵢ₊₁, …, xₙ};
2. porta m in posizione i, scambiandolo con xᵢ.

Si cerca il minimo n − 1 volte, su insiemi sempre più piccoli: il primo ha n elementi, il secondo n − 1, e così via. I confronti sono

(n − 1) + (n − 2) + … + 2 + 1 = n · (n − 1) / 2

Per n = 1000 sono 499 500 confronti, circa n²/2. Per n grande conta solo il termine più importante, quindi la complessità è dell'ordine di n² (quadratica).

x = [5, 4, 3, 2, 1]     # prova anche [1, 2, 3, 4, 5] e [3, 1, 5, 2, 4]
print('Prima: ', x)

confronti = 0
scambi = 0
n = len(x)
for i in range(n - 1):
    # cerco la posizione del minimo tra x[i], ..., x[n-1]
    pos_min = i
    for j in range(i + 1, n):
        confronti = confronti + 1
        if x[j] < x[pos_min]:
            pos_min = j
    # porto il minimo in posizione i
    if pos_min != i:
        temp = x[i]
        x[i] = x[pos_min]
        x[pos_min] = temp
        scambi = scambi + 1

print('Dopo:  ', x)
print('Confronti:', confronti, '| scambi:', scambi)

Con 5 elementi i confronti sono sempre 5 · 4 / 2 = 10. Gli scambi invece cambiano: 0 con la lista già ordinata, 2 con [5, 4, 3, 2, 1], 3 con [3, 1, 5, 2, 4].

La progettazione degli algoritmi¶

Progettare un algoritmo è un'attività intellettuale impegnativa: richiede creatività e intuito, ed è più difficile che scriverlo in un linguaggio di programmazione. Bisogna valutare:

• la complessità computazionale, per usare bene le risorse;
• la correttezza, cioè che la soluzione rispetti davvero le specifiche del problema.

La produzione del software non può essere "artigianale", affidata all'esperienza del singolo programmatore. Deve seguire metodi sistematici, con parametri di qualità fissati. Di questo si occupa l'Ingegneria del Software, la branca dell'Ingegneria Informatica che raccoglie metodi e tecniche per produrre software con requisiti di qualità prefissati e in modo standard.

Il ciclo di vita del software¶

Il ciclo di vita del software è l'insieme delle fasi con cui si sviluppa un sistema software. Le fasi tipiche sono:

flowchart TD
    A["Analisi dei requisiti: COSA deve fare"] --> B["Progetto: COME lo fa"]
    B --> C["Codifica nel linguaggio di programmazione"]
    C --> D["Verifica e collaudo"]
    D --> E["Manutenzione"]

Separare analisi e progetto. Si tiene ben distinto il "cosa" (analisi dei requisiti, specifiche funzionali) dal "come" (progetto, a vari livelli di dettaglio). Così l'analisi non è condizionata da scelte di progetto fatte troppo presto, e anzi guida quelle scelte.

Analisi dei requisiti¶

L'analisi raccoglie le informazioni per capire il problema: dai colloqui con gli utenti e dall'esame dell'ambiente in cui il programma sarà usato. Produce:

• requisiti funzionali: cosa deve fare il programma e su quali dati;
• requisiti non funzionali: quali prestazioni deve offrire (velocità, memoria, …).

L'analista deve trasformare esigenze confuse e a volte contraddittorie in un modello chiaro del problema.

Le specifiche ottenute devono avere un'unica interpretazione e coprire tutte le situazioni possibili. La loro correttezza si verifica con la documentazione su: i dati di ingresso, i dati di uscita e un metodo risolutivo che, sulla carta, risolva il problema.

Progetto¶

Il progetto comprende il raffinamento successivo dei dati e dell'algoritmo e la sua codifica: si esamina il problema, se ne costruisce un'astrazione, si riduce la complessità con un approccio top-down e infine si scrive la soluzione in un linguaggio di programmazione.

La programmazione strutturata¶

Un programma di buona qualità deve essere:

• leggibile;
• documentabile;
• modificabile;
• provabile (si può verificare che funziona).

La programmazione strutturata ottiene queste qualità con cinque strumenti:

1. la documentazione;
2. la modularità;
3. l'uso di strutture di controllo a un ingresso e a una uscita;
4. il metodo top-down o bottom-up nella progettazione;
5. l'analisi critica del prodotto.

1. La documentazione¶

La documentazione rende il programma chiaro. Aiuta a capire il problema e a controllare la correttezza, a riprendere il lavoro dopo un'interruzione, a spiegare le scelte agli altri e a modificare il programma quando cambiano le specifiche.

Due regole: va scritta durante il progetto (nel momento in cui si fanno le scelte) e va messa il più possibile dentro il programma. Ha due livelli.

Tra i commenti sono particolarmente utili:

• le motivazioni (sigla M:): spiegano a cosa serve un pezzo di programma, indipendentemente da come è scritto. Importante la motivazione globale all'inizio, che riassume il problema risolto;
• le asserzioni (sigla A:): dicono che cosa è vero sulle variabili in quel punto. Servono per una prova qualitativa della correttezza, soprattutto sulle variabili di input (le condizioni limite in cui il programma lavora).

Spesso si trovano scritte nella sintassi dei commenti di altri linguaggi (/* M: ... */). In Python si usa #:

# M: calcola la media di n voti inseriti da tastiera (motivazione globale)

n = int(input('Quanti voti? '))
# A: n > 0, altrimenti la media non è definita
if n > 0:
    # M: calcolo la somma degli n voti
    somma = 0
    for i in range(n):
        voto = float(input('Voto: '))
        somma = somma + voto
    # A: somma contiene la somma di tutti gli n voti
    media = somma / n
    print('Media:', media)
else:
    print('Il numero di voti deve essere positivo')

2. La modularità¶

Un programma deve essere composto da moduli funzionali. Ogni modulo ha un solo compito, ben preciso. Così si esamina un aspetto del problema alla volta. In Python i moduli sono le funzioni (le vedrai nel capitolo 5).

3. Strutture di controllo a un ingresso e una uscita¶

Le strutture di controllo (sequenza, selezione, iterazione) sono gli schemi con cui si compongono i moduli. Decidono quando, in che ordine e quante volte si eseguono le istruzioni. Devono avere un solo ingresso e una sola uscita: componendo più moduli si ottiene ancora un modulo con un solo ingresso e una sola uscita. Nei diagrammi di flusso vuol dire evitare frecce che "saltano" dentro o fuori da un blocco a caso.

4. Top-down e bottom-up¶

Top-down (dal generale al particolare, metodo deduttivo). Un problema complesso non si può risolvere pensando a tutto insieme. Si procede per raffinamenti successivi (stepwise refinement):

1. si analizza il problema al livello più astratto, individuando i passi principali;
2. si suppone di avere un esecutore capace di eseguire quei passi;
3. ogni passo diventa a sua volta un problema, da scomporre in sottoproblemi più semplici;
4. si continua finché si arriva a passi comprensibili all'esecutore (istruzioni del linguaggio) o a software già esistente.

Astrarre vuol dire tenere i dettagli essenziali e omettere quelli non essenziali. I livelli alti dicono cosa fare; i livelli bassi dicono come farlo. A ogni passo i sottoproblemi si organizzano in sequenza, selezione o iterazione, e vanno documentate le variabili di ingresso e di uscita di ciascuno.

La soluzione si può disegnare come un albero: la radice è il problema, i nodi sono le decisioni di progetto, le foglie sono i passi che l'esecutore sa fare.

Esempio: calcolare la percentuale di esami superati da uno studente.

flowchart TD
    R["Calcola la percentuale di esami superati"] --> A["Leggi i dati"]
    R --> B["Calcola la percentuale"]
    R --> C["Stampa il risultato"]
    A --> A1["Leggi il numero di esami sostenuti"]
    A --> A2["Leggi il numero di esami superati"]
    B --> B1["Se sostenuti > 0"]
    B1 --> B2["percentuale = superati / sostenuti * 100"]
    C --> C1["Stampa la percentuale con 1 decimale"]

Le foglie si traducono direttamente in Python:

# M: calcola la percentuale di esami superati
sostenuti = int(input('Esami sostenuti: '))
superati = int(input('Esami superati: '))
# A: 0 <= superati <= sostenuti
if sostenuti > 0:
    percentuale = superati / sostenuti * 100
    print(f'Esami superati: {percentuale:.1f}%')
else:
    print('Nessun esame sostenuto')

Bottom-up (dal particolare al generale, metodo induttivo). Si parte da ciò che il sistema sa già fare: si creano moduli elementari e li si combina in moduli via via più complessi, fino a ottenere quello che risolve il problema. Nell'albero si va dalle foglie verso la radice.

5. L'analisi critica¶

Alla fine si valuta con cura la soluzione:

• si verifica la correttezza, ad esempio simulando l'esecuzione con un insieme di dati di prova;
• si valuta l'efficienza, confrontandola con altre soluzioni e studiando l'effetto delle scelte di progetto;
• si controlla che ogni azione sia documentata, così che in futuro l'algoritmo si possa modificare.

Errori frequenti negli esercizi¶

Esercizi¶

Esercizio 1 · Riconosci la complessità. Per ciascun frammento, conta quante volte viene eseguita l'istruzione passi = passi + 1 con n = 8 e indica l'ordine di complessità (log n, n, n² o 2ⁿ).

# Frammento A
for i in range(n):
    passi = passi + 1
for j in range(n):
    passi = passi + 1

# Frammento B
for i in range(n):
    for j in range(n):
        passi = passi + 1

# Frammento C
i = 1
while i < n:
    i = i * 2
    passi = passi + 1

# Verifica qui le tue risposte

n = 8
passi = 0
for i in range(n):
    passi = passi + 1
for j in range(n):
    passi = passi + 1
print('A:', passi)

passi = 0
for i in range(n):
    for j in range(n):
        passi = passi + 1
print('B:', passi)

passi = 0
i = 1
while i < n:
    i = i * 2
    passi = passi + 1
print('C:', passi)

Esercizio 2 · Ricerca in una lista. Vuoi sapere se un valore è presente in una lista di n elementi, controllandoli uno alla volta dal primo e fermandoti appena lo trovi. Quanti confronti fai nel caso migliore e nel caso peggiore? Qual è la complessità nel caso peggiore? Scrivi il programma e conta i confronti.

# Scrivi qui la tua soluzione

# M: cerca un valore in una lista e conta i confronti
lista = [7, 3, 9, 1, 5, 8]
cercato = int(input('Valore da cercare: '))

confronti = 0
trovato = False
i = 0
while i < len(lista) and not trovato:
    confronti = confronti + 1
    if lista[i] == cercato:
        trovato = True
    i = i + 1
# A: trovato è True se e solo se cercato è nella lista
print('Trovato:', trovato, '| confronti:', confronti)

Esercizio 3 · Progetto top-down. Un negozio vuole un programma che legga i prezzi di alcuni prodotti (finché si inserisce 0), calcoli il totale, applichi uno sconto del 10% se il totale supera 100 € e stampi il totale da pagare. Scomponi il problema con il metodo top-down (almeno due livelli), poi scrivi il programma con una motivazione globale (M:) e almeno un'asserzione (A:).

# Scrivi qui la tua soluzione

flowchart TD
    R["Calcola il totale da pagare"] --> A["Leggi i prezzi e calcola il totale"]
    R --> B["Applica lo sconto"]
    R --> C["Stampa il totale"]
    A --> A1["totale = 0"]
    A --> A2["finché prezzo diverso da 0: totale = totale + prezzo"]
    B --> B1["se totale > 100: totale = totale * 0.9"]
    C --> C1["stampa con 2 decimali"]

# M: legge i prezzi dei prodotti (0 per finire), applica uno sconto
# M: del 10% sopra i 100 euro e stampa il totale da pagare

SOGLIA = 100
SCONTO = 0.10

# M: lettura dei prezzi e calcolo del totale
totale = 0
prezzo = float(input('Prezzo (0 per finire): '))
while prezzo != 0:
    totale = totale + prezzo
    prezzo = float(input('Prezzo (0 per finire): '))
# A: totale è la somma di tutti i prezzi inseriti

# M: applicazione dello sconto
if totale > SOGLIA:
    totale = totale * (1 - SCONTO)

print(f'Totale da pagare: {totale:.2f} euro')

Verifica¶