रॉबर्ट टार्जन: कुशल एल्गोरिदम का व्याकरण

किसी भी कंप्यूटर विज्ञान के छात्र से गहराई-प्रथम खोज (depth-first search) के साथ एक ग्राफ को ट्रैक करने के लिए कहें, और वे, चाहे वे इसे जानते हों या नहीं, एक ऐसी तकनीक का उपयोग कर रहे होंगे जिसे रॉबर्ट टार्जन ने एक जिज्ञासा से एक अनुशासन में बदल दिया। उनका 1972 का शोध पत्र "डेप्थ-फर्स्ट सर्च एंड लीनियर ग्राफ एल्गोरिदम" आज एक मौलिक व्याकरण पाठ की तरह पढ़ा जाता है - यह काम इस क्षेत्र में इतनी गहराई से समा गया है कि इसके लेखक का नाम लोगों की बातचीत से लगभग गायब हो गया है, भले ही उनका नाम उन आधा दर्जन संरचनाओं से जुड़ा हो जिनका वे हर दिन उपयोग करते हैं।

मशीनों की ओर एक गणितज्ञ का मार्ग

रॉबर्ट एंड्रे टार्जन का जन्म 30 अप्रैल, 1948 को पोमोना, कैलिफोर्निया में हुआ था। उनके पिता जॉर्ज टार्जन, बौद्धिक विकलांगता के विशेषज्ञ बाल मनोचिकित्सक थे; उनके छोटे भाई जेम्स शतरंज के ग्रैंडमास्टर बने। टार्जन बचपन में खगोलशास्त्री बनना चाहते थे, जब तक कि साइंटिफिक अमेरिकन में मार्टिन गार्डनर के पहेली कॉलम और आठवीं कक्षा के एक प्रेरक शिक्षक ने उन्हें गणित की ओर नहीं खींचा। उन्होंने 1969 में कैलटेक से गणित में स्नातक की डिग्री हासिल की, फिर 1971 में कंप्यूटर विज्ञान में मास्टर डिग्री और 1972 में पीएचडी के लिए स्टैनफोर्ड गए, जहाँ उन्होंने रॉबर्ट फ्लॉयड और डोनाल्ड नुथ की देखरेख में प्लानरिटी एल्गोरिदम पर शोध प्रबंध लिखा। उन्होंने बाद में अपने क्षेत्र के चुनाव का वर्णन स्पष्ट रूप से किया: कंप्यूटर विज्ञान गणित करने का एक तरीका था जिसका व्यावहारिक प्रभाव हो सकता था - एक वाक्य जो उनके पूरे काम के विवरण के रूप में भी काम करता है।

टूलकिट का निर्माण

टार्जन का करियर, जो कॉर्नेल, यूसी बर्कले, स्टैनफोर्ड, एटी एंड टी बेल लैब्स, एनवाईयू, एनईसी रिसर्च इंस्टीट्यूट, माइक्रोसॉफ्ट रिसर्च, कॉम्पैक, हेवलेट पैकर्ड और इंटरट्रस्ट टेक्नोलॉजीज से होकर गुजरा और 1985 में प्रिंसटन में जेम्स एस. मैकडॉनेल डिस्टिंग्विश्ड यूनिवर्सिटी प्रोफेसर के रूप में स्थापित हुआ, ने एल्गोरिदम और डेटा संरचनाओं का एक ऐसा निकाय तैयार किया जो इस बात के लिए असामान्य है कि उनमें से कितने सैद्धांतिक जिज्ञासाओं के बजाय लोड-बेयरिंग इंफ्रास्ट्रक्चर बन गए। उनका नाम ग्राफ में दृढ़ता से जुड़े घटकों को खोजने के लिए टार्जन के एल्गोरिदम, न्यूनतम सामान्य पूर्वजों की गणना करने के लिए एक ऑफ-लाइन एल्गोरिदम, और पुलों को खोजने के लिए एक रैखिक-समय एल्गोरिदम से जुड़ा है - ये सभी तकनीकें गहराई-प्रथम खोज ढांचे पर आधारित हैं जिसे उन्होंने औपचारिक रूप दिया था। 1975 में उन्होंने पाथ कम्प्रेशन के साथ संयुक्त यूनियन-फाइंड डेटा संरचना का पहला सटीक विश्लेषण दिया, और व्युत्क्रम एकरमैन फ़ंक्शन का उपयोग करके इसके लगभग निरंतर परिशोधित रनिंग टाइम को साबित किया, एक परिणाम जो वास्तविक दुनिया के प्रदर्शन से इतना मजबूती से जुड़ा है कि यह अब क्रुस्कल के न्यूनतम-स्पैनिंग-ट्री एल्गोरिदम से लेकर कंपाइलर अनुकूलन तक सब कुछ का आधार है। बेल लैब्स में डैनियल स्लेटर के साथ उन्होंने स्प्ले ट्री का सह-आविष्कार किया, जो स्वयं-समायोजन बाइनरी सर्च ट्री हैं जो स्पष्ट संतुलन मेटाडेटा ले जाने के बजाय उपयोग के माध्यम से खुद को पुनर्संतुलित करते हैं, और उनके साथ उन्होंने प्रतिस्पर्धी विश्लेषण का बीड़ा उठाया, जो एक सर्वज्ञ प्रतिद्वंद्वी के खिलाफ ऑनलाइन एल्गोरिदम को आंकने के लिए एक ढांचा है। माइकल फ्रेडमैन के साथ उन्होंने 1985 में फाइबोनैचि हीप्स विकसित किए, जो एक प्राथमिकता-कतार संरचना है जिसने डिज्स्ट्रा के सबसे छोटे-पथ एल्गोरिदम और नेटवर्क-अनुकूलन एल्गोरिदम को पहले से मौजूद किसी भी चीज़ की तुलना में एसिम्प्टोटिक रूप से तेज़ बना दिया। उनकी पाठ्यपुस्तक, डेटा स्ट्रक्चर्स एंड नेटवर्क एल्गोरिदम, ने फ्रेडरिक डब्ल्यू. लैंकेस्टर पुरस्कार जीता और इस क्षेत्र में मानक पठन बन गई।

