خوارزمية TPK

📅 آخر تحديث: ١٨ يوليو ٢٠٢٦
✍️ نُشر في: ١٨ يوليو ٢٠٢٦
📷 يحتوي على 7 صور
الموسوعة الحرة

خوارزمية TPK هي برنامج بسيط قدمه دونالد كنوث ولويس تراب باردو لتوضيح تطور لغات البرمجة . في كتابهما الصادر عام 1977 بعنوان "التطور المبكر للغات البرمجة"، قدم تراب باردو وكنوث برنامجًا صغيرًا يتضمن المصفوفات ، والفهرسة، والدوال الرياضية، والإجراءات الفرعية ، والإدخال /الإخراج ، والشروط ، والتكرار . ثم قاما بكتابة تطبيقات للخوارزمية في العديد من لغات البرمجة المبكرة لإظهار كيفية التعبير عن هذه المفاهيم.

لتفسير اسم "TPK"، استند المؤلفان إلى قانون غريم (الذي يتعلق بالحروف الساكنة 't' و'p' و'k')، وأصوات كلمة "typical"، والأحرف الأولى من اسميهما (تراب باردو وكنوث). [ 1 ] وفي محاضرة استندت إلى هذه الورقة البحثية، قال كنوث: [ 2 ]

لا يُمكنك إدراك عمق هذا الموضوع إلا من خلال رؤية كيف كافح المفكرون المتميزون في سبيله، وكيف تبلورت الأفكار تدريجيًا. لدراسة هذا الموضوع - وأعتقد أن لويس كان المحرك الرئيسي لهذه الفكرة - نختار برنامجًا واحدًا - خوارزمية واحدة - ونكتبها بكل لغة برمجة. وبهذه الطريقة، نستطيع من خلال مثال واحد أن نستنتج بسرعة خصائص تلك اللغة. نسمي هذا البرنامج "برنامج TPK"، ومن المصادفة الطريفة أن اسمه يحمل الأحرف الأولى من اسمي تراب باردو وكنوث.

الخوارزمية

يصفها كنوت على النحو التالي: [ 3 ]

قدّمنا إجراءً بسيطًا يُسمى "خوارزمية TPK"، وأضفينا طابع كل لغة من خلال التعبير عن TPK بأسلوبها الخاص. [...] تُدخل خوارزمية TPK أحد عشر رقمًا.أ0،أ1،...،أ10{\displaystyle a_{0},a_{1},\ldots ,a_{10}}ثم يُخرج سلسلة من أحد عشر زوجًا.(10،ب10)،(9،ب9)،...،(0،ب0)،{\displaystyle (10,b_{10}),(9,b_{9}),\ldots ,(0,b_{0}),}أين

