What is algorithm? {Algorithm क्या है?}
किसी भी समस्या का step-by-step तरीके से समाधान निकालने की प्रक्रिया को Algorithm कहते है। इसके जरिये हम Problem को छोटे-छोटे भागों में बाँटकर उसे Solve करते है।
Algorithm (Al-go-rith-um) यह एक Procedure (Step by Step Process) या फिर यह एक Formula है, जो की एक Problem को Solve करता है। यह एक Procedure है जिसमें सीमित rules होते हैं, जिन्हें Instruction भी कहा जाता है। इन rules को one-by-one steps में लिखा जाता है और हर एक rules/steps कुछ ना कुछ Operation को दर्शाते हैं। इन rules के जरिए Problem का Solution निकलते हैं। Algorithm को Problem के Solution का या किसी काम को करने का Procedure या Formula भी कहा जा सकता है।
Daily life के Example से Algorithm को समझते हैं माना हमें चाय बनानी है तो उसकी Algorithm कैसे लिखेंगे-
1. गैस ON करेंगे।
2. बर्तन में पानी व चाय पत्ती डाल गर्म करेंगे।
3. अब उसमें दूध व चीनी मिलायेंगे।
4. गर्म होने के बाद गैस बंद करेंगे।
5. चाय को छानकर कप में डाल लेंगे चाय तैयार है। यह बहुत ही Basic Example है।
Computer Programming के क्षेत्र में Algorithm का उपयोग Algorithm का उपयोग ज्यादातर Computer और Programming के Field में किया जाता है। यह भी कह सकते है कि Computer पूरी तरह से Algorithm के द्वारा चलता है। Algorithm निर्देशों का एक Set (समूह) है जिसके द्वारा किसी विशेष problem (समस्या) को solve किया जाता है। दूसरे शब्दों में कहें तो, “algorithm एक process है जिसके द्वारा programming में आने वाली problems को solve किया जाता है। Algorithm (एल्गोरिथम) rules (नियमों) का एक set (समूह) होता है जिनका इस्तेमाल step by step किसी काम को पूरा करने में किया जाता है। Algorithm (एल्गोरिथम) का प्रयोग mathematics और computer science में Problems को सुलझाने के लिए किया जाता है। यह जटिल (complex) कार्यों को करने में सक्षम होता है।
Algorithm का प्रयोग किसी भी programming language जैसे C, C++, Java, और Python आदि में कर सकते हैं। Computer में किसी भी काम को करने के लिए Computer program या Software की आवश्यकता होती है। एक Computer program को Programming द्वारा बनाया जाता है। Programming में step-by-step instructions लिखते हैं। तथा इन्हीं instructions के माध्यम से बताना होता है कि कौनसा काम कैसे करना है। इन्हीं सुव्यवस्थित steps को algorithm कहा जाता है। Algorithm को coding करने से पहले ही तैयार कर लिया जाता है और इसी के अनुसार Code लिखा जाता है। Algorithm से flow chart भी बनाया जाता है जो कि पूरे process को graphical तरीके से represent करता है।
Algorithm का उपयोग
Algorithm problem solution step-by-step तरीके से दर्शाते हैं। फिर उन steps को follow करके समस्या को सुलझा सकते है। Algorithm का उद्देश्य किसी task को perform करके output प्राप्त करना होता है। Algorithm में समस्या के होते है। अनुसार बहुत सारे निश्चित steps जब तक सारे steps एक sequence में पूरे नहीं होते है user को output प्राप्त नहीं होता है। अर्थात् Algorithm हमें बताता है कि किसी काम को कैसे करना है।
Algorithm की जरूरत क्या है (Need of Algorithm)
Algorithm हमें problem का विश्लेषण करने तथा इसको समाधान करने के लिए बुनियादी तरीका बताता है। कई कारणों से इसकी जरूरत महसूस होता है। Algorithm की जरूरत निम्न कारणों में है-
- Algorithm वर्तमान तकनीक की efficiency को improve करता है।
- इसकी सहायता से एक Technology की दूसरे Technology से तुलना करते हैं।
- Algorithm की सहायता से flow of control को समझने में मदद मिलती है।
- Algorithm, Input, Output and Memory के जरूरत की पहचान करता है।
- Algorithm की मदद से problem की time complexity और space complexity को analysis और calculate करते हैं।
- इसकी सहायता से किसी भी Method की परफॉर्मेंस (Best case, Worst case, average case) measure करते हैं।
- Algorithm, design में होने वाले खर्च को कम करता है।
एल्गोरिथम की विशेषताएँ (Characteristics of Algorithm)
एक सही Algorithm को लिखने के लिए बहुत सी बातों का ध्यान रखना पड़ता है जिनमें से कुछ महत्वपूर्ण characteristics निम्न है-
Input — Problem के solution के लिए कुछ न कुछ चीजों की आवश्यकता होती है जिसे input कहा जाता है। Algorithm में 0 (Zero) या उससे अधिक inputs हो सकते है।
Output — Steps follow करने के बाद क्या Output या परिणाम मिलेगा यह भी पहले से define होना चाहिए। Unambiguous (स्पष्ट )— Process पूरी तरह से स्पष्ट होनी चाहिए। ऐसी Algorithm जो Confusion पैदा करती है वह user का समय व resources बर्बाद कर सकती है। Feasible किसी process के लिए data पर्याप्त मात्रा में होने चाहिए। एक algorithm तभी बनायी जा सकती है जब user को पता हो की जो task perform करने जा रहे है क्या वह संभव है व user के पास उपलब्ध data या resources से क्या उस task को पूरा कर सकते है। तो एक algorithm बनायी जा सकती है।
Independent (स्वतंत्र) – Algorithm स्वतंत्र होनी चाहिए। यह किसी language पर निर्भर नहीं होनी चाहिए अर्थात् इसका उपयोग सभी languages में किया जा सकता है। Finiteness (परिमित) Algorithm finite (परिमित) अर्थात् उसकी सीमा होनी चाहिए, यह infinite (अपरिमित) नहीं हो सकती।
Algorithm का उपयोग कहाँ होता है?
Algorithm 34 Mathematics, Science, Computer Programming, Artificial Intelligent, Medical जैसे क्षेत्रों में अधिक उपयोग में ली जाती है। एक सामान्य मनुष्य Daily life में रोजमर्रा के कुछ कामों में Algorithm का उपयोग करता है-
★ Social Media Platform, algorithm का उपयोग करते है। जिससे कोई Post viral हो जाती है।
★ Search Engine result page पर केवल top की sites को दिखाया जाता है। Search engine, web sites को उनकी quality के आधार पर rank देते है और अच्छी sites को पहले page पर दिखाया जाता है। इस काम के लिए ranking algorithm का उपयोग किया जाता है। Computer system पर एक ही समय में कई सारे task चलते रहते है, Operating system के Scheduling algorithm इन सभी tasks को उनकी priority के आधार पर process करती है।
एल्गोरिथम के फायदे (Advantage of Algorithm Algorithm)
किसी भी problem के solution को छोटे-छोटे parts में divide कर देता है जिससे इसे समझने में आसानी होती है। Algorithm step by step solution उपलब्ध करता है जिससे इसकी Clarity (स्पष्टता) बढ़ जाती है। किसी Task को Complete करने के लिए हमें किन-किन चीजों की जरूरत है यह पहले ही algorithm के माध्यम से पता चल जाता है। Algorithm, Decision making को आसान बनाता है। Algorithm बनने के बाद इसके अनुसार किसी भी programming language में code लिखा जा सकता है अर्थात् यह किसी Programming language पर depend (निर्भर) नहीं होता। यह किसी problem को सुलझाने में मदद करता है। Algorithm को वास्तविक प्रोग्राम में convert करना आसान होता है। इसमें debugging करना आसान होता है। Algorithm की मदद से बड़ी problems को छोटी problems में विभाजित कर सकते है। यह program के blue print की तरह कार्य करता है इसलिए program को लिखना बहुत आसान हो जाता है।
Algorithm के नुकसान
Algorithm बनाने में काफी समय लगता है इसलिए यह time consuming work है। Algorithm में looping और Branching को दर्शाना थोड़ा कठिन है अर्थात् इसमें loop statement जैसे कि While loop, For loop आदि को दिखाना मुश्किल होता है। बड़े Project के लिए algorithm बनाने में काफी मेहनत लगती है।
Example of Algorithm (Algorithm के उदाहरण) एक Algorithm कैसे बनायी जाती है उदाहरण के तौर पर समझते है।
Example 1 : User द्वारा enter किये गये दो Number को जोड़ने के लिए Algorithm-
Step 1 : Start
Step 2 : Declare variables number1, number2 and Result.
Step 3 : Read values number1 and number2
Step 4 : Add number1 and number2 and assign the result to Result
Step 5 : Display Result
Step 6 : Stop
Example 2 : तीन number में से सबसे बड़ी संख्या को खोजना-
Step 1 : Start
Step 2 : declare Variables A, B and C.
Step 3 : Read variables values A, B and C
Step 4 : If A > B If A > C
Else Display “A is the largest number”. Display “C is the largest number”. Display “B is the largest number”.
Else
If B > C
Display “C is the largest number”.
Else
Step 5 : Stop
Types of Algorithm (एल्गोरिथम के प्रकार) Algorithm के निम्नलिखित प्रकार हैं-
Search : इस algorithm (एल्गोरिथम) का इस्तेमाल किसी item को खोजने के लिए किया जाता है।
Sort : इस algorithm (एल्गोरिथम) का इस्तेमाल items को एक विशेष क्रम में sort करने के लिए किया जाता है।
Delete : इस algorithm (एल्गोरिथम) का इस्तेमाल items को delete करने के लिए किया जाता है।
Insert : इस algorithm (एल्गोरिथम) का इस्तेमाल items को insert करने के लिए किया जाता है या नया items जोड़ने में।
Update : इस algorithm (एल्गोरिथम) का प्रयोग पहले से मौजूद items को update करने के लिए किया जाता है।
Complexity of Algorithm (एल्गोरिथम की जटिलता) : किसी Algorithm की complexity को दो प्रकार से मापा जाता
- Time Complexity (टाइम कॉम्प्लेक्सिटी)
एक algorithm की time complexity, एल्गोरिथम के द्वारा अपनी process को पूरा करने में लगने वाले कुल time (समय) की मात्रा है। ज्यादातर एल्गोरिथम की time complexity को Big O notation का उपयोग करके व्यक्त किया जाता है। यह एक asymptotic notation है। इसको व्यक्त करने के सभी notations निम्नलिखित हैं-
Big O – O(n)
Big Theta – 0 (n)
Big Omega – 2 (n)
Execution को समाप्त करने के लिए किसी भी algorithm द्वारा perform किये गये steps की संख्या की गिनती (counting) के द्वारा time complexity को estimate किया जाता है।
2. Space Complexity (स्पेस कॉम्प्लेक्सिटी)
एक algorithm की ‘ space complexity, algorithm के द्वारा ली गई space की मात्रा है। Space complexity के अंदर auxiliary space तथा input के द्वारा use लिया गया space दोनों आते हैं। Auxiliary space वह होता है जो algorithm के द्वारा execution के दौरान प्रयोग किया गया temporary space या extra space होता है। एक algorithm की space complexity को Big 0 (n) notation के द्वारा व्यक्त किया जाता है। बहुत सारी algorithms के पास inputs होते हैं जो size में different होते हैं ऐसी स्थिति में space complexity input के size पर निर्भर रहती है।
Factor of Algorithm (एल्गोरिथम के फैक्टर) किसी भी algorithm को लिखने से पहले कुछ factors को ध्यान में रखा जाता है-
Modularit दी गयी problem को छोटे छोटे steps में विभाजित करना modularity कहलाता है।
Correctness : यदि दिए गए input के द्वारा वांछित output प्राप्त होता है तो उससे पता चलता है कि एल्गोरिथम correct (सही) है।
Maintainability : इसमें maintainability का अर्थ है हमें algorithm (एल्गोरिथम) को बहुत ही सरल तरीके से लिखना चाहिए, जिससे कि हमें बाद में इसमें ज्यादा बदलाव ना करना पड़े।
Functionality : इसमें बहुत सारे steps आते हैं जो वास्तविक दुनिया की problems को solve करते हैं।
Rebustness : यह algorithm की क्षमता होती है जिसके द्वारा problem को सही तरीके से define किया जाता है।
User-friendly : Algorithm user friendly (यूजर फ्रेंडली) होनी चाहिए अर्थात् user के आसानी से समझ में आ सके। Simplicity अगर algorithm simple होती है तो उसे समझना आसान होता है।
Extensibility Algorithm : extensible होनी चाहिए जिससे कि इसका इस्तेमाल कोई दूसरा Designer (डिजाइनर) और Programmer (प्रोग्रामर) भी कर सकें। Design Techniques (एल्गोरिथम डिजाइन तकनीकी) Algorithm Algorithm के लिए एक सही design technique को select करना कठिन है परन्तु यह बहुत ही महत्वपूर्ण कार्य है। Programming (प्रोग्रामिंग) में किसी भी programming language का प्रयोग कर सकते हैं लेकिन algorithm design techniques को सीखना important होता है क्योंकि यह सभी languages में काम में आता है।
कुछ मुख्य Algorithm Design Techniques निम्नलिखित हैं-
- Divide and conquer
- Greedy Method
- Dynamic Programming
- Backtracking
- Branch & Bound
- Linear Programming
Divide and Conquer : Divide and conquer approach
Divide and conquer में, एक problem को छोटे छोटे sub-problems में divide (विभाजित) कर लिया जाता है। उसके बाद इन sub-problems को एक एक करके solve किया जाता है और अंत में सभी solutions को combine करके main problem का solution प्राप्त किया जाता है।
इसमें प्रत्येक level में निम्नलिखित तीन steps होते हैं-
Divide : Main problem को sub-problems में विभाजित किया जाता है।
Conquer Sub-problems one by one solve किया जाता है।
Combine सभी sub-problems के solutions को एक साथ मिलाकर main problem का solution प्राप्त किया जाता है।
Divide and conquer approach का उपयोग निम्नलिखित algorithms में होता है-
Binary Search, Quick Sort, Merge Sort Integer Multiplication Matrix Multiplication Matrix Inversion
2. Greedy Method Greedy method का उपयोग optimization problem को solve करने के लिए किया जाता है। एक optimization problem वह होती है जिसमें हमें input values का एक set दिया जाता है, जिसे या तो बढ़ाने या कम करने की आवश्यकता होती है। इस greedy method को कठिन problems में apply करना बहुत ही आसान होता है। Greedy method decide करता है कि कौन-सा step अगले step में सबसे सही solution प्रदान करेगा। इसलिए इसे greedy कहा जाता है क्योंकि यह हर step पर सबसे अच्छा solution खोजने की कोशिश करता है। इसमें पहले step को इस प्रकार select किया जाता है कि तुरंत benefit दे सके।
Greedy Algorithm क्या है?
सभी algorithm approaches में से सबसे सरल और सीधी approach greedy algorithm है। इस approach में, भविष्य की चिंता किये बिना वर्तमान में उपलब्ध जानकारी के आधार पर निर्णय लिया जाता है। यह एक सरल तरीका है जो ह step पर सबसे अच्छा solution खोजने की कोशिश करता है। इसमें पहले step को इस प्रकार चुना जाता है कि वह तुरंत benefit (लाभ) देता है। यह approach पिछले चुने गये solution को दुबारा से नहीं देखती है। इस approach को मुख्य रूप से optimization problems को solve करने के लिए किया जाता है। Greedy algorithm को implement करना बहुत ही आसान है और बहुत सारे मामलों में यह efficient भी होती है। इसलिए greedy algorithm एक algorithmic paradigm है जो कि अनुमान पर आधारित है। यह global optimal solution खोजने की आशा के साथ प्रत्येक step में local optimal choice को follow करता है। कई problems में यह optimal solution प्रदान नहीं करता है परन्तु यह एक उचित समय में optimal (श्रेष्ठ) के आसपास का solution दे देता है या नहीं। Components of Greedy Algorithm Greedy algorithms के निम्नलिखित 5 components होते हैं-
Candidate Set इस set के द्वारा solution को create किया जाता है। Selection Function इसका use solution में सबसे best candidate को add करने के लिए किया जाता है। Feasibility Function इसका उपयोग यह निर्धारित करने के लिए किया जाता है कि क्या candidate को solution में योगदान करने के लिए इस्तेमाल किया जा सकता है।
Objective Function इसका प्रयोग solution या partial Solution को एक value देने के लिए किया जाता है।
Solution Function : इसका प्रयोग यह indicate करने के लिए किया जाता है कि क्या पूरा solution प्राप्त हो चुका है। Greedy Algorithm के अनुप्रयोग (Applications) इसका use बहुत सारी problems को solve करने के लिए किया। जाता है जैसे कि- इसका उपयोग Dijkstra’s algorithm का use करके दो vertices के बीच shortest path खोजने के लिए किया जाता है। इसका उपयोग Prim’s/Kruskal’s algorithm का use करके graph में minimal spanning tree खोजने के लिए किया जाता है।
3. Dynamic Programming : Dynamic programming एक bottom up approach है, इसमें हम सभी संभावित छोटी problems को solve करते हैं और फिर बड़ी problems के solution को प्राप्त करने के लिए उन्हें combine करते हैं। Divide and conquer method के विपरीत dynamic programming कई बार sub-problems के solution का फिर से उपयोग करता है। Fibonacci Series के लिए recursive algorithm इसका उदाहरण है।
4. Backtracking : Combination eft problems solve करने के लिए backtracking एक optimization technology Backtracking का प्रयोग programs और real life दोनों में किया जाता है। Backtracking eight queen problem Sodoku puzzle और Maze आदि में किया जाता है। Backtracking में, user एक possible solution के साथ शुरू करता है, जो सभी आवश्यक conditions को पूरा करता है। फिर अगले level पर जाता है और यदि वह level संतोषजनक solution नहीं देता है, तो user एक level वापस पीछे आता है और एक नए option के साथ शुरू करता हैं।
5. Branch and Boun : इस algorithm में दिए हुए sub-problem, जिसे bound नहीं किया जा सकता है, को कम से कम दो नए restricted sub-problems में विभाजित किया जाता है। Non-convex problems में global optimization के लिए यह algorithm method है। Branch and bound search 3 depth bounded search और depth-first search में किया जाता है।
6. Linear Programming : Linear Programming में बहुत सारे optimization job describe किया गया है जहाँ, optimization criteria और constraints दोनों linear functions होते हैं। इस Technique का प्रयोग सबसे अच्छे परिणाम प्राप्त करने में किया जाता है जैसे – maximum profit, shortest path, या lowest cost आदि। इस programming में user के पास variables का एक set होता है और user को linear equations के set को संतुष्ट करने के लिए absolute (पूर्ण) वैल्यू assign करनी होती है।