Algorithms CS 3005 all units notes in hindi

Rajasthan Polytechnic (BTER) February 08, 2025

 Hello Everyone,

Garima Kanwar This Side. These Notes are short notes for revision purpose only. Please Refer Your college study material & Reference Book for Complete Study.


For Further Notes 📄 & Videos 🎥 Subscribe BTER Polytechnic Classes 🎥 YouTube Channel & Join WhatsApp Group & Whatsapp Group.


📍YouTube Channel - https://www.youtube.com/@Polytechnicbter

📌Instagram Account - https://www.instagram.com/bterpolytechnicclasses


📍Telegram Channel - https://t.me/polytechnicbter


📍WhatsApp Channel - https://whatsapp.com/channel/0029Vb3ggEG7dmedl2pJd30p

📌WhatsApp Group - https://chat.whatsapp.com/DWpN7vYqSutBNXY9R5Q2Te 


Course Code CS 3005(Same as IT 3005)
Course Title Algorithms

💥💥UNIT 1💥💥

1. Fundamentals (मूल बातें)

इस खंड में कंप्यूटर विज्ञान और प्रोग्रामिंग के कुछ महत्वपूर्ण बुनियादी पहलुओं का वर्णन किया गया है, जो किसी भी कंप्यूटर प्रोग्राम को समझने और सही तरीके से डिज़ाइन करने के लिए महत्वपूर्ण होते हैं।

1.1. Programming Models (प्रोग्रामिंग मॉडल्स)

प्रोग्रामिंग मॉडल यह वह तरीका है, जिसमें हम किसी समस्या को हल करने के लिए कंप्यूटर के साथ संवाद करते हैं। प्रोग्रामिंग के विभिन्न मॉडल्स को समझने से यह जानने में मदद मिलती है कि अलग-अलग स्थितियों में कौन सा मॉडल सबसे अच्छा रहेगा। सबसे आम प्रोग्रामिंग मॉडल्स में शामिल हैं:

  • Imperative Model (आदेशात्मक मॉडल): इसमें हम प्रोग्राम को एक सीक्वेंस में निर्देश देते हैं और कंप्यूटर को उन निर्देशों के अनुसार काम करने का आदेश देते हैं।
  • Declarative Model (घोषणात्मक मॉडल): इसमें हम केवल यह बताते हैं कि हमें क्या चाहिए, न कि यह कि यह कैसे करना है।
  • Object-Oriented Model (वस्तु-उन्मुख मॉडल): यह प्रोग्रामिंग का एक तरीका है जिसमें डेटा और उसके साथ जुड़े कार्य (functions) को एक साथ रखा जाता है, जिसे "वस्तुएं" (objects) कहा जाता है।

1.2. Data Abstraction (डेटा अमूर्तिकरण)

डेटा अमूर्तिकरण (Data Abstraction) का मतलब है कि हम किसी डेटा संरचना को इस प्रकार प्रस्तुत करें, ताकि उपयोगकर्ता को उसके आंतरिक कार्यप्रणाली की जानकारी न हो, बल्कि केवल डेटा से संबंधित आवश्यक कार्यों की जानकारी हो।

1.2.1. Sets (संग्रह)

सेट एक संगठित समूह है जिसमें विभिन्न प्रकार के तत्व हो सकते हैं, लेकिन प्रत्येक तत्व केवल एक बार ही मौजूद होता है।

  • विशेषताएँ:
    • किसी भी सेट में कोई भी तत्व एक ही बार हो सकता है।
    • सेट में तत्वों का क्रम मायने नहीं रखता।

उदाहरण: {1, 2, 3, 4, 5} एक सेट है।

सेट ऑपरेशन्स:

  • Union: दो सेट्स का जोड़। उदाहरण: A ∪ B
  • Intersection: दो सेट्स का सामान्य हिस्सा। उदाहरण: A ∩ B
  • Difference: एक सेट में दूसरे सेट के तत्वों को हटाना। उदाहरण: A - B

सेट का चित्र:

A = {1, 2, 3}
B = {3, 4, 5}

A ∪ B = {1, 2, 3, 4, 5}
A ∩ B = {3}
A - B = {1, 2}

1.2.2. Multisets (मल्टीसेट्स)

मल्टीसेट (जिसे अक्सर बैग भी कहा जाता है) एक सेट जैसा होता है, लेकिन इसमें एक ही तत्व एक से अधिक बार हो सकता है।

  • विशेषताएँ:
    • मल्टीसेट में एक ही तत्व कई बार हो सकते हैं।

उदाहरण: {1, 1, 2, 3, 3, 3} एक मल्टीसेट है।

मल्टीसेट ऑपरेशन्स:

  • Union: जैसे सेट का युनियन होता है वैसे ही मल्टीसेट का युनियन होता है, लेकिन इसमें तत्वों की आवृत्ति (frequency) को ध्यान में रखा जाता है।
  • Intersection: मल्टीसेट का इंटरसेक्शन में हमें आम तत्वों की न्यूनतम आवृत्ति मिलती है।

1.2.3. Stacks (स्टैक्स)

स्टैक एक डेटा संरचना है जिसमें "LIFO" (Last In First Out) का सिद्धांत लागू होता है। इसका मतलब है कि जो तत्व सबसे बाद में डाला गया हो, वही सबसे पहले निकाला जाएगा।

  • ऑपरेशन्स:
    • Push: स्टैक में तत्व जोड़ना।
    • Pop: स्टैक से तत्व हटाना।
    • Peek: स्टैक के शीर्ष पर मौजूद तत्व को देखना।
    • IsEmpty: स्टैक खाली है या नहीं, यह चेक करना।

स्टैक का चित्र:

Top ->  [5]  <- Push(5)
         [4]  <- Push(4)
         [3]  <- Push(3)
         [2]  <- Pop() -> 3
         [1]  <- Push(1)

