Category Archives: Teoria e pratica

Linguaggi regolari

Oggi si va un po’ di più sulla teoria. Oh, prima o poi toccava farlo. Qui il link al post precedente.

Linguaggi

Chi di voi conosce Noam Chomsky? Si proprio lui, avete sentito bene: il vecchio anarchico americano, uno dei pochissimi rimasti. Una persona decisamente controcorrente, sempre pronto a dire la sua fuori dal coro, dai tempi in cui si oppose alla guerra in Vietnam, fino alla guerra del golfo e la guerra in Iraq con il suo attivismo pacifista, nonostante l’età. In effetti, non deve essere facile essere come lui in un paese come gli USA.

Ma che c’entra Noam Chomsky con l’informatica e con le espressioni regolari? Moltissimo a dire la verità. Infatti, il vero mestiere di Noam Chomsky è quello del ricercatore nel campo della linguistica, e uno dei padri ispiratori della disciplina della linguistica computazionale, una disciplina al confine tra l’informatica e la linguistica classica.

In particolare, Chomsky è l’inventore del concetto di grammatica generativa e della classificazione dei linguaggi formali. Cosè un linguaggio formale?

Si parte con un alfabeto definito come un insieme di simboli (ad esempio le lettere dell’alfabeto italiano o inglese, oppure il codice ASCII). L’importante è definire appunto l’insieme dei simboli.

Una parola è una sequenza di simboli. Ad esempio, se prendiamo l’alfabeto italiano, sono parole le seguenti abc, aaaa, informatica, parola, ecc. Basta prendere una sequenza di simboli, non importa se abbia o no “senso comune”. La sequenza potrebbe anche essere illimitata, ovvero contenere un numero a priori illimitato di simboli.

A questo punto un linguaggio L è un sottoinsieme delle possibili parole. Ad esempio, potrei definire un linguaggio L1 che contiene le parole “Giuseppe” e “aaa”. Non che un linguaggio così abbia senso, ma è per farvi capire la generalità della definizione. Un altro linguaggio potrebbe essere quello dei codici di una tastiera che permettono l’apertura di una porta. Ovvero, l’esempio visto negli scorsi post. Ad esempio, il linguaggio L2 di una fantomatica porta potrebbe contenere due parole soltanto, 12A45 e 22B48.

Oppure potrei dire che il linguaggio L3 contiene parole che cominciano per il simbolo a e successivamente sono formate da un numero da zero a illimitato di sequenze della coppia ab. Per esempio, aababab è una parola del linguaggio, così come a e aab, mentre la parola aaa non lo è.

Quindi i linguaggi possono contenere un numero finito di parole, oppure infinito. Nel primo caso basta elencarle tutte. Nel secondo caso, devo dare una regola di appartenenza.

Le regole di un linguaggio

Concentriamoci sul secondo caso: vogliamo definire un linguaggio dando delle regole. Possiamo farlo in due modi: generativo, oppure riconoscitivo.

Nel caso generativo, diamo delle regole per generare tutte le parole che appartengono al linguaggio: in pratica, dato l’alfabeto iniziale e le regole, possiamo creare la lista delle parole che compongono il linguaggio. Queste regole si chiamano grammatica. Si, proprio come la vostra vecchia grammatica di italiano che portavate a scuola tutti i giorni quando eravate dei pischelli. Naturalmente, in questo contesto, grammatica significa in realtà algoritmo o procedura per generare un elenco di parole.

Nel caso riconoscitivo, vogliamo risolvere in problema leggermente diverso: data una parola, vogliamo sapere se questa fa parte di un linguaggio. Naturalmente, ogni linguaggio avrà le sue regole. Salta fuori che un cosa come gli automi che abbiamo visto negli scorsi post sarebbero adatti ad implementare dei riconoscitori.

I due metodi sono uno il duale dell’altro: in particolare, una strategia per riconoscere se una data parola w appartiene o no al linguaggio potrebbe essere la seguente:

  • generare la lista di tutte le parole del linguaggio che hanno la stessa lunghezza di w;
  • vedere se w è presente nella lista.

Viceversa, se vogliamo generare tutte le parole di un linguaggio, si potrebbe:

  • generare tutte le possibili parole di lunghezza 1, 2, 3, … n,
  • e vedere quali di queste sono riconosciute dal riconoscitore.

E quindi, grammatica o riconoscitore, per noi pari sono. Più o meno.

Potenza espressiva

Ma non tutti i linguaggi sono ugualmente “facili”. In particolare, certi linguaggi sono più “semplici” e altri sono più difficili. Chomsky classificò i linguaggi in varie categorie, a seconda del tipo di algoritmo per generare/riconoscere il linguaggio. Ecco la tabella dal più “semplice” al più “complesso”.

Tipo Linguaggio Tipo di Automa
3 Linguaggi regolari Automi a stati finiti
2 Linguaggi liberi dal contesto Automi a pila
1 Linguaggi dipendenti dal contesto Automi lineari
0 Ricorsivo Decisore / Macchina di Turing

Avete visto cosa c’è in alto a destra? I nostri amici automi a stati finiti! Si, gli automi sono in grado di riconoscere la categoria di linguaggi più semplice che c’è. Invece nella casella in basso a destra c’è la famosa Macchina di Turing, la macchina calcolatrice più espressiva di tutte. Quindi, i linguaggi ricorsivi sono i più “difficili” di tutti.

Esempio

A questo punto bisogna fare un esempio. Prendiamo il linguaggio che avevo definito prima: una parola appartiene al linguaggio se c’è una a come primo simbolo seguita da una sequenza di un numero qualsiasi (anche 0) di coppie ab. Ecco l’automa che riconosce le parole di questo linguaggio:

automa-linguaggio.png

Figure 1: Automa a stati finiti per il linguaggio dell’esempio

Nel disegnare la figura, ho fatto l’assunzione che se uno stato riceve un simbolo per cui non ha un arco in uscita, allora si blocca con errore. Per esempio, se mentre siamo in S0 arriva una b, allora l’automa si blocca con un errore. In realtà avrei dovuto mettere un stato apposito, per esempio ERR in cui si finisce quando arriva un simbolo inaspettato, e aggiungere degli archi da ciascuno stato allo stato di errore. Ma il disegno si complica inutilmente, e allora molto spesso si utilizza questa scorciatoia.

L’automa in figura definisce il linguaggio in maniera esatta. Cioè, invece di scrivere la definizione del linguaggio a parole, descrivo l’automa, che sicuramente è più preciso di qualunque descrizione in italiano. In effetti, l’automa è un modo procedurale di definire il linguaggio.

E se volessi utilizzare una grammatica? Si scrive più o meno così:

