Galileo Galilei “Meglio è una piccola verità, che una grande bugia”

Albert Einstein “Non penso mai al futuro. Arriva così presto.”

Informatica: gli algoritmi e il codice

Postato da on Giu 24th, 2019 e file sotto formazione, Primo Piano, Programmazione. You can follow any responses to this entry through the RSS 2.0. Responses are currently closed, but you can trackback from your own site.

Cos’è un algoritmo?
Un algoritmo è una sequenza di istruzioni elementari codificate in modo esplicito, preciso, inequivocabile, tale sequenza è eseguibile meccanicamente e di solito è utilizzato per realizzare uno scopo specifico: soluzione di un problema, codifica di azioni per uno scopo specifico. In modo più esplicito:

Un algoritmo `e una procedura computazionale che prende un valore in ingresso (input) e restituisce un valore in uscita (output). Un algoritmo è corretto rispetto ad un problema oppure risolve un problema se, per ogni ingresso del problema, l’algoritmo termina fornendo l’uscita del problema.

 

Teoria della computazione

La teoria della computazione studia le funzioni astrattamente calcolabili, senza preoccuparsi dell’efficienza dell’algoritmo che le computa. Nasce negli anni ’30, a seguito dell’esigenza, sorta nell’ambito degli studi di logica:

di fornire un equivalente rigoroso al concetto di algoritmo;

di indagare le possibilità ed i limiti dei metodi di calcolo effettivi.

Caratteristiche della computazione

Il processo di calcolo è definito dalle seguenti caratteristiche:

  1. un algoritmo è di lunghezza finita;
  2. esiste un esecutore che può effettuare le istruzioni dell’algoritmo;
  3. Il calcolo è deterministico;
  4. l’esecuzione avviene per passi discreti;
  5. l’esecutore dispone di una memoria ausiliaria per immagazzinare i risultati intermedi dell’elaborazione;
  1. non c’è limite alla lunghezza dei dati;
  2. non c’è limite alla quantità di memoria ausiliaria;
  3. le istruzioni hanno una complessità finita;
  4. l’esecuzione termina dopo un numero di passi finito, ma illimitato;
  5. l’esecuzione può non terminare.

la caratteristica 10 dice che una funzione calcolabile può essere non definita per alcuni elementi del dominio.

Gli algoritmi assomigliano alle ricette. Le ricette ti dicono come eseguire un compito eseguendo una serie di passaggi.

Ad esempio, per cuocere una torta i passaggi sono:

  • preriscaldare il forno;
  • mescolare farina, zucchero e uova accuratamente;
  • versare in una teglia; e così via.

Ma cosa è nato prima il calcolatore oppure gli algoritmi? Bene, procediamo con ordine.

  • la parola algoritmo deriva dal nome del matematico uzbeko-persiano al-Khwarismi الخوارزمي) vissuto intorno all’anno 800), il cui libro “Calcoli con i numerali indiani” descriveva i procedimenti di calcolo per le operazioni aritmetiche con il sistema di numerazione indiano, cioè quelli che ancora oggi studiamo nella scuola elementare;
  • è un anagramma di logaritmo; come vedremo, la funzione logaritmo ha un ruolo abbastanza importante nell’analisi degli algoritmi !

Continua nel prossimo post, Informatica: nascita degli algoritmi


Leggi Ancora

Comments are closed