In matematica e informatica, un algoritmo è una specifica inequivocabile su come risolvere una classe di problemi. Gli algoritmi possono eseguire operazioni di calcolo, elaborazione dati e ragionamento automatico.

Come metodo efficace, un algoritmo può essere espresso in una quantità limitata di spazio e tempo e in un linguaggio formale ben definito per il calcolo di una funzione. Partendo da uno stato iniziale e da un input iniziale (forse vuoto), le istruzioni descrivono un calcolo che, una volta eseguito, procede attraverso un numero finito di stati successivi ben definiti, producendo alla fine “output” e terminando in uno stato finale finale. Il passaggio da uno stato all’altro non è necessariamente deterministico; alcuni algoritmi, noti come algoritmi randomizzati, incorporano input casuali.

Il concetto di algoritmo esiste da secoli e l’uso del concetto può essere attribuito ai matematici greci, ad es. il setaccio di Eratostene e l’algoritmo di Euclide; il termine algoritmo stesso deriva dal matematico del 9 ° secolo Muhammad ibn Mūsā al’Khwārizmī, latinizzato ‘Algoritmi’. Una formalizzazione parziale di quella che sarebbe diventata la nozione moderna dell’algoritmo è iniziata con i tentativi di risolvere il problema Entscheidungsproblem (il “problema decisionale”) posto da David Hilbert nel 1928. Le formalizzazioni successive sono state formulate come tentativi di definire “calcolabilità effettiva” o “metodo efficace” ; quelle formalizzazioni includevano le funzioni ricorsive di Gödel-Herbrand-Kleene del 1930, 1934 e 1935, il lambda calculus di Alonzo Church del 1936, la Formulazione 1 di Emil Post del 1936 e le macchine di Turing di Alan Turing del 1936-7 e 1939.

Etimologia
La parola “algoritmo” ha le sue radici nel latinizzare il nome di Muhammad ibn Musa al-Khwarizmi in un primo passo verso l’algoritmo. Al-Khwārizmī (persiano: خوارزمی, 780-850 circa) era un matematico persiano, astronomo, geografo e studioso nella Casa della saggezza a Baghdad, il cui nome significa “nativo di Khwarezm”, una regione che faceva parte di Grande Iran ed è ora in Uzbekistan.

Circa 825, al-Khwarizmi scrisse un trattato in lingua araba sul sistema numerico indù-arabo, che fu tradotto in latino durante il 12 ° secolo sotto il titolo Algoritmi de numero Indorum. Questo titolo significa “Algoritmi sui numeri degli indiani”, dove “Algoritmi” era la latinizzazione del traduttore del nome di Al-Khwarizmi. Al-Khwarizmi era il matematico più letto in Europa nel tardo Medioevo, principalmente attraverso un altro dei suoi libri, l’Algebra. Nel latino del tardo medioevo, l’algoritmo, l'”algoritismo” inglese, la corruzione del suo nome, significava semplicemente “il sistema dei numeri decimali”. Nel XV secolo, sotto l’influenza della parola greca ἀριθμός ‘numero’ (cfr ” aritmetica ‘), la parola latina fu alterata all’algoritmo, e il corrispondente termine inglese’ algoritmo ‘è attestato per la prima volta nel XVII secolo; il senso moderno è stato introdotto nel 19 ° secolo.

In inglese, fu usato per la prima volta intorno al 1230 e poi da Chaucer nel 1391. L’inglese adottò il termine francese, ma non fu fino alla fine del XIX secolo che “algoritmo” assunse il significato che ha nell’inglese moderno.

Un altro uso iniziale della parola risale al 1240, in un manuale intitolato Carmen de Algorismo composto da Alexandre de Villedieu. Inizia così:

Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.

che si traduce come:

Algorism è l’arte con cui attualmente usiamo quelle figure indiane, che sono due volte cinque.

Il poema è lungo alcune centinaia di righe e riassume l’arte del calcolo con il nuovo stile di dadi indiani, o Talibus Indorum o numeri indù.

