يستخدم وظيفة أكرمان؟

Question

في مسارنا الرياضيات المنفصلة في دراستي الجامعية، ويظهر المعلم طلابه على أكرمان وظيفة وتعيين الطالب على تطوير وظيفة على الورق.

وبجانب كونه معيارا لتحسين العودية، لا وظيفة أكرمان لديه أي استخدامات حقيقية؟

Answer 1

نعم. تظهر (معكوس) أكرمان وظيفة في تحليل تعقيد الخوارزميات. عندما تفعل ذلك، فهذا يعني أنك يمكن تجاهل تقريبا هذا المصطلح لأنه ينمو ببطء شديد (الكثير مثل السجل (سجل ... سجل (ن) ...)) أي جي * (ن). على سبيل المثال: الدنيا الامتداد الأشجار (وأيضا <أ href ل = "http://www.andreygoder.com/talks/mstackermann.pdf" يختلط = "noreferrer"> هنا ) و <لأ href = "http://en.wikipedia.org/wiki/Disjoint- set_data_structure "يختلط =" noreferrer "> منفصلتين مجموعة بناء الغابات.

وأيضا: تسلسل دافنبورت-Scinzel

Answer 2

وكان "الاستخدام" الأصلي وظيفة أكرمان لاظهار ان هناك وظائف التي هي ليست بدائية العودية، أي التي لا يمكن حسابها باستخدام فقط لحلقات مع الحدود العليا محددة سلفا.

وظيفة أكرمان هي تلك الوظيفة، فإنه ينمو بسرعة كبيرة لتكون العودية البدائية.

وأنا لا أعتقد أن هناك استخدامات عملية حقا، وأنها تنمو بسرعة كبيرة أن تكون مفيدة. لا يمكنك حتى تمثل بوضوح الأرقام تتجاوز (4،3) في مساحة معقولة.

Answer 3

وأنا أتفق مع الإجابة أخرى (عن طريق wrang-wrang) "نظريا".

في ممارسة أكرمان ليس من المفيد جدا، لأنه في الممارسة تعقيدات الخوارزمية الوحيدة التي تميل لقاء تنطوي 1، N، N ^ 2، N ^ 3، ولكل من هذه مضروب ب logN. (ومنذ logN أبدا أكثر من 64 عاما، انها فعليا الحد الثابت على أي حال).

والنقطة الوجود، "عمليا"، إلا خوارزمية تعقيد الخاص بك هو "N مرات كبيرة جدا"، لا يهتمون التعقيد، لأن عوامل العالم الحقيقي والهيمنة. (A ظيفة الذي ينفذ في O (معكوس أكرمان) هو أفضل نظريا من وظيفة الذي ينفذ في الوقت O (logN)، ولكن في الممارسة العملية، عليك قياس اثنين من التطبيقات الفعلية ضد البيانات في العالم الحقيقي واختر أيهما يؤدي في الواقع أفضل في المقابل، نظرية التعقيد يفعل "المسألة في ممارسة" لمثل N مقابل N ^ 2، حيث تفعل آثار تعقيد حسابي في الواقع تغلب على أي آثار "العالم الحقيقي". وأجد أن "N" هو أصغر قياس ما يهم في الواقع العملي .)