1.2.4. Queues (क्यूज)

क्यू एक डेटा संरचना है जिसमें "FIFO" (First In First Out) का सिद्धांत लागू होता है। इसका मतलब है कि जो तत्व पहले डाला गया हो, वही पहले निकाला जाएगा।

  • ऑपरेशन्स:
    • Enqueue: क्यू में तत्व जोड़ना।
    • Dequeue: क्यू से तत्व निकालना।
    • Front: क्यू के सामने वाले तत्व को देखना।
    • IsEmpty: क्यू खाली है या नहीं, यह चेक करना।

क्यू का चित्र:

Front -> [1]  <- Enqueue(1)
            [2]  <- Enqueue(2)
            [3]  <- Enqueue(3)
            [4]  <- Dequeue() -> 1
            [5]  <- Enqueue(5)

1.3. Asymptotic and Worst-case Analysis of Algorithms (असिम्प्टोटिक और सबसे खराब स्थिति विश्लेषण)

असिम्प्टोटिक विश्लेषण (Asymptotic Analysis) का उपयोग किसी एल्गोरिथ्म के प्रदर्शन को समय या स्थान की दृष्टि से मापने के लिए किया जाता है। इसमें हम यह जानने की कोशिश करते हैं कि एल्गोरिथ्म बड़े इनपुट के लिए कैसे प्रदर्शन करेगा।

विभिन्न प्रकार के समय जटिलता:

  1. O(1) - स्थिर समय (Constant Time): एल्गोरिथ्म का समय इनपुट आकार के साथ नहीं बदलता।
  2. O(n) - रेखीय समय (Linear Time): समय इनपुट आकार के अनुपात में बढ़ता है।
  3. O(n^2) - द्विगुणी समय (Quadratic Time): समय इनपुट आकार के वर्ग के अनुपात में बढ़ता है।
  4. O(log n) - लॉगारिथमिक समय (Logarithmic Time): समय इनपुट आकार के लॉग के अनुपात में बढ़ता है।

Worst-Case Analysis (सबसे खराब स्थिति का विश्लेषण): इसमें हम एल्गोरिथ्म की सबसे खराब स्थिति का अध्ययन करते हैं, यानी, उस स्थिति का विश्लेषण करते हैं जिसमें एल्गोरिथ्म अधिकतम समय लेता है।

उदाहरण के लिए, एक सॉर्टिंग एल्गोरिथ्म में सबसे खराब स्थिति तब होती है जब एल्गोरिथ्म को पूरे डेटा को देखना पड़ता है, जैसे QuickSort का औसत समय O(n log n) होता है, लेकिन सबसे खराब स्थिति में यह O(n^2) हो सकता है।


💥💥UNIT 2💥💥

2. Sorting (सॉर्टिंग)

सॉर्टिंग का मतलब है किसी सूची (list) के तत्वों को किसी विशेष क्रम (ascending या descending) में व्यवस्थित करना। सॉर्टिंग एल्गोरिदम कंप्यूटर विज्ञान में महत्वपूर्ण होते हैं क्योंकि वे डेटा को व्यवस्थित करने में मदद करते हैं, जिससे उसे आसानी से खोजा और उपयोग किया जा सकता है। सॉर्टिंग की समस्या में, एक नीतिगत एल्गोरिदम का चयन किया जाता है जो सूची को कम से कम समय और स्थान में व्यवस्थित करता है।

2.1. The Sorting Problem (सॉर्टिंग समस्या)

सॉर्टिंग समस्या तब उत्पन्न होती है जब हमें एक सूची दी जाती है और हमे उसे किसी विशेष क्रम में व्यवस्थित करना होता है। सबसे सामान्य प्रकार की सॉर्टिंग:

  • Ascending Order: छोटे से बड़े क्रम में (जैसे 1, 2, 3, 4, 5)
  • Descending Order: बड़े से छोटे क्रम में (जैसे 5, 4, 3, 2, 1)

सॉर्टिंग एल्गोरिदम का लक्ष्य यह होता है कि हम किसी सूची के तत्वों को न्यूनतम समय में व्यवस्थित कर सकें। इसमें समय की जटिलता (Time Complexity) और स्थान की जटिलता (Space Complexity) को ध्यान में रखा जाता है।

2.2. Bubble Sort (बबल सॉर्ट)

बबल सॉर्ट एक सरल सॉर्टिंग एल्गोरिदम है जो लगातार सूची के तत्वों की तुलना करता है और उन्हें स्वैप करता है यदि वे गलत क्रम में होते हैं। यह प्रक्रिया तब तक जारी रहती है जब तक पूरी सूची क्रमबद्ध नहीं हो जाती।

ऑपरेशन:

  1. सूची के पहले तत्व से शुरू करें।
  2. प्रत्येक तत्व को अगले तत्व से तुलना करें।
  3. यदि वे गलत क्रम में हैं, तो उन्हें स्वैप करें।
  4. इस प्रक्रिया को सूची के अंत तक दोहराएं।

समय जटिलता:

  • Worst-case: O(n^2)
  • Best-case: O(n) (जब सूची पहले से सॉर्टेड हो)

चित्र:

Unsorted List: [5, 2, 9, 1, 5, 6]

Pass 1: [2, 5, 1, 5, 6, 9] (9 is bubbled to the end)
Pass 2: [2, 1, 5, 5, 6, 9] (6 is bubbled to the second last position)
Pass 3: [1, 2, 5, 5, 6, 9] (5 and 6 are in correct positions)

2.3. Selection Sort (सेलेक्शन सॉर्ट)

