Algoritmo

In ambito matematico (entscheidungsproblem) e informatico (teoria della calcolabilità) rappresenta una sequenza finita di operazioni, o istruzioni, che permettono di risolvere i quesiti di una stessa classe o di calcolare il risultato di un’espressione matematica.

Molti algoritmi si avvalgono di tecniche per rappresentare (strutture dati) ed organizzare i dati utilizzati nel calcolo e non sono necessariamente altrettanto sofisticate rispetto all’algoritmo che le usa in quanto algoritmi semplici possono richiedere strutture dati complesse e viceversa.

Data la moltitudine di applicazione e tipologie vengono raggruppati e catalogati a seconda della loro funzione o delle tecniche utilizzate per realizzarli:

• Algoritmo iterativo: costituito da una sequenza di azioni ripetute, finché è necessaria la ripetizione del un ciclo;
• Algoritmo ricorsivo: consente di eseguire dei compiti ripetitivi su di un set di variabili in input;
• Algoritmo di ordinamento: utilizzato per posizionare gli elementi di un insieme secondo una sequenza stabilita da una relazione d’ordine;
• Algoritmi di ricerca: permette di trovare un elemento avente determinate caratteristiche all’interno di un insieme di elementi:
  • ricerca sequenziale: trovare un elemento in un insieme non ordinato;
  • ricerca binaria: trovare un elemento in un insieme ordinato di dati;
• Algoritmo genetico evolutivo: basato sul principio della selezione naturale ed evoluzione biologica tentare di risolvere problemi di ottimizzazione per i quali non si conoscono altri algoritmi efficienti di complessità lineare o polinomiale;
• Algoritmo per la Swarm Intelligence: basato sul metodo euristico di ottimizzazione per la ricerca tramite la misurazione sulla qualità della soluzione;
• Algoritmo combinatorio: utilizzato per inserire gli elementi di un insieme in un’opportuna struttura dati che permetta di verificare successivamente se un generico elemento appartiene oppure no all’insieme;
• Algoritmo del codice automodificante: utilizzato per creare programmi, come virus, in grado di modificare il proprio codice durante l’esecuzione;
• Algoritmo della conversione e codifica: utilizzato per convertire un numero decimale in binario;
  • UUencode/UUdecode: converte file binari in formato ASCII con caratteri compressi tra 32 e 95 escludendo caratteri di controllo e a 8 bit;
  • MIME (Multipurpose Internet Mail Extensions): è uno standard del WWW (World Wide Web) che estende la definizione del formato dei messaggi di posta elettronica;
• Algoritmo di compressione: utilizzato per l’elaborazione dei dati riducendone la quantità di bit necessari alla rappresentazione digitale di un’informazione:
  • senza perdita di informazioni:
    • run-length encoding (PackBits e PCX);
    • codifica a riduzione locale di Entropia (Huffman e aritmetica);
    • codifica a dizionario (DEFLATE, LZ77, LZ78, Lempel-Ziv-Welch o ZIP e LZMA);
    • trasformata di Burrows-Wheeler;
    • PPM;
  • con perdita di informazione:
    • trasformata discreta del coseno (MPEG e JPEG);
    • compressione frattale (trasformazione frattale);
  • Wavelet (rappresentazione di un segnale mediante l’uso di una forma d’onda oscillante di lunghezza finita o a decadimento rapido):
    • MP3;
    • JPEG2000;
