Darò la stessa risposta che ho dato la volta precedente in cui è stata posta questa domanda.

Innanzitutto, tieni presente che non esiste una buona definizione formale di “algoritmo” al momento della scrittura. La parola chiave qui è “formale”.

Tuttavia, ci sono persone intelligenti che ci lavorano.

Quello che sappiamo è che qualunque sia un “algoritmo”, si trova da qualche parte tra “funzione matematica” e “programma per computer”.

Una funzione matematica è nozione formale di una mappatura dagli input agli output. Quindi, ad esempio, “sort” è una mappatura tra una sequenza di elementi ordinabili e una sequenza di elementi ordinabili dello stesso tipo, che mappa ogni sequenza alla sua sequenza ordinata. Questa funzione potrebbe essere implementato utilizzando algoritmi differenti (es. merge sort, heap sort) Ciascun algoritmo, a sua volta, potrebbe essere implementato utilizzando programmi diversi (anche con lo stesso linguaggio di programmazione).

Quindi il miglior controllo che abbiamo su cosa sia un “algoritmo” è che è una sorta di classe di equivalenza sui programmi, dove due i programmi sono equivalenti se fanno “essenzialmente la stessa cosa”. Qualsiasi due programmi che implementano lo stesso algoritmo devono calcolare la stessa funzione, ma il contrario non è vero.

Allo stesso modo, esiste una classe di equivalenza tra algoritmi, dove due algoritmi sono equivalenti se calcolano la stessa funzione matematica .

La parte difficile in tutto questo è cercare di catturare ciò che intendiamo per “essenzialmente la stessa cosa”.

Ci sono alcune cose ovvie che dovremmo includere. Ad esempio, due programmi sono essenzialmente gli stessi se differiscono solo per la ridenominazione delle variabili. La maggior parte dei modelli di linguaggi di programmazione ha nozioni native di “equivalenza” (ad es. Riduzione beta e conversione eta nel lambda calcolo), quindi dovremmo inserire anche quelle.

Qualunque relazione di equivalenza scegliamo, questo ci dà una struttura . Gli algoritmi formano una categoria in virtù del fatto che sono la categoria quoziente dei programmi. È noto che alcune interessanti relazioni di equivalenza danno origine a strutture categoriali interessanti; per esempio, la categoria degli algoritmi ricorsivi primitivi è un oggetto universale nella categoria delle categorie. Ogni volta che vedi una struttura interessante come questa, sai che questa riga di richiesta sarà probabilmente utile.

Commenti

• Grazie per la tua risposta precisa, solo unaltra domanda. Se consideriamo qualsiasi programma, indipendentemente da ciò che fa, ottengono comunque alcuni input e seguono alcune istruzioni e danno alcuni risultati mentre vengono eseguiti. Possono anche non ‘ risolvere alcun problema (come lo chiamiamo), ma è pur sempre una mappatura. potrebbero essere algoritmi noti, intendo qualsiasi programma?
• Se ‘ ti leggo correttamente, ‘ chiedo se una definizione formale di un ” algoritmo ” debba o meno prevedere la condizione che deve essere ” utile “. Direi ” no “, se non altro perché ‘ è impossibile formalizzarlo nozione.
• scusa! il mio inglese non va bene, allora dici ” no ” a cosa? ammetti che ‘ è impossibile formalizzare lutilità di un programma e, per definizione, qualsiasi programma è un algoritmo? o dici che ‘ è necessario che si consideri lutilità accanto allalgoritmo?
• Non ‘ penso che una definizione formale di un ” algoritmo ” dovrebbe richiedere che sia utile, perché ” useful ” può ‘ t essere definito formalmente.
• La tua risposta è la più utile in questo thread +1. Credo che per ” essenzialmente la stessa cosa “, intendi ” semanticamente equivalente “. Inoltre, penso che tutti i programmi siano essenzialmente algoritmi (come dice OP), poiché tutti i programmi sono implementazioni che mappano un input su un output, anche se questa mappatura è implicita. Come hai affermato, tutto dipende dalla prospettiva.