\displaystyle  a(ab)^n

dove l’elevazione a n indica la ripetizione per un numero intero di volte dei simboli contenuti tra le parentesi tonde. Sembra quasi uguale a un’espressione regolare, vero? L’espressione sarebbe:

a(ab)*

dove l’asterisco significa “il precedente pattern può essere ripetuto un numero arbitrario di volte (anche zero volte)”.

Notate che il pattern è illimitato. In altre parole, non abbiamo messo un limite alla lunghezza delle parole del linguaggio. Il nostro linguaggio L contiene dunque un numero infinito di parole! Tuttavia, poiché il pattern con cui queste parole sono generate è molto semplice, altrettanto semplici sono la grammatica e l’automa che lo descrivono.

Quindi, la difficoltà di un linguaggio non ha niente a che vedere con il numero di parole che contiene, ma semmai con la complessità del pattern di riconoscimento. Nell’ultima puntata spiegherò perché un automa a stati finiti non è poi così potente, e cosa non può riconoscere.

Errata Corrige

Nello scorso post ho fatto un errore: nella figura ho messo una freccia da da S3 a S2 con etichetta “2”; in realtà, la freccia doveva essere da S3 a S4, sempre con etichetta “2”. Grazie a Stefano per la segnalazione, è molto gratificante avere lettori attenti che ti trovano i bachi! Grazie ancora.

Macchine a stati finiti – 2

Seconda puntata. Cominciamo risolvendo il problema della scorsa volta. Ricordiamo che i due codici che aprono la porta sono 12A45 e 22B48. Ecco il sistema corretto, dove per semplicità ho tolto tutti gli archi rossi: fate l’assunzione implicita che, ogni volta che premo un tasto sbagliato, il sistema vada automaticamente in S0

soluzione.png

Figure 1: Soluzione corretta del riconoscitore con due codici.

Anche così non è proprio semplicissimo, ma sono evidenti due file orizzontali di stati (anche perché le ho messe apposta così): quella superiore si occupa del primo codice 12A45, mentre quella inferiore si occupa del secondo codice 22B48. Inoltre, se mentre sto facendo il primo codice premo 2, il sistema passa a S2, e se mentre sto facendo il secondo codice premo 1, il sistema passa a S1, per cui ho tutte le frecce incrociate. Si può dimostrare (ma è abbastanza evidente) che questo automa riconosce solo i due codici voluti.

Implementazione

Come si implementano nella pratica questi automi? Non è affatto difficile, una volta che avete fatto il grafo. Se siete degli smanettoni elettronici, potete provare a costruire un semplice circuito digitale che riconosca i due codici. Innanzitutto serve una locazione di memoria per fare in modo di ricordarsi in quale stato siamo arrivati. Serve memorizzare 10 stati, per cui basta un registro a 4 bit. Poi naturalmente un tastierino alfanumerico che vi dia in output una sequenza di bit diversa per ogni tasto.

Poi si costruisce una bella tabella, con tante righe quanti sono gli stati, e con tante colonne quanti sono i possibili simboli in input. Nelle cella alla posizione (s,x) ci si mette lo stato in cui si finisce quando siamo nello stato s e riceviamo in input il simbolo x Per esempio, una cosa così:

Stato ‘1’ ‘2’ ‘4’ ‘5’ ‘8’ ‘A’ ‘B’ ‘*’
S0 S1 S2 S0 S0 S0 S0 S0 S0
S1 S1 S3 S0 S0 S0 S0 S0 S0
S2 S1 S4 S0 S0 S0 S0 S0 S0
S3 S1 S4 S0 S0 S0 S5 S0 S0
S4 S1 S4 S0 S0 S0 S0 S6 S0
               

Non avevo molta voglia di scriverla tutta a mano, ma naturalmente queste tabelle possono essere generate automaticamente. A questo punto avete sulle righe la rappresentazione in bit dello stato, e sulle colonne la rappresentazione in bit dell’input, e produrrete in output la rappresentazione in bit del prossimo stato. Questo è un semplice circuito combinatorio, e un elettronico dilettante dovrebbe sapere come sintetizzarlo, vero?

E quindi basta, abbiamo finito. E se vogliamo riprogrammarlo periodicamente con nuovi codici? Potete usare un Programmable Logic Device, ad esempio.

Avete la mano porcina per i lavori manuali, come il sottoscritto, e volete smanettare come un vero informatico che non si abbassa a toccare nient’altro che la tastiera di un PC? Potete implementare la stessa cosa in un qualunque linguaggio di programmazione. Lo stato viene memorizzato in una variabile, la tabella con uno switch-case oppure con una sequenza di if-then-else, oppure ancora con un array-bidimensionale. Non starò qui a spiegare per filo e per segno come fare, i nostri affezionati lettori di Ok, Panico sanno già tutto, vero?

Conclusioni parziali

Ma le espressioni regolari dove sono? La scorsa volta avevamo detto che avremmo parlato di RE, e fin qui abbiamo visto automi, macchine, latch e circuiti combinatori. Dove diavolo sono le RE?

In realtà le RE risolvono esattamente questo problema: come riconoscere una sequenza di caratteri in un testo (ed eventualmente fare delle sostituzioni). Quindi, i più sgamati di voi avranno probabilmente capito che gli automi e le RE sono collegati. Ma come?

La risposta alla prossima puntata!

Macchine a stati finiti

Recentemente ci sono stati alcuni post su Ok, Panico che riguardavano le espressioni regolari, (RE). Mi sono detto che forse è il caso di fare una serie di post un pochino teorici sull’argomento, se ve la sentite. Ve la sentite? Ma sì, dai. Cominciamo da lontano, (anche se non troppo).

Un esempio di automa

Una macchina a stati finiti (o automa a stati finiti) è un aggeggio matematico-informatico che può aiutarci a descrivere alcuni semplici sistemi automatici. Per spiegarvi in pratica di cosa si tratta, parto come al solito da un esempio pratico: il sistema d’accesso al mio palazzo.

Il portone del palazzo dove abito, come quasi tutti i palazzi di Parigi, si apre quando si inserisce il codice alfanumerico corretto su una tastiera. La tastiera permette l’inserimento delle cifre 0-9, e delle lettere A e B. Un tipico codice contiene 5 caratteri, per esempio 12A45. Se si inserisce il codice corretto la porta si apre, altrimenti niente. Se sbagliate qualche cifra potete sempre ripartire da capo. Ad esempio, se sbagliate e premete 23 come prime due cifre, potere ricominciare da capo immediatamente, e quindi la porta si aprirà anche con la sequenza 2312A45, l’importante è che gli ultimi 5 caratteri siano corretti.