Definizione informale
Per una presentazione dettagliata dei vari punti di vista sulla definizione di “algoritmo”, vedere Algoritmi caratterizzazioni.
Una definizione informale potrebbe essere “un insieme di regole che definisce precisamente una sequenza di operazioni”. che includerebbe tutti i programmi per computer, inclusi i programmi che non eseguono calcoli numerici. Generalmente, un programma è solo un algoritmo se si ferma alla fine.

Un esempio prototipico di un algoritmo è l’algoritmo euclideo per determinare il massimo comune divisore di due interi; un esempio (ce ne sono altri) è descritto dal diagramma di flusso sopra e come esempio in una sezione successiva.

Boolos, Jeffrey e 1974, 1999 offrono un significato informale della parola nella seguente citazione:

Nessun essere umano può scrivere abbastanza velocemente, o abbastanza a lungo, o abbastanza piccolo † († “più piccolo e più piccolo senza limiti … staresti cercando di scrivere su molecole, atomi, elettroni”) per elencare tutti i membri di un insieme infinitamente infinito scrivendo i loro nomi, uno dopo l’altro, in qualche notazione. Ma gli umani possono fare qualcosa di altrettanto utile, nel caso di alcuni insiemi infinitamente infiniti: possono dare istruzioni esplicite per determinare l’ennesimo membro dell’insieme, per un arbitrario finito n. Tali istruzioni devono essere date in modo abbastanza esplicito, in una forma in cui potrebbero essere seguite da una macchina informatica, o da un umano che è in grado di eseguire solo operazioni molto elementari sui simboli.

Un “insieme infinitamente infinito” è uno i cui elementi possono essere messi in corrispondenza uno-a-uno con gli interi. Quindi, Boolos e Jeffrey stanno dicendo che un algoritmo implica istruzioni per un processo che “crea” interi in uscita da un intero o “intero” arbitrario di “input” che, in teoria, può essere arbitrariamente grande. Quindi un algoritmo può essere un’equazione algebrica come y = m + n – due “variabili di input” arbitrarie m e n che producono un output y. Ma i tentativi di vari autori di definire la nozione indicano che la parola implica molto più di questo, qualcosa dell’ordine di (per l’esempio di addizione):

Istruzioni precise (in linguaggio compreso da “il computer”) per un processo veloce, efficiente, “buono” che specifica le “mosse” del “computer” (macchina o umano, dotato delle necessarie informazioni e capacità interne) per trovare , decodifica e quindi elabora gli interi di ingresso arbitrario / simboli m e n, i simboli + e = … e “efficacemente” producono, in un tempo “ragionevole”, l’intero di output y in un punto specificato e in un formato specificato.
Il concetto di algoritmo è anche usato per definire la nozione di decidibilità. Questa nozione è fondamentale per spiegare come nascono i sistemi formali a partire da un piccolo insieme di assiomi e regole. Nella logica, il tempo che un algoritmo richiede di completare non può essere misurato, in quanto non è apparentemente correlato con la nostra dimensione fisica consueta. Da tali incertezze, che caratterizzano il lavoro in corso, deriva l’indisponibilità di una definizione di algoritmo che si adatta sia all’uso concreto (in un certo senso) che astratto del termine.

Formalizzazione
Gli algoritmi sono essenziali per il modo in cui i computer elaborano i dati. Molti programmi per computer contengono algoritmi che descrivono le istruzioni specifiche che un computer deve eseguire (in un ordine specifico) per svolgere un’attività specifica, come il calcolo degli stipendi dei dipendenti o la stampa delle pagelle degli studenti. Pertanto, un algoritmo può essere considerato come una qualsiasi sequenza di operazioni che può essere simulata da un sistema Turing-completo. Gli autori che sostengono questa tesi includono Minsky (1967), Savage (1987) e Gurevich (2000):