In definitiva, la differenza è di prospettiva . Un programma è un programma: una sequenza di istruzioni in un linguaggio, forse un linguaggio di programmazione o istruzioni a livello di macchina. Gli algoritmi sono generalmente descritti a un livello superiore rispetto alle istruzioni della macchina o alle dichiarazioni del linguaggio di programmazione, ma quanto alto sia un livello piuttosto flessibile. Ad esempio, in alcune circostanze, “Ordina larray, quindi guarda lelemento $ k $ th” è una descrizione perfettamente valida di un algoritmo per trovare loggetto $ k $ th più grande in un array; in altre circostanze, potresti voler specificare molti più dettagli su come avviene lordinamento.

Come dici tu, un algoritmo è qualcosa come “un processo o un insieme di regole da seguire nei calcoli o altri problemi -risolvere le operazioni, soprattutto da un computer. ” Quindi, letteralmente parlando, ogni programma è un algoritmo. Di solito, però, si parla di programmi che implementano algoritmi. Di solito, quando descriviamo un algoritmo, evitiamo i dettagli di basso livello di come esattamente le cose vengono implementate, assumendo che un programmatore competente sarebbe in grado di implementarlo nella lingua che preferisce.

Commenti

• Penso che la precisione dellalgoritmo sia correlata al concetto di matematica, lambda-calcolo o macchina di Turing, ancora non ‘ non so cosa sia linguaggio di astrazione? matematica o un linguaggio naturale con molte affermazioni sfocate
• @Ahmad Algorithm è un concetto informale. Non ha una definizione formale. In un certo senso, ‘ è come una dimostrazione matematica, che è diversa da una dimostrazione formale in un sistema di dimostrazione formale. Riteniamo che le dimostrazioni informali possano essere ” arricchite ” in prove formali in qualsiasi sistema di dimostrazione formale scelto (abbastanza forte), proprio come qualsiasi lalgoritmo può essere completamente implementato in qualsiasi linguaggio di programmazione (Turing-complete).

Algoritmi in Turing -La mentalità completa è solitamente specificata da input e output. I programmi reali fanno di più; essi

• comunicano con lutente,
• comunicano con altre macchine,
• reagiscono allambiente,
• non terminano e sono ancora utili,

e altro ancora. Queste cose di solito non sono considerate negli algoritmi o nella teoria del calcolo, ma sono essenziali per la maggior parte dei programmi.

Commenti

• Questo è un ottimo punto. Ma intendi qualcosa come ” solitamente specificato come mezzo per mappare linput alloutput “? Basta specificare linput e loutput ‘ t abbastanza: ad esempio, mergesort e quicksort producono lo stesso output da qualsiasi input ma non sono ‘ considerati essere lo stesso algoritmo.
• @DavidRicherby stavo pensando alla specifica nel senso PL; non ‘ specifichiamo nientaltro, quindi gli algoritmi potrebbero non fare nientaltro. Ovviamente, dobbiamo fornire più delle specifiche per descrivere un algoritmo concreto.
• Aspetti positivi, ma se ammettiamo che alla fine qualsiasi programma è un algoritmo, non ‘ Non so come gli argomenti che hai affrontato vengono misurati su un algoritmo. Forse un argomento di intelligenza artificiale ?!
• Chi lo ammetterebbe e perché? E cosa intendi per misura qui? (E certamente non ‘ t vedere langolo di intelligenza artificiale qui.)
• @Raphael posso ammetterlo (guardando la sintassi, tutti i programmi sembrano simili, sono sequenze di istruzioni, o mappatura dellinput alloutput), semplicemente non ‘ so come sia possibile estrarre altre caratteristiche di un programma (quelle a cui si è parlato) da quella definizione. ad esempio la differenza tra ordinamento rapido e MATLAB o Windows Media Player !!

• Un algoritmo è un approccio sistematico alla risoluzione di un problema specifico.

• Un programma è un insieme di istruzioni che un computer deve seguire.

