Cos'è un algoritmo?

12

Che cos'è esattamente un algoritmo, come in Algorithm? Il piccolo capisco la parola, è che non è specifico per una lingua particolare, o un modello di progettazione, piuttosto è uno dei principi più basilari (quindi suppongo che questa domanda mi faccia sembrare stupida).

Una delle "opzioni" che ho di comprenderlo è che significa il metodo per ottenere qualcosa, che potrebbe essere scritto come una lista in pseudocodice.

Quando scrivo codice più complicato, penso a cosa si deve fare, con cosa e come ci arriverò (non in un linguaggio di programmazione), quindi scriverlo nel codice. È un buon modo per farlo, ed è qualcosa che ha a che fare con gli algoritmi?

(volevo chiedere qui piuttosto su Stackoverflow, perché non si tratta di un problema specifico / lingua più ho la sensazione che la maggior parte delle persone qui sappia il "perché", o almeno le risposte qui sono più dettagliate, piuttosto che su Stackoverflow dove è diverso, mi dispiace se avrei dovuto chiedere laggiù)

    
posta Jonathan. 17.04.2011 - 22:08
fonte

11 risposte

18

Un algoritmo è una sequenza finita di istruzioni ben definite per il calcolo di una funzione (o l'esecuzione di una procedura) che termina in uno stato finale ben definito.

    
risposta data 18.04.2011 - 01:01
fonte
14

Questa è in realtà una domanda piuttosto interessante, e in effetti è ancora una questione di ricerca aperta.

Yuri Gurevich, uno dei giganti di Algorithm Theory, sta attualmente dando una serie di video conferenze sul sito web della community di Microsoft Channel9:

Come puoi vedere, la tua stessa domanda è in realtà il titolo della seconda lezione. Tuttavia, ti consiglio vivamente di guardarli tutti e tre.

Il primo, in particolare, contiene un paio di esempi di algoritmi che invalidano praticamente tutte le definizioni date nella maggior parte delle altre risposte qui.

    
risposta data 18.04.2011 - 04:38
fonte
3

Un algoritmo è come una buona ricetta di cucina . Hai alcuni input, alcuni passaggi intermedi ben definiti e ottieni un risultato finale.

Applicato alla programmazione, è una descrizione univoca dei passaggi che devi risolvere per risolvere un particolare problema. Tutto ciò che puoi scrivere nel linguaggio di programmazione di tua scelta potrebbe essere visto come un algoritmo, ma in genere il termine viene utilizzato solo per attività logiche o matematiche comuni, come l'ordinamento o la ricerca.

    
risposta data 17.04.2011 - 22:21
fonte
2

Un algoritmo è un insieme di regole o processi (in un calcolo) usati per la risoluzione dei problemi. Fondamentalmente, c'è un problema, vuoi una soluzione, e il processo per questa soluzione è un algoritmo. Un algoritmo ha un insieme finito di regole / processi per raggiungere una soluzione.

Se sei come Edsger W. Dijkstra , scriverai il tuo algoritmo su un pezzo di carta e elaborare / rifinire l'algoritmo su carta finché non si è soddisfatti dei propri algoritmi. Altrimenti (specialmente quando si scrivono documentazioni), un diagramma di flusso viene utilizzato per rappresentare graficamente il flusso di un algoritmo / processo. Ciò consente ad altri di criticare il diagramma di flusso e migliorare se necessario (senza preoccuparsi di quale linguaggio di programmazione è necessario).

Non so se questo risponde alla tua domanda.

    
risposta data 17.04.2011 - 22:17
fonte
0

Se dovessi dare una definizione generale, direi che un algoritmo è una formula per risolvere un problema di calcolo che è più complesso di, e finisce per essere più efficiente di, l'ovvia / forza bruta soluzione.

Inoltre, è importante notare che un algoritmo non è un codice sorgente specifico; è lo stesso calcolo. Tra le altre cose, ciò significa che qualsiasi linguaggio completo di Turing può implementare qualsiasi algoritmo che qualsiasi altra lingua completa di Turing possa implementare.

    
risposta data 17.04.2011 - 22:18
fonte
0

Uso il termine per descrivere una formula per risolvere un problema specifico. La formula non deve necessariamente essere scritta in matematica o avere una relazione 1: 1 con un metodo. Algoritmi scolastici e strutture dati sono strettamente correlati e possono essere scritti come formule matematiche o dimostrazioni usando prove.

    
risposta data 17.04.2011 - 22:23
fonte
0

Un algoritmo è un'astrazione di un programma per computer e consiste in un insieme di istruzioni per ottenere alcune attività ben definite in un numero finito di passaggi, sebbene il limite sul conteggio dei passi potrebbe essere molto grande e le singole fasi potrebbero essere compiti complessi (finiti) a pieno titolo. Mentre ci sono programmi (corretti) che sono generalmente noti-non-algoritmici, funzionano tutti ripetendo pezzi algoritmici in qualche schema. (Più interessanti sono i programmi il cui stato di terminazione non è noto, ma la maggior parte dei programmatori non si occupa effettivamente di tali cose intenzionalmente, lo so che non lo faccio!)

    
risposta data 18.04.2011 - 02:37
fonte
0

Algoritmo: un insieme ben ordinato di operazioni che sono 1) non ambiguo e 2) efficacemente calcolabile tale che l'esecuzione delle operazioni a partire dal primo produce un risultato dopo un numero finito di operazioni.

    
risposta data 18.04.2011 - 05:25
fonte
0