सेलेक्शन सॉर्ट एक अन्य सरल सॉर्टिंग एल्गोरिदम है जो सूची में सबसे छोटे (या सबसे बड़े) तत्व को खोजता है और उसे सही स्थान पर रखता है। यह प्रक्रिया तब तक जारी रहती है जब तक पूरी सूची सॉर्टेड नहीं हो जाती।

ऑपरेशन:

  1. सूची से सबसे छोटा तत्व (ascending order) खोजें।
  2. उसे सूची के पहले स्थान पर रख दें।
  3. फिर, बाकी बचे हुए हिस्से में से सबसे छोटा तत्व खोजें और उसे अगले स्थान पर रख दें।
  4. यह प्रक्रिया तब तक जारी रखें जब तक पूरी सूची सॉर्ट नहीं हो जाती।

समय जटिलता:

  • Worst-case: O(n^2)
  • Best-case: O(n^2) (इसमें बदलाव नहीं आता, चाहे सूची पहले से सॉर्टेड हो या नहीं)

चित्र:

Unsorted List: [64, 25, 12, 22, 11]

Pass 1: [11, 25, 12, 22, 64] (11 is placed at the first position)
Pass 2: [11, 12, 25, 22, 64] (12 is placed at the second position)
Pass 3: [11, 12, 22, 25, 64] (22 is placed at the third position)
Pass 4: [11, 12, 22, 25, 64] (No change)

2.4. Insertion Sort (इन्सर्शन सॉर्ट)

इन्सर्शन सॉर्ट एक सॉर्टिंग तकनीक है जिसमें सूची के तत्वों को एक-एक करके सही स्थान पर डाला जाता है। यह विधि तब तक जारी रहती है जब तक पूरी सूची सॉर्टेड नहीं हो जाती। इसे एक कार्ड के खेल से समझा जा सकता है, जिसमें एक-एक कार्ड को सही स्थान पर डाला जाता है।

ऑपरेशन:

  1. सूची के दूसरे तत्व से शुरू करें और इसे पहले तत्व के साथ तुलना करें।
  2. यदि वर्तमान तत्व छोटे हैं, तो इसे पहले तत्व से स्वैप करें।
  3. फिर अगले तत्व के लिए यह प्रक्रिया दोहराएं।

समय जटिलता:

  • Worst-case: O(n^2)
  • Best-case: O(n) (जब सूची पहले से सॉर्टेड हो)

चित्र:

Unsorted List: [5, 2, 9, 1, 5, 6]

Pass 1: [2, 5, 9, 1, 5, 6]
Pass 2: [2, 5, 9, 1, 5, 6]
Pass 3: [1, 2, 5, 9, 5, 6]
Pass 4: [1, 2, 5, 5, 9, 6]
Pass 5: [1, 2, 5, 5, 6, 9]

2.5. Merge Sort (मर्ज सॉर्ट)

मर्ज सॉर्ट एक विभाजन और विजय (Divide and Conquer) एल्गोरिदम है। यह एल्गोरिदम सूची को छोटे हिस्सों में विभाजित करता है और फिर उन हिस्सों को मर्ज करता है जब तक पूरी सूची सॉर्ट नहीं हो जाती।

ऑपरेशन:

  1. सूची को दो भागों में विभाजित करें।
  2. दोनों हिस्सों को पुनः विभाजित करें जब तक हर हिस्से में केवल एक तत्व न बच जाए।
  3. फिर उन हिस्सों को मिलाकर सॉर्टेड सूची बनाएं।

समय जटिलता:

  • Worst-case: O(n log n)
  • Best-case: O(n log n)

चित्र:

Unsorted List: [38, 27, 43, 3, 9, 82, 10]

Divide: [38, 27, 43, 3] & [9, 82, 10]
Divide further: [38, 27] & [43, 3], [9, 82] & [10]
Merge: [27, 38], [3, 43], [9, 10, 82]
Final Merge: [3, 9, 10, 27, 38, 43, 82]

2.6. Quicksort (क्विकसॉर्ट)

क्विकसॉर्ट एक अन्य विभाजन और विजय एल्गोरिदम है। इसमें एक pivot तत्व का चयन किया जाता है, और सूची को इस pivot के चारों ओर दो हिस्सों में विभाजित किया जाता है। एक हिस्सा छोटे तत्वों का होता है और दूसरा हिस्सा बड़े तत्वों का होता है। फिर इस प्रक्रिया को प्रत्येक हिस्से पर लागू किया जाता है।

ऑपरेशन:

  1. एक pivot तत्व चुनें।
  2. सभी तत्वों को दो हिस्सों में विभाजित करें: एक हिस्सा pivot से छोटे और दूसरा हिस्सा pivot से बड़े।
  3. फिर प्रत्येक हिस्से पर फिर से क्विकसॉर्ट लागू करें।

समय जटिलता:

  • Worst-case: O(n^2) (जब pivot सबसे खराब स्थिति में चुना जाए)
  • Best-case: O(n log n)

चित्र:

Unsorted List: [10, 80, 30, 90, 40, 50, 70]

Pivot: 50
Partition: [10, 30, 40] 50 [80, 90, 70]
Apply QuickSort on both sublists.

Final Sorted List: [10, 30, 40, 50, 70, 80, 90]


💥💥UNIT 3💥💥

3. Searching (खोज)

खोज (Searching) एक महत्वपूर्ण प्रक्रिया है जिसका उपयोग डेटा संरचनाओं में एक विशिष्ट तत्व को खोजने के लिए किया जाता है। विभिन्न प्रकार की डेटा संरचनाएं होती हैं, और इनमें से प्रत्येक संरचना में खोजने का तरीका अलग होता है। इस खंड में हम विभिन्न खोज तकनीकों और संरचनाओं को विस्तार से समझेंगे।

3.1. Symbol Tables (सिंबोल टेबल्स)