Minsky: “Ma manterremo anche, con Turing … che qualsiasi procedura che possa essere chiamata” naturalmente “efficace, può in realtà essere realizzata da una (semplice) macchina. Anche se questo può sembrare estremo, gli argomenti … il suo favore è difficile da confutare “.

Gurevich: “… L’argomentazione informale di Turing a favore della sua tesi giustifica una tesi più forte: ogni algoritmo può essere simulato da una macchina di Turing … secondo Savage [1987], un algoritmo è un processo computazionale definito da una macchina di Turing” .

In genere, quando un algoritmo è associato all’elaborazione delle informazioni, i dati possono essere letti da una sorgente di input, scritti su un dispositivo di output e memorizzati per un’ulteriore elaborazione. I dati memorizzati sono considerati parte dello stato interno dell’entità che esegue l’algoritmo. In pratica, lo stato è memorizzato in una o più strutture di dati.

Per alcuni di questi processi computazionali, l’algoritmo deve essere rigorosamente definito: specificato nel modo in cui si applica in tutte le possibili circostanze che potrebbero sorgere. Cioè, tutti i passaggi condizionali devono essere sistematicamente trattati, caso per caso; i criteri per ciascun caso devono essere chiari (e calcolabili).

Poiché un algoritmo è un elenco preciso di passaggi precisi, l’ordine di calcolo è sempre cruciale per il funzionamento dell’algoritmo. Si presume che le istruzioni siano elencate in modo esplicito e che siano descritte come “dall’inizio” e “giù fino in fondo”, un’idea che viene descritta in modo più formale dal flusso di controllo.

Finora, questa discussione sulla formalizzazione di un algoritmo ha assunto le premesse della programmazione imperativa. Questa è la concezione più comune e tenta di descrivere un’attività in modo discreto, “meccanico”. Unico a questa concezione di algoritmi formalizzati è l’operazione di assegnazione, che imposta il valore di una variabile. Deriva dall’intuizione della “memoria” come graffio. C’è un esempio sotto di tale incarico.

Per alcune concezioni alternative di ciò che costituisce un algoritmo vedi programmazione funzionale e programmazione logica.

Esprimere algoritmi
Gli algoritmi possono essere espressi in molti tipi di notazione, inclusi linguaggi naturali, pseudocodici, diagrammi di flusso, grafici di drakon, linguaggi di programmazione o tabelle di controllo (elaborati da interpreti). Le espressioni in linguaggio naturale degli algoritmi tendono ad essere verbose e ambigue e sono raramente utilizzate per algoritmi complessi o tecnici. Pseudocodice, diagrammi di flusso, diagrammi di drenaggio e tabelle di controllo sono modi strutturati per esprimere algoritmi che evitano molte delle ambiguità comuni nelle dichiarazioni in linguaggio naturale. I linguaggi di programmazione sono principalmente concepiti per esprimere algoritmi in una forma che può essere eseguita da un computer, ma sono spesso usati come un modo per definire o documentare algoritmi.

C’è una grande varietà di rappresentazioni possibili e si può esprimere un dato programma di macchina di Turing come una sequenza di tabelle macchina (vedi di più su macchina a stati finiti, tabella di transizione di stato e tabella di controllo), come diagrammi di flusso e diagrammi di Drakon (vedi più a diagramma di stato), o come una forma di codice macchina o codice di assemblaggio rudimentale chiamato “serie di quadrupli” (vedi più sulla macchina di Turing).

Le rappresentazioni di algoritmi possono essere classificate in tre livelli accettati della descrizione della macchina di Turing:

1 descrizione di alto livello
“… prosa per descrivere un algoritmo, ignorando i dettagli di implementazione: a questo livello non è necessario menzionare come la macchina gestisce il nastro o la testa”.
2 Descrizione di implementazione
“… prosa usata per definire il modo in cui la macchina di Turing usa la sua testa e il modo in cui memorizza i dati sul suo nastro.A questo livello non forniamo dettagli di stati o funzioni di transizione.”
3 Descrizione formale
Il più dettagliato, “livello più basso”, fornisce la “tabella di stato” della macchina di Turing.
Per un esempio dell’algoritmo semplice “Aggiungi m + n” descritto in tutti e tre i livelli, vedere Algoritmo # Esempi.