हॉपक्रॉफ्ट के साथ प्लानरिटी में सफलता

उनके ट्यूरिंग अवार्ड प्रशस्ति पत्र में सबसे स्पष्ट रूप से श्रेय दी गई एकमात्र उपलब्धि जॉन हॉपक्रॉफ्ट के साथ संयुक्त कार्य है: 1974 में प्रकाशित, यह परीक्षण करने के लिए पहला रैखिक-समय एल्गोरिदम कि क्या किसी ग्राफ को बिना किसी किनारे के क्रॉस किए एक विमान पर खींचा जा सकता है। प्लानरिटी परीक्षण एक धीमी, बोझिल समस्या थी, इससे पहले कि उनके एल्गोरिदम ने इसे सावधानीपूर्वक गहराई-प्रथम ट्रैवर्सल के मामले में कम कर दिया - एक तकनीक जो उनके समाधान के लिए इतनी केंद्रीय थी कि टार्जन का गहराई-प्रथम खोज का पिछला औपचारिकता, पीछे मुड़कर देखने पर, वह उपकरण बन गया जिसने हॉपक्रॉफ्ट-टार्जन परिणाम को संभव बनाया। दोनों ने 1986 का एसीएम ट्यूरिंग अवार्ड "एल्गोरिदम और डेटा संरचनाओं के डिजाइन और विश्लेषण में मौलिक उपलब्धियों के लिए" साझा किया, एक प्रशस्ति पत्र जो किसी एक पेपर के बजाय संयुक्त और समानांतर कार्यों के एक निकाय को श्रेय देता है।

चार दशकों में मान्यता

टार्जन 1983 में सूचना विज्ञान में नेवानलिना पुरस्कार के पहले प्राप्तकर्ता थे, जिन्होंने कंप्यूटर विज्ञान के गणितीय पहलुओं में उत्कृष्ट योगदान का सम्मान किया। उन्होंने 1986 में ट्यूरिंग अवार्ड जीता, 1985 में अमेरिकन एकेडमी ऑफ आर्ट्स एंड साइंसेज, 1987 में नेशनल एकेडमी ऑफ साइंसेज और 1988 में नेशनल एकेडमी ऑफ इंजीनियरिंग के लिए चुने गए। उन्होंने 1999 में सिद्धांत और व्यवहार में पेरिस कनेलाकिस पुरस्कार और 2010 में कैलटेक का डिस्टिंग्विश्ड एलुमनाई अवार्ड प्राप्त किया। उनका प्रकाशन रिकॉर्ड 250 से अधिक पत्रों के साथ हजारों की संख्या में उद्धरणों तक चलता है, और उनके पास डेटा संरचनाओं और सुरक्षा में एक दर्जन से अधिक अमेरिकी पेटेंट हैं, जो एक ऐसे करियर को दर्शाते हैं जो प्रिंसटन में अकादमिक सिद्धांत और बेल लैब्स, एनईसी और माइक्रोसॉफ्ट जैसी औद्योगिक प्रयोगशालाओं में अनुप्रयुक्त अनुसंधान के बीच तरल रूप से चलता रहा।