Come è implementato il circuito elettronico che regola l’apertura della porta? Esso riceve i caratteri, uno alla volta, e appena ha riconosciuto la sequenza giusta apre la porta. Quindi, il circuito deve ricordarsi la storia passata. Vediamo come può farlo efficacemente facendo un piccolo diagramma “a palle”:

macchina.png

Figure 1: Macchina a stati per l’apertura del portone con un codice

Ogni “palla” rappresenta uno stato del sistema. Inizialmente il sistema si trova nello stato S0, e aspetta i nostri comandi. Ogni comando che arriva può causare una “transizione di stato” che viene rappresentata da una freccia (o più precisamente, un arco orientato). Ho indicato in nero le transizioni “buone” per noi, mentre ho indicato in rosso le transizioni che ci fanno “tornare indietro” perché abbiamo sbagliato il codice. Per aprire la porta a partire dallo stato S0 dobbiamo fare uno dei percorsi con gli archi “neri”. Inoltre, ho colorato di verde la “palla” corrispondente allo stato che vogliamo raggiungere.

Ad esempio, se il sistema è nello stato S0 e premiamo il tasto ‘1’, il sistema si porta nello stato S1, altrimenti resta nello stato S0. Se il sistema si trova nello stato S3, abbiamo fatto la metà dello sforzo: se premiamo ancora il tasto ‘4’ andiamo avanti, se facciamo un errore torniamo allo stato S0, e infine se premiamo ‘1’ andiamo direttamente nello stato S1 perché questo potrebbe essere l’inizio di una nuova sequenza corretta.

Sembra complicato? In realtà la rappresentazione grafica è un pochino complicata da disegnare e da leggere per chi non è pratico (mentre è o dovrebbe essere pane per i denti di ogni informatico). La figura che vedete si chiama “grafo orientato”, e come potete immaginare c’è un’intera branca della matematica che se ne occupa.

Dato che abbiamo formalizzato il problema, potremmo fare delle analisi. Per esempio, è possibile dimostrare formalmente che:

  • da qualunque stato parto tra S0, S1, S2, S3, S4, digitando il codice giusto arrivo in S5;
  • che non c’è nessun altro modo per raggiungere S5.

In altre parole, possiamo dimostrare che il sistema funziona come volevamo: basta enumerare tutti i possibili casi.

Macchine a stati finiti

Le macchine a stati finiti sono utilizzate in moltissimi campi dell’ingegneria, dall’elettronica all’informatica, e sono state studiate per molti anni. Sono infatti alla base della teoria dell’informazione.

Si chiamano macchine o automi perché all’inizio furono applicate alla meccanica. D’altronde, i primi computer erano meccanici (la pascalina, la macchina analitica di Babbage…), e in molti casi servivano ad automatizzare dei compiti ripetitivi, da cui il nome di automi (in inglese si usa la parola latina automaton al singolare, e automata al plurale). Sono “a stati finiti” perché il numero di stati (le palle nel disegno) sono in numero finito.

Quest’ultima cosa è importante. Il fatto che gli stati siano finiti ci permette di controllare tutti i possibili percorsi nel grafo, ma ci dice anche che queste macchine non sono poi così tanto potenti … ma ne riparleremo più avanti.

La macchina che vi ho presentato è un riconoscitore, perché il suo scopo è di riconoscere una sequenza di input. Le macchine a stati finiti possono essere usati anche per scopi di controllo: si può complicare la notazione permettendo la possibilità di dare dei “comandi”. Ad esempio una macchina a stati finiti può essere utilizzata per leggere dei valori di temperatura e dei valori orari, e comandare l’accensione o lo spegnimento di una caldaia. In quel caso si parla di sistema ibrido ed è l’argomento di cui mi sto occupando recentemente nelle mie ricerche.

Macchine a stati finiti possono essere utilizzate per implementare il sistema di navigazione dei menu del vostro televisori; e ancora, Emacs, il mio editor preferito, usa gli automi a stati finiti per riconoscere sequenze di pressione dei tasti per comandi complicati; e lo stesso fa l’editor Vim. Insomma, dovunque ci sia uno “stato” in base al quale bisogna fare cose diverse, si possono utilizzare gli automi.

In questa mini-serie di post, noi ci focalizzeremo solo sulle macchine riconoscitrici: lo scopo è riconoscere se una sequenza in input è corretta. Se lo è, l’automa termina su uno stato di “accettazione” (nell’esempio in figura, lo stato S5 colorato in verde). Se la sequenza non è corretta, l’automa finisce su uno stato “non accettante” e “rifiuta” la sequenza.

Un esercizio

Per concludere questo primo post facciamo un esercizio. Supponiamo che i codici validi per aprire la porta siano 2: oltre a 12A45 c’è anche 22B48. Come facciamo a definire un unico automa che si occupi di aprire la porta in uno (e uno solo) dei due casi?

Proviamo subito.

seconda.png

Figure 2: Questa macchina non funziona

Senza stare a pensarci su, ho semplicemente aggiunto sugli archi le etichette del secondo codice.

Secondo voi, funziona bene questo secondo automa?

La risposta è niente affatto! Non posso semplicemente aggiungere le etichette sugli archi in questa maniera brutale, perché così facendo ho fatto un errore: all’uscita di S1 ci sono due archi che hanno l’etichetta ‘2’. Se il sistema è in S1 e viene premuto il tasto ‘2’ che succede? Si ricomincia ritorna in S1 oppure si va a S2?

Inoltre, anche supponendo di risolvere il problema togliendo l’etichetta ‘2’ dall’arco S1 -> S2, la porta si apre con molti più codici di prima! Ad esempio, il codice 12B48 apre la porta, e non dovrebbe.

Insomma, è tutto sbagliato. Volete pensare un po’ a risolvere il problema da soli? La prossima puntata vi riporto la soluzione e si continua la strada verso le espressioni regolari.

Perché JavaScript non va bene per i dispositivi mobili

E’ possibile che un tablet possa sostituire efficacemente un PC?

Qualche tempo fa mi sono imbattuto in questo post che contiene un sacco di informazioni interessanti sui linguaggi di programmazione dinamici e sul perché non siano adatti alla programmazione di applicazioni per dispositivi mobili. Ne consiglio a tutti la lettura. Ma dato che il post è lungo, ne farò qui un sommario aggiungendo i miei commenti.

Il garbage collector

