In questi giorni in ogni scuola c’è un docente che passa le giornate rinchiuso in una stanza con un compito ingrato, che lo fa litigare con i colleghi e con la famiglia e gli toglie l’appetito: fare l’orario. Ma perché è così difficile?
La complessità dell’orario scolastico
L’orario scolastico è uno di quei problemi in cui si dice che c’è una “grande correlazione tra le variabili”. È facile capire perché: non appena facciamo un cambiamento, ad esempio spostiamo in 3B il docente che faceva la prima ora in 3A, dovremo fare una serie di altri cambiamenti a cascata. La 3A rimane scoperta, il collega della 3B dovrà avere un’altra classe, e così via… Inoltre devono ogni volta rimanere fissati sia il numero di ore totali che svolge ogni docente, sia il numero totale di ore per ogni materia per ogni classe. Tutto questo, naturalmente, tenendo conto delle richieste dei docenti, delle possibilità della scuola, di un equilibrio tra le materie. Si capisce che il docente che fa l’orario abbia già bisogno di una vacanza a scuola nemmeno iniziata!
Un problema non polinomiale
I problemi con grande correlazione tra le variabili sono tipicamente problemi di alta complessità computazionale. A seconda di questa complessità, gli scienziati dividono solitamente i problemi in due categorie, dai poco eloquenti nomi di P e NP. Queste sigle stanno per “Polinomiale” e “Non Polinomiale” e si riferiscono al tempo necessario per risolverli, e in particolare a come varia aumentando il numero di variabili del problema, che viene chiamato N.
Facciamo un esempio: consideriamo il problema di sommare tutti i numeri da 1 a un certo numero N. La somma di tutti i numeri da 1 a 10 si può fare a mente in meno di un minuto; se vogliamo fare la somma dei numeri da 1 a 100 il tempo aumenta, ma lo fa in modo lineare con N, cioè per ogni numero in più dobbiamo considerare un certo tempo in più. Questo è particolarmente vero se facciamo i calcoli con un computer, in cui il numero di operazioni che la macchina esegue al secondo è fissato. In altre parole, se abbiamo un computer il doppio più potente, all’incirca nello stesso tempo possiamo arrivare a sommare i numeri fino a un N doppio (in realtà ci metteremo un po’ di più, ma poco di più, per sommare i numeri più grandi).
La vera difficoltà emerge quando l’aumento con N non è più lineare, ma esponenziale. Per esempio nel giochino nella figura seuente, chiamato torre di Hanoi, bisogna spostare tutti i dischi da un piolo all’altro muovendo un solo disco alla volta e senza mai mettere un disco più grande su uno più piccolo.
© Wikimedia
Con 1 solo disco ci vuole una sola mossa, con 2 dischi ci vogliono 3 mosse, con 3 dischi 7 mosse… si può dimostrare che con N dischi ci vogliono 2N – 1 mosse. Quella N all’esponente fa sì che il numero di mosse diventi gigantesco con N relativamente piccolo: per N = 8 del modello in figura vengono fuori ben 255 mosse. Questo problema non è più lineare in N, ma appunto esponenziale, e potete verificare che con N = 100 il tempo necessario per risolverlo, perfino con un computer che possa eseguire un numero enorme di operazioni al secondo, supera di gran lunga il tempo di vita residuo dell’Universo!
I problemi NP mettono sotto scacco qualsiasi computer superveloce e sono pertanto considerati intrattabili. Le cose potrebbero cambiare con l’avvento dei computer quantistici, che permettono di effettuare le operazioni non più solo in sequenza ma contemporaneamente. Quando saranno in circolazione, il mondo della complessità computazionale sarà rivoluzionato. E chissà che i docenti che fanno l’orario non potranno dormire sonni più tranquilli.
Per saperne di più:
Tommaso Castellani, Risolvere i problemi difficili, Zanichelli
