pensiero-computazionale-algoritmi-coding-python

Pubblichiamo in questo post l’intervista a Paolo Ferragina e Fabrizio Luccio autori del libro “Il pensiero computazionale. Dagli algoritmi al coding” acquistabile, per esempio, qui e qui.

Paolo Ferragina è professore ordinario di Informatica presso l’Università di Pisa. Fabrizio Luccio è professore emerito di Informatica presso la stessa università

 

 


 

Parte 1:

– Come è nata l’idea di scrivere questo libro sul coding?

PF: L’idea è stata quella di introdurre il “Pensiero Computazionale” — inteso come  pensiero-computazionaleattitudine mentale a descrivere, analizzare e risolvere problemi (problem solving) — attraverso un approccio progettuale e scientifico che prescindesse dall’uso del computer (coding) e quindi fosse proprio delle discipline scientifiche. Per raggiungere questo obiettivo abbiamo adottato nel libro un linguaggio accessibile a chiunque abbia cognizioni matematiche elementari per introdurre i lettori, anche senza pre-requisiti informatici, alla comprensione e progettazione di algoritmi che risolvono problemi provenienti da diversi campi rilevanti della scienza e della tecnologia, quali Crittografia, Motori di Ricerca, Finanza, Compressione Dati, ecc.. Per soddisfare comunque la curiosità di lettori appassionati di coding, il libro dispone anche di un sito Web creato al proposito (http://github.com/IlPensieroComputazionale/DagliAlgoritmiAlCoding/ ) che contiene la realizzazione in linguaggio Python degli algoritmi descritti nel libro e fornisce ogni mezzo necessario alla loro esecuzione e alla eventuale costruzione di nuovi esempi

 

– A che tipologia di lettori pensate sia diretto il vostro libro?

PF: Il lettore che abbiamo in mente è il docente della scuola secondaria di secondo grado, i suoi studenti, così come gli universitari di discipline non necessariamentecomputational-thinking scientifico-tecnologiche che hanno esami di “programmazione” nei primi anni del loro corso di laurea. Come già accennato, il testo si rivolge a lettori che non dispongono di conoscenze di coding ma hanno, sicuramente, cognizioni matematiche elementari. Il testo è stato recentemente tradotto in inglese per Springer (disponibile qui), garantendone così una diffusione internazionale. Osserviamo che il testo in inglese potrebbe essere adottato nelle scuole italiane che desiderino coniugare l’uso della lingua inglese con l’insegnamento di materie scientifico-tecnologiche.

– Nell’introduzione al testo parlate di computazione a partire da un papiro egizio del 1650 a.C e spiegate in modo molto chiaro cosa si intende per “pensiero computazionale”. Potreste spiegarlo ai nostri lettori?

Perché, inoltre la computazione ha assunto un ruolo fondamentale nel mondo?

FL:  Lo scopo, per citare il papiro di Ahmes, era quello di mettere in luce che il concetto ht_prhinddi algoritmo è antichissimo e largamente diffuso; è stato formalizzato per problemi di matematica, potremmo riferirci a quelle babilonese o vedica per la risoluzione di semplici equazioni o per il calcolo di radici quadrate, ma si ritrova ovunque pur senza conoscerne una descrizione precisa. Per esempio, l’età del bronzo nasce oltre cinque millenni or sono perché l’uomo sviluppa metodi per estrarre minerali di rame e stagno e fonderli assieme, e ciò può essere avvenuto solo seguendo precise sequenze di azioni esattamente specificate che possiamo legittimamente chiamare algoritmi. Dunque, la “computazione” se opportunamente interpretata ha avuto sempre un ruolo fondamentale.

Al concetto di algoritmo si lega quello di coding, cioè della realizzazione di un algoritmo in un ambiente applicativo specifico. Oggi fare coding è essenzialmente trasformare le azioni richieste da un algoritmo in un programma eseguibile da una macchina (tipicamente un calcolatore). Ma per il coding della moltiplicazione di Ahmes si doveva usare un abaco, e per inciso è questo a mio parere il motivo per cui, come si vede nel testo, l’algoritmo è basato su raddoppiamenti e dimezzamenti di numeri facili da ottenere su un abaco. Il coding per il bronzo consisteva nelle operazioni di estrazione dei minerali, di costruzione di forni, di getto del metallo fuso, eccetera.

Il concetto di “pensiero computazionale” è invece figlio dei tempi presenti. La popolarità e l’obiettiva importanza del termine si devono anzitutto a uno straordinario breve articolo della Professoressa Jeanette M. Wing che raccomando a chiunque sia interessato a un serio approfondimento (si veda: https://www.cs.cmu.edu/~15110-s13/Wing06-ct.pdf). In estrema sintesi è l’attitudine mentale a descrivere, analizzare e risolvere problemi progettando algoritmi che possono essere sperimentati su un calcolatore.

– Il secondo capitolo è dedicato a trattare i termini algoritmo e coding. Qual è il legame fra questi due termini? 

FL Come già accennato, i due termini indicano due fasi successive ma strettamente correlate del procedimento di risoluzione di un problema mediante un calcolatore e sono i due concetti di base del pensiero computazionale. Con le parole del libro, algoritmo e coding “indicano come organizzare e descrivere una serie di azioni per raggiungere un risultato desiderato: l’algoritmo costituisce la fase di concezione e valutazione della strategia su cui costruire le singole mosse, il coding ne riflette la fase operativa”. Questi concetti diverranno man mano più chiari nel seguito del discorso.

– Gli esempi riportati nel testo sono tutti scritti usando lo pseudocodice. Potreste spiegare cosa è ai nostri lettori e perché avete fatto questa scelta di usarlo?

– Il libro è affiancato ad un web dove sono inseriti tutti i codici presentati scritti in Python. Come mai la scelta di questo linguaggio? 

FL: Il coding è di fatto realizzato impiegando linguaggi di programmazione che i codicecalcolatori possono interpretare e trasformare in specifiche azioni di calcolo. Questi linguaggi, ad eccezione di alcuni di essi concepiti per compiti particolari, hanno oggi una struttura largamente condivisa e le principali “istruzioni” sono equivalenti tra loro. Lo “pseudocodice”, oggi largamente utilizzato in testi a carattere sia didattico che scientifico, è un linguaggio di riferimento che include tutte le caratteristiche dei linguaggi di programmazione senza coincidere con alcuno di essi, tale che i suoi programmi si prestano in modo immediato e essere trasformati in qualsiasi linguaggio eseguibile.

Così mentre gli algoritmi contenuti nel libro sono presentati in pseudocodice, il sito Web di accompagnamento contiene gli stessi programmi redatti in linguaggio Python che è oggi molto diffuso. Voglio aggiungere che il sito Web è stato progettato con attenzione per essere fruibile con grande semplicità anche da persone digiune di programmazione, che hanno così la possibilità di esaminare e mettere in esecuzione i programmi ivi contenuti, e magari costruirne di propri: il che può dare molta soddisfazione a chi non l’avesse mai provato in precedenza.

– Nel primo capitolo parlate usando un bellissimo esempio di due concetti essenziali nella costruzione di un algoritmo: limite superiore e inferiore. Potreste introdurli ai nostri lettori?

FL: Ho insegnato all’università teoria degli algoritmi (oggi si chiama “algoritmica”) per molti anni, sin da quando il termine era dissueto per i non specialisti e completamente ignoto al largo pubblico. E ho sempre aperto i miei corsi con l’esempio che citate, tratto da un problema classico di teoria dell’informazione. Infatti considero che il concetto di limiti alle risorse di calcolo, il tempo nel caso presente, sia il primo da considerare quando si deve risolvere un problema.

Al di là dell’esempio specifico, nell’ipotesi che il numero di operazioni elementari richieste da un algoritmo sia di primaria importanza per un’efficiente risoluzione del problema, e quindi il tempo di esecuzione del programma corrispondente lo sia nel coding, è opportuno studiare preliminarmente il minimo numero di operazioni che qualsiasi algoritmo risolutivo dovrà necessariamente eseguire (limite inferiore), e il numero di operazioni che un determinato algoritmo effettivamente richiede (limite superiore), considerando che diversi algoritmi possono in genere risolvere lo stesso problema e se ne cerca quindi il più efficiente.

Ne risulta che se il limite superiore associato a un certo algoritmo coincide con il limite inferiore per il problema trattato, tale algoritmo è “ottimo” e non è necessario cercarne di migliori. Come si può immaginare la cosa non è così semplice e un suo studio può avvenire solo seguendo i ragionamenti via via sviluppati per diversi problemi.

– Nel capitolo 3 intitolato “Torneo” partite dell’esempio dell’impostazione di un torneo a sedici squadre che ha come scopo, tramite scontri ad eliminazione diretta, di individuare la squadra più forte. Che legame c’è con la ricerca del massimo numero all’interno di una lista? 

FL: Assegnando a ogni squadra un numero intero che ne indichi la bravura e stabilendo che in un incontro diretto vince la squadra cui è assegnato il numero più alto, stabilire chi è il vincitore del torneo equivale a individuare il massimo in una lista di numeri. Se si desidera che questo avvenga eseguendo il minimo numero di partite il problema diviene quello di determinare quanti confronti tra coppie di numeri si devono eseguire nella lista per determinare il massimo, in funzione dell’algoritmo scelto. Così si vedrà che se le squadre sono n occorrono necessariamente almeno n-1 incontri con qualsiasi algoritmo (limite inferiore), e l’algoritmo classico del torneo è ottimo perché ne esegue esattamente n-1 (limite superiore).

Naturalmente le cose non sono così semplici perché una squadra cui è teoricamente assegnato un numero superiore potrebbe perdere per varie circostanze con una che ha un numero inferiore. Né, come si dimostra nel libro, è giusto assegnare la posizione di vice-campione alla squadra che raggiunge e perde la finale perché ha circa il 50% di probabilità di non meritare quella posizione.

– Nel capitolo 4 si parla di algoritmi cubici, quadratici e lineari. In che cosa consistono questi differenti algoritmi e che cosa è una trappola computazionale?

PF: Come già specificato precedentemente, il numero di operazioni che un determinato algoritmo richiede per risolvere un problema è un’indicazione abbastanza accurata della sua efficienza in tempo, quando questo algoritmo viene eseguito da un calcolatore. Questo numero di operazioni è chiaramente funzione del numero di dati che l’algoritmo deve processare: ci aspettiamo che maggiore è il numero di dati in input all’algoritmo, maggiore è il numero di passi eseguiti da esso per risoluzione del problema cui questi dati si riferiscono. La funzione che lega il numero dei dati in input con il numero di passi eseguiti dall’algoritmo su di essi prende il nome di complessità in tempo dell’algoritmo proposto. Tanto più lentamente cresce questa funzione con la dimensione dell’input, quanto più l’algoritmo è veloce nella pratica, e quindi considerato “buono”. Nel libro si propone un semplice esempio di problema tratto dal mondo della finanza che ammette tre interessanti algoritmi di risoluzione aventi una complessità in tempo che cresce in modo lineare, quadratico e cubico con il numero di dati in input. L’algoritmo cubico sarà in grado di processare in un tempo ragionevole molti meno dati di quello lineare. Ancora più interessante è l’osservazione, riportata in modo matematicamente preciso nel libro, sull’impatto che l’uso di un calcolatore più potente possa avere sui tre algoritmi: evidenzieremo che l’acquisto di nuovi calcolatori è pressoché inutile se disponiamo di algoritmi inefficienti, come quello cubico.

– Il quinto capitolo è incentrato sul “problema dell’ordinamento” e analizza alcuni algoritmi per ordinare dati di qualunque tipo.

Potreste spiegare ai nostri lettori uno di questi?

PF: Il problema consiste nell’ordinare in modo crescente (o decrescente) una lista di numeri eseguendo il minimo numero di operazioni possibile. Questo problema ricorre in molte applicazioni, soprattutto come primo passo per l’esecuzione di operazioni più sofisticate. Si pensi per esempio alla necessità di trovare in un archivio le persone che hanno un’età compresa in un intervallo dato, sarebbe facile trovarle se fossero ordinate per età. Oppure si consideri il caso di una lista di studenti e si voglia stabilire se esistono studenti che hanno, per errore, uno stesso numero di matricola: ebbene, ordinandoli per matricola verificheremmo facilmente se una di queste si ripete. La letteratura informatica è ricca di algoritmi per l’ordinamento, nel libro ne descriviamo solo alcuni che comunque permettono di offrire al lettore un quadro dell’efficienza di varie soluzioni (il limite superiore) e della complessità del problema (il limite inferiore). L’algoritmo che tutti usiamo quando giochiamo a carte e consiste nell’esaminare le carte in mano una alla volta collocandole nella posizione corretta tra quelle già viste, è provatamente inefficiente, ma non ce ne accorgiamo perché le carte sono poche. Il libro discute vari algoritmi solitamente utilizzati per ordinare le carte da gioco, e ne commenta la complessità in tempo; per poi proporre un algoritmo “ottimo” ossia il migliore possibile nel numero di confronti eseguiti tra carte per ordinarle. Prende il nome di MergeSort e risulta abbastanza contro-intuitivo. Opera fondendo a due a due mazzi di carte precedentemente ordinate, attraverso una loro scansione, e partendo da mazzi che consistono di una sola carta e quindi sono sicuramente ordinati. La fusione a due a due (merge, in inglese) di mazzi ordinati è semplice da eseguire, basta confrontare le prime carte di ogni mazzo e “scartare” quella più piccola: le carte scartate saranno ordinate e formeranno un nuovo mazzo ordinato di lunghezza doppia rispetto ai due fusi che lo hanno originato.

– In che modo l’avvento dei Big Data comporta una modifica dei modelli di calcolo? 

PF: Come già detto il libro discute l’efficienza degli algoritmi concentrandosi sul numero big-datadi operazioni che questi eseguono per risolvere un determinato problema. Questa misura descrive abbastanza bene il tempo di calcolo dell’algoritmo, se questo fosse eseguito su un calcolatore su pochi dati. Ma se il numero di dati in input cresce a dismisura (i cosiddetti Big Data) allora questi devono essere memorizzati su vari livelli di memoria di un calcolatore moderno: cache, DRAM, dischi meccanici (hard disk) e allo stato solido (SSD), cartelle sul cloud, nastri. In questo caso il costo in tempo di ogni singola operazione non si può considerare costante e sempre uguale, ma dispende fortemente dal tipo di memoria che contiene i dati coinvolti in questa operazione. Infatti se i dati sono contenuti in cache, pochi nanosecondi saranno sufficienti per la sua esecuzione; se i dati sono contenuti su un hard disk, allora sono necessari alcuni millisecondi. Si tratta di una differenza in tempo dell’ordine di un milione, e quindi non trascurabile se si vogliono progettare algoritmi efficienti. Quando si ha a che fare con Big Data è cruciale utilizzare modelli di calcolo che tengano conto delle gerarchie di memoria e quindi consentano di valutare accuratamente come la disposizione dei dati impatta sull’efficienza degli algoritmi.

– Il capitolo settimo ha come obiettivo quello di analizzare classi di problemi “facili” e “difficili” spiegando ai lettori la differenza fra problemi di classe N, NP e NP-completi.

Pur essendo l’argomento complesso e invitando i nostri lettori alla lettura di questo capitolo, potreste provare a dare l’idea ai nostri lettori?

FL: Questo campo di studio è apertissimo a considerazioni estremamente complesse. Inpvsnp particolare, stabilire se le classi P e NP coincidono tra loro è stato dichiarato uno dei dieci problemi aperti della matematica di questo secolo e la sua soluzione comporta un premio di un milione di dollari. Cecherò di introdurre l’argomento in un modo anticonvenzionale che non troverete nel libro, riferendomi all’età del bronzo di cui abbiamo già parlato (nihil sub sole novum, ma con una certa ironia).

È lecito immaginare che la definizione del processo di costruzione di oggetti di bronzo abbia richiesto un tempo estremamente lungo per mancanza di cognizioni in materia. Tentativi, casi fortuiti, confronti tra esperienze in campi diversi portarono finalmente a definire un protocollo di esecuzione che poteva poi essere ripetuto ogni volta fosse richiesto. In sostanza lo sforzo per trovare una soluzione deve esser stato enorme ma, una volta stabilito, la replicazione del processo era relativamente semplice. In termini strettamente matematici, in mancanza di una strategia appropriata un problema potrebbe essere risolto eseguendo un numero enorme di prove fino a trovare una soluzione possibile, ma una volta nota questa soluzione potrebbe essere semplice verificarne la correttezza.

Questo è quanto avviene in queste classi di problemi. Nella classe P, quella dei problemi “facili”, se i dati del problema sono n occorre un numero polinomiale s di operazioni per risolverli, ovvero s = nk ove k è una costante (comunemente k è un piccolo intero come abbiamo visto nel capitolo 4). Vi sono però problemi, anche molto importanti nella pratica, che siamo capaci di risolvere solo con un numero esponenziale di operazioni, ovvero s = kn, anche se poi il controllo che la soluzione sia corretta richiede tempo polinomiale. E si noti che kn diviene enormemente maggiore di nk al crescrere di n. Questi sono i problemi NP-completi, ovvero i “più difficili” nella classe NP. Intuitivamente la loro soluzione avviene “provando tutti i casi possibili e verificandone l’effetto”.

– Il successivo capitolo è dedicato ai motori di ricerca. Nel testo date una definizione molto chiara di PageRank a partire da quella degli hyperlink. Perché l’introduzione dell’algoritmo del PageRank fece la differenza?

PF: Il biennio 1997-1998 segna l’inizio di una nuova generazione di motori di ricerca che coincide con la nascita di Google e del suo famoso algoritmo PageRank. Il PageRank fornisce una misura di rilevanza della pagina P all’interno della rete del Web in funzione del numero e della rilevanza delle pagine che puntano a P. Si tratta quindi di una definizione ricorsiva, basata sulla struttura del Web come rete di interconnessioni tra pagine, sorprendentemente ben fondata dal punto di vista matematico e ben più complessa del semplice conteggio degli hyperlink che puntano a quella pagina. Una pagina P per essere rilevante deve essere puntata da molte pagine altrettanto rilevanti. Sin dal suo debutto il PageRank si è attestato come una delle misure più importanti e tuttora utilizzate nel Web, nei Social Network e nelle reti in genere, per stabilire la rilevanza di un «nodo» presente in esse: sia esso un utente, un ristorante, un tweet, o per l’appunto una pagina Web. Il concetto si è evoluto nel corso degli anni, ma la sua definizione e proprietà originarie sono ancora valide.

Il PageRank venne usato da Google in combinazione con altre misure classiche di rilevanza basate sul contenuto testuale delle pagine, per ordinare i risultati di una ricerca che quindi dipendevano non solo dalla presenza in una pagina delle parole chiave cercate dall’utente ma anche dalla rilevanza di quella pagina all’interno nella rete del Web (il suo PageRank, appunto).

– Potreste raccontare ai nostri lettori il caso della ricerca “miserabile fallimento” che portava alla pagina dell’ex presidente George W. Bush? 

PF: Nonostante i motori di ricerca fornissero risultati straordinari a cui gli utenti si erano immediatamente abituati, alcuni meccanismi di rilevanza furono messi in breve tempo in difficoltà da alcune nuove tecniche di spamming, la più famosa delle quali prendeva il nome di Google Bombing. Un esempio famoso, del dicembre 2003, è quello dell’interrogazione ”miserable failure” (miserevole fallimento) che portava Google a restituire come primo risultato la pagina personale dell’ex Presidente degli Stati Uniti George W. Bush. L’idea seguita dai cosiddetti spammer era stata quella di creare automaticamente milioni di pagine Web contenenti hyperlink alla pagina presidenziale e con un testo àncora (quello che solitamente appare in blu) uguale proprio a ”miserable failure”. Il motore Google arricchiva la pagina di George W. Bush con quelle parole considerate “descrittive” della pagina stessa poiché scritte da molti autori per puntare a essa. E così, alla ricerca per ”miserable failure” il motore di ricerca restituiva proprio la pagina di George W. Bush. A tutto questo Google pose subito un rimedio, ma oggi la “battaglia” tra spammer e progettisti di motori di ricerca continua, diventando sempre più sofisticata.

– Su che cosa si fonda la nuova generazione dei motori di ricerca? 

PF: Viviamo oggi nell’era della quarta generazione dei motori di ricerca che vede impegnati a livello mondiale pressoché due soli protagonisti — Bing e Google — più una moltitudine di altri motori di ricerca che agiscono su contenuti specifici (prodotti, pubblicazioni, utenti, mappe, ecc.), su domini nazionali (Istella in Italia, Baidu in Cina, Yandex in Russia, ecc.), oppure dichiarano di eseguire ricerche «semantiche» (Blekko, DuckDuckGo, ecc.) mediante l’interpretazione delle interrogazioni e un’analisi approfondita del contenuto dei documenti. Quest’ultima generazione è infatti segnata da un miglioramento dell’efficienza e dell’efficacia della tecnologia messa a disposizione degli utenti e da una espansione dei contenuti sui quali essi possono fare le ricerche: non più solo pagine Web ma anche notizie di stampa, contenuti di Social Network, enciclopedie (Wikipedia, Treccani, ecc.), orari di aerei e treni, risultati di eventi (partite di calcio, olimpiadi, ecc.), file multimediali o di vari formati (pdf, xls, doc, ecc.) e molto altro ancora. Così oggi un motore di ricerca risponde a un’interrogazione visualizzando anche mappe, notizie, previsioni meteo o definizioni di un dizionario. Sembra impossibile che le tecniche algoritmiche che oggi guidano il funzionamento dei motori di ricerca si siano sviluppate in così pochi anni: solo pochi giorni fa Google ha festeggiato il suo ventesimo compleanno !

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.