Di algoritmi si parla molto oggi con riferimento ai computer, a Google, alla profilazione degli utenti dei social e all'avvento dell'intelligenza artificiale. Ma la loro storia è molto più antica: la necessità di risolvere problemi matematici con opportune regole computazionali ha sempre accompagnato la vita dell'uomo, a partire da esigenze molto concrete come distribuire i prodotti agricoli, dividere un'eredità, misurare un terreno e permettere ai mercanti di svolgere con profitto la loro attività. Il Medioevo, in particolare, fu un periodo di grande evoluzione della cultura, grazie alla riscoperta delle fonti culturali e scientifiche, greche e ai matematici arabi, che nel IX secolo diffusero nel Mediterraneo il sistema di numerazione indiano, cambiando radicalmente il modo di fare i calcoli. Le figure di Muhammad ibn Musa al-Khwarizmi (da cui deriva il termine algoritmo), dei monaci spagnoli che tradussero in latino le opere dei matematici arabi, del pisano Fibonacci, mercante e matematico, dei tanti «maestri d'abaco» che insegnarono il calcolo ai figli dei mercanti, nonché dei matematici umanisti come Piero della Francesca e Luca Pacioli, spiccano in questo libro corale il cui protagonista è una società che nel Medioevo stava gettando le basi della nostra contemporaneità.

I temi presentati in questo testo costituiscono una parte essenziale della preparazione di uno specialista informatico. La loro trattazione si può svolgere in un unico corso, o anche in più corsi universitari di informatica, ingegneria informatica o matematica, nell'ambito sia della laurea triennale che della laurea magistrale. Oltre che per gli specialisti, la conoscenza dei principi teorici dell'informatica assume anche un ruolo importante nella preparazione culturale degli insegnanti di discipline informatiche nell'ambito della scuola media superiore. In ogni caso, la conoscenza delle proprietà di grammatiche ed automi, dei limiti del calcolo automatico, della complessità computazionale e del problema 'da un milione di dollari' P = NP? ha assunto un ruolo importante anche nella cultura scientifica contemporanea, e può risultare interessante per chi voglia approfondire alcuni dei temi che hanno caratterizzato la logica e la matematica dell'ultimo secolo. Il volume contiene anche esercizi, note storiche e bibliografiche che consentono di comprendere meglio i concetti introdotti e rinviano ad altre letture di approfondimento. Questa nuova edizione, ampliata, riveduta e corretta, presenta un capitolo aggiuntivo dedicato agli algoritmi di risoluzione approssimata di problemi di ottimizzazione; inoltre, sono state aggiunge delle sezioni dedicate alle applicazioni pratiche degli argomenti trattati.

To examine, analyze, and manipulate a problem to the point of designing an algorithm for solving it is an exercise of fundamental value in many fields. With so many everyday activities governed by algorithmic principles, the power, precision, reliability and speed of execution demanded by users have transformed the design and construction of algorithms from a creative, artisanal activity into a full-fledged science in its own right. This book is aimed at all those who exploit the results of this new science, as designers and as consumers.

The first chapter is an overview of the related history, demonstrating the long development of ideas such as recursion and more recent formalizations such as computability. The second chapter shows how the design of algorithms requires appropriate techniques and sophisticated organization of data. In the subsequent chapters the contributing authors present examples from diverse areas – such as routing and networking problems, Web search, information security, auctions and games, complexity and randomness, and the life sciences – that show how algorithmic thinking offers practical solutions and also deepens domain knowledge.

The contributing authors are top-class researchers with considerable academic and industrial experience; they are also excellent educators and communicators and they draw on this experience with enthusiasm and humor. This book is an excellent introduction to an intriguing domain and it will be enjoyed by undergraduate and postgraduate students in computer science, engineering, and mathematics, and more broadly by all those engaged with algorithmic thinking.