रॉबर्ट को जीनियस क्यों कहा जाता है

टार्जन के लिए इस शब्द का मामला कुछ विशिष्ट पर टिका है: उन्होंने केवल व्यक्तिगत कठिन समस्याओं को हल नहीं किया, उन्होंने अंतर्निहित संयोजी मशीनरी - गहराई-प्रथम खोज, परिशोधित विश्लेषण, स्वयं-समायोजन - की पहचान की, जिसने पहले से धीमी एल्गोरिदम की पूरी श्रेणियों को तेज़ बना दिया, और उन्होंने इसे एक बार के बजाय चार दशकों में बार-बार किया। यूनियन-फाइंड विश्लेषण और हॉपक्रॉफ्ट-टार्जन प्लानरिटी एल्गोरिदम सटीक रूप से इसलिए पाठ्यपुस्तक सामग्री बने हुए हैं क्योंकि वे चतुर तरकीबें नहीं हैं, बल्कि सामान्य तकनीकें हैं जिन्हें अन्य शोधकर्ता पुन: उपयोग कर सकते हैं; वह पुन: प्रयोज्यता, किसी भी एक परिणाम से अधिक, वह है जिसे नेवानलिना पुरस्कार और ट्यूरिंग अवार्ड समितियों ने पुरस्कृत किया था। ईमानदार जटिलता यह है कि उनका सबसे प्रसिद्ध परिणाम, रैखिक-समय प्लानरिटी एल्गोरिदम, स्पष्ट रूप से जॉन हॉपक्रॉफ्ट के साथ संयुक्त कार्य है, और ट्यूरिंग अवार्ड प्रशस्ति पत्र दोनों पुरुषों को संयुक्त रूप से श्रेय देता है, न कि किसी एक को एकल जीनियस के रूप में ताज पहनाता है - पुरस्कार स्वयं इस बात का प्रमाण है कि क्षेत्र इसे एक एकल आविष्कार के बजाय एक सहयोगात्मक उपलब्धि के रूप में मानता है। टार्जन के अन्य ऐतिहासिक परिणाम भी इसी तरह नामित सह-लेखकों के साथ बनाए गए थे: डैनियल स्लेटर के साथ स्प्ले ट्री, माइकल फ्रेडमैन के साथ फाइबोनैचि हीप्स। जो निर्विवाद है वह उनके नाम वाले मौलिक, अभी भी पढ़ाए जाने वाले परिणामों का घनत्व है, एक ऐसा रिकॉर्ड जिसे क्षेत्र में बहुत कम लोगों ने हासिल किया है।

विरासत

हर कंप्यूटर विज्ञान का छात्र जो गहराई-प्रथम खोज, यूनियन-फाइंड, स्प्ले ट्री, या फाइबोनैचि हीप्स सीखता है, वास्तव में, टार्जन के पत्रों द्वारा अभी भी पढ़ाया जा रहा है, उनके लिखे जाने के दशकों बाद। उनका काम कंपाइलर, नेटवर्क रूटिंग और भौगोलिक सूचना प्रणालियों के नीचे बैठता है, बिना इसके अधिकांश उपयोगकर्ताओं को उनका नाम जाने - इंफ्रास्ट्रक्चर-स्तरीय गणित का शांत भाग्य जो पूरी तरह से सफल रहा। उन्होंने अपने सत्तर के दशक तक नए परिणाम देना जारी रखा, प्रिंसटन के संकाय और इंटरट्रस्ट टेक्नोलॉजीज में मुख्य वैज्ञानिक और माइक्रोसॉफ्ट और हेवलेट पैकर्ड में शोधकर्ता के रूप में भूमिकाओं के बीच चलते रहे, एक करियर आकार जो खुद उन्हें विशुद्ध रूप से अकादमिक व्यक्ति के रूप में मानने के खिलाफ तर्क देता है: उनका अधिकांश सबसे उद्धृत कार्य विश्वविद्यालय के वैक्यूम के बजाय औद्योगिक अनुसंधान प्रयोगशालाओं के अंदर किया गया, परीक्षण किया गया और लागू किया गया। यह दोहरा जीवन, व्यावहारिक प्रणालियों का पेटेंट कराते समय कठोर गणित प्रकाशित करना, वह हिस्सा है जो उनके रिकॉर्ड को उन सिद्धांतकारों से अलग करता है जिनके विचार पत्रिकाओं तक ही सीमित रहे।