IMO nessuno lo sa bene :) Ho visto il termine applicato solo alle funzioni di calcolo matematico, a qualsiasi funzione che prende input e produce output, ea qualsiasi che prende input ed esegue qualche tipo di operazione su di esso.

Considereresti / tutti i seguenti elementi come un algoritmo?

  1. Una funzione che calcola il tasso di interesse di un prestito su un periodo di 20 anni
  2. Logica di business che controlla se tutte le informazioni sono state inserite in un'applicazione di prestito
  3. Una funzione finder che interroga un database per un oggetto Cliente
  4. Una funzione "helper" che pulisce e formatta l'immissione di dati
  5. Una funzione che analizza un file XML e mappa i dati sugli oggetti business
  6. Una classe che prende input e li scrive in un file di testo
risposta data 22.04.2011 - 14:34
fonte
0

Un algoritmo è un'idea, un metodo, una tecnica, "intelligente" per il calcolo o l'esecuzione di un compito che è di natura astratta, ma mentre gira su computer nel mondo reale, noi aspiriamo perché utilizzi il minor numero possibile di risorse , che sono, nel mondo dei computer, Tempo e memoria.

    
risposta data 22.04.2011 - 17:44
fonte
0

Un algoritmo è una sequenza di passaggi ben definiti che producono un risultato in un tempo finito.

Passo ben definito: è qualcosa che puoi fare, o calcolare, che è definito con precisione. Solo leggendo il passo sai cosa devi fare e come farlo. Nello specifico, puoi scriverlo in un linguaggio di programmazione che conosci e assicurarti che il frammento del programma corrisponda esattamente al passo.

Sequenza: i passaggi vengono eseguiti in un ordine specificato. I passaggi possono essere eseguiti più volte a seconda dei dati (cicli) o non eseguiti affatto a seconda dei dati (se le istruzioni). Gli algoritmi paralleli impongono solo un ordine parziale sui passaggi, quindi qui sto semplificando eccessivamente. Sarebbe più corretto descriverlo come un insieme parzialmente ordinato rispetto a una sequenza, ma volevo mantenere le parole un po 'più semplici. Inoltre, è facilmente possibile incorporare un set parzialmente ordinato in un ordine completo.

Risultato: uno stato o un valore finale. Non deve essere prevedibile in anticipo, ma deve essere un fine definito che soddisfi alcune condizioni. Ciò significa che un sistema operativo non è un algoritmo, sebbene ne utilizzi molti.

Finite: è garantito che un algoritmo si fermi a volte, almeno su una macchina che può funzionare abbastanza a lungo. Non è necessariamente garantito che si fermi in un tempo prevedibile e non è garantito che si fermi prima che il sole si espanda e diventi rosso su qualsiasi macchina esistente. Ciò significa anche che un sistema operativo non è un algoritmo, poiché idealmente funzionerà per sempre. Ho visto la parola "procedura" usata per descrivere qualcosa che sarebbe un algoritmo se fossimo sicuri che si fermerebbe prima o poi. (È possibile avere un algoritmo che si fermerà in una quantità di tempo sconosciuta Supponiamo che la congettura di Goldbach sia stata dimostrata matematicamente falsa, in una dimostrazione non costruttiva, quindi c'era un numero pari > 2 che non era la somma di due primi, un algoritmo che ha semplicemente testato i numeri pari alla fine terminerebbe, anche se nessuno saprebbe quando.)

L'algoritmo è un tipo di cosa intenzionalmente astratto, quindi non consideriamo domande come "È fisicamente possibile eseguirlo prima della morte termica dell'Universo?". Sarebbero troppo difficili da rispondere. Se si riferisce alle operazioni del computer, è facile da implementare in un linguaggio di programmazione.

    
risposta data 22.04.2011 - 17:36
fonte

Leggi altre domande sui tag