Implementazione
La maggior parte degli algoritmi sono pensati per essere implementati come programmi per computer. Tuttavia, gli algoritmi sono implementati anche con altri mezzi, come in una rete neurale biologica (ad esempio, il cervello umano che implementa l’aritmetica o un insetto in cerca di cibo), in un circuito elettrico o in un dispositivo meccanico.

Algoritmi informatici
Nei sistemi informatici, un algoritmo è fondamentalmente un’istanza di logica scritta nel software dagli sviluppatori di software per essere efficace per i computer “target” desiderati per produrre l’output da un dato input (forse nullo). Un algoritmo ottimale, anche con hardware vecchio, produrrebbe risultati più veloci di un algoritmo non ottimale (complessità temporale più elevata) per lo stesso scopo, eseguito in hardware più efficiente; ecco perché gli algoritmi, come l’hardware del computer, sono considerati tecnologia.

Programmi “eleganti” (compatti), programmi “buoni” (veloci): la nozione di “semplicità ed eleganza” appare informalmente in Knuth e precisamente in Chaitin:

Knuth: “… vogliamo buoni algoritmi in un senso estetico definito in modo approssimativo … Un criterio … è il tempo impiegato per eseguire l’algoritmo … Altri criteri sono l’adattabilità dell’algoritmo ai computer, la sua semplicità ed eleganza , eccetera”
Chaitin: “… un programma è ‘elegante’, con il quale intendo dire che è il più piccolo programma possibile per produrre l’output che fa”
Chaitin prefigura la sua definizione con: “Mostrerò che non puoi provare che un programma è ‘elegante'” – una tale prova risolverebbe il problema di Halting (ibid).

Algoritmo contro funzione calcolabile da un algoritmo: Per una data funzione possono esistere più algoritmi. Questo è vero, anche senza espandere il set di istruzioni disponibile disponibile per il programmatore. Rogers osserva che “è importante distinguere tra la nozione di algoritmo, cioè la procedura e la nozione di funzione calcolabile dall’algoritmo, cioè la mappatura resa dalla procedura, la stessa funzione può avere diversi algoritmi”.

Sfortunatamente potrebbe esserci un compromesso tra bontà (velocità) ed eleganza (compattezza) – un programma elegante potrebbe richiedere più passaggi per completare un calcolo rispetto a uno meno elegante. Un esempio che utilizza l’algoritmo di Euclid appare sotto.

Computer (e computatori), modelli di calcolo: un computer (o “computor” umano) è un tipo limitato di macchina, un “dispositivo meccanico deterministico discreto” che segue ciecamente le sue istruzioni. I modelli primitivi di Melzak e Lambek hanno ridotto questa nozione a quattro elementi: (i) posizioni distinte e distinguibili, (ii) contatori discreti e indistinguibili (iii) un agente e (iv) un elenco di istruzioni che sono efficaci rispetto alla capacità del agente.

Simulazione di un algoritmo: linguaggio del computer (computatore): Knuth consiglia al lettore che “il modo migliore per imparare un algoritmo è provarlo … prendere immediatamente carta e penna e utilizzare un esempio”. Ma che dire di una simulazione o esecuzione della cosa reale? Il programmatore deve tradurre l’algoritmo in un linguaggio che il simulatore / computer / computatore può effettivamente eseguire. Stone ne fornisce un esempio: quando si calcolano le radici di un’equazione quadratica, il computor deve sapere come prendere una radice quadrata. In caso contrario, l’algoritmo, per essere efficace, deve fornire una serie di regole per l’estrazione di una radice quadrata.

Ciò significa che il programmatore deve conoscere un “linguaggio” efficace rispetto all’agente di calcolo di destinazione (computer / computatore).