सिंबोल टेबल (Symbol Table) एक डेटा संरचना है जो कुंजी (key) और संबंधित मान (value) को स्टोर करने के लिए उपयोग की जाती है। यह मुख्य रूप से कंपाइलर डिज़ाइन, डाटाबेस सिस्टम, और अन्य प्रणालियों में उपयोग होती है, जहाँ हमें जल्दी से डेटा का पता लगाने की आवश्यकता होती है।

सिंबोल टेबल का मुख्य उद्देश्य कुंजी-मूल्य जोड़े (key-value pairs) को स्टोर करना है और उन जोड़ों के लिए तेज़ी से खोज, जोड़ने, हटाने, या अपडेट करने की प्रक्रिया को लागू करना है।

विशेषताएँ:

  • खोज (Search): सिंबोल टेबल के माध्यम से, हम कुंजी का उपयोग करके डेटा की जल्दी खोज कर सकते हैं।
  • संशोधन (Insertion/Deletion): हमें सिंबोल टेबल में डेटा जोड़ने या हटाने के लिए उपयुक्त तरीका मिल जाता है।

सिंबोल टेबल बनाने के लिए विभिन्न डेटा संरचनाओं का उपयोग किया जा सकता है, जैसे हैश टेबल या बाइनरी सर्च ट्री।

3.2. Binary Search Trees (बाइनरी सर्च ट्री)

बाइनरी सर्च ट्री (BST) एक प्रकार का बाइनरी ट्री है जिसमें प्रत्येक नोड के दो चाइल्ड होते हैं, और सभी बाएं चाइल्ड के तत्व रूट के तत्व से छोटे होते हैं, जबकि दाएं चाइल्ड के तत्व रूट से बड़े होते हैं।

इसकी मुख्य विशेषताएँ:

  • खोज: BST में खोज ओ(log n) समय में की जा सकती है, क्योंकि हम हर बार केवल एक दिशा (बाएं या दाएं) में चलते हैं।
  • संशोधन (Insertion/Deletion): नए नोड्स को डालने और हटाने की प्रक्रिया भी इसी तरीके से काम करती है।

ऑपरेशन्स:

  • Search: एक नोड को BST में ढूंढने के लिए, हम प्रत्येक नोड की तुलना करते हैं और छोटे या बड़े नोड्स की दिशा में चलते हैं।
  • Insertion: नए नोड को BST में डालते समय, हम रूट से शुरू करके उस नोड के सही स्थान पर डालते हैं।
  • Deletion: एक नोड को हटाने के लिए तीन केस होते हैं:
    1. अगर नोड का कोई बच्चा नहीं है, तो उसे सीधा हटा दिया जाता है।
    2. अगर नोड का एक बच्चा है, तो नोड को उसके एकमात्र बच्चे से बदल दिया जाता है।
    3. अगर नोड के दोनों बच्चे हैं, तो उस नोड को उसके इनऑर्डर सक्सेसर से बदल दिया जाता है।

चित्र:

         50
       /    \
     30      70
    /  \    /  \
   20   40  60   80

3.3. Balanced Search Trees (बैलेंस्ड सर्च ट्रीज)

बैलेंस्ड सर्च ट्री वह बाइनरी सर्च ट्री होते हैं जिनमें एक विशेष प्रकार का बैलेंस होता है, ताकि ट्री के हर नोड की ऊंचाई समान रूप से नियंत्रित रहे। इसका उद्देश्य यह है कि खोज, जोड़, और हटाने की प्रक्रिया हमेशा O(log n) समय में हो।

प्रमुख बैलेंस्ड सर्च ट्रीज़:

  1. AVL Tree (Adelson-Velsky and Landis Tree): यह एक बैलेंस्ड बाइनरी सर्च ट्री है, जिसमें हर नोड का बैलेंस फैक्टर (left height - right height) -1, 0, या +1 होना चाहिए। यदि यह सीमा से बाहर हो, तो पुनर्संतुलन की प्रक्रिया लागू की जाती है।
  2. Red-Black Tree: यह एक विशेष प्रकार का बैलेंस्ड बाइनरी सर्च ट्री है जिसमें प्रत्येक नोड को लाल या काले रंग का होना चाहिए और कुछ विशेष नियमों का पालन करना चाहिए, जिससे ट्री हमेशा बैलेंस्ड रहे।
  3. B-Trees: ये एक प्रकार के बैलेंस्ड ट्री होते हैं, जो विशेष रूप से डेटाबेस इंडेक्सिंग के लिए उपयोगी होते हैं। इसमें नोड्स में कई बच्चे हो सकते हैं।

विशेषताएँ:

  • ऑपरेशन्स: बैलेंस्ड सर्च ट्री में सभी ऑपरेशन्स (खोज, जोड़ना, हटाना) O(log n) समय में किए जा सकते हैं।
  • ऑटो बैलेंसिंग: जैसे ही हम एक नोड जोड़ते हैं या हटाते हैं, बैलेंसिंग के नियमों के आधार पर ट्री अपने आप बैलेंस हो जाता है।

चित्र (Red-Black Tree उदाहरण):


        10 (Black)
       /      \
  5 (Red)    20 (Red)
 /  \          \
1 (Black)    30 (Black)

3.4. Hash Tables (हैश टेबल्स)

हैश टेबल एक डेटा संरचना है जो कुंजी-मूल्य जोड़ (key-value pair) को स्टोर करने के लिए प्रयोग की जाती है। इसमें एक हैश फंक्शन का उपयोग करके कुंजी को एक सूचकांक (index) में परिवर्तित किया जाता है, और इस सूचकांक का उपयोग करके तत्व को तेजी से खोजा जाता है।

