Algoritmi

Al momento dell'esecuzione di un codice sorgente (dopo che è stato verificato, linkato e compilato) vengono alla luce i problemi legati alla velocità: un codice può essere corretto, ma impiegare un tempo inaccettabile per la sua esecuzione. "Inaccettabile" può significare sia che l'utente umano che sta aspettando si stufa, sia che un altro programma che sta in attesa del risultato non può più attendere e va in errore.

Nginx timeout
Source: Nginx timeout
In certi casi si può ricorrere ad un approccio hardware (utilizzare un computer più potente o aumentare le risorse disponibili). Ma esiste una famoa "legge" attribuita a Niklaus Wirth che dice che «Il software diventa lento più rapidamente di quanto l'hardware diventi più veloce».

L'altra strada è quella di ripensare il codice sorgente tenendo conto dell'efficienza, cioè usare un algoritmo diverso.

La parola "algoritmo" di recente ha avuto una certa notorietà. Quanto sarebbe stato felice il vecchio Abū Jaʿfar Muḥammad ibn Mūsā al-Khwārizmī, matematico, geografo, astronomo persiano del IX secolo, autore di un libro famosissimo, tradotto in Latino col titolo di “Algoritmi de numero Indorum” (generando un po’ di confusione tra il nome dell’autore e l’argomento).

Però gli algoritmi di oggi non hanno a che fare con l’algebra ma con l’informatica: si tratta della definizione di una procedura in passi elementari, così semplice che la può eseguire anche una macchina. Ci sono esempi famosissimi: l’algoritmo detto “Crivello di Eratostene” per trovare tutti i numeri primi.

Ci sono algoritmi più veloci di altri, a parità di tutto il resto. Il caso dell'ordinamento è uno dei più noti: a partire dall'algoritmo più naturale (l'inserimento), sono stati inventati algoritmi più veloci (l'ordinamento per combinazione, inventato da Von Neumann nel 1945, l'ordinamento "quick", inventato da Hoare nel 1961).

Come fanno ad essere più veloci? Perché raggiungono lo stesso risultato con meno operazioni. Certo, ma come è possibile? In generale, il trucco è non perdere informazioni strada facendo: se una parte dell'insieme di elementi è già parzialmente ordinato, questa informazione viene conservata nel processo.

Ma non c'è solo la velocità che rendere preferibile un algoritmo ad un altro.

Alcuni algoritmi usano più memoria di altri; alcuni funzionano meglio nella media ma si comportano malissimo nei casi limite.

Alcuni algoritmi sono considerati semplicemente più eleganti di altri. Ad esempio, gli algoritmi ricorsivi sono quelli che dividono un problema in una parte risolvibile immediatamente e in una ancora da trattare; prendono la seconda parte e la dividono ancora in due parti, e così via finché non arrivano ad avere tanti piccoli problemi risolti. E' un po' la strategia del "divide et impera" che sembra fosse cara al re Filippo di Macedonia (che però la diceva in greco: διαίρει καὶ βασίλευε).

Ad esempio, supponiamo di voler trasformare "Garibaldi fu ferito..." in "Garabalda fa farata...". Sappiamo come fare per sostituire qualsiasi vocale con "a" ma non sappiamo come trasformare un intero testo.

La versione più intuitiva dell'algoritmo è questa:

  1. prendi il testo della canzoncina e conta la lunghezza del testo il lettere (sono 90)
  2. prepara una variabile – vuota – dove andrà a finire la versione trasformata
  3. prepara una variabile che si chiama I e che servirà a contare le lettere; mettici dentro 1
  4. ripeti novanta volte:
    4.1 prendi la lettera numero I del testo
    4.2 è una vocale?
      4.2.1 se sì. sostituiscila con la A, e mettila all’inizio della variabile finale
      4.3.2 altrimenti, metti la lettera originale all’inizio della variabile finale
    4.3 aumenta I di 1
  5. quando hai finito, restituisci la versione trasformata
Una versione ricorsiva invece è quest'altra:
  1. prendi il testo della canzoncina
  2. il testo ha lunghezza 1 (cioè è composto da una sola lettera) ?
    - se sì, ed è una vocale, cambiala con "a"; altrimenti lasciala stare
    - se no, ricomincia da capo con il testo della canzoncina meno la prima lettera
  2. alla fine unisci i risultati parziali che provengono da queste due passi

Prossima stanza:  Musei



Versione: 24/01/2022 - 19:09:40

Parole: 355

Pannelli

Concetti                    
MagiaDigitale               
Programmi                   
Codice                      
Linguaggi                   
Errori                      
Esecuzione                  
Algoritmi                   
🔎