Analisi algoritmica
È spesso importante sapere quanta parte di una particolare risorsa (come il tempo o lo spazio di archiviazione) è teoricamente richiesta per un determinato algoritmo. Sono stati sviluppati metodi per l’analisi degli algoritmi per ottenere tali risposte quantitative (stime); per esempio, l’algoritmo di ordinamento sopra ha un requisito di tempo di O (n), usando la notazione O grande con n come la lunghezza della lista. In ogni momento l’algoritmo deve solo ricordare due valori: il numero più grande trovato finora e la sua posizione corrente nella lista di input. Pertanto, si dice che abbia uno spazio richiesto da O (1), se lo spazio richiesto per memorizzare i numeri di input non viene contato, o O (n) se viene contato.

Formale contro empirico
L’analisi e lo studio degli algoritmi è una disciplina dell’informatica, ed è spesso praticata in modo astratto senza l’uso di un linguaggio di programmazione o implementazione specifici. In questo senso, l’analisi algoritmica assomiglia ad altre discipline matematiche in quanto si concentra sulle proprietà sottostanti dell’algoritmo e non sulle specifiche di una particolare implementazione. Di solito lo pseudocodice viene utilizzato per l’analisi in quanto è la rappresentazione più semplice e più generale. Tuttavia, in definitiva, la maggior parte degli algoritmi viene solitamente implementata su particolari piattaforme hardware / software e la loro efficienza algoritmica viene infine messa alla prova utilizzando codice reale. Per la soluzione di un problema “una tantum”, l’efficienza di un particolare algoritmo potrebbe non avere conseguenze significative (a meno che n sia estremamente grande) ma per algoritmi progettati per un utilizzo scientifico interattivo, commerciale o di lunga durata può essere critico. Il ridimensionamento da piccolo a grande n espone frequentemente algoritmi inefficienti altrimenti benigni.

Efficienza di esecuzione
Per illustrare i possibili miglioramenti possibili anche in algoritmi ben consolidati, una recente innovazione significativa, relativa agli algoritmi FFT (utilizzata pesantemente nel campo dell’elaborazione delle immagini), può ridurre i tempi di elaborazione fino a 1.000 volte per applicazioni come l’imaging medico. In generale, i miglioramenti della velocità dipendono dalle proprietà speciali del problema, che sono molto comuni nelle applicazioni pratiche. Speedup di questa portata consentono di utilizzare dispositivi di elaborazione che fanno ampio uso dell’elaborazione delle immagini (come fotocamere digitali e apparecchiature mediche) per consumare meno energia.

Classificazione
Esistono vari modi per classificare gli algoritmi, ciascuno con i propri meriti.

Per implementazione
Un modo per classificare gli algoritmi è tramite mezzi di implementazione.

ricorsione
Un algoritmo ricorsivo è uno che invoca (fa riferimento a) se stesso ripetutamente fino a quando una certa condizione (nota anche come condizione di terminazione) corrisponde, che è un metodo comune alla programmazione funzionale. Gli algoritmi iterativi utilizzano costrutti ripetitivi come loop e talvolta strutture di dati aggiuntive come stack per risolvere i problemi indicati. Alcuni problemi sono naturalmente adatti per un’implementazione o l’altra. Ad esempio, le torri di Hanoi sono ben comprese utilizzando l’implementazione ricorsiva. Ogni versione ricorsiva ha una versione iterativa equivalente (ma probabilmente più o meno complessa) e viceversa.

Logico
Un algoritmo può essere visto come deduzione logica controllata. Questa nozione può essere espressa come: Algorithm = logic + control. Il componente logico esprime gli assiomi che possono essere utilizzati nel calcolo e la componente di controllo determina il modo in cui la detrazione viene applicata agli assiomi. Questa è la base per il paradigma della programmazione logica. Nei linguaggi di programmazione pura logica il componente di controllo è fisso e gli algoritmi vengono specificati fornendo solo il componente logico. L’attrattiva di questo approccio è l’elegante semantica: un cambiamento negli assiomi ha un cambiamento ben definito nell’algoritmo.