بأنا={و(أأنا)،لو و(أأنا)≤400؛999،لو و(أأنا)>400؛و(x)=|x|+5x3.{\displaystyle b_{i}={\begin{cases}f(a_{i}),&{\text{if }}f(a_{i})\leq 400;\\999,&{\text{if }}f(a_{i})>400;\end{cases}}\quad f(x)={\sqrt {|x|}}+5x^{3}.}

من الواضح أن هذه المهمة البسيطة ليست تحدياً كبيراً، في أي لغة برمجة جيدة.

بلغة شبه رمزية:

اطلب قراءة 11 رقمًا في تسلسل S. اعكس التسلسل S. لكل عنصر في التسلسل S، استدعِ دالة لإجراء عملية حسابية. إذا تجاوزت النتيجة الحد المسموح به ، فأبلغ المستخدم. وإلا، اطبع النتيجة.

تقوم الخوارزمية بقراءة أحد عشر رقماً من جهاز الإدخال، وتخزينها في مصفوفة، ثم معالجتها بترتيب عكسي، وتطبيق دالة معرفة من قبل المستخدم على كل قيمة، والإبلاغ إما عن قيمة الدالة أو رسالة تفيد بأن القيمة قد تجاوزت حداً معيناً.

التطبيقات

التطبيقات الواردة في الورقة الأصلية

في الورقة الأصلية، التي غطت "العقد الأول تقريبًا" من تطوير لغات البرمجة عالية المستوى (من عام 1945 حتى عام 1957)، قدموا مثال التنفيذ التالي "بلهجة من ALGOL 60 "، مشيرين إلى أن ALGOL 60 كان تطورًا لاحقًا للغات التي تمت مناقشتها بالفعل في الورقة: [ 1 ]

TPK : begin integer i ; real y ; real array a [ 0 : 10 ] ;دالة حقيقية f ( t ) ؛ عدد حقيقي t ؛ قيمة t ؛f := sqrt ( abs ( t )) + 5 × t ↑ 3 ;for i := 0 step 1 until 10 do read ( a [ i ]) ;for i := 10 step - 1 until 0 doابدأ y := f ( a [ i ]) ;إذا كانت قيمة y أكبر من 400 ، فاكتب ( i ، 'كبير جدًا' )وإلا اكتب ( i ، y ) ؛نهايةنهاية TPK .

بما أن العديد من لغات البرمجة عالية المستوى المبكرة لم تكن قادرة على التعامل مع خوارزمية TPK بشكل دقيق، فإنها تسمح بالتعديلات التالية: [ 1 ]

  • إذا كانت اللغة تدعم المتغيرات الصحيحة فقط، فافترض أن جميع المدخلات والمخرجات ذات قيم صحيحة، وهذا sqrt(x)يعني أن أكبر عدد صحيح لا يتجاوزx{\displaystyle {\sqrt {x}}}.
  • إذا كانت اللغة لا تدعم الإخراج الأبجدي، فبدلاً من السلسلة النصية 'TOO LARGE'، قم بإخراج الرقم 999.
  • إذا كانت اللغة لا تسمح بأي إدخال أو إخراج، فافترض أن قيم الإدخال الـ 11أ0،أ1،...،أ10{\displaystyle a_{0},a_{1},\ldots ,a_{10}}تم توفيرها بواسطة عملية خارجية بطريقة ما، والمهمة هي حساب قيم الإخراج الـ 2210،و(10)،9،و(9)،...،0،و(0){\displaystyle 10,f(10),9,f(9),\ldots ,0,f(0)}(مع استبدال القيم الكبيرة جدًا بـ 999)و(أنا){\displaystyle f(i)}).
  • إذا كانت اللغة لا تسمح للمبرمجين بتعريف وظائفهم الخاصة، فاستبدلها f(a[i])بتعبير مكافئ لـ|أأنا|+5أأنا3{\displaystyle {\sqrt {|a_{i}|}}+5a_{i}^{3}}.

مع إجراء هذه التعديلات عند الضرورة، قام المؤلفون بتطبيق هذه الخوارزمية في Plankalkül لكونراد تسوز ، وفي مخططات التدفق لغولدستين وفون نيومان ، وفي الترميز المقترح لهاسكل كاري ، وفي Short Code لجون موشلي وآخرين، وفي لغة البرمجة الوسيطة لآرثر بيركس ، وفي ترميز هاينز روتشاوزر ، وفي اللغة والمترجم لكورادو بوم في 1951-1952، وفي Autocode لأليك غليني ، وفي نظام A-2 لغريس هوبر ، وفي نظام لانينغ وزيرلر ، وفي أول نسخة مقترحة من Fortran (1954) لجون باكوس ، وفي Autocode لـ Mark 1 لتوني بروكر ، وفي ПП-2 لأندريه إرشوف ، وفي BACAIC لماندالاي غريمز وRE بورتر، وفي Kompiler 2 لـ A. كينتون إلسورث وآخرين، وفي ADES لـ EK بلوم، وInternal مترجم أعمال آلان بيرليس ، بلغة فورتران لأعمال جون باكوس، في لغتي ARITH-MATIC و MATH-MATIC من مختبر غريس هوبر ، في نظام باور وساميلسون ، و(في إضافات عامي 2003 و2009) لغتي PACT I و TRANSCODE. ثم يصفون أنواع العمليات الحسابية المتاحة، ويقدمون تقييمًا شخصيًا لهذه اللغات بناءً على معايير "التنفيذ" و"سهولة القراءة" و"هياكل التحكم" و"هياكل البيانات" و"استقلالية الآلة" و"التأثير"، بالإضافة إلى ذكر ما كانت كل لغة رائدة فيه. [ 1 ]

تطبيقات في لغات أحدث

تنفيذ بلغة C

يوضح هذا تطبيقًا بلغة C مكافئًا لـ ALGOL 60 المذكور أعلاه.

#include <math.h>#include <stdio.h>دالة f مزدوجة ( دالة t مزدوجة ){return sqrt ( fabs ( t )) + 5 * pow ( t , 3 );}int main ( void ){double a [ 11 ] = { 0 }, y ;for ( int i = 0 ; i < 11 ; i ++ )scanf ( "%lf " , &a a [ أنا ])؛for ( int i = 10 ; i > = 0 ; i-- ) {y = f ( a [ i ]);إذا ( ص > 400 )printf ( "%d كبير جدًا \n " , i );آخرprintf ( "%d %.16g \n " , i , y );}}

