W naszym dyskretnym kursie matematyki na moim uniwersytecie nauczyciel pokazuje swoim studentom Ackermann function i przypisuje uczniowi rozwinięcie funkcji na papierze.Używa funkcji Ackermanna?
Czy oprócz funkcji benchmarkingu optymalizacji rekursji funkcja Ackermann ma rzeczywiste zastosowania?
Tak. Funkcja (odwrotna) Ackermanna pojawia się w analizie złożoności algorytmów. Kiedy to robi, oznacza to, że możesz prawie zignorować ten termin, ponieważ rośnie tak wolno (podobnie jak log (log ... log (n) ...)), tj. Lg * (n). Na przykład: Minimum Spanning Trees (także here) i Disjoint Set budownictwo leśne.
również: Davenport-Scinzel sequences
W szczególności algorytm znajdowania związku, jeśli chcesz podać przykład. http://www.yucs.org/~gnivasch/alpha/index.html – Joshua
Ale jest to odwrotność funkcji, a co z prawdziwą funkcją? –
zgadzam się z drugiej odpowiedzi (przez wrang-wrang) "w teorii".
W praktyce Ackerman nie jest zbyt przydatny, ponieważ w praktyce jedynymi złożonymi problemami algorytmu są 1, N, N^2, N^3 i każdy z nich pomnożony przez logN. (A ponieważ logN nigdy nie jest dłuższy niż 64, to i tak jest to stały termin).
Punkt jest "w praktyce", chyba że złożoność algorytmu jest "N razy za duża", nie zależy Ci na złożoności , ponieważ dominować będą czynniki świata rzeczywistego. (Funkcja, która wykonuje w O (inverse-Ackermann) jest teoretycznie lepsza niż funkcja wykonywana w czasie O (logN), ale w praktyce będziesz mierzyć dwie rzeczywiste implementacje względem danych rzeczywistych i wybierać te, które faktycznie działają lepiej W przeciwieństwie do tego, teoria złożoności "ma znaczenie w praktyce", np. N versus N^2, gdzie algorytmiczne efekty złożoności faktycznie obezwładniają wszelkie efekty "rzeczywistego świata". Uważam, że "N" jest najmniejszą miarą, która ma znaczenie w praktyce. .)
Rzeczywiście, analiza teoretyczna daje tylko podstawę do analizy wydajności. –
Czy możesz wyjaśnić, w jaki sposób logN nigdy nie jest dłuższy niż 64? –
Zazwyczaj "log" jest podstawą 2. Jeśli log (n) wynosi 64, oznacza to, że masz 2^64 pozycji danych. To znacznie więcej niż w praktyce; w rzeczywistości na 64-bitowym komputerze masz 64-bitowe wskaźniki, więc nie możesz z łatwością reprezentować więcej niż 2^64 bajty. – Andrey
Pierwotnym "użyciem" funkcji Ackermanna było pokazanie, że istnieją funkcje, które nie są prymitywne rekursywne, tj. Które nie mogą być obliczone przy użyciu tylko dla pętli z ustalonymi górnymi granicami.
Funkcja Ackermanna jest taką funkcją, rośnie zbyt szybko, aby być prymitywną rekursywną.
Nie sądzę, że istnieją naprawdę praktyczne zastosowania, rośnie zbyt szybko, aby być użytecznym. Nie można nawet jednoznacznie przedstawić liczb powyżej (4,3) w rozsądnej przestrzeni.
https://en.wikipedia.org/wiki/Hyperoperation – starblue