Cosa c’entrano i batteri con gli algoritmi? Molto, se il loro meccanismo di duplicazione è sfruttato per risolvere, con il computer, il famoso ‘problema delle frittelle bruciate’…
Come è noto, l’informatica si occupa di automatizzare la risoluzione di problemi, scomponendo il metodo risolutivo in passi elementari la cui opportuna combinazione permette di ottenere la soluzione del problema. Oggi si dice che un problema è affrontabile dal punto di vista computazionale se la sua complessità algoritmica rientra nella classe
polinomiale (la lunghezza del calcolo espressa come funzione della lunghezza dell’input) ed è maggiorabile da un polinomio (classe P).
Tuttavia, non per tutti i problemi conosciamo un modo di ottenere la soluzione in tempo polinomiale: per problemi più difficili come si può fare? Se siamo autorizzati a seguire più strade allo stesso tempo, ognuna delle quali ci porta a una soluzione in un tempo polinomiale, rientriamo in una classe più ampia.
Più precisamente, supponiamo di avere a ogni passo di calcolo la possibilità di raddoppiare il dispositivo computazionale utilizzato, eseguendo da quel momento in poi due versioni del programma in due configurazioni possibili, e supponiamo che questa possibilità valga a ogni passo di computazione. Il risultato sarà che, anche se limitiamo il tempo di esecuzione (a una durata polinomiale), alla fine avremo fatto un numero di passi di computazione esponenziale nella dimensione dell’input.
Chiaramente, rispetto ai calcolatori così come oggi li conosciamo, non è pensabile che a ogni iterazione sia possibile duplicare il dispositivo computazionale per portare avanti un numero di computazioni che cresca durante l’esecuzione del programma. Tuttavia negli ultimi 20 anni la ricerca in informatica teorica ha studiato e fornito alcune proposte (anche pratiche) per dispositivi e modelli di calcolo non convenzionali, che permettono (almeno in via teorica) di rendere fattibili tali computazioni.
Un esempio recente utilizza i meccanismi di duplicazione dei batteri per risolvere il problema dei burnt pancakes (problema delle frittelle bruciate o BPP). Nel BPP bisogna determinare il minimo numero di mosse necessarie ad ordinare una pila di frittelle. La pila contiene frittelle di dimensioni diverse ognuna delle quali ha un lato dorato ed uno bruciato, e bisogna ordinare la pila in modo tale che le frittelle più grandi siano in basso alla pila e tutte le frittelle siano orientate con la parte dorata rivolta verso l’alto. Una mossa consiste nel rovesciare una o più frittelle consecutive della pila, per le quali quindi si inverte sia l’ordine che l’orientamento della faccia dorata.
Lo scopo è quello di trovare il numero minimo di operazioni di rovesciamento necessarie per ordinare una pila di n frittelle, per n qualsiasi.
Un team di ricercatori provenienti dai dipartimenti di biologia, di matematica, informatica e fisica del Davidson College, della Missouri Western State University e della Hampton University, hanno utilizzato frammenti di DNA per rappresentare le frittelle del BPP. Hanno aggiunto geni di un altro batterio ed inserito nel DNA di E. Coli una sequenza che è in grado di rovesciare una parte di DNA. Inoltre è stato aggiunto un frammento di DNA che rende il batterio resistente agli antibiotici ma solo quando l’orientamento è quello corretto. Il tempo richiesto per ottenere i primi batteri resistenti all’antibiotico corrisponde al minimo tempo necessario per risolvere il problema, e quindi al minimo numero di passi necessari.
Risolvere questo problema quando la dimensione della pila cresce diventa computazionalmente molto difficile. Non è ancora conosciuta un’equazione che fornisce direttamente la risposta. Per sei frittelle ci sono 46080 configurazioni possibili per 12 ce ne sono 1.9 miliardi. Il numero di configurazioni è dato dalla formula 2n*n!: uno spazio di ricerca che cresce molto rapidamente per cui anche avendo a disposizione enormi reti di calcolatori non è possibile calcolare la soluzione minima. Invece il numero di batteri di una colonia in ambiente favorevole cresce in modo esponenziale ed ogni individuo contiene il DNA per effettuare i passi di calcolo. Quindi ogni batterio agisce calcolando una diversa configurazione; l’evoluzione in parallelo di miliardi di questi micro-computer permette finalmente di ottenere la soluzione in modo molto più rapido ed economico.
di Marco Pedicini
Marco Pedicini è un ricercatore dell’IAC-CNR e insegna Informatica Generale all’Università di Roma Tre.
Link:
L’articolo originale: Engineering bacteria to solve the Burnt Pancake Problem.
