Migliore risposta
Non cè risposta a questa.
Troviamo la risposta a questa affermazione del problema:
Q. Come scoprire che un algoritmo funziona meglio?
A. I modi più comuni di confrontare gli algoritmi:
1) Complessità temporale
2) Complessità spaziale
3) Qualità della soluzione (potrebbe non essere applicabile se si propone di risolvere esattamente un problema). Questo può essere un fattore enorme se parliamo di algoritmi di approssimazione.
4) Facilità di implementazione / adattamento dellalgoritmo. Alcuni algoritmi possono avere molto overhead per essere implementati correttamente. A volte ci sono algoritmi più adatti per la tua applicazione. Ad esempio, nel calcolo parallelo, la maggior parte troverà Bellman-Ford più utile dellalgoritmo di Dijkstra a causa del modo in cui funziona Bellman-Ford.
Tuttavia, il tempo e la complessità non sono * sempre * la caratteristica desiderabile da massimizzare; Fornirò due esempi.
Uno è la “stabilità numerica” , una caratteristica degli algoritmi sia nellalgebra lineare che nelle equazioni differenziali. Impiegheremo più tempo algoritmico e più complessità algoritmica su algoritmi numericamente più stabili. Nellalgebra lineare linstabilità è generalmente causata quando un algoritmo incontra numeri troppo vicini allo zero o allinfinito o entrambi, a causa della rappresentazione finita dei numeri la risoluzione può essere persa. In generale, questo fa sì che numeri leggermente diversi, solo pochi epsilon diversi luno dallaltro (dove epsilon è il numero più piccolo che può essere aggiunto a uno, su una macchina, e ottenere un risultato! = 1), per produrre grandi differenze in la risposta. Quindi, ad esempio, impieghiamo molto tempo e spazio per la complessità “ruotando” nella fattorizzazione LU per ottenere un algoritmo stabile; senza la rotazione LU non è stabile. Allo stesso modo, abbiamo algoritmi che non fanno altro che “condizionare” matrici per evitare instabilità.
Un secondo esempio è “robustezza” in il suo senso tecnico statistico. Per robustezza si intende una misura o un algoritmo che * non * è sensibile ai valori anomali. Quindi, ad esempio, quando adeguo una linea dei minimi quadrati a un insieme di punti, la linea può essere fortemente distorta da un singolo valore estremamente grande. Anche se ho 99 coppie di numeri che formano una linea perfetta di 45 gradi, se aggiungo una singola coppia anomala per la quale il valore Y è cento volte quello che “dovrebbe” essere per cadere sulla stessa linea, la linea adattata sarà gravemente distorta dalla linea di 45 gradi. Lalgoritmo “rinuncerà” alla misura perfetta per 99 punti per rappresentare meglio lunico punto anomalo. Questo è * non * robusto.
Un approccio robusto ai minimi quadrati consiste, invece di trovare la linea che minimizza la somma degli errori al quadrato creati utilizzando quella linea, per trovare la linea che minimizza la * mediana * di gli errori al quadrato creati utilizzando quella linea. Nellesempio, quella linea è la linea di 45 gradi e la mediana degli errori al quadrato è zero e il punto anomalo (e in effetti fino a 98 valori anomali più folli) verrebbe completamente ignorato. La linea di 45 gradi verrebbe trovata.
Esistono algoritmi robusti simili per ladattamento di curve statistiche, la ricerca di forme, ecc. Tuttavia, sono costosi in termini di tempo, a volte molto. Ma il costo in termini di tempo ne vale la pena perché statistiche affidabili sono effettivamente immuni al “rumore” nei segnali, mentre gli approcci allerrore minimo quadrato non lo sono. Il mondo reale è pieno sia di rumore che di valori anomali, alcuni dei quali causati da errori umani o meccanici, in particolare nelle immagini pixelate o nel suono campionato. In tali circostanze, un algoritmo robusto più costoso in termini di tempo può trovare segnali in un ambiente rumoroso in cui algoritmi più veloci producono risposte così corrotte dal rumore da essere inutili o addirittura pericolose se accettate.
In alcuni casi, il tempo e la complessità dello spazio non sono così importanti quanto trovare una risposta molto probabile per modellare il segnale effettivo nonostante il rumore e la degradazione del segnale.
Risposta
Gli algoritmi hanno avuto origine in matematica come “ricette” per eseguire calcoli basati su funzioni, che possono essere seguiti meccanicamente. Nella visione del mondo matematica basata sulla funzione, tutti gli input devono essere specificati allinizio del calcolo, che procede in modo chiuso. La nozione di algoritmo è intrinsecamente informale, poiché una descrizione algoritmica non è limitata a nessun singolo linguaggio o formalismo.
Forse lesempio più antico è lalgoritmo di Euclide per trovare divisori comuni. Gli algoritmi catturano cosa significa per un calcolo essere “efficace”. Come le formule matematiche, gli algoritmi ci dicono come calcolare un valore; a differenza di loro, gli algoritmi possono coinvolgere ciò che ora chiamiamo loop o rami.
Ruolo dellalgoritmo: dato un valore di input finito x, un algoritmo descrive i passaggi per trasformarlo efficacemente in un valore di output y, dove y è f (x) per alcune funzioni ricorsive f.
Gli algoritmi furono adottati dai primi scienziati informatici negli anni 50, che stabilirono la connessione tra algoritmi e macchine di Turing (TM, un modello formale di calcolo risalente al 1936), equiparando la loro espressività.
Il famoso e influente libro di testo di Knuth, “The Art of Computer Programming, Vol. 1” alla fine degli anni 60, rese popolare la centralità degli algoritmi nellinformatica. Nella sua definizione di algoritmi, Knuth era coerente con i fondamenti matematici basati sulla funzione della teoria del calcolo. “Esistono molti altri modi essenzialmente equivalenti per formulare il concetto di un metodo di calcolo efficace (ad esempio, utilizzando le TM).”
Knuth ha specificato esplicitamente che gli algoritmi sono chiusi; nessun nuovo input viene accettato una volta che il calcolo è iniziato: “Un algoritmo ha zero o più input, cioè quantità che gli vengono fornite inizialmente prima che lalgoritmo inizi.” Ha distinto gli algoritmi dal calcolo arbitrario che può coinvolgere I / O. Un esempio che ha fornito di un problema che non è algoritmico è la seguente istruzione da una ricetta: “mescolare leggermente fino a quando la miscela è friabile”. Questo problema non è algoritmico perché è impossibile per un computer sapere per quanto tempo mescolare; questo può dipendere da condizioni esterne che cambiano dinamicamente come lumidità, che non possono essere previste con certezza in anticipo.
Sebbene non vi sia accordo sulla nozione esatta di algoritmi, la discussione di Knuth sugli algoritmi rimane definitiva.
Il primo linguaggio di programmazione di alto livello sviluppato espressamente per specificare algoritmi era ALGOL (ALGOrithmic Language). Introdotto alla fine degli anni 50 e perfezionato negli anni 60, è servito come standard per la pubblicazione di algoritmi. Fedele alla concettualizzazione degli algoritmi basata sulla funzione, ALGOL non ha fornito costrutti per input e output, considerando queste operazioni al di fuori degli algoritmi. (Non sorprende che questa assenza abbia ostacolato ladozione di ALGOL da parte dellindustria per applicazioni commerciali.)
Gli anni 60 hanno visto una proliferazione di programmi di informatica (CS) universitari. Secondo lAssociation for Computing Machinery (ACM), il numero di programmi CS negli Stati Uniti è passato da 11 nel 1964 a 92 nel 1968. Questo aumento è stato accompagnato da unintensa attività volta a stabilire la legittimità di questa nuova disciplina agli occhi degli accademici. Comunità. ACM ha svolto un ruolo centrale in questa attività. Nel 1965, enunciò la giustificazione e la descrizione della CS come disciplina, che servì come base delle sue raccomandazioni del 1968 per i programmi di CS universitari
La descrizione di ACM della CS identificava leffettiva trasformazione delle informazioni come una preoccupazione centrale: ” Linformatica si occupa di informazione più o meno nello stesso senso in cui la fisica si occupa di energia … Lo scienziato informatico è interessato a scoprire i mezzi pragmatici con cui le informazioni possono essere trasformate “. Questa descrizione pone gli algoritmi al centro dellinformatica, poiché sono le “ricette” per eseguire queste trasformazioni efficaci di input in output. Infatti, ACM ha reso esplicito questo focus sugli algoritmi nella frase successiva del loro rapporto:
“Questo interesse porta alla ricerca di modi efficaci per rappresentare le informazioni, algoritmi efficaci per trasformare le informazioni, linguaggi efficaci con cui esprimere algoritmi … e modi efficaci per realizzarli a un costo ragionevole. “
Avere una preoccupazione algoritmica centrale, analoga alla preoccupazione per lenergia in fisica, ha aiutato a stabilire CS come disciplina accademica legittima alla pari con fisica. Gli algoritmi sono rimasti al centro dellinformatica fino ad oggi.
La coesistenza degli approcci informali (basati su algoritmi) e formali (basati su TM) per definire i problemi risolvibili persiste ancora oggi e può essere trovata in tutti i libri di testo moderni su algoritmi o computabilità. Ciò si è rivelato molto conveniente per gli informatici, permettendoci di descrivere il calcolo algoritmico in modo informale utilizzando “pseudocodice”, con la consapevolezza che una macchina di Turing equivalente può essere costruita.
– Un problema è risolvibile se può essere specificato da un algoritmo. – Un problema è risolvibile se esiste una macchina di Turing per esso.
La decisione degli anni 60 di teorici ed educatori di porre gli algoritmi al centro del CS si rifletteva chiaramente nei primi libri di testo universitari. Tuttavia, non esisteva una definizione standard esplicita di un algoritmo e vari libri di testo hanno scelto di definire questo termine in modo diverso. Mentre alcuni libri di testo come quello di Knuth sono stati attenti a limitare esplicitamente gli algoritmi a quelli che calcolano le funzioni e sono quindi equivalenti alle macchine di Turing, la maggior parte dei libri di teoria ha lasciato questa restrizione implicita ma non dichiarata.
Un primo esempio è un libro di testo di Hopcroft e Ullman del 1969, le cui edizioni successive vengono utilizzate ancora oggi: “Una procedura è una sequenza finita di istruzioni che può essere eseguita meccanicamente, come un programma per computer …Una procedura che termina sempre è chiamata algoritmo. “
Questa descrizione di un algoritmo non preclude esplicitamente calcoli non funzionali come la preparazione del cibo. Tuttavia, i loro esempi di vari problemi rendono chiaro che hanno considerato solo il calcolo basato sulla funzione. In effetti, hanno usato ALGOL per i loro esempi, che non offriva nemmeno alcun costrutto per input e output.
Dalla fine degli anni 60, i linguaggi di programmazione di alto livello usati nella pratica e insegnati nei programmi CS non erano più vincolato dai vincoli algoritmici dei primi ALGOL. Potresti scrivere programmi che interagiscono con il loro ambiente in modo continuo durante il calcolo, come sistemi operativi, interfacce utente grafiche o veicoli automatici e altri robot.
In risposta, libri di testo di programmazione contemporanei come Rice e Rice (1969) ha ampliato esplicitamente la nozione di algoritmi per includere problemi non funzionali. Questo approccio, che riflette la centralità degli algoritmi senza limitarli al calcolo delle funzioni, è diventato tipico dei libri di testo non teorici. Largomento di questi libri di testo è la metodologia di programmazione piuttosto che la teoria del calcolo, ei principi matematici che stanno alla base dei nostri modelli di calcolo sono stati messi da parte per motivi di praticità.
In superficie, la definizione di un algoritmo in Rice and Rice e altri libri di testo simili non è diverso da Hopcroft e Ullman: “Un algoritmo è una ricetta, un insieme di istruzioni o le specifiche di un processo per fare qualcosa. Quel qualcosa di solito risolve un problema di qualche tipo. ” Tuttavia, i loro esempi di problemi calcolabili non sono più basati sulla funzione, ammettendo solo il tipo di calcolo che Knuth aveva rifiutato. Due di questi esempi, che presumibilmente possono essere risolti da un algoritmo, sono la produzione di vodka di patate e il riempimento di un fossato di sabbia; Knuth li avrebbe rifiutati entrambi.
Questi libri di testo non rivendicavano lequivalenza della MT per i loro “algoritmi”. Tuttavia, gli studenti non sono stati informati che questa nozione di algoritmi è diversa da quella di Knuth e che linsieme dei problemi considerati calcolabili era stato così ampliato. Associando una più ampia, più pratica, concettualizzazione di algoritmi (e quindi di problemi calcolabili) con teorie che affermano che un problema molto computabile può essere calcolato dalle MT, il curriculum CS incentrato sullalgoritmo ha lasciato agli studenti limpressione errata che questo insieme più ampio di problemi potrebbe essere risolto anche dalle TM.
Mentre gli informatici pratici hanno seguito da tempo lesempio di Rice e Rice e hanno ampliato il concetto di algoritmi oltre il calcolo delle funzioni, linformatica teorica ha mantenuto la visione matematica del mondo che inquadra calcolo come funzione basata e delimita di conseguenza la nostra nozione di problema computazionale. Questo è vero almeno a livello universitario. Il risultato è una dicotomia, in cui la comunità informatica pensa che gli algoritmi siano sinonimo della nozione generale di computazione (“cosa fanno i computer”) ma allo stesso tempo equivalenti alle macchine di Turing.
Ho pensato Ho dovuto scrivere questa lunga risposta, per rendere le persone consapevoli di questa dicotomia. Come ho detto allinizio, la nozione di algoritmo è informale. Possiamo pensarlo come equivalente al calcolo di funzioni (o alle macchine di Turing) o possiamo pensarlo come qualsiasi cosa per cui puoi scrivere un programma, inclusi programmi interattivi in tempo reale come sistemi operativi o macchine automatiche. Ma le due definizioni non sono equivalenti, nonostante la comune confusione sul contrario.