تطبيق بايثون

هذا يوضح تطبيقًا بلغة بايثون.

من الرياضيات استورد الجذر التربيعيdef f ( t ):أعد الجذر التربيعي ( القيمة المطلقة لـ t ) + 5 * t ** 3a = [ float ( input ()) for _ in range ( 11 )]for i , t in reversed ( list ( enumerate ( a ))):ص = د ( ت )اطبع ( i ، "كبير جدًا" إذا كان y > 400 وإلا y )

تطبيق جافا

هذا يوضح تطبيقًا بلغة جافا.

استيراد java.util.Arrays ؛استيراد java.util.ArrayList ؛استيراد java.util.Collections ؛استيراد java.util.List ;استيراد java.util.Scanner ؛public class TPKAlgorithm {// دالة معرفة من قبل المستخدمprivate static double f ( double x ) {return Math.sqrt ( Math.abs ( x ) ) + 5 * Math.pow ( x , 3 ) ;​​​​}public static void main ( String [] args ) {// إنشاء كائن Scanner لإدخال المستخدمScanner scanner = new Scanner ( System . in );// إنشاء قائمة ArrayList لتخزين أرقام الإدخالList <Double> inputNumbers = new ArrayList <> ( ) ;System.out.println ( " أدخل أحد عشر رقمًا: " ) ;int inputNumber ;// الحصول على 11 رقمًا من مدخلات المستخدمfor ( int i = 1 ; i <= 11 ; i ++ ) {إذا كان الماسح الضوئي يحتوي على عدد عشري تالٍ {inputNumber = scanner.nextDouble ( ) ;أرقام الإدخال . إضافة ( رقم الإدخال )؛}}scanner.close ( ) ;// منطق الخوارزميةCollections.reverse ( inputNumbers ) ;​for ( int n = 0 ; n < inputNumbers.size ( ) ; n ++ ) {int i = inputNumbers.size ( ) - ( n + 1 ) ;double y = f ( inputNumbers . get ( n ));إذا كانت ( ص > 400 ) {System.out.printf ( " % d كبير جدًا%n " , i ) ;} آخر {System.out.printf ( " % d % .2f %n" , i , y ) ;}}}}

تطبيق بلغة Rust

هذا يوضح تطبيقًا بلغة Rust.

استخدم std ::{ io , iter };fn f ( t : f64 ) -> Option < f64 > {دع ص = ر . القيمة المطلقة (). sqrt () + 5.0 * t . باوي ( 3 ) ؛( y <= 400.0 ). then_some ( y )}fn main () {let mut a = [ 0 f64 ; 11 ];for ( t , input ) in iter :: zip ( & mut a , io :: stdin (). lines ()) {* t = input . unwrap (). parse (). unwrap ();}a.iter ( ). enumerate (). rev ( ). for_each ( | ( i , & t ) | match f ( t ) {None => println! ( "{i} كبير جدًا" ),بعض ( y ) => println! ( "{i} {y}" ),});}

مراجع

  1. 1 2 3 4 لويس تراب باردو ودونالد إي. كنوث، "التطور المبكر للغات البرمجة".
    • نُشر لأول مرة في أغسطس 1976 في شكل مسودة مطبوعة، تحت عنوان تقرير ستانفورد لعلوم الحاسوب STAN-CS-76-562
    • نُشر في موسوعة علوم وتكنولوجيا الحاسوب ، جاك بيلزر، ألبرت ج. هولزمان، وألين كينت (محررون)، المجلد 6، الصفحات 419-493. ديكر، نيويورك، 1977.
    • أُعيد طبعه ( doi : 10.1016/B978-0-12-491650-0.50019-8 ) في كتاب "تاريخ الحوسبة في القرن العشرين" ، تحرير ن. متروبوليس ، ج. هاوليت ، وج.-س. روتا ، نيويورك، دار النشر الأكاديمية، 1980. ISBN 0-12-491650-3
    • أُعيد طبعه مع تعديلات كالفصل الأول من كتاب "أوراق مختارة حول لغات الحاسوب" ، دونالد كنوث، ستانفورد، كاليفورنيا، CSLI، 2003. ISBN 1-57586-382-0)
  2. ↑ "اثنا عشر سلفًا للغة فورتران"، محاضرة لدونالد كنوث، 3 ديسمبر 2003 في متحف تاريخ الحاسوب : ملخص ، فيديو
  3. ↑ دونالد كنوث، TPK في INTERCAL ، الفصل 7 من أوراق مختارة حول المرح والألعاب ، 2011 (ص 41)