il carattere fondamentale del concetto di algoritmo in informatica può essere riconosciuto nella definizione di quest'ultima come

• scienza della risoluzione di problemi mediante algoritmi

l'utilità pratica di algoritmi ben formalizzati deriva dal fatto che essi permettono di automatizzare la risoluzione di (classi di) problemi

• una definizione più formale del concetto di algoritmo serve invece alla nostra comprensione dell'esatta natura dell'oggetto di questa scienza

il testo (Schneider & Gersting, 2007) propone la seguente:

• un insieme ordinato di operazioni non ambigue ed effettivamente computabili che, quando eseguito, produce un risultato e si arresta in un tempo finito

come gli stessi autori notano, la definizione è piuttosto stringente... forse un po' troppo?

1. sebbene la definizione non lo implichi, gli autori intendono un ordinamento totale delle operazioni da eseguire, ovvero una unica sequenza di esecuzione (per un dato input); vediamo appresso un esempio che solleva qualche dubbio in proposito;
2. il requisito di arresto in ogni caso è inoltre piuttosto critico, come vedremo

il testo citato illustra la definizione di algoritmo con un esempio familiare dai banchi di scuola elementare: l'addizione di due numeri

lo si confronti con quello analogo, ma relativo ad una diversa scelta dei simboli per le cifre, mutuata dalla cultura Maya (per semplicità qui in base 10: la rappresentazione Maya dei numeri è in base 20)

le cifre diverse da zero sono costruite mettendo assieme costituenti di due tipi:

•  • :  vale 1 (lo chiamiamo "unità")
• —— :  vale 5 (lo chiamiamo "cinquina")

nella rappresentazione decimale, un cifra non nulla è costituita da al più 4 unità e al più 1 cinquina

ecco un procedimento per sommare due (o più) numeri in tale rappresentazione:

1. allineare a destra le sequenze di cifre che rappresentano i numeri da sommare
2. raccogliere assieme in fondo a ciascuna colonna i costituenti delle cifre di quella colonna
3. trasformare la raccolta ottenuta da ciascuna colonna, ed eventualmente altre di maggiore significatività generate dal procedimento, applicando in qualsiasi ordine, in ciascuna posizione, le due regole seguenti, fintantoché applicabili:
   •   se presenti, rimpiazza 5 unità con una cinquina
   •   se presenti, rimpiazza 2 cinquine nella posizione data con una unità nella successiva posizione più significativa (a sinistra)

sia f : N₊ → N₊ la funzione definita sui numeri naturali positivi (0 escluso) dalla regola:

• se n è pari, allora f n = n/2, altrimenti f n = 3n + 1

un algoritmo di calcolo per questa funzione può essere descritto da un diagramma a blocchi

con un piccolo ritocco al diagramma a blocchi, lo trasformiamo in quello di un sistema dinamico, che, avviato da un input x, genera la sequenza infinita delle applicazioni iterate di f : f x, f f x, f f f x, ...

sia f ^kx il k-simo elemento della sequenza; si dice ritardo di x il minimo k tale che f ^kx = 1

• Problema: tale minimo esiste per qualsiasi x ?
• risposta: così pare, ma non è certo che così sia

dal diagramma a blocchi del sistema dinamico si ottiene facilmente quello di un algoritmo per il calcolo del ritardo, ma...

• stando alla definizione di algoritmo vista sopra, sarebbe un algoritmo?
• risposta: come sopra :(

ecco una definizione informale meno esigente di quella citata, tale da permettere di annoverare fra gli algoritmi i procedimenti visti nei due esempi precedenti:

• un insieme ordinato di passi eseguibili e non ambigui

dove è inteso che

• l'ordine non sia necessariamente sequenziale, ovvero sia parziale
• esistano uno o più esecutori in grado di interpretare i passi (purché non ambigui) ed effettivamente eseguirli rispettando l'ordine prescritto

la definizione non prescrive che l'esecuzione termini

la non terminazione di un algoritmo non è necessariamente sintomo di un errore di progettazione o di realizzazione dell'algoritmo

• ad esempio, algoritmi di allocazione e rilascio di risorse, o di dispaccio di richieste di servizio, tipicamente devono esaminare ciclicamente richieste in arrivo da un insieme finito di canali in ingresso, per servirle secondo un disciplina predefinita; la presenza di un ciclo infinito è una caratteristica inerente a questi algoritmi

un rapida escursione introduttiva:

• etimologia di "calcolo"
• antichi algoritmi e strumenti di calcolo: abaci
• il Liber abaci di Leonardo Pisano (Fibonacci)
• le calcolatrici del XVII secolo: Pascalina, Stepped Reckoner (Leibniz)
• Leibniz: "calculemus!"
• rivoluzione industriale: telai Jacquard, logaritmi di Prony
• XIX secolo: l'Analytical engine di Babbage
• Boole, De Morgan, Pierce, Schröder, Cantor, Frege, ...
• XX secolo, il problema dei fondamenti della matematica:
       paradossi, programma di Hilbert, teorema di Gödel
• i primi calcolatori sono "virtuali": Post, Turing, Church
• Von Neumann : architettura del calcolatore "reale"
• anni '50: l'Informatica dalla preistoria alla storia

l'idea di J.-M. Jacquard (1804): introdurre nei telai delle schede di cartone forato; ad ogni scheda corrispondeva un preciso disegno, formato dai fori

• lettura delle schede: le file di aghi potevano attraversarle solo dove c'erano i fori

la prima invenzione di Charles Babbage è la macchina differenziale (1823): estende le idee di Pascal e Leibniz, ed è in grado di operare fino a 6 cifre significative

XX secolo: elaborazione automatica di dati su larga scala, motivazioni:

• civili: censimento, grandi aziende, ... : macchine di Hollerith
  — non a caso, in francese "calcolatore" si traduce in "ordinateur" —
• militari: codici crittografici, calcoli balistici, ...
  enormi macchine da calcolo elettromeccaniche, come ad es. Mark I

negli anni '40, grazie alla disponibilità delle prime tecnologie elettroniche, prende definitivamente avvento la rappresentazione binaria dell'informazione

• non è una novità: ad es., il codice Morse aveva fatto la sua comparsa con l'invenzione del telegrafo, nel secolo precedente

spesso si riporta quale primo esemplare di calcolatore elettronico l'ENIAC, costruito da Eckert e Mauchly (U. of Pennsylvania, 1946), ma la questione è controversa

• v. ad es. la storia del calcolatore di Atanasoff e Berry (ABC)
• altri predecessori di ENIAC sono Colossus (A. Turing, U. of Manchester), costruito per scopi bellici e coperto dal segreto militare, ricostruito al National Museum of Computing (1994 — 2004), e le macchine programmabili Z1 – Z4 (K. Zuse, Berlin)

l'idea di Von Neumann (che aveva preso parte al progetto dell'ENIAC): rappresentare e memorizzare il programma di calcolo così come si rappresentano e memorizzano i dati su cui opera