Un programma quindi non ha nemmeno bisogno di risolvere un problema.Sono sicuro che tutti possiamo pensare a diversi programmi che hanno causato più problemi di quanti ne abbiano risolti. Un programma può essere unimplementazione di molti algoritmi oppure un algoritmo può essere implementato collegando insieme molti programmi. Un programma può anche non contenere algoritmi. Ad esempio, il programma vuoto che semplicemente esce, o forse anche un Hello World, potrebbe essere considerato un programma senza algoritmo.

Poiché un algoritmo risolve un problema specifico, si concentra su un intero concetto specifico. Un algoritmo fornisce quindi passaggi astratti per elaborare un insieme di informazioni correlate in un diverso insieme di informazioni derivate. Un programma non richiede affatto che i suoi componenti siano concettualmente correlati. Ad esempio, un programma può avere un easter egg, ma una cosa chiamata propriamente algoritmo non dovrebbe. Puoi avere un virus o un trojan in agguato in un programma, ma non in un algoritmo. Il più vicino possibile a un algoritmo sarebbe qualcosa di simile a una backdoor in un algoritmo di crittografia, in cui il difetto pianificato fa parte della relazione di informazioni stabilita dallalgoritmo.

E infine, un programma, così comè abbreviazione di un programma per computer, tautologicamente richiede un computer. Un algoritmo no. Se separo sistematicamente camicie, pantaloni e calzini dal mio bucato prima di metterli via, questo è un algoritmo. Si occupa di input e output correlati, può essere descritto in un diagramma di flusso e ha conseguenze calcolabili in termini di efficienza (ad esempio, il numero di capi di abbigliamento che devono essere confrontati per trovare calzini corrispondenti).

Un algoritmo è un concetto o unidea. È un approccio formale per risolvere un problema. Gli algoritmi possono essere espressi o implementati in una varietà di linguaggi di programmazione (di solito, quasi tutti i linguaggi possono implementare qualsiasi algoritmo). Per alcuni esempi dovresti leggere gli algoritmi di ordinamento su Wikipedia.

Un programma per computer è una sequenza specifica di istruzioni in un linguaggio di programmazione specifico . Un programma può contenere limplementazione di molti algoritmi. Excel è un programma, ma le sue capacità di ordinamento sono la manifestazione di un algoritmo.

Un algoritmo è un insieme autonomo di operazioni passo passo da eseguire per risolvere un problema specifico o una classe di problemi.

Un programma per computer è una sequenza di istruzioni che rispettano le regole di uno specifico linguaggio di programmazione, scritte per eseguire unattività specifica con un computer.

Gli algoritmi sono generali e devono essere tradotti in un linguaggio di programmazione specifico (implementato).

Commenti

• Ma il punto centrale della domanda è che un programma (o il suo codice sorgente o il binario compilato ) è ” un insieme autonomo di operazioni passo passo da eseguire per risolvere un problema specifico o una classe di problemi. ”
• Ma non è ‘ t. Un programma non è Quelle operazioni, ma una loro implementazione : qualcosa che le esegue in un particolare contesto. Per esempio. lutility Unix sort non è un algoritmo di ordinamento, ma utilizza un algoritmo di ordinamento.

Un algoritmo esprime la nostra idea o soluzione per un problema specifico in un approccio graduale. È solo un approccio comprensibile per la risoluzione di problemi e dalluomo non per il sistema informatico

Il programma è istruzioni passo passo implementate per la risoluzione dei problemi dal sistema informatico. Deve essere comprensibile non solo dal programmatore ma anche dal computer.

Commenti

• Benvenuto in Computer Science Stack Exchange. Leggi cs.stackexchange.com/tour.if non lhai ancora fatto.

Le altre risposte qui, credo, perdono un punto importante. La definizione di “algoritmo” che mi è stata insegnata includeva il requisito che la procedura si interrompesse su tutti gli input . Naturalmente questo fa di “programma” una classe di procedure più ampia di “algoritmo”, poiché alcuni programmi si arrestano su tutti gli input e altri no.