Seriale, parallelo o distribuito
Gli algoritmi vengono solitamente discussi con l’assunto che i computer eseguano un’istruzione di un algoritmo alla volta. Quei computer sono talvolta chiamati computer seriali. Un algoritmo progettato per tale ambiente è chiamato algoritmo seriale, al contrario di algoritmi paralleli o algoritmi distribuiti. Gli algoritmi paralleli sfruttano le architetture dei computer in cui più processori possono lavorare contemporaneamente su un problema, mentre gli algoritmi distribuiti utilizzano più macchine collegate a una rete di computer. Gli algoritmi paralleli o distribuiti dividono il problema in sottoproblemi più simmetrici o asimmetrici e raccolgono i risultati insieme. Il consumo di risorse in tali algoritmi non è solo i cicli del processore su ciascun processore, ma anche il sovraccarico di comunicazione tra i processori. Alcuni algoritmi di ordinamento possono essere parallelizzati in modo efficiente, ma il loro sovraccarico di comunicazione è costoso. Gli algoritmi iterativi sono generalmente parallelizzabili. Alcuni problemi non hanno algoritmi paralleli e sono chiamati problemi intrinsecamente seriali.

Deterministico o non deterministico
Gli algoritmi deterministici risolvono il problema con una decisione esatta ad ogni passo dell’algoritmo mentre gli algoritmi non deterministici risolvono i problemi tramite l’indovinare, sebbene le ipotesi tipiche siano rese più accurate attraverso l’uso dell’euristica.

Esatto o approssimativo
Mentre molti algoritmi raggiungono una soluzione esatta, gli algoritmi di approssimazione cercano un’approssimazione più vicina alla vera soluzione. L’approssimazione può essere raggiunta usando una strategia deterministica o casuale. Tali algoritmi hanno valore pratico per molti problemi difficili. Uno degli esempi di un algoritmo approssimativo è il problema dello zaino. Il problema dello zaino è un problema in cui esiste un insieme di elementi dati. L’obiettivo del problema è quello di mettere in valigia lo zaino per ottenere il massimo valore totale. Ogni oggetto ha un certo peso e un certo valore. Il peso totale che possiamo trasportare non è più di un numero fisso X. Pertanto, dobbiamo considerare il peso degli articoli e il loro valore.

Algoritmo quantistico
Corrono su un modello realistico di computazione quantistica. Il termine è solitamente usato per quegli algoritmi che sembrano intrinsecamente quantici, o usano alcune caratteristiche essenziali del calcolo quantistico come la sovrapposizione quantistica o l’entanglement quantistico.

Per paradigma del design
Un altro modo per classificare gli algoritmi è la loro metodologia di progettazione o paradigma. Esiste un certo numero di paradigmi, ciascuno diverso dall’altro. Inoltre, ciascuna di queste categorie include molti diversi tipi di algoritmi. Alcuni paradigmi comuni sono:

Ricerca a forza bruta o esauriente
Questo è il metodo ingenuo di provare ogni possibile soluzione per vedere quale è il migliore.

Dividere e conquistare
Un algoritmo divide et impera riduce ripetutamente un’istanza di un problema a una o più istanze più piccole dello stesso problema (di solito in modo ricorsivo) fino a quando le istanze sono sufficientemente piccole da essere risolte facilmente. Uno di questi esempi di divisione e conquista è l’ordinamento di fusione. L’ordinamento può essere fatto su ogni segmento di dati dopo aver diviso i dati in segmenti e l’ordinamento di interi dati può essere ottenuto nella fase di conquista unendo i segmenti. Una variante più semplice di divide et impera è chiamata algoritmo di riduzione e conquista, che risolve un sottoprocesso identico e utilizza la soluzione di questo sottoproblema per risolvere il problema più grande. Dividere e conquistare divide il problema in più sottoproblemi e quindi lo stadio di conquista è più complesso degli algoritmi di riduzione e conquista. Un esempio di algoritmo di riduzione e conquista è l’algoritmo di ricerca binaria.