I linguaggi di programmazione possono essere categorizzati in molti modi. Uno dei modi è quello di distinguere i linguaggi managed da quelli unmanaged. I primi utilizzano, tra le altre cose, il meccanismo di garbage collection (o GC) per gestire automaticamente la memoria dinamica utilizzata dai nostri programmi, mentre i secondi lasciano il compito di gestire la memoria essenzialmente al programmatore. Tra i linguaggi managed ci sono per lo più linguaggi dinamici come Python, Ruby, JavaScript, ma anche linguaggi compilati come Java e Haskell. Il tipico linguaggio unmanaged è il C/C++. Oggi, moltissimi linguaggi sono managed, e la ragione sarà più evidente nel proseguimento del post.

La GC è stata inventata da una vecchia conoscenza di questo blog: da John McCarthy, si proprio lui, l’inventore del linguaggio LISP. L’idea è quella di liberare il programmatore dal difficile compito di dover gestire personalmente la memoria dinamica. In un linguaggio non managed, come il C ad esempio, ogni volta che faccio una p = malloc(nbytes) ottengo un puntatore a una nuova zona di memoria della dimensione richiesta che posso usare per memorizzare i miei dati; corrispondentemente, quando quella zona di memoria non mi serve più dovrò fare una free(p) per liberare la memoria e renderla di nuovo disponibile. Se mi scordo di fare la free(), e magari cancello il puntatore, la memoria resterà occupata, almeno fino a quando il programma resterà in esecuzione. Se il programma rimane in esecuzione per lungo tempo, è bene assicurarsi che ad ogni malloc() corrisponda sempre una free(), altrimenti la memoria occupata dal programma potrebbe crescere in maniera incontrollata.

Pensate ad esempio ad un server che accetta richieste di connessione; questo programma eseguirà per un tempo indeterminato, giorni, mesi, anni. Supponiamo che ad ogni richiesta venga allocata della memoria, ma al termine del completamente del servizio questa memoria non viene deallocata. Ad ogni richiesta, le dimensioni della memoria del programma continueranno a crescere mandando prima o poi in crash il sistema. Inoltre, la memoria si riempie di spazzatura, ovvero dati ormai inutili. Un tale tipo di errore viene chiamato memory leak, perché sembra che la memoria “goccioli via” come da un secchio bucato. Nel passato, il numero di errori che avevano a che fare con una cattiva gestione della memoria da parte del programma era piuttosto elevato, per cui si pensò di porre rimedio sottraendo il compito di gestire la memoria al programmatore.

I linguaggi managed permettono al programmatore di allocare memoria per i propri dati; evitano però che il programmatore debba liberare la memoria quando non è più necessaria. In pratica, permettono la malloc(), ma evitano di farci fare la free(). Un algoritmo, chiamato garbage collector periodicamente analizza la memoria del nostro programma per vedere se qualche zona di memoria precedentemente allocata può essere liberata. In pratica, raccoglie la spazzatura per noi. Per far questo, ad ogni zona di memoria viene associato un contatore dei riferimenti (reference counter) che conta quanti puntatori attivi riferiscono quella particolare zona di memoria. Ogni volta che la zona viene riferita da una nuova variabile puntatore, il contatore viene incrementato; ogni volta che un puntatore che riferisce quella zona viene cancellato, il contatore viene decrementato. Quando il contatore raggiunge il valore zero, vuol dire che nessun’altra parte del programma riferisce quella zona, che quindi può essere liberata. Non viene però liberata immediatamente (a causa di una serie di casi particolari, non è sempre così facile accorgersi del fatto che una zona di memoria può essere liberata!). In particolare, il GC esegue periodicamente due fasi: nella prima, chiamata mark, si marcano le zone da liberare; nella seconda, chiamata sweep, le zone marcate vengono effettivamente liberate.

La GC è stata sempre oggetto del contendere tra due diversi modi di vedere la programmazione: da una parte quelli che dicono che la GC è la panacea di tutti i mali; dall’altra quelli che dicono che la GC è inutilmente pesante e sostanzialmente inutile. Chi ha ragione? Il post che ho citato all’inizio ci da un punto di vista secondo me molto chiaro e rilevante.

VM

Per implementare la GC ci vuole una Virtual Machine. In pratica, bisogna essere in grado di tradurre un assegnamento tra puntatori in una operazione più complicata che coinvolge i reference counters. Inoltre, le variabili puntatori assumono uno status tutto particolare e differente dalle variabili int o float, perché il GC deve essere in grado di riconoscerle e seguire la “pista” alla ricerca di zone di memoria da liberare. Naturalmente, una VM significa overhead in più di traduzione. E’ vero che ci sono i Just in Time Compilers, che generano codice macchina a partire dal byte code; è anche vero che la VM si può evitare del tutto, come ad esempio fa Haskell con un run-time corposo. Quello che è importate sottolineare però è che per quanto si possa ottimizzare lo strato di VM o di run-time, resta il fatto che l’algoritmo di GC va implementato, e per quanto si possa fare in maniera efficiente, resta sempre un algoritmo piuttosto pesante.

Problemi con il GC

Io vedo due ordini di problemi con il GC. Il primo è strettamente tecnico: il GC ha bisogno di analizzare la memoria del nostro programma alla ricerca di zone di memoria da poter liberare. Mentre fa questo lavoro, la VM quasi sempre di blocca in attesa che il GC abbia finito. Questo perché il GC “legge” e “modifica” le strutture dati del gestore di memoria, e queste strutture dati sono costantemente utilizzate dalla VM sia per allocare nuova memoria, sia per aggiornare i reference counters. Non è sempre possibile permettere che il GC vada in parallelo con il resto del programma, per cui potrebbe accadere che la vostra applicazione abbia un piccolo “freeze” (cioè si blocchi completamente) per un po’ di tempo a causa del GC.

Quanto dura questo “freeze” dipende da un sacco di fattori, il più importante dei quali è l’uso che il programma fa della memoria. Se il programma alloca e libera continuamente tanti oggetti di piccola dimensione, il GC potrebbe prendere tantissimo tempo per eseguire, e il freze potrebbe durare anche qualche secondo. Un altro problema tecnico è capire quando il GC viene eseguito per liberare la memoria. All’inizio del post ho scritto che il GC viene eseguito periodicamente, ma con quale periodo? beh, dipende anche dall’utilizzo della memoria: se c’è poca memoria libera nel sistema, il GC verrà eseguito più frequentemente, nel tentativo di liberare memoria, e questo incrementerà l’overhead, cioè il numero e la durata dei “freeze”.

In ogni caso, quel che è peggio è che quasi nessun linguaggio managed permette al programmatore di controllare quando e quanto spesso il GC va in esecuzione. Quindi il programmatore ha poco controllo.

E veniamo con questo al secondo ordine di problemi del GC. Dato che la gestione della memoria è completamente demandata al sistema e nascosta al programmatore, il programmatore poco esperto tende a usare tanta memoria, creando e distruggendo oggetti inutilmente. Per esempio, in programmi Java scritti da programmatori poco esperti è comune leggere codice come il seguente:

String s = new String("Questa è una stringa");
String c = s.toUpperCase();

questa linea di codice crea un oggetto di tipo stringa per copia da una costante di tipo stringa. Quindi trasforma tutti i caratteri in maiuscolo.
Quello che il programmatore non sa, o dimentica spesso, è che la classe stringa è immutabile, ovvero non si può modificare un oggetto di classe stringa. Ad esempio, ogni volta che volete rimuovere un carattere da una String Java, viene creata un nuovo oggetto di tipo stringa che contiene tutti i caratteri di quello originale meno quello da rimuovere. Per cui, nella riga sopra ci sono 3 oggetti: la stringa originale, quella puntata da s che non può essere modificata, e quella puntata da c. Quella puntata da s è quindi un inutile duplicato, anzi più che inutile, dannoso, perché prima o poi il GC dovrà occuparsi anche di lui! Un modo efficiente di scrivere sarebbe semplicemente:

String s = "Questa è una stringa";
String c = s.toUpperCase();

In questo caso ci sono solo due oggetti, l’originale e quello puntato da c. Di esempi così se ne potrebbero fare molti. E’ così facile creare nuovi oggetti che il programmatore inesperto lo fa senza quasi accorgersene, incrementando notevolmente il lavoro del GC e quindi la lentezza del programma.

Quello che io considero un problema, però, è anche la forza dei linguaggi managed. Poiché non c’è da occuparsi della gestione della memoria, scrivere programmi funzionanti (anche se non molto efficienti) è più semplice, quindi aumenta la produttività del programmatore medio, si riduce il time-to-market, il costo di sviluppo, ecc. E finché la potenza e la memoria disponibile aumentavano, non c’erano problemi: più memoria avete sul vostro PC, meglio funzioneranno programmi scritti con linguaggi managed.

Come detto efficacemente da Miguel de Icaza,

This is a pretty accurate statement on the difference of the mainstream VMs for managed languages (.NET, Java and Javascript). Designers of managed languages have chosen the path of safety over performance for their designs.

Alcuni numeri

Nel post il buon Drew Crawford riporta alcune statistiche che non conoscevo, prese da questo paper. Riporto qui le frasi più importanti, come fa Drew:

In particular, when garbage collection has five times as much memory as required, its runtime performance matches or slightly exceeds that of explicit memory management. However, garbage collection’s performance degrades substantially when it must use smaller heaps. With three times as much memory, it runs 17% slower on average, and with twice as much memory, it runs 70% slower. Garbage collection also is more susceptible to paging when physical memory is scarce. In such conditions, all of the garbage collectors we examine here suffer order-of-magnitude performance penalties relative to explicit memory management. [...]
These graphs show that, for reasonable ranges of available memory (but not enough to hold the entire application), both explicit memory managers substantially outperform all of the garbage collectors. For instance, pseudoJBB running with 63MB of available memory and the Lea allocator completes in 25 seconds. With the same amount of available memory and using GenMS, it takes more than ten times longer to complete (255 seconds). We see similar trends across the benchmark suite. The most pronounced case is 213 javac: at 36MB with the Lea allocator, total execution time is 14 seconds, while with GenMS, total execution time is 211 seconds, over a 15-fold increase.

La conclusione quindi è che per stare sicuri di avere performance decenti con il GC, bisogna avere almeno 3-4 volte la memoria minima strettamente necessaria (cioè quella richiesta da un programma che usa allocazione esplicita della memoria). Su un PC prendetevi almeno 4Gb di RAM (meglio 8Gb) e andate tranquilli. Su un dispositivo mobile però non è così semplice.

Il problema delle webapp

Una webapp è una applicazione web, che di solito usa il cosidetto AJAX, ovvero una combinazione di programmi client e server, per fornire funzionalità dinamiche complesse. Per quanto riguarda la parte client, si usa JavaScript (o più propriamente ECMAScript), un linguaggio ormai popolarissimo proprio in ambito web. Si tratta di un linguaggio dinamico, managed, che usa il browser come VM. E naturalmente, usa un GC per gestire la memoria. Essendo un linguaggio vero e proprio, è possibile costruire applicazioni anche molto complesse, che però eseguiranno nel vostro browser.

Una web app particolarmente complicata, ad esempio, è Google Docs, che cerca di replicare un subset delle funzionalità di una suite office sul browser. Qualche anno fa, quando Google Docs fu proposto, ci fu una certa euforia fra i primi utilizzatori e fra gli stessi sviluppatori: era convinzione diffusa che si potesse interamente sostituire una suite come Microsoft Office con qualcosa come Google Docs basata interamente sul web. Se usate Google Docs sul vostro PC, e se questo è abbastanza carrozzato, non ci sono grandi problemi: non è velocissimo, ma è ancora usabile. Se invece qualcuno tentasse di usare Google Docs sul suo Tablet o sul cellulare, beh, i tempi di risposta andrebbero a farsi benedire. Ecco cosa dice personale di Google a proposito:

Complex web apps–the kind that Google specializes in–are struggling against the platform and working with a language that cannot be tooled and has inherent performance problems.

A dire la verità, anche web app molto più semplici soffrono notevolmente: per esempio provate ad accedere alla pagina di Dropbox tramite browser su tablet: dovrete attendere diversi secondi dopo ogni click. In effetti, molto meglio scaricarsi l’app di Dropbox e tentare di fare le proprie operazioni da lì (ma anche quella non è un fulmine).

Il problema è duplice. Il primo problema è di lentezza del processore. Una cosa è avere un bell’Intel i7 sul proprio desktop o portatile, una cosa completamente diversa è di avere un ARM progettato e realizzato con il risparmio energetico in mente. Inoltre, JavaScript è interpretato (o JIT-compilato), e le performance sono nettamente inferiori per questo motivo; Drew calcola che un programma JavaScript è da 5 a 10 volte più lento su un dispositivo mobile rispetto allo stesso programma su PC. Quello che richiede un secondo sul PC può richiedere 10 secondi sul mobile. Leggetevi attentamente la prima parte del post per una lunga analisi delle differenze di velocità.

A questo aggiungete il fatto che JavaScript usa il GC, e che la memoria di un dispositivo mobile è severamente limitata e avete il quadro completo della situazione.

Cosa succederà ora?

Eh, ad avere la palla di cristallo.

Ovviamente, credo non sia possibile continuare sulla strada di sviluppare Webapp sempre più complesse con l’idea che possano completamente sostituire programmi sviluppati nativimente per la piattaforma hardware. I programmi .exe, insomma, non spariranno tanto presto, anzi.