ऑपरेशन्स:

  • Insertion: जब हम एक नया तत्व डालते हैं, तो कुंजी को हैश फंक्शन के द्वारा एक सूचकांक में बदलते हैं और उस सूचकांक पर मान को डालते हैं।
  • Search: जब हमें कोई तत्व खोजना होता है, तो हम कुंजी के आधार पर हैश फंक्शन का उपयोग करते हैं और सीधे सूचकांक पर जाते हैं।
  • Deletion: हैश टेबल से एक तत्व को हटाने के लिए, हम उस कुंजी का उपयोग करके सूचकांक का पता लगाते हैं और वहां से तत्व को हटा देते हैं।

कोलिज़न्स (Collisions): हैश टेबल में कोलिज़न तब होता है जब दो कुंजी एक ही सूचकांक उत्पन्न करती हैं। इसे हल करने के लिए कोलिज़न रेज़ॉल्यूशन तकनीकों का उपयोग किया जाता है, जैसे:

  • Chaining: जब कोलिज़न होता है, तो हम एक लिंक्ड लिस्ट में तत्वों को स्टोर करते हैं।
  • Open Addressing: जब एक स्थान पहले से भरा होता है, तो हम अगले उपलब्ध स्थान पर तत्व को डालते हैं।

समय जटिलता:

  • Search/Insert/Delete: औसतन O(1) समय में होता है, यदि हैश फंक्शन अच्छा हो और कोलिज़न्स कम हों।

चित्र (हैश टेबल उदाहरण):

    Hash Table:
    Index 0 -> [10]
    Index 1 -> [20]
    Index 2 -> [30]
    Index 3 -> [50, 70] (Collision resolved using chaining)

निष्कर्ष

  • सिंबोल टेबल्स कुंजी-मूल्य जोड़ें स्टोर करने के लिए प्रयोग की जाती हैं।
  • बाइनरी सर्च ट्री (BST) में डेटा को एक अनुशासित तरीके से स्टोर किया जाता है ताकि डेटा को तेज़ी से खोजना जा सके।
  • बैलेंस्ड सर्च ट्रीज (जैसे AVL और Red-Black Trees) बेहतर प्रदर्शन के लिए बाइनरी सर्च ट्री की तरह होते हैं, लेकिन वे हमेशा बैलेंस्ड रहते हैं।
  • हैश टेबल्स कुंजी के माध्यम से तत्वों को तेज़ी से खोजने और स्टोर करने के लिए अत्यधिक प्रभावी डेटा संरचनाएँ हैं।


💥💥UNIT 4💥💥

4. Graphs (ग्राफ़)

ग्राफ़ (Graph) एक डेटा संरचना है जो वस्तुओं के बीच संबंधों को मॉडल करने के लिए उपयोग की जाती है। यह वस्तुओं (या नोड्स) और उनके बीच के कनेक्शनों (या एजेस) का एक सेट होता है। ग्राफ़ का उपयोग विभिन्न क्षेत्रों में किया जाता है, जैसे नेटवर्क्स, सोशियल मीडिया कनेक्शन्स, और रोड मैप्स में।

4.1. Definition of a Directed and Undirected Graph (निर्देशित और अप्रतिबंधित ग्राफ़ की परिभाषा)

  • निर्देशित ग्राफ़ (Directed Graph, या Digraph): इसमें हर एज के लिए एक दिशा होती है, यानि एज एक नोड से दूसरे नोड तक केवल एक दिशा में जा सकती है। इसे एक एरो द्वारा दर्शाया जाता है।

    उदाहरण: अगर A से B के बीच एक एज है, तो इसका मतलब है A → B, लेकिन B → A नहीं है।

  • अप्रतिबंधित ग्राफ़ (Undirected Graph): इसमें एज के लिए कोई दिशा नहीं होती। यानी, अगर A और B के बीच एक एज है, तो हम कह सकते हैं A - B और B - A दोनों हैं।

    उदाहरण: अगर A और B के बीच एक एज है, तो हम A - B या B - A दोनों में से किसी का भी उपयोग कर सकते हैं।

चित्र:

  1. निर्देशित ग्राफ़ (Directed Graph):

    A → B → C
↑     ↓
D ← E

  2. अप्रतिबंधित ग्राफ़ (Undirected Graph):

    A - B - C
|   |
D - E

4.1.1. Paths (पाथ्स)

पाथ (Path) एक ग्राफ़ में नोड्स का एक अनुक्रम है, जिसमें प्रत्येक नोड अपने पिछले नोड से जुड़ा हुआ होता है।

  • साधारण पाथ (Simple Path): एक पाथ जिसमें कोई नोड बार-बार नहीं आता।
  • पाथ की लंबाई: पाथ में शामिल एजों की संख्या।

उदाहरण:

  • A → B → C → D एक पाथ है क्योंकि हर नोड उसके अगले नोड से जुड़ा है।

4.1.2. Cycles (साइकल्स)

साइकल (Cycle) एक पाथ है जो अपने पहले नोड पर वापस लौटती है। यानी, यह एक पाथ है जो नोड्स और एजेस से गुजरने के बाद पुनः प्रारंभ बिंदु पर वापस लौटता है।

  • साधारण साइकल: एक साइकल जिसमें कोई नोड बार-बार नहीं आता।

उदाहरण:

  • A → B → C → A एक साइकल है, क्योंकि यह A से शुरू होकर फिर A पर लौटता है।

4.1.3. Spanning Trees (स्पैनिंग ट्रीज़)

स्पैनिंग ट्री (Spanning Tree) किसी ग्राफ़ का एक उपसमूह होता है, जो सभी नोड्स को जोड़ता है, लेकिन इसमें कोई साइकल नहीं होता। किसी ग्राफ़ का एक या अधिक स्पैनिंग ट्री हो सकते हैं।

  • स्पैनिंग ट्री की विशेषताएँ:
    • यह ग्राफ़ के सभी नोड्स को जोड़ता है।
    • इसमें कोई साइकल नहीं होता।
    • इसे बिना किसी अतिरिक्त एजेस के बनाने के लिए सिर्फ n-1 एजेस की आवश्यकता होती है (जहां n नोड्स की संख्या है)।