Ricerca ed enumerazione
Molti problemi (come il gioco degli scacchi) possono essere modellati come problemi sui grafici. Un algoritmo di esplorazione del grafico specifica le regole per lo spostamento di un grafico ed è utile per tali problemi. Questa categoria include anche algoritmi di ricerca, enumerazione di rami e rilanci e backtracking.
Algoritmo randomizzato

Riduzione della complessità
Questa tecnica implica la risoluzione di un problema difficile trasformandolo in un problema più noto per il quale abbiamo (si spera) algoritmi asintoticamente ottimali. L’obiettivo è trovare un algoritmo di riduzione la cui complessità non sia dominata dall’algoritmo ridotto risultante. Ad esempio, un algoritmo di selezione per trovare la mediana in una lista non ordinata implica prima ordinare l’elenco (la parte costosa) e quindi estrarre l’elemento intermedio nella lista ordinata (la porzione economica). Questa tecnica è anche conosciuta come trasformazione e conquista.

Problemi di ottimizzazione
Per problemi di ottimizzazione esiste una classificazione più specifica degli algoritmi; un algoritmo per tali problemi può rientrare in una o più delle categorie generali descritte sopra e in uno dei seguenti:

Programmazione lineare
Quando si ricercano soluzioni ottimali per una funzione lineare legata a vincoli di uguaglianza lineare e disuguaglianza, i vincoli del problema possono essere utilizzati direttamente per produrre le soluzioni ottimali. Esistono algoritmi in grado di risolvere qualsiasi problema in questa categoria, come il popolare algoritmo del simplesso. I problemi che possono essere risolti con la programmazione lineare includono il problema massimo di flusso per i grafici diretti. Se un problema richiede inoltre che una o più delle incognite debbano essere un numero intero, allora viene classificata nella programmazione di numeri interi. Un algoritmo di programmazione lineare può risolvere tale problema se si può dimostrare che tutte le restrizioni per i valori interi sono superficiali, cioè le soluzioni soddisfano comunque queste restrizioni. Nel caso generale, viene utilizzato un algoritmo specializzato o un algoritmo che trova soluzioni approssimative, a seconda della difficoltà del problema.
Programmazione dinamica

Quando un problema mostra sottostrutture ottimali – ovvero la soluzione ottimale a un problema può essere costruita da soluzioni ottimali a sottoproblemi – e sottoproblemi sovrapposti, il che significa che gli stessi sottoproblemi vengono usati per risolvere molte diverse istanze di problema, un approccio più rapido chiamato programmazione dinamica evita di ricalcolare soluzioni che sono già stati calcolati Ad esempio, l’algoritmo di Floyd-Warshall, il percorso più breve verso un obiettivo da un vertice in un grafico ponderato può essere trovato utilizzando il percorso più breve verso l’obiettivo da tutti i vertici adiacenti. La programmazione dinamica e la memoizzazione vanno di pari passo. La differenza principale tra programmazione dinamica e divisione e conquista è che i sottoproblemi sono più o meno indipendenti in divisione e conquista, mentre i sottoproblemi si sovrappongono nella programmazione dinamica. La differenza tra la programmazione dinamica e la ricorsione diretta è nella memorizzazione nella cache o nella memoizzazione delle chiamate ricorsive. Quando i sottoproblemi sono indipendenti e non c’è ripetizione, la memoizzazione non aiuta; quindi la programmazione dinamica non è una soluzione per tutti i problemi complessi. Usando la memoizzazione o mantenendo una tabella di sottoproblemi già risolti, la programmazione dinamica riduce la natura esponenziale di molti problemi alla complessità polinomiale.