• l'idea si era già manifestata nel concetto di Macchina di Turing Universale

con Von Neumann, l'idea prende "corpo tecnologico": nasce il calcolatore general-purpose a programma memorizzato

• primo esemplare della specie è l'EDVAC (1951), UNIVAC I ne è la versione commerciale, l'EDSAC (M. Wilkes, U. of Cambridge) è dello stesso periodo

sviluppi salienti:

• anni '50:
  • linguaggi di programmazione simbolici, assembler
  • impiego di transistor, memorie a nuclei, dischi magnetici
  • primi linguaggi di programmazione ad alto livello
• anni '60 e '70 (prima metà):
  • sistemi operativi, time-sharing, programmazione strutturata
  • impiego di circuiti integrati, primi minicalcolatori
  • industria del software, standard di compatibilità fra sistemi
• anni '70 (seconda metà) e '80:
  • programmazione di sistema (Unix), programmazione dichiarativa e ad oggetti
  • impiego di circuiti integrati LSI, VLSI, ULSI
  • microcalcolatori, calcolatori personali, interfacce grafiche (GUI)
  • reti di calcolatori, basi di dati
• dagli anni '90 ad oggi:
  • Internet, World Wide Web, standard per l'industria del software
  • architetture parallele, supercalcolatori, enormi capacità di memoria
  • calcolatori portatili e palmari, interfacce multimediali
  • standard per suoni, immagini e filmati digitali, informatica pervasiva

1. Descrivere un algoritmo per la sottrazione di un numero da un altro non più grande, utilizzando la rappresentazione dei numeri, qui descritta, simile a quella Maya ma in base 10.
2. La scheda su al-Khwarizmi a p. 5 del testo (Schneider & Gersting, 2007) è affetta da un errore, in merito al significato della parola araba al-jabr : trovarlo.
   • N.B. Si suggerisce di consultare una fonte attendibile sull'etimologia della parola "algebra", quale ad es. il testo su L'algebra nella matematica islamica di Clara Silvia Roero, contribuito ai materiali per la scuola del sito
     Il giardino di Archimede:   web.math.unifi.it/archimede
3. Descrivere un algoritmo per determinare il valore massimo presente nella sequenza di numeri prodotta dal sistema dinamico 3x+1 visto a lezione.
   • N.B. Si può garantire l'esistenza di tale massimo se il ritardo di x ha un valore definito: perché? Tale condizione è sufficiente, ma non necessaria: perché? Quale condizione è necessaria e sufficiente?
4. Esercizi proposti dal testo (Schneider & Gersting, 2007): pp. 31-32, n. 3-5, 7-9, 14.

1. Precisione della definizione di "algoritmo"
   Né la definizione di algoritmo qui proposta, né le sue varianti più comuni, precisano se l'ordine a cui si fa riferimento riguardi la descrizione dei passi dell'algoritmo o piuttosto la loro esecuzione. Riflettere sulle differenze fra le due interpretazioni della definizione che ne conseguono, e possibilmente proporre una definizione migliore.
2. Approfondimenti storici su algoritmi e calcolo
   In ciascuno dei 12 punti qui proposti (e in altri "in mezzo") fra i precedenti storici del rapporto fra algoritmi e calcolo, si individuano facilmente uno o più temi suscettibili di approfondimento storico; sceglierne uno di particolare interesse personale, reperire fonti attendibili di studio sul tema e produrre una sintesi documentata dello studio svolto.
3. Algoritmi paralleli e griglie computazionali
   Molti problemi possono essere risolti da algoritmi eseguibili da più agenti di calcolo che operano contemporanemente, spesso ciascuno su una parte assegnata dei dati in ingresso (ad esempio, l'algoritmo per l'addizione Maya qui descritto ha questa proprietà, dove ciascun esecutore opera sulle cifre di una colonna assegnata); le griglie computazionali sono reti di calcolatori organizzate per l'esecuzione di tali algoritmi, e il termine grid computing designa questo tipo di elaborazione; raccogliere documentazione su queste reti e/o su algoritmi eseguiti su griglie e produrne una sintesi, corredata di riferimenti alle fonti.
4. Altri temi proposti dal testo (Schneider & Gersting, 2007): p. 32, Esercizi 10, 12, 15.