Commenti

• Questo non è universale. La definizione che mi è stata insegnata non ‘ includeva tale requisito.

Ecco un paio di modi per tracciare la linea tra un algoritmo e un programma:

Scopo significativo

I programmi sono scritti con uno scopo e rappresentano un tentativo di raggiungere un obbiettivo. Gli algoritmi possono essere visti come strumenti per raggiungere questo obiettivo.

Ad es. un cacciavite è un algoritmo per modificare lo stato di una vite ma il cacciavite stesso non ha uno scopo per farlo.Lo scopo è nella testa delloperatore cacciavite che tiene il programma come se mettesse degli scaffali.

Logica aziendale

Questo punto è fortemente correlato allo scopo di un programma. Poiché i programmi hanno uno scopo, inevitabilmente contengono frammenti di mondo reale come date specifiche, misurazioni, tecnologie, nomi ecc.

Gli algoritmi daltra parte non contengono né logica di business né bit di mondo reale e invece di operare su valori specifici operano sulle variabili.

Ad esempio in questo senso è possibile confrontare una funzione matematica come f(x) = x^2 che è astratta e opera su variabili con una ricetta di cucina che contiene valori precisi (almeno uno di riferimento).

Risultato

Questo punto è fortemente correlato alla logica di business di un programma. Un agente (come un utente di browser web) consuma il risultato di un programma e non il risultato di un algoritmo.

Ad es. il consumatore di una ricetta di cucina consuma la torta non il risultato della panna montata o del riscaldamento del forno.

Commenti

• Forse sarebbe meglio dire che il cacciavite ‘ non ha intenzione di girare le viti? Nellinglese di tutti i giorni, diremmo sicuramente che un cacciavite ha lo scopo di girare le viti: girare le viti è esattamente la cosa per cui è stato progettato.
• Inoltre, I ‘ Non sono sicuro di cosa intendi per ” logica aziendale ” (molti programmi non hanno nulla da fare con gli affari) o dicendo che un algoritmo ” non contiene né logica di business né bit del mondo reale “. Ad esempio, potrei benissimo formulare un algoritmo di percorso più breve in termini di città e strade piuttosto che vertici e bordi. Lalgoritmo ‘ non contiene ” … bit del mondo reale ” ?
• @DavidRicherby, hai ragione, la mia frase è ambigua. Quello che volevo dire è uno scopo significativo . Girare le viti per girare le viti è inutile così come ordinare un array che non viene mai utilizzato. Per logica aziendale intendo tutta la logica del programma ad eccezione della logica di utilità e dello stack tecnologico, ovvero tutta la logica che implementa effettivamente lo scopo del programma, ovvero la logica aziendale di cuocere una torta è mescolare ingredienti e cuocere e non include imparare a mescolare o cuocere ( che è la logica di utilità riutilizzata in questo caso).
• @DavidRicherby, come per bit di mondo reale , intendo attualizzazione cioè un programma a differenza di un algoritmo deve comunicare in qualche modo con il mondo fisico. Un algoritmo, daltra parte, può essere un concetto puramente matematico.

I Sono abbastanza sicuro che altre risposte siano abbastanza buone per prendere liniziativa, ma ecco come vedo la differenza tra un algoritmo e un programma

• Un algoritmo consiste semplicemente dei passaggi (indipendenti dalla macchina) che devono essere seguiti in un certo ordine per risolvere un problema.

• Un programma è un insieme di istruzioni per un tipo specifico di macchina per mettere in pratica un algoritmo .

Ad esempio.

Supponiamo che tu abbia un algoritmo che ha un passaggio per raggiungere un punto particolare prima di fare qualche altro passaggio Ora come questo passaggio verrà eseguito non è definito esattamente. Puoi scegliere di camminare o correre o prendere un autobus per farlo, ma dipende da come scegli di implementarlo (che è il tuo prog ram).

Puoi dire che un algoritmo è unastrazione di un programma, cioè manca i dettagli esatti ma delinea un piano per fare qualcosa .