उदाहरण:

ग्राफ़: A - B - C - D
         |
         E
स्पैनिंग ट्री: A - B - C - D

4.2. Directed Acyclic Graphs (DAGs) (निर्देशित ऐसीक्लिक ग्राफ़)

निर्देशित ऐसीक्लिक ग्राफ़ (Directed Acyclic Graph, या DAG) एक ग्राफ़ है जिसमें कोई भी साइकल नहीं होती और इसमें एजेस का एक निश्चित दिशा होती है। DAG का उपयोग विशेष रूप से उन समस्याओं में किया जाता है जिनमें चरणों के बीच निर्भरता होती है, जैसे टास्क शेड्यूलिंग, प्रोजेक्ट प्रबंधन, और कंपाइलर डिज़ाइन।

विशेषताएँ:

  • इसमें कोई साइकल नहीं होती।
  • यह अक्सर उस समय उपयोगी होता है जब हमें डेटा प्रवाह या निर्भरता को दिखाना हो।

उदाहरण:

A → B → D
↓    ↑
C → E

4.3. Topological Sorting (टॉपोलॉजिकल सॉर्टिंग)

टॉपोलॉजिकल सॉर्टिंग एक DAG (Directed Acyclic Graph) के लिए एक विशेष प्रकार की सॉर्टिंग तकनीक है, जिसमें हम नोड्स को इस प्रकार सॉर्ट करते हैं कि प्रत्येक एज का स्रोत नोड पहले आता है। इसे तब उपयोग किया जाता है जब हमें प्रक्रियाओं की एक निर्दिष्ट अनुक्रमणिका की आवश्यकता होती है।

ऑपरेशन्स:

  1. DAG से सभी नोड्स को सूचीबद्ध करें।
  2. हर बार एक नोड निकालें और उसे उस क्रम में डालें जहां सभी उसके पहले के नोड्स पहले आएं।

उदाहरण:

DAG: A → B → C
          ↓
         D
टॉपोलॉजिकल सॉर्ट: A, B, D, C

4.4. Minimum Spanning Tree Algorithms (न्यूनतम स्पैनिंग ट्री एल्गोरिदम)

न्यूनतम स्पैनिंग ट्री (MST) उस ट्री को कहा जाता है जिसमें ग्राफ़ के सभी नोड्स जुड़े होते हैं और एजेस का कुल वजन न्यूनतम होता है। यह विशेष रूप से नेटवर्क डिज़ाइन में उपयोगी होता है, जैसे सड़क निर्माण या नेटवर्क कनेक्टिविटी।

Kruskal's Algorithm:

  1. सभी एजेस को उनके वजन के अनुसार बढ़ते क्रम में क्रमबद्ध करें।
  2. सबसे छोटे एज को जोड़ें, लेकिन यह सुनिश्चित करें कि कोई साइकल न बने।
  3. यह प्रक्रिया तब तक जारी रखें जब तक n-1 एजेस न मिल जाएं (n नोड्स के लिए)।

Prim's Algorithm:

  1. एक नोड से शुरुआत करें।
  2. उस नोड से जुड़े सभी एजेस में से सबसे छोटे वजन वाला एज चुनें।
  3. उस एज को जोड़कर नए नोड को ग्राफ़ में जोड़ें।
  4. इस प्रक्रिया को तब तक जारी रखें जब तक सभी नोड्स जोड़ नहीं जाते।

4.4.1. Shortest Path Algorithms: Dijkstra’s Algorithm (सबसे छोटा मार्ग एल्गोरिदम: डायकस्ट्रा एल्गोरिदम)

डायकस्ट्रा एल्गोरिदम एक ग्राफ़ के लिए सबसे छोटे मार्ग को खोजने के लिए एक ग्रीडी एल्गोरिदम है, जहां प्रत्येक एज का वजन सकारात्मक होता है। यह एक स्रोत से सभी नोड्स तक के सबसे छोटे रास्ते की लंबाई का निर्धारण करता है।

ऑपरेशन्स:

  1. सबसे पहले सभी नोड्स को अनइन्शियलाइज्ड के रूप में चिह्नित करें।
  2. स्रोत नोड को 0 से और बाकी नोड्स को ∞ से इनिशियलाइज करें।
  3. नोड्स के माध्यम से चलते हुए सबसे छोटे दूरी के मार्ग को चुनें और अपडेट करें।
  4. इस प्रक्रिया को तब तक जारी रखें जब तक सभी नोड्स का shortest path तय न हो जाए।

समय जटिलता: O(V^2) (V = नोड्स की संख्या), लेकिन प्रायः इसे O((V + E) log V) में सुधारा जा सकता है।

4.4.2. Flow-Based Algorithms (फ्लो-आधारित एल्गोरिदम)

फ्लो-आधारित एल्गोरिदम नेटवर्क फ्लो समस्याओं में उपयोग होते हैं, जैसे Ford-Fulkerson Algorithm जो नेटवर्क फ्लो की अधिकतम क्षमता को ढूंढने के लिए काम आता है। इसका मुख्य उद्देश्य स्रोत से गंतव्य तक के लिए अधिकतम फ्लो (flow) को प्राप्त करना है।

उदाहरण:

  • Ford-Fulkerson Algorithm: यह एल्गोरिदम नेटवर्क के फ्लो को बढ़ाने के लिए augmenting paths का उपयोग करता है। यह तब तक प्रक्रिया को दोहराता है जब तक कोई और augmenting path उपलब्ध न हो।

