कुतूहल : अल्गोरिदम – किती कठीण?

संगणकशास्त्रात मुळात अल्गोरिदम किती कठीण आहे याची तपासणी आवश्यक ठरते.

दिलेल्या प्रश्नाची उकल करण्यासाठी रीत कशी वापरायची याचे काटेकोर वर्णन म्हणजे अल्गोरिदम. संगणकाच्या कार्यात अल्गोरिदम कळीची भूमिका बजावतो. त्यामुळे अल्गोरिदम अत्यंत कार्यक्षम असणे अपेक्षित असते. म्हणजे उत्तर काढण्यास तो संगणकाचा कमीत कमी वेळ घेईल आणि किमान संसाधने, उदाहरणार्थ, स्मृतिमंजूषा वापरील. तंत्रज्ञानाच्या प्रगतीने अधिक जलद गतीने काम करणारे किंवा समांतररीत्या काम करणारे महासंगणकातील प्रक्रियक (प्रोसेसर्स) आणि प्रचंड प्रमाणात स्मृतिमंजूषा असलेले संगणक उपलब्ध होत असले तरी त्यांवर मर्यादा आहेच. म्हणून संगणकशास्त्रात मुळात अल्गोरिदम किती कठीण आहे याची तपासणी आवश्यक ठरते. असा अभ्यास ‘प्रगणन व्यामिश्रता’ (कम्प्युटेशनल कॉम्प्लेक्सिटी) अशा व्यापक संज्ञेने ओळखला जातो. अल्गोरिदम व्यामिश्रता हा त्याचा एक पैलू आहे. त्याचे दोन प्रमुख भाग आहेत. एक म्हणजे अल्गोरिदमची वेळ व्यामिश्रता (टाइम कॉम्प्लेक्सिटी) आणि दुसरी म्हणजे माहिती साठवून ठेवण्याबाबतची अंतराळ व्यामिश्रता (स्पेस कॉम्प्लेक्सिटी). यातील वेळ व्यामिश्रता तुलनेत अधिक महत्त्वाची मानली जाते, कारण संगणक किती वेळात उत्तर देईल, की देऊच शकणार नाही हे समजणे प्रत्यक्ष व्यवहारात महत्त्वाचे ठरते.

अल्गोरिदम व्यामिश्रतेच्या मोजमापनासाठी सहसा प्रश्नासाठी निविष्टी (इनपुट) म्हणून वापरल्या जाणाऱ्या संख्या किंवा अन्य माहिती, यांचा एकूण आकार हा एकक (युनिट) मानला जातो. समजा तो आकार ‘न’ आहे. तरी अल्गोरिदमला उत्तर काढण्यास लागणारा वेळ, ‘न’च्या विविध स्वरूपांवर अवलंबून असू शकतो आणि त्याप्रमाणे प्रश्नांची काठिण्यपातळी बदलत जाते. उदाहरणार्थ, सोबतच्या तक्त्यामध्ये उत्तरासाठीचा वेळ ‘न’च्या विविध स्वरूपांत कसा असतो हे विविध व्यामिश्रता संज्ञांनी दर्शवले आहे.

अल्गोरिदमला उत्तर काढण्यास लागणारा वेळ ‘न’च्या एखाद्या बहुपदीच्या (पॉलिनोमिअल) प्रमाणात असेल तर तो अल्गोरिदम प्रभावी मानला जातो. अशा प्रकारच्या प्रश्नांना पॉलिनोमिअल म्हणजे ‘पी’ (ढ) समूहातील प्रश्न म्हटले जाते. मात्र काही प्रश्नांसाठी बहुपदीने मर्यादित केलेला अल्गोरिदम नसतो, परंतु मिळालेले उत्तर बरोबर आहे की नाही हे तपासणे सोपे असते. अशा प्रकारच्या प्रश्नांना ‘नॉनडिटरमिनिस्टिक पॉलिनोमिअल’ म्हणजेच ‘एनपी’ (ठढ) समूहातील प्रश्न म्हणतात. साहजिकच असे काही प्रश्न आहेत का जे एनपी समूहात आहेत पण पी समूहात नाहीत? थोडक्यात पी = एनपी हे खरे आहे का, हा प्रश्न अजून अनुत्तरित आहे. मात्र ‘एनपी कम्प्लीट प्रश्न’ या नावाचा एक समूह आहे ज्यातील एक प्रश्न जरी बहुपदी वेळ घेणारा अल्गोरिदम सोडवू शकला तर, त्या समूहातील सारे प्रश्न सोडवता येतील! संशोधनासाठी अल्गोरिदम व्यामिश्रता हा सखोल आणि विस्तृत विषय आहे.

– डॉ. विवेक पाटकर

मराठी विज्ञान परिषद,

वि. ना. पुरव मार्ग,  चुनाभट्टी,  मुंबई २२  office@mavipamumbai.org

Loksatta Telegram लोकसत्ता आता टेलीग्रामवर आहे. आमचं चॅनेल (@Loksatta) जॉइन करण्यासाठी येथे क्लिक करा आणि ताज्या व महत्त्वाच्या बातम्या मिळवा.

मराठीतील सर्व नवनीत बातम्या वाचा. मराठी ताज्या बातम्या (Latest Marathi News) वाचण्यासाठी डाउनलोड करा लोकसत्ताचं Marathi News App. ताज्या बातम्या (latest News) फेसबुक , ट्विटरवरही वाचता येतील.

Web Title: Algorithm play a key role in computer operations zws

Next Story
कुतूहल : दूषित पाणी प्यायल्यामुळे प्राण्यांना होणारे रोग