Per quanto riguarda Android, la strada scelta da Google di basarsi su Java è sembrata essere vincente all’inizio, perché ha permesso di sviluppare una grande quantità di app in breve tempo grazie alla maggiore produttività e sicurezza di un linguaggio managed come Java. Sul lungo termine però, il GC sta ponendo più problemi che soluzioni perché, come descrive Drew, i programmatori si vedono costretti ad aggirare il GC con trucchi e trucchetti per evitare la degradazione delle performance.

Si tornerà ad utilizzare il C++ anche sui dispositivi mobili? Credo piuttosto che l’hardware arriverà in soccorso del software ancora una volta… ma chi può saperlo?

Python e me

Nei giorni scorsi ero alle prese con la preparazione di uno dei nostri articoli di ricerca, in cui ad un certo punto abbiamo cercato di comparare tre strumenti software di analisi. Ognuno degli strumenti è in realtà un prodotto di ricerca, e ognuno è scritto con un linguaggio diverso: il nostro programma, RTSCAN, è scritto in C++; IMITATOR, un tool che hanno sviluppato qui in Francia, è scritto in OCaml; e infine MAST è uno strumento sviluppato all’Universidad de Cantabria in Spagna, ed è scritto in Ada. Ognuno produce risultati in maniera completamente diversa, e c’era quindi la necessità di elaborare questi dati in output in maniera uniforme, per poi produrre dei grafici “decenti”.

Avevamo quindi bisogno di un po’ di script per generare dei dati in input ai tre strumenti, lanciarli, collezionare e uniformare gli output. Abbiamo cominciato con un grande classico: un po’ di bash scripting. Però dopo un po’ ci siamo resi conto che non saremmo andati molto lontano. Un po’ perché io sono sempre stato lento con bash: non mi piace molto la sintassi, e quindi trovo difficile memorizzarla. Un po’ perché sarebbero stati necessari dei tool esterni non banali, e quindi alla fine il risultato non sarebbe stato molto portabile.

Per fortuna che c’è Python. Io non ho mai davvero imparato il Python, perché non ne ho mai avuto il tempo. Non ho tempo per mettermi davanti a un libro o a un corso (anche di quelli accellerati) per imparare l’ABC di un linguaggio. E soprattutto, non ho tempo per imparare a usare le varie librerie (e ce n’è davvero tante). Ma per fortuna, Python ha due caratteristiche peculiari:

1) E’ facile cominciare. Cioè, in realtà all’inizio potete considerarlo tranquillamente come se fosse un linguaggio di scripting. Non c’è bisogno di astruse direttive, di dichiarare variabili, di scrivere funzioni, non c’è bisogno neanche di un main. Si parte a scrivere codice come viene viene, ed è molto probabile che funzioni subito come avevamo pensato.

2) In linea c’è tutto. Qualunque cosa tu voglia fare, basta googlare, e finisci o sul manuale di Python in linea, o su stackoverflow, dove hanno sempre la ricetta pronta per te.

Naturalmente, bisogna conoscere un minimo le basi della programmazione. Ma dal pensiero alla realizzazione passa davvero molto poco.

E passiamo a scrivere brevemente il nostro lavoro. Come prima cosa, avevamo bisogno di specificare il sistema da far analizzare ai tre strumenti. Per semplicità ed immediatezza, abbiamo scelto il formato JSON, che adesso va per la maggiore.  E naturalmente Python ha una libreria per leggere e interpretare un file JSON con sole due funzioni, e il risultato è una lista di dizionari.

Poi, abbiamo scritto 3 funzioni per visitare la lista di dizionari e produrre tre file di input per i tre strumenti. Poi abbiamo scritto 3 funzioni per lanciare i 3 strumenti. Infine, abbiamo fatto post-processing sugli output. Tutto questo in una mezza giornata. Un altro paio di giornate è passato a mettere a posto le cose (perché c’è sempre qualcosa da sistemare, naturalmente) e a cercare di far produrre dei grafici decenti a gnuplot (e ci siamo riusciti solo parzialmente).

Ma la cosa bella di Python è che non si limita ad essere un semplice linguaggio di scripting, ma ha tutte le potenzialità di un vero linguaggio di programmazione. Costrutti evoluti, Object Orientation, ma anche un po di functional programming. C’è la tipizzazione a run-time (il cosidetto duck-typing), il garbage collector. Utilizzando uno stile di programmazione pulito, Python consente di scrivere programmi molto eleganti e “belli”, senza grosso sforzo.

E’ insomma un linguaggio scalabile: si può andare facilmente dal piccolo script di poche linee, al programma mediamente complesso senza grossi problemi. Inoltre ti consente di fare fast prototyping: se hai un’idea, la butti giù e la testi in pochi minuti e con poco sforzo, e la puoi tenere lì in caldo pronto a riprenderla e ad evolverla in qualcosa di più complesso più avanti.

Ha dei difetti? Non sono sicurissimo di quanto possa scalare Python. Se il progetto diventa veramente grande, e con tanti programmatori, non sono sicuro che Python basti. Per esempio, il codice Python può diventare orribile se scritto male e senza giudizio; il fatto che si usi duck-typing richiede una certa dose di coordinazione sulle interfacce quando si lavora in tanti; e quando un progetto è grande, non è detto che tutti i programmatori siano allo stesso livello.

Insomma, mi sa che mi tocca studiarmelo meglio. Adesso che l’ho provato in un caso quasi reale, penso che comincerò ad utilizzarlo sempre più spesso!

Ottimizzazioni a volte sorprendenti

Nel post precedente riguardante newLISP ho inserito uno scriptino di una dozzina di righe per far vedere quando sia bello ed efficiente newLISP. Ebbene ho barato, solo un pochino (quello che da noi si direbbe na frisa o ‘n cicinin). Ma forse è il caso di raccontare tutta la storia, che ha una morale (laicista), quindi istruttiva.

La prima versione dello script usava (append-file)

syntax: (append-file str-filename str-buffer)
Works similarly to write-file, but the content in str-buffer is appended if the file in str-filename exists. If the file does not exist, it is created (in this case, append-file works identically to write-file). This function returns the number of bytes written.

Questo è lo script

