Computational thinking is a mental process for solving problems through an ordered series of precise instructions. This ordered series is an “algorithm”, an ancient term of Arabic origin which has become so fashionable that plenty of people use it without really knowing what it means. Whenever we use a smartphone to call someone, take a picture, listen to music or access the internet, we set off – in a completely imperceptible way – an extremely complicated “computation” allowing us to use sounds, images and character sequences. Computation plays an essential role in the modern world and has become a general activity dealing with all sorts of data. The book introduces the reader to computational thinking by addressing and solving increasingly complex problems. The author describes some of its most important applications, from managing big data to text compression, to the operation of search engines.
Paolo Ferragina teaches Algorithms at the University of Pisa and also teaches at Pisa’s Scuola Normale Superiore.
Fabrizio Luccio has taught at the Polytechnic University of Milan, the MIT in Boston and other American universities and is now professor emeritus of Computer Science at the University of Pisa.
- Premessa
- La nascita del pensiero computazionale
- I. Un piccolo problema per cominciare
- II. Algoritmi e coding
- 1. Lo pseudocodice
- 2. Un programma più utile
- 3. Interazione con la macchina
- 4. La ricerca binaria
- III. Il torneo
- 1. Limite inferiore al problema del massimo
- 2. Il tabellone del torneo
- 3. Il problema del secondo
- IV. Un problema finanziario
- 1. Un algoritmo «cubico»
- 2. Un algoritmo «quadratico»
- 3. Un algoritmo lineare
- 4. L'efficienza algoritmica in rapporto all'efficienza hard-ware
- 5. Alcune interessanti varianti del problema
- V. Mettere in ordine
- 1. Il problema dell'ordinamento
- 2. Un algoritmo più efficiente
- 3. Un limite inferiore
- 4. Ordinare numeri interi
- 5. Ordinare Big Data
- 6. La fusione a più vie
- VI. Messaggi segreti
- 1. La modularità
- 2. La crescita esponenziale
- 3. Il disco di Leon Battista Alberti
- 4. I cifrari di oggi
- 5. Le disposizioni di n caratteri
- 6. La costruzione di chiavi
- VII. Problemi «facili» e «difficili»
- 1. Camminare per una città
- 2. P=NP ?
- VIII. Motori di ricerca
- 1. Dalle parole agli hyperlink
- 2. La quarta generazione
- 3. La struttura
- 4. Come risolvere una interrogazione
- 5. Ancora un miglioramento
- 6. Una considerazione conclusiva
- IX. La compressione dei testi
- 1. I compressori statistici
- 2. I compressori basati su dizionario
- 3. I compressori basati su ordinamento
- 4. La correttezza della trasformazione inversa
- 5. Alcune considerazioni conclusive
- X. La ricorsività
- 1. Un gioco molto istruttivo
- 2. Confronto tra ricorsività e iterazione
- 3. Altri esempi
- 4. Un famoso algoritmo
- 5. Un po' di cautela, per concludere
- Indice analitico
