Algoritmo, la base della programmazione

Il termine “algoritmo” deriva dal nome del matematico persiano Al-Khwarizmi, che visse nel IX secolo d.C. Egli scrisse un trattato sulla matematica e sull’astronomia in cui descriveva un metodo per eseguire calcoli aritmetici, come l’estrazione di radici quadrate e cubiche. Questo metodo divenne noto come “algoritmo” in onore del suo autore.

Successivamente, il termine algoritmi venne utilizzato per descrivere qualsiasi insieme di istruzioni passo-passo utilizzate per risolvere un problema o eseguire un compito specifico. Nel corso dei secoli, l’uso del termine si è evoluto e ora viene comunemente utilizzato per descrivere gli algoritmi informatici utilizzati nella programmazione e nell’informatica in generale.

definizione di algoritmo

Un algoritmo è una serie finita di istruzioni che permettono di risolvere un problema o di eseguire un compito specifico in modo efficiente ed automatico. Le caratteristiche fondamentali di un algoritmo sono:

1. Input e output: l’algoritmo deve essere in grado di ricevere input da parte dell’utente o dall’ambiente esterno.
2. Output: l’algoritmo deve produrre un output, ovvero un risultato che risolve il problema o esegue il compito specifico.
3. Definizione chiara e precisa delle istruzioni: ogni passo dell’algoritmo deve essere ben definito e preciso, in modo da poter essere eseguito da una macchina o da un essere umano.
4. Finitezza: l’algoritmo deve terminare dopo un numero finito di passi.
5. Efficienza: l’algoritmo deve essere in grado di risolvere il problema o eseguire il compito specifico in modo efficiente, ovvero con un numero ragionevole di risorse (tempo e memoria).
6. Generalità: l’algoritmo deve essere generale, ovvero deve poter essere applicato a una vasta gamma di input.

esempi di algoritmi

1. L’algoritmo di ordinamento “Bubble Sort” consiste nel confrontare ogni elemento di un array con il successivo e scambiarli se sono in ordine inverso. Questo processo viene ripetuto fino a quando l’array non è completamente ordinato.
2. L’algoritmo di ricerca “Binary Search* consiste nel dividere l’array in due parti e cercare l’elemento cercato nella metà dell’array che contiene il valore cercato. Questo processo viene ripetuto fino a quando non si trova l’elemento o fino a quando l’array non è più diviso.
3. L’algoritmo di calcolo del fattoriale consiste nel moltiplicare un numero per tutti i numeri minori di esso, fino a raggiungere 1.

esempi di ciò che non è un algoritmo

1. Una persona che esegue un compito senza seguire un insieme preciso di istruzioni.
2. Un processo naturale come la crescita di una pianta o il movimento dei pianeti.
3. Un sistema complesso come l’economia o il clima, che non può essere descritto da un insieme finito di istruzioni.

Lo pseudocodice

Lo pseudocodice è una rappresentazione informale delle istruzioni di un algoritmo utilizzata per descrivere il funzionamento dell’algoritmo stesso in modo indipendente dalla piattaforma o dal linguaggio di programmazione utilizzato. Viene spesso utilizzato per progettare e documentare algoritmi prima di implementarli in un linguaggio di programmazione specifico.

Lo pseudocodice utilizza un insieme di istruzioni standard, come “inizia”, “finché”, “se”, “altrimenti” e “ripeti”, che vengono utilizzate per descrivere il flusso dell’algoritmo. Inoltre, lo pseudocodice può includere commenti e note esplicative per chiarire il funzionamento dell’algoritmo.

In generale, lo pseudocodice è uno strumento utile per la progettazione di algoritmi poiché permette di concentrarsi sulla logica dell’algoritmo stesso senza dover pensare alla sua implementazione in un linguaggio di programmazione specifico. Inoltre, lo pseudocodice può essere utilizzato per documentare l’algoritmo e renderlo più comprensibile a chi lo legge.

Il teorema di Jacopini Bohem

Il Teorema di Jacopini-Boehm è un risultato fondamentale nella teoria dei linguaggi di programmazione che stabilisce una relazione tra i concetti di algoritmo e programma.

In particolare, il teorema afferma che ogni algoritmo può essere rappresentato da un programma in un linguaggio di programmazione che include solo tre costrutti fondamentali:

• sequenza
• selezione
• iterazione

Esempi di algoritmi

Ecco tre esempi di algoritmi scritti in pseudocodice:

1. Algoritmo per calcolare il fattoriale di un numero intero positivo n:

funzione fattoriale(n)
   se n = 0 o n = 1
      allora restituire 1
   altrimenti
      restituire n * fattoriale(n - 1)

2. Algoritmo per cercare un elemento in un array ordinato utilizzando la ricerca binaria:

funzione cerca_elemento(array, elemento)
   definire indice_inferiore = 0
   definire indice_superiore = lunghezza(array) - 1

   mentre indice_inferiore <= indice_superiore
      definire indice_medio = (indice_inferiore + indice_superiore) / 2

      se elemento = array[indice_medio]
         allora restituire True
      altrimenti se elemento < array[indice_medio]
         allora indice_superiore = indice_medio - 1
      altrimenti
         indice_inferiore = indice_medio + 1

   restituire False

3. Algoritmo per calcolare la somma di tutti i numeri interi da 1 a n:

funzione somma_numeri(n)
   definire somma = 0
   per i = 1 a n
      somma = somma + i

   restituire somma