निष्कर्ष

  • ग्राफ़ नोड्स और एजेस का एक सेट होता है, जो किसी नेटवर्क या प्रणाली का प्रतिनिधित्व करता है।
  • निर्देशित और अप्रतिबंधित ग्राफ़ दोनों में एजेस की दिशा होती है या नहीं होती है।
  • पाथ्स, साइकल्स, और स्पैनिंग ट्रीज़ ग्राफ़ के महत्वपूर्ण तत्व होते हैं।
  • DAG और टॉपोलॉजिकल सॉर्टिंग विशेष रूप से डेटा प्रवाह और निर्भरता को दर्शाते हैं।
  • न्यूनतम स्पैनिंग ट्री एल्गोरिदम और सबसे छोटा मार्ग एल्गोरिदम वास्तविक जीवन में नेटवर्क डिज़ाइन और रूटिंग समस्याओं को हल करने के लिए महत्वपूर्ण होते हैं।


💥💥UNIT 5💥💥

5. Strings (स्ट्रिंग्स)

स्ट्रिंग्स (Strings) एक विशेष प्रकार का डेटा संरचना है जो एक या अधिक वर्णों (characters) का अनुक्रम होती है। यह डेटा संरचना सामान्यतः टेक्स्ट प्रोसेसिंग, डेटा एन्कोडिंग, और विभिन्न अन्य कंप्यूटर विज्ञान के समस्याओं में उपयोग होती है। स्ट्रिंग्स के साथ कार्य करते समय कई महत्वपूर्ण एल्गोरिदम और तकनीकों का उपयोग किया जाता है, जिन्हें नीचे विस्तार से बताया गया है।

5.1. String Sort (स्ट्रिंग सॉर्ट)

स्ट्रिंग सॉर्ट वह प्रक्रिया है जिसमें एक या अधिक स्ट्रिंग्स को उनके वर्णों के क्रम के आधार पर व्यवस्थित किया जाता है। स्ट्रिंग्स को सामान्यतः लексिकल क्रम में सॉर्ट किया जाता है, जैसे शब्दकोश में शब्दों का क्रम।

स्ट्रिंग सॉर्ट एल्गोरिदम:

  1. कंपेयर-बेस्ड एल्गोरिदम:

    • क्विक सॉर्ट (Quick Sort)
    • मर्ज सॉर्ट (Merge Sort)
    • हीप सॉर्ट (Heap Sort)

  2. रेडिक्स सॉर्ट (Radix Sort): यह एल्गोरिदम वर्णों को उनके ASCII मान के आधार पर सॉर्ट करता है, विशेष रूप से जब स्ट्रिंग्स की लंबाई समान होती है।

समय जटिलता:

  • कंपेयर-बेस्ड एल्गोरिदम में समय जटिलता O(n log n) होती है, जहां n स्ट्रिंग्स की संख्या है।
  • रेडिक्स सॉर्ट में समय जटिलता O(k * n) होती है, जहां k स्ट्रिंग्स की अधिकतम लंबाई है और n कुल स्ट्रिंग्स की संख्या है।

उदाहरण:

  • ["apple", "banana", "cherry"] को लексिकल क्रम में सॉर्ट करने पर: ["apple", "banana", "cherry"]

5.2. Tries (ट्रीज़)

ट्री (Trie), जिसे प्रिफिक्स ट्री (Prefix Tree) भी कहा जाता है, एक विशेष प्रकार की डेटा संरचना है जिसका उपयोग शब्दों या स्ट्रिंग्स के संग्रह को संग्रहीत करने और उनके प्रिफिक्स को जल्दी से खोजना करने के लिए किया जाता है। यह विशेष रूप से शब्दकोशों, ऑटो-सुझाव (auto-suggestions), और पैटर्न मैचिंग में उपयोगी होता है।

विशेषताएँ:

  • प्रत्येक नोड एक अक्षर को दर्शाता है।
  • प्रत्येक पथ एक शब्द को दर्शाता है, और शब्द की समाप्ति को विशेष रूप से चिह्नित किया जाता है।
  • यह तेज़ी से प्रिफिक्स मैचिंग और खोज (prefix search) करने में सक्षम है।

ऑपरेशन्स:

  • Insertion: एक शब्द को ट्राई में जोड़ना।
  • Search: एक शब्द की उपस्थिति को ट्राई में खोजने के लिए।
  • Prefix Search: कोई शब्द ट्राई में किसी विशेष प्रिफिक्स से शुरू होता है या नहीं, इसे जांचना।

समय जटिलता: O(L), जहां L शब्द की लंबाई है, क्योंकि प्रत्येक अक्षर के लिए एक ट्राई नोड में संक्रमण होता है।

उदाहरण:

Trie Structure:
       root
        |
      'a'
     /   \
   'p'   'b'
   / \     \
  'p' 'l'   'a'
   |
  'l'

5.3. Substring Search (सबस्ट्रिंग खोज)

सबस्ट्रिंग खोज (Substring Search) वह प्रक्रिया है जिसमें हम किसी दिए गए टेक्स्ट में किसी विशेष पैटर्न (substring) को खोजते हैं। इस समस्या का समाधान विभिन्न एल्गोरिदम द्वारा किया जा सकता है जो तेज़ी से पैटर्न को खोजने के लिए काम करते हैं।

