In ogni momento, grandi telescopi sono puntati verso il cielo notturno, perché da qualche parte sul pianeta è sempre notte. Scrutano Betelgeuse che, si dice, starebbe per esplodere, cercano esopianeti, fotografano nebulose e persino buchi neri. E il loro tempo è prezioso! Ogni osservazione può svolgersi soltanto in una finestra temporale favorevole: occorre quindi scegliere quali osservazioni effettuare ogni notte e in quale preciso momento. Più sotto, nello schema a sinistra, compare un catalogo di undici osservazioni. Ciascuna è rappresentata da una durata (rettangolo nero) e da un intervallo temporale possibile. Sotto è indicato il programma di osservazione del telescopio elaborato dagli astrofisici, che ne comprende nove distribuite su due notti. Per il telescopio non ci sono quasi tempi morti, poiché passerà dall’una all’altra.
Problemi di assegnazione -----------------------
Ma si può fare di meglio e osservare una stella in più in due notti? La posta in gioco è alta per il gruppo di astrofisica, perché un telescopio si affitta per notte! È questo il programma migliore, la migliore combinazione fra tutte quelle possibili? Come saperlo, quando il catalogo stellare dell’Istituto di planetologia e astrofisica di Grenoble (Isère) comprende centinaia di migliaia di obiettivi? L’analisi combinatoria studia collezioni, spesso finite, di oggetti che soddisfano determinate proprietà. Enumerare tutte queste collezioni o individuare la «migliore» sono questioni combinatorie.
Un celebre problema combinatorio fu posto da Leonhard Eulero nel 1779: considerando sei reggimenti di sei ufficiali di grado distinto, è possibile disporre i trentasei ufficiali in un quadrato di 6 per 6 in modo che ogni riga e ogni colonna non contengano due ufficiali dello stesso grado o dello stesso reggimento? Il problema è semplice da formulare e la sua difficoltà deriva spesso dal numero eccessivo di combinazioni da valutare per determinare quella giusta. Si tratta di limitare quanto più possibile questa esplosione combinatoria, ma persino i problemi più semplici superano le capacità umane. Il computer è quindi uno strumento indispensabile per la risoluzione, almeno dal 1953, se si dà credito a Harold William Kuhn (1925 − 2014), inventore del metodo ungherese per il problema di assegnazione. Nemmeno il computer può esplorare l’albero di tutte le combinazioni possibili senza una buona dose di anticipazione (look-ahead ) e un’adeguata analisi dell’esplorazione già compiuta (look-back)!