Il metodo goloso
Un algoritmo avido è simile a un algoritmo di programmazione dinamica in quanto funziona esaminando le sottostrutture, in questo caso non del problema ma di una determinata soluzione. Tali algoritmi iniziano con una soluzione, che può essere data o costruita in qualche modo, e migliorarla apportando piccole modifiche. Per alcuni problemi possono trovare la soluzione ottimale mentre per altri si fermano a optima locale, cioè a soluzioni che non possono essere migliorate dall’algoritmo ma non sono ottimali. L’uso più diffuso di algoritmi greedy è la ricerca dello spanning tree minimo in cui trovare la soluzione ottimale è possibile con questo metodo. Huffman Tree, Kruskal, Prim, Sollin sono algoritmi avidi che possono risolvere questo problema di ottimizzazione.

Il metodo euristico
Nei problemi di ottimizzazione, gli algoritmi euristici possono essere utilizzati per trovare una soluzione vicina alla soluzione ottimale nei casi in cui non è possibile trovare la soluzione ottimale. Questi algoritmi funzionano avvicinandosi sempre più alla soluzione ottimale man mano che progrediscono. In linea di principio, se corrono per una quantità infinita di tempo, troveranno la soluzione ottimale. Il loro merito è che possono trovare una soluzione molto vicina alla soluzione ottimale in un tempo relativamente breve. Tali algoritmi includono ricerca locale, ricerca tabu, ricottura simulata e algoritmi genetici. Alcuni di essi, come la ricottura simulata, sono algoritmi non deterministici mentre altri, come la ricerca tabu, sono deterministici. Quando è noto un limite all’errore della soluzione non ottimale, l’algoritmo viene ulteriormente classificato come un algoritmo di approssimazione.

Per settore di studio
Ogni campo della scienza ha i suoi problemi e ha bisogno di algoritmi efficienti. I problemi correlati in un campo sono spesso studiati insieme. Alcune classi di esempio sono algoritmi di ricerca, algoritmi di ordinamento, algoritmi di fusione, algoritmi numerici, algoritmi di calcolo, algoritmi geometrici computazionali, algoritmi combinatori, algoritmi medici, apprendimento automatico, crittografia, algoritmi di compressione dati e tecniche di analisi.

I campi tendono a sovrapporsi l’uno con l’altro e gli avanzamenti dell’algoritmo in un campo possono migliorare quelli di altri campi, a volte completamente non correlati. Ad esempio, la programmazione dinamica è stata inventata per l’ottimizzazione del consumo di risorse nell’industria, ma ora viene utilizzata per risolvere una vasta gamma di problemi in molti campi.

Dalla complessità
Gli algoritmi possono essere classificati in base alla quantità di tempo che devono essere completati rispetto alla loro dimensione di input:

Tempo costante: se il tempo richiesto dall’algoritmo è lo stesso, indipendentemente dalla dimensione dell’input. Per esempio. un accesso a un elemento dell’array.
Tempo lineare: se il tempo è proporzionale alla dimensione dell’input. Per esempio. la traversa di una lista.
Tempo logaritmico: se il tempo è una funzione logaritmica della dimensione di input. Per esempio. algoritmo di ricerca binaria.
Tempo polinomiale: se il tempo è un potere della dimensione di input. Per esempio. l’algoritmo di ordinamento delle bolle ha una complessità quadratica temporale.
Tempo esponenziale: se il tempo è una funzione esponenziale della dimensione di input. Per esempio. Ricerca forza bruta.
Alcuni problemi possono avere più algoritmi di diversa complessità, mentre altri problemi potrebbero non avere algoritmi o algoritmi efficienti noti. Ci sono anche mappature da alcuni problemi ad altri problemi. A causa di ciò, è stato trovato più adatto a classificare i problemi stessi anziché gli algoritmi in classi di equivalenza basate sulla complessità dei migliori algoritmi possibili per loro.

Algoritmi continui
L’aggettivo “continuo” quando applicato alla parola “algoritmo” può significare:

Un algoritmo che opera su dati che rappresentano quantità continue, anche se questi dati sono rappresentati da approssimazioni discrete – tali algoritmi sono studiati in analisi numerica; o
Un algoritmo sotto forma di un’equazione differenziale che opera continuamente sui dati, in esecuzione su un computer analogico.