روبرت تارجان: قواعد الخوارزميات الفعالة

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

مسار عالم رياضيات نحو الآلات

وُلد روبرت إندري تارجان في 30 أبريل 1948 في بومونا، كاليفورنيا، لأب يدعى جورج تارجان، وهو طبيب نفسي للأطفال متخصص في الإعاقة الذهنية؛ وأصبح شقيقه الأصغر جيمس أستاذاً كبيراً في الشطرنج. أراد تارجان أن يصبح عالم فلك عندما كان صبياً، حتى جذبه أعمدة الألغاز لمارتن جاردنر في مجلة ساينتفك أمريكان ومعلم ملهم في الصف الثامن نحو الرياضيات بدلاً من ذلك. حصل على درجة البكالوريوس في الرياضيات من معهد كاليفورنيا للتقنية (كالتك) في 1969، ثم ذهب إلى ستانفورد للحصول على درجة الماجستير في علوم الحاسوب في 1971 والدكتوراه في 1972، مع أطروحة حول خوارزميات التسطيح تحت إشراف روبرت فلويد ودونالد كنوت. سيصف لاحقاً اختياره للمجال ببساطة: كانت علوم الحاسوب وسيلة للقيام بالرياضيات التي يمكن أن يكون لها تأثير عملي - وهي جملة تتضاعف كوصف لعمله بأكمله.

بناء مجموعة الأدوات

أنتجت مسيرة تارجان المهنية، التي امتدت عبر كورنيل، وجامعة كاليفورنيا في بيركلي، وستانفورد، ومختبرات بيل التابعة لـ AT&T، وجامعة نيويورك، ومعهد NEC للأبحاث، ومايكروسوفت للأبحاث، وشركة كومباك، وهيوليت باكارد، وشركة إنترترست تكنولوجيز قبل الاستقرار في برينستون في 1985 كأستاذ جامعي متميز، مجموعة من الخوارزميات وهياكل البيانات غير العادية لعددها الذي أصبح بنية تحتية داعمة بدلاً من كونها فضولاً نظرياً. يرتبط اسمه بخوارزمية تارجان لإيجاد المكونات المتصلة بقوة في رسم بياني، وخوارزمية غير متصلة لحساب الأسلاف المشتركين الأقل، وخوارزمية زمن خطي لإيجاد الجسور - وكلها تقنيات مبنية على إطار البحث بالعمق أولاً الذي أضفى عليه الطابع الرسمي. في 1975 قدم التحليل الدقيق الأول لهيكل بيانات الاتحاد والبحث (union-find) مدمجاً مع ضغط المسار، مما أثبت وقت تشغيله المطفأ شبه الثابت باستخدام دالة أكرمان العكسية، وهي نتيجة مرتبطة ارتباطاً وثيقاً بالأداء في العالم الحقيقي لدرجة أنها أصبحت الآن أساس كل شيء من خوارزمية كروسكال للشجرة الممتدة الدنيا إلى تحسينات المترجم. مع دانييل سليتور في مختبرات بيل، شارك في اختراع أشجار التمدد (splay trees)، وهي أشجار بحث ثنائية ذاتية الضبط تعيد توازن نفسها من خلال الاستخدام بدلاً من حمل بيانات وصفية صريحة للتوازن، ومعها كان رائداً في التحليل التنافسي، وهو إطار لتقييم الخوارزميات عبر الإنترنت مقابل خصم كلي العلم. مع مايكل فريدمان طور أكوام فيبوناتشي في 1985، وهو هيكل طابور أولوية جعل خوارزمية ديكسترا لأقصر مسار وخوارزميات تحسين الشبكة أسرع تقاربياً من أي شيء جاء من قبل. فاز كتابه الدراسي، هياكل البيانات وخوارزميات الشبكات، بجائزة فريدريك دبليو لانكستر وأصبح قراءة قياسية في هذا المجال.

اختراق التسطيح مع هوبكروفت

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

التقدير عبر أربعة عقود

كان تارجان أول متلقٍ لجائزة نيفانلينا في علوم المعلومات في 1983، تكريماً للمساهمات البارزة في الجوانب الرياضية لعلوم الحاسوب. فاز بجائزة تورينج في 1986، وانتُخب للأكاديمية الأمريكية للفنون والعلوم في 1985، والأكاديمية الوطنية للعلوم في 1987، والأكاديمية الوطنية للهندسة في 1988. حصل على جائزة باريس كانيلاكيس في النظرية والتطبيق في 1999 وجائزة الخريجين المتميزين من كالتك في 2010. يتجاوز سجل منشوراته 250 ورقة بحثية مع عشرات الآلاف من الاستشهادات، ويحمل أكثر من دزينة من براءات الاختراع الأمريكية في هياكل البيانات والأمن، مما يعكس مسيرة مهنية انتقلت بسلاسة بين النظرية الأكاديمية في برينستون والأبحاث التطبيقية في مختبرات صناعية مثل مختبرات بيل، وNEC، ومايكروسوفت.

لماذا يُدعى روبرت عبقرياً

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

الإرث

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