सबसे सामान्य एल्गोरिदम:

  1. ब्रूट-फोर्स एल्गोरिदम (Brute-Force Algorithm):
    • प्रत्येक पोजीशन से पैटर्न को मिलाने की कोशिश करता है। इसकी समय जटिलता O(n*m) होती है, जहां n टेक्स्ट की लंबाई और m पैटर्न की लंबाई है।
  2. KMP (Knuth-Morris-Pratt) एल्गोरिदम:
    • यह एल्गोरिदम पैटर्न के भीतर की पूर्वसूचना (prefix-suffix) का उपयोग करता है, ताकि अगर कोई मेल न हो, तो अगला संभावित मैच को जल्दी से ढूंढा जा सके।
    • इसकी समय जटिलता O(n + m) होती है, जहां n टेक्स्ट की लंबाई और m पैटर्न की लंबाई है।
  3. Boyer-Moore एल्गोरिदम:
    • यह एल्गोरिदम पैटर्न के भीतर चिह्नों का उपयोग करता है ताकि सबसे बड़े संभावित स्थान पर पैटर्न की तुलना की जा सके, जिससे मैच जल्दी मिल सके।

उदाहरण:

  • टेक्स्ट: "hello world"
  • पैटर्न: "world"
  • परिणाम: पैटर्न टेक्स्ट के 6वें स्थान से शुरू होता है।

5.4. Regular Expressions (नियमित अभिव्यक्तियाँ)

नियमित अभिव्यक्तियाँ (Regular Expressions या Regex) एक शक्तिशाली टूल है जो स्ट्रिंग्स को मैच करने, उनका विश्लेषण करने और संशोधित करने के लिए उपयोग की जाती हैं। यह विशेष रूप से स्ट्रिंग पैटर्न की पहचान करने में मदद करता है।

मुख्य पैटर्न:

  • .: किसी भी एकल वर्ण से मेल खाता है।
  • *: पिछले वर्ण को 0 या अधिक बार मैच करता है।
  • +: पिछले वर्ण को 1 या अधिक बार मैच करता है।
  • []: वर्णों के सेट से मेल खाता है। जैसे [a-z] छोटे अक्षरों से मेल खाता है।
  • ^: स्ट्रिंग के शुरुआत से मैच करता है।
  • $: स्ट्रिंग के अंत से मैच करता है।
  • |: "या" ऑपरेटर, जैसे a|b a या b से मेल खाता है।

उदाहरण:

  • पैटर्न: ^a.*b$
    • यह पैटर्न उन स्ट्रिंग्स से मेल खाता है जो 'a' से शुरू होती हैं और 'b' पर समाप्त होती हैं।
  • स्ट्रिंग: "ab"
    • यह पैटर्न "ab" से मेल खाता है क्योंकि यह 'a' से शुरू होती है और 'b' पर समाप्त होती है।

5.5. Elementary Data Compression (मूलभूत डेटा संपीड़न)

डेटा संपीड़न (Data Compression) वह प्रक्रिया है जिसमें डेटा के आकार को छोटा किया जाता है, ताकि उसे अधिक कुशलता से स्टोर या ट्रांसफर किया जा सके। यह विशेष रूप से नेटवर्किंग और डेटा स्टोरिज में उपयोगी होता है।

आधिकारिक संपीड़न एल्गोरिदम:

  1. Run-Length Encoding (RLE):

    • इस तकनीक में डेटा की निरंतर पुनरावृत्तियों (repetitions) को संपीड़ित किया जाता है। उदाहरण के लिए, AAAABBBCCDAA को 4A3B2C1D2A के रूप में संपीड़ित किया जा सकता है।

  2. Huffman Coding:

    • यह एक हफ्ते कोडिंग तकनीक है, जो अधिक आवृत्त (frequent) वाले प्रतीकों को छोटा कोड देता है और कम आवृत्त वाले प्रतीकों को बड़ा कोड देता है। इसे आमतौर पर टेक्स्ट और इमेजेस के संपीड़न में उपयोग किया जाता है।

  3. Lempel-Ziv-Welch (LZW):

    • LZW एक बिना हानि वाले संपीड़न एल्गोरिदम है, जिसे GIF और TIFF फाइल फॉर्मेट्स में उपयोग किया जाता है। यह टेक्स्ट और इमेज डेटा को संपीड़ित करने के लिए एक dictionary आधारित तकनीक का उपयोग करता है।

उदाहरण:

  • Run-Length Encoding (RLE):
    • AAAABBBCCDAA → 4A3B2C1D2A

समय जटिलता:

  • RLE: O(n), जहां n डेटा का आकार है।
  • Huffman: O(n log n), जहां n प्रतीकों की संख्या है।

निष्कर्ष

  • स्ट्रिंग सॉर्ट: स्ट्रिंग्स को लексिकल क्रम में सॉर्ट करने के लिए विभिन्न एल्गोरिदम होते हैं।
  • ट्रीज़: ट्राई डेटा संरचना का उपयोग विशेष रूप से प्रिफिक्स को जल्दी से खोजने के लिए किया जाता है।
  • सबस्ट्रिंग खोज: पैटर्न को स्ट्रिंग्स में खोजने के लिए विभिन्न एल्गोरिदम जैसे ब्रूट-फोर्स, KMP और Boyer-Moore का उपयोग किया जाता है।
  • नियमित अभिव्यक्तियाँ: स्ट्रिंग पैटर्न की पहचान और संशोधन के लिए शक्तिशाली उपकरण होते हैं।
  • डेटा संपीड़न: RLE, Huffman और LZW जैसे एल्गोरिदम का उपयोग डेटा को संपीड़ित करने के लिए किया जाता है।

इन विधियों का उपयोग विभिन्न समस्याओं को हल करने के लिए किया जाता है, जैसे टेक्स्ट प्रोसेसिंग, डेटा संचार, और नेटवर्किंग।

Rajasthan Polytechnic (BTER)

Posted by Rajasthan Polytechnic (BTER)

Hi! I’m Garima Kanwar, founder of Rajasthan Polytechnic (BTER). This platform provides notes, PDFs, and video lectures for all Polytechnic branches (ME, CS, EE) and semesters to make learning easy .I ensure exam-focused, updated, and simple-to-understand content, along with academic updates and career guidance.

Post a Comment

1 Comments