Usi della funzione Ackermann?

Question

Nel nostro corso di matematica discreta nella mia università, l'insegnante mostra ai suoi studenti la funzione di Ackermann e incaricare lo studente di sviluppare la funzione su carta.

Oltre ad essere un punto di riferimento per l'ottimizzazione della ricorsione, la funzione Ackermann ha qualche reale utilizzo?

Answer 1

Sì. La funzione (inversa) di Ackermann appare nell'analisi della complessità degli algoritmi. Quando lo fa, significa che puoi quasi ignorare quel termine poiché cresce così lentamente (molto simile a log (log ... log (n) ...)) cioè lg * (n). Ad esempio: Minimum Spanning Trees (anche qui ) e Set disgiunto costruzione forestale.

Inoltre: Sequenze di Davenport-Scinzel

Answer 2

L'originale " usa " della funzione di Ackermann era mostrare che ci sono funzioni che non sono ricorsive primitive, cioè che non possono essere calcolate usando solo per anelli con limiti superiori predeterminati.

La funzione Ackermann è una tale funzione, cresce troppo velocemente per essere ricorsiva primitiva.

Non penso che ci siano usi davvero pratici, cresce troppo velocemente per essere utile. Non puoi nemmeno rappresentare esplicitamente i numeri oltre un (4,3) in uno spazio ragionevole.

Answer 3

Sono d'accordo con l'altra risposta (di wrang-wrang) "in teoria".

In pratica Ackerman non è troppo utile, perché in pratica le uniche complessità dell'algoritmo che tendi ad incontrare riguardano 1, N, N ^ 2, N ^ 3, e ognuna di quelle multiplate da logN. (E poiché logN non è mai più di 64, è effettivamente un termine costante comunque.)

Il punto è, "in pratica", a meno che la complessità dell'algoritmo non sia "N volte troppo grande", non ti interessa la complessità, perché i fattori del mondo reale domineranno. (Una funzione che viene eseguita in O (inverse-Ackermann) è teoricamente migliore di una funzione che viene eseguita in tempo O (logN), ma in pratica, misurerai le due implementazioni effettive rispetto ai dati del mondo reale e selezionerai quale effettivamente funziona meglio Al contrario, la teoria della complessità ha "importanza nella pratica" per esempio N contro N ^ 2, dove gli effetti della complessità algoritmica in effetti prevalgono su qualsiasi effetto "mondo reale". Trovo che "N" sia la misura più piccola che in pratica.)