• Algoritmo quantistico: utilizzato per il calcolo quantistico svolto dalle macchine di Touring quantistiche;
• Algoritmo apriori: utilizzato anche nel data mining per effettuare una ricerca delle associazioni;
• Algoritmo di Berger: utilizzato per stilare il calendario di una competizione sportiva con la formula del girone all’italiana;
• Algoritmo di Sturm: utilizzato per calcolare il numero di radici reali di un polinomio a coefficienti reali che cadono in un determinato intervallo;
• Algoritmo online: utilizzato per la risoluzione di un problema, che deve fornire dei risultati pur non avendo a disposizione, inizialmente, alcuni dei dati in ingresso;
• Algoritmo di pitch detection: utilizzato per valutare la frequenza fondamentale di un segnale periodico o quasi periodico, generalmente una registrazione digitale della voce o di una nota musicale;
• Algoritmo di sommatoria di Kahan: utilizzato per ridurre significativamente l’errore numerico nel totale ottenuto sommando una sequenza di numeri in virgola mobile con precisione finita, se confrontato con il consueto procedimento;
• Algoritmo di Euclide: utilizzato per trovare il massimo comune divisore tra due numeri interi;
• Algoritmo di prostaferesi: utilizzato per determinare in modo approssimato il risultato di una moltiplicazione sfruttando alcune relazioni trigonometriche;
• Algoritmo di pattern matching su stringhe: utilizzato per provare a individuare una posizione all’interno di una stringa più grande (testo), in cui una o più stringhe più piccole (pattern) si trovano;
• Algoritmo Doomsday: utilizzato per calcolare il giorno della settimana di una specifica data passata o futura;
• Algoritmo di Dijkstra: utilizzato per cercare i cammini minimi in un grafo con o senza ordinamento, ciclico e con pesi non negativi sugli archi e consente di ottimizzare le realizzazioni delle reti (telecomunicazioni, idriche, stradali, circuitali, ecc.);
• Algoritmo di Boyer-Moore: utilizzato per elaborare la stringa (pattern) da cercare, ma non la stringa esaminata (testo);
• Algoritmo di Knuth-Morris-Pratt: utilizzato per trovare le occorrenze di una stringa (pattern) in una stringa (testo);
• Algoritmo di Prim: utilizzato nella teoria dei grafi, informatica e ricerca operativa per determinare gli alberi di supporto minimi di un grafo non orientato e con pesi non negativi;
• Algoritmo di Gauss-Newton: utilizzato per risolvere problemi di minimi quadrati (funzioni) e regressioni non lineari (statistica);
• Algoritmo della linea di Bresenham: utilizzato per la rasterizzazione di linee, soprattutto per la sua bassa richiesta di risorse computazionali (conversione di una immagine bidimensionale vettoriale in raster o bitmap);
• Algoritmo del simplesso: utilizzato per risolvere problemi di programmazione lineare;
• Algoritmo delle colonie di formiche: utilizzato per la ricerca dei percorsi ottimali in un grafo partendo dal comportamento dei superorganismi sull’ottimizzazione metaeuristica del percorso ottimale tra la colonia e la fonte di cibo;
• Algoritmo del banchiere: utilizzato per evitare deadlock (due risorse si bloccano a vicenda entrando in stallo sistemico) nell’allocazione delle risorse indicando le risorse che consentono lo sblocco e la messa in sicurezza del sistema;
• Algoritmo del fornaio: utilizzato come metodo mutex (procedimento di sincronizzazione fra thread concorrenti per impedire che più task paralleli accedano contemporaneamente ai dati in memoria) che trovano applicazione pratica nella programmazione parallela per serializzare l’esecuzione delle sezioni critiche (porzione di codice che accede a una risorsa condivisa tra più flussi di esecuzione di un sistema concorrente) da parte di thread concorrenti;
• Algoritmo dell’ascensore: utilizzato per il disk scheduling (decide l’ordine delle operazioni di I/O richieste da sottoporre al volume di immagazzinamento) per stabilire l’ordine in cui devono essere processate le richieste di lettura e richieste di scrittura su disco rigido (dispositivo di memoria di massa magnetico);
• Algoritmo del puzzle: utilizzato nella crittografia a chiave pubblica dove solo i soggetti coinvolti conoscono la chiave di cifratura;
• Algoritmo del biglietto: utilizzato per sincronizzare i processi per verificare dei thread in esecuzione che hanno i permessi di accesso ad una sezione critica del sistema, ovvero una risorsa condivisa tra più processi;
• Algoritmo di elezione: utilizzato nei sistemi distribuiti per stabilire il coordinatore a cui i processi fanno riferimento per un servizio:
  • Algoritmo dello spaccone di Garzia;
  • Algoritmo ad anello di Le Lann;
  • Algoritmo di Chang e Robert;
  • Algoritmo di Dolev, Klawe e Rodeh.