;; versione lenta come raccontato nel post
(set 'k 1000)
(set 'm (* k k))
(set 'tstart (time-of-day))
(append-file "primes" (string 2 "\n"))
(dolist (n (sequence 3 (* 10 m) 2))
    (if (= (length (factor n)) 1)
        (append-file "primes" (string n "\n")))
)
(println (- (time-of-day) tstart))
(exit)

Sul mio ‘puter, con processore Intel Core Duo @ 2.4 GHz, 2 GB di RAM e Ubuntu 10.10 è tutto OK, l’esecuzione richiede circa 42-44 secondi (il dato che compare alla fine dell’esecuzione, viene da (time-of-day) che restituisce millisecondi)

A prima vista esaminando il grafico Cronologia CPU sembra che newLISP sia davvero fatto bene e riesca a utilizzare tutte le risorse disponibili: non è vero. La riga rossa è newlisp, quella arancione è nautilus. Ecco! (append-file) non richiede che il file sia aperto prima con (open) e chiuso alla fine con (close) ma ogni volta che viene chiamata è lei stessa che lo apre e chiude. Se c’è una sola CPU ci dev’essere uno swap continuo e le prestazioni decadono. Di molto.

Sul PC con Windows che uso di solito (XP su AMD Sempron @ 1.67 GHz, 448 MB di RAM) i tempi di esecuzione per la versione con (write-line) sono di 97-103 secondi, con (append-file) di 6440-6840 secondi (1h 38m e 1h 54m), cioè 86-87 volte peggiori!

CPU occupata con la versione (write-line)

 

CPU occupata con la versione (append-file)

 

distribuzione della CPU tra i processi durante l'esecuzione dello script

Ah! dimenticavo: con Windows dovete mettere in conto l’antivirus, che serve (eccome!) ma mangia.

L’esecuzione su un portatile con Vista su Acer Extensa Celeron 560 @ 2.13 MHz, 1 GB di RAM ha dato grafici simili (a proposito adesso Task Manager si chiama Gestione Attività Windows). La versione veloce ha richiesto 70-71 secondi, quella lenta l’ho interrotta.

versione (write-line)

 

versione (append-file)

Conclusione

Ed ecco la morale della storiella: mai fermarsi alla prima versione, se qualcosa non va come ci aspettiamo, prima di dare la colpa al programma, al computer o al mondo, verificare. E leggere tutto il manuale, fino in fondo, ma questo mi sembra di averlo già detto ;-)

Programmare o progettare?

Ultimamente scrivo molto poco sui miei blog perché sto preparando le slides e gli appunti per i due corsi che sto tenendo in questo momento, ed è una cosa che mi prende molto tempo. Per uno di questi corsi in particolare sto preparando tutto il materiale da zero, perché è la prima volta che lo tengo.

Il corso si intitola Object Oriented Software Design, e lo scopo del corso è di formare progettisti di software. Si parte da una introduzione al linguaggio Java, per passare poi al C++ in maniera piuttosto approfondita.  Poi si studiano i cosidetti Design Patterns; poi un po’ di ingegneria del software, elementi di testing, la progettazione agile. In tutto il corso consisterà di 12 crediti, per più di 100 ore tra lezioni frontali ed esercitazioni.

Fino ad adesso ho fatto un po’ di lezioni e sto per concludere la parte su Java. Conto di finire con Java in altre 8-10 ore massimo, dopodiché mi dedicherò al C++.

Dovete sapere che io mi faccio un punto d’onore di rilasciare liberamente tutte le mie slides. E quindi, mi sembra giusto segnalarle anche su questo blog: se volete saperne di più, andate su mio sito web alla pagina del corso. Le slides delle lezioni dalle 03 alle 05 sono prese abbastanza pedissequamente dal libro “Thinking in Java” third edition, di Bruce Eckel (scaricabile liberamente dal sito); dalla lezione 07 in poi, invece, mi distacco abbastanza. In cambio di questa mia liberalità, chiedo solo di segnalarmi errori, omissioni, cose da migliorare, da togliere, da aggiungere. Ogni commento è il benvenuto!

Tra poco rilascerò una lezione su Run-Time Type Identification, Anonymous Inner Classes, Binary Tree. E naturalmente, se vi interessa, andate a guardare ogni tanto e ci troverete le nuove slides man mano che le completo.

E veniamo al titolo del post: che differenza c’è tra programmare e progettare? E, ha senso parlare di progettazione del software? Ovviamente la risposta alla seconda domanda è sì, altrimenti non avrei intitolato così il corso. La progettazione si rende necessaria per grandi programmi. Finché si fanno piccoli programmini o utility, si può anche lavorare da soli e fare un po’ gli artisti (o se volete gli artigiani). Si dice spesso che programmare è un arte; perché l’atto di passare dall’idea alla sua realizzazione tramite un algoritmo è un atto quasi artistico e misterioso e poco compreso del nostro cervello. E va tutto bene finché appunto ci limitiamo a risolvere un problema ben limitato e definito (ad esempio ordinare un insieme di elementi, effettuare un ricerca in un testo, etc.).

Quando però la complessità di un programma supera un certo livello, si rende necessario pianificare attentamente lo sviluppo e dividerlo tra più team di programmatori. Si passa a un livello industriale: bisogna elencare i requisiti, dividere il probelma in sottopobremi più piccoli, dividere il carico di lavoro tra gruppi di programmatori, pianificare il test di unità, il test di integrazione, etc. C’è poco spazio per l’arte qui: si passa dall’artigianato alla produzione industriale.

E veniamo alla prima domanda: la differenza fra il progettista e il programmatore è un po la stessa che c’è fra l’ingegnere e il geometra. Il primo costruisce palazzi, grattacieli, ponti, il secondo ti alza un muro o ti mette la veranda sulla terrazza.

La mia impressione è che in molte università in Italia i docenti insegnino al massimo a fare i programmatori. Ma quasi nessuno insegna a fare il progettista. Ci sono corsi di Ingegneria del Software, ma sono troppo spesso un’enunciazione di tecniche senza applicazioni pratiche. E invece, trovo difficile che si possa imparare a progettare il software senza un minimo di pratica.  La mia impressione (ma spero di essere smentito da qualche collega) è che in Italia siamo rimasti indietro anche su questo. Nel mio piccolo, spero di colmare almeno parzialmente questo gap. Almeno ci tento.

Impacchettare

Potrebbe esservi capitato qualche volta di dover caricare l’auto di valige, pacchi e pacchettini. E  se avete una moglie come la mia, non vi bastarebbe la monovolume più capiente sul mercato! Però, bisogna anche essere bravi ad impacchettare le cose per bene (cosa che mi toccherà fare tra un paio di giorni). E quasi mai riesce alla prima volta vero? Di solito si comincia a mettere la roba, e dopo un po’ ci si accorge che così non va. E allora bisogna tirare tutto fuori e ricominciare da capo con la santa pazienza.

In effetti, non è (sempre) colpa vostra: i problemi di impacchettamente sono tra i più “difficili” problemi matematico/informatici, fanno infatti parte della classe dei problemi NP-hard.

scatole...

Cominciamo con il più semplice, chiamato Bin-packing. In questo problema avete un certo numero di oggetti di dimensione varia, da mettere dentro delle scatole tutte uguali con una certa capacità. L’obiettivo è di utilizzare il minor numero di scatole. Per semplificare, consideriamo il problema unidimensionale: gli oggetti sono parallelepipedi tutti con la stessa base e con altezza varia, e gli scatoloni hanno la stessa base degli oggetti (che quindi si possono solo impilare uno sul’altro). Ad esempio, consideriamo il problema di avere scatole di altezza pari a 30 cm, e 5 oggetti di altezza pari a 5cm, 10 cm, 12 cm, 13 cm, 15 cm.

Se ci pensate un attimo, troverete che vi bastano 2 scatole: la prima contenente l’oggetto da 15 cm e quello da 13 cm; la seconda contiene tutti gli altri. Poiché gli oggetti non entrano evidentemente in una sola scatola, abbiamo trovato la soluzione minima.

Perché dico che questo problema è difficile? L’abbiamo risolto a mente in pochi secondi!

In informatica, i problemi “difficili” non sono quelli impossibili da risolvere, ma piuttosto quelli che scalano male con la dimensione dell’input. La dimensione dell’input al problema in questo caso è dato dal numero di oggetti da impacchettare. In un problema difficile, il tempo per risolverlo aumenta esponenzialmente con la dimensione dell’input.

Purtroppo il problema del bin-packing è un problema difficile perché per trovare la soluzione ottima dobbiamo per forza analizzare tutte le possibilità. Per essere più precisi: ad oggi non si conosce alcun algoritmo furbo per questo problema, cioè gli unici algoritmi ottimi conosciuti si limitano ad enumerare tutte le combinazioni possibili. E purtroppo, il numero di combinazioni è esponenziale nel numero degli oggetti.

Per capirlo considerate questo semplice ragionamento: supponiamo di avere 20 oggetti e al massimo 10 scatole. Numeriamo le scatole da 0 a 9. A questo punto, ogni possibile combinazione può essere identificata da un numero a 20 cifre: ogni posizione corrisponde a un oggetto, e il suo valore (da 0 a 9) indicherà in quale pacchetto infiliamo l’oggetto in questione. E’ chiaro che il numero di combinazioni corrisponderà a 1.000.000.000.000.000.000.000 (ovvero 10^{21}). Non male, no?

E stiamo parlando del problema unidimensionale. Nella pratica, spesso si ha a che fare con problemi in 3D (quello del bagagliaio dell’automobile ad esempio) o solo in 2D (il piazzamento di circuiti su un chip). Non è che siano più difficili in senso informatico, intendiamoci: anche in quel caso bisogna analizzare tutte le combinazioni di oggetti.

Panico? Ok, panico!

Cioè, aspettate un attimo, spesso non è che ci interessi proprio la soluzione ottimale, anche una abbastanza buona può andare bene, no? Dai, accontentiamoci!

Per questo si usano delle euristiche, ovvero degli algoritmi semplici che magari non ci danno proprio la soluzione ottima, ma per lo meno ci danno una soluzione accettabilmente buona. Per il bin-packing ci sono i seguenti:

  • First fit decreasing: in pratica, ordiniamo gli oggetti in ordine di altezza decrescente, e poi li mettiamo l’uno dopo l’altro nel primo scatolone in cui entrano. E se un oggetto non entra in nessuno di quelli già incignati, ne prendiamo uno nuovo.
  • Best fit decreasing: ordiniamo come prima gli oggetti in ordine di altezza decrescente, e poi mettiamo ogni oggetto nella scatola in cui entra meglio (ovvero quella in cui lascia meno spazio libero). Come prima, se necessario prendiamo uno scatolone nuovo.

Questi algoritmi sono nettamente più semplici di quelli di enumerazione. Innanzitutto, ordinare n elementi in ordine descente si fa in un tempo proporzionale a n log n. Per esempio con 20 oggetti, l’ordinamento si fa più o meno in 24-25 passi. Poi l’inserimento nello scatolone di ogni oggetto si fa in tempo pari a log n, e ci sono n oggetti, quindi anche qui n log n. In informatica teorica, si usa scrivere che la complessità di questi algoritmi è O(n \log{n}). Quindi, con una cinquantina di passi al più abbiamo risolto il problema contro il numero improbabile di cifre di prima.

E infine, quanto sono “buoni” questi algoritmi rispetto all’algoritmo ottimo? Se chiamiamo con OPT il numero minimo di scatole necessarie (calcolate dall’algoritmo ottimo), è stato dimostrato che First-Fit decreasing ne richiede al massimo 11/9 OPT + 6/9. Che non è poi tanto male!!

Perché mi interesso di bin-packing? Perché mi capita tra i piedi piuttosto spesso… infatti, sappiate che la mia specializzazione è nella schedulazione dei processi nei sistemi operativi, e in quest’ambito il bin-packing salta fuori piuttosto spesso.

E adesso a voi: se volete esercitarvi nella programmazione, scrivete una semplice funzioncina che implementi uno dei due algoritmi di cui sopra, per esempio in Python! perché no? o in qualunque altro linguaggio di vostro gradimento, inclusi l’italiano con tutti i suoi dialetti! Qui ad esempio ne trovate uno in Visual Basic (credo). E qui un’intera serie in Haskell dal mio amico Bjorn Brandeburg.

Buona programmazione!

Il problema della fattorizzazione

NP

Hronir ci fa un piacere ricordandoci in un paio di ottimi post che il problema della fattorizzazione dei numeri non è necessariamente un problema NP (non polinomiale). Da leggere attentamente!

Il fatto è che molte persone, anche molti ricercatori in matematica, informatica, etc. danno per scontato che:

  1. La fattorizzazione sia un problema NP-completo, e quindi gli algoritmi di crittografia, basati sul problema della fattorizzazione, siano intrinsicamente sicuri.
  2. I calcolatori quantistici renderanno i problemi NP-hard risolvibili in tempo polinomiale, e quindi renderanno inutili gli attuali algoritmi di crittografia.

In quanto al primo assunto, in realtà non si sa quale sia la complessità del problema di fattorizzazione. Hronir da degli ottimi link, vi consiglio di seguirli. Il sospetto è che in realtà non sia un problema NP-completo, ma un problema un po’ più semplice (magari non proprio polinomiale, ma insomma). In quanto al secondo assunto, Hronir ci dice che non esiste (ad oggi) alcun algoritmo quantistico in grado di risolvere un problema NP-hard.

Non ci avete capito una mazza? E’ il momento di iscriversi a un corso di informatica! :)

Altri link utili:

Iscriviti

Ricevi al tuo indirizzo email tutti i nuovi post del sito.

Unisciti agli altri 77 follower