खोज डेटा के लिए एल्गोरिदम और संरचनाएं। यैंडेक्स से व्याख्यान और पाठ्यक्रम

आज हम स्कूल ऑफ़ डेटा एनालिसिस के व्याख्यानों पर नए साल की श्रृंखलाएँ समाप्त कर रहे हैं। अंतिम, लेकिन कम से कम, पाठ्यक्रम एल्गोरिथ्म और संरचनाएं हैं खोज डेटा।

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

हमने पिछले पाठ्यक्रमों पर टिप्पणियों में जो पूछा गया था, उसे ध्यान में रखा - अब, यदि आप चाहें, तो आप न केवल व्यक्तिगत रूप से व्याख्यान देख / डाउनलोड कर सकते हैं, बल्कि Yandex.Disk पर एक खुले फ़ोल्डर के रूप में एक बार में सब कुछ अपलोड कर सकते हैं। वैसे - पिछले पोस्टों में समान अपडेट दिखाई दिए (यहाँ सुविधा के लिए लिंक हैं: " मशीन लर्निंग ", " असतत विश्लेषण और संभाव्यता सिद्धांत ", " समानांतर और वितरित कंप्यूटिंग ")।



मैक्सिम अलेक्जेंड्रोविच बबेंको, कंप्यूटर विज्ञान के उप निदेशक, गणितीय तर्क विभाग के सहायक और मास्को राज्य विश्वविद्यालय के यांत्रिकी और गणित संकाय के एल्गोरिथ्म द्वारा व्याख्यान दिए गए हैं। एम.वी. लोमोनोसोवा, भौतिक और गणितीय विज्ञान के उम्मीदवार।

Yandex.Disk पर एक फ़ोल्डर के रूप में पूर्ण पाठ्यक्रम

व्याख्यान 1. जटिलता और कम्प्यूटेशनल मॉडल। लेखांकन मूल्यों का विश्लेषण (शुरुआत)

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

व्याख्यान 2. लेखा मूल्यों का विश्लेषण (अंत)

लेन-देन लेखांकन लागत का विश्लेषण: संभावित कार्य, सही और लेखांकन मूल्य। ढेर और कतार। वैरिएबल आकार की एक सरणी और एक लिंक्ड सूची के आधार पर कार्यान्वयन। दो ढेर का उपयोग करके एक कतार मॉडलिंग। स्टैक और कतार में एक गतिशील अधिकतम बनाए रखने का कार्य। टिकाऊ और अपरिवर्तनीय डेटा संरचनाएं। लगातार डेटा संरचनाएं। अपरिवर्तनीय ढेर और अपरिवर्तनीय कतार। लगातार संरचनाओं में लेखांकन मूल्यों का विश्लेषण करते समय एक बहु भविष्य की समस्या।

व्याख्यान 3. त्वरित प्रकार और विलय प्रकार के कार्य

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

व्याख्यान 4. साधारण आँकड़े। हीप्स (शुरू)

त्वरित-सॉर्ट एल्गोरिथ्म के एक यादृच्छिक संशोधन का उपयोग करके क्रमिक आँकड़े खोजना। परिचालन समय की अपेक्षा की रैखिकता। लगभग मंझला। सबसे खराब स्थिति में रैखिक के लिए kth क्रमिक आंकड़ों की पसंद। ढेर गुणों वाले पेड़। लगभग पूर्ण बाइनरी पेड़: वर्टेक्स नंबरिंग, नेविगेशन। बाइनरी हीप। स्क्रीनिंग ऑपरेशन ऊपर और नीचे। सम्मिलन, विलोपन और न्यूनतम खोज कार्यों का कार्यान्वयन। एक गुच्छा (मेक-हीप ऑपरेशन), रैखिक संचालन समय में चाबियों का एक मनमाना सरणी परिवर्तित करना। हीप-सॉर्ट सॉर्टिंग एल्गोरिदम।

व्याख्यान 5. ढेर (शुरुआत)। हाशिंग (प्रारंभ)

k-ary हीप्स, k की पसंद पर संचालन की जटिलता की निर्भरता। द्विपद (द्विपद), वामपंथी (वामपंथी) और तिरछा (तिरछा) ढेर।

व्याख्यान 6. हास करना

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

व्याख्यान 7. खोज पेड़ (शुरुआत)

खोज वृक्ष की परिभाषा। आइटम डालें और हटाएं। इनवर्टर-ट्री ट्रैवर्सल। लाल-काले पेड़: परिभाषा और बुनियादी गुण। लाल और काली लकड़ी के लिए सम्मिलित संचालन का कार्यान्वयन। सिपल के पेड़। Splay ऑपरेशन: zig, zig-zig और zig-zag चरण। आवारा पेड़ों के लिए डालें, हटाएं, मर्ज करें और विभाजन को लागू करें।

व्याख्यान 8. खोज पेड़ (समाप्त)। कार्तीय वृक्ष

कार्तीय वृक्ष (दुची)। विभिन्न कुंजियों और प्राथमिकताओं के दिए गए सेट के लिए कार्तीय वृक्ष की विशिष्टता। आत्मा की ऊंचाई की अपेक्षा का लघुगणकीय अनुमान। आत्माओं के लिए विलय और पृथक्करण का संचालन। डोच के लिए तत्वों को डालने और हटाने के लिए संचालन। एक कार्तीय वृक्ष का निर्माण रैखिक समय में कुंजियों की प्रारंभिक छंटाई के अधीन होता है।

व्याख्यान 9. बी-पेड़। सेट प्रणाली को अस्वीकृत करें

बी + पेड़: परिभाषाएं और बुनियादी गुण। B + पेड़ों के लिए ऑपरेशन खोजें, डालें और हटाएं। डिसऑइंटमेंट का सिस्टम सेट करता है। जंगल का उपयोग कर कार्यान्वयन। चोटियों रैंक, हेयूरिस्टिक रैंक। तत्वों की संख्या के माध्यम से लॉगरिदमिक रैंक का अनुमान है। यादृच्छिक रैंक विधर्मी। यकृत संपीड़न पथ। संचालन के पुस्तक मूल्य का अनुमान (बिना सबूत के)।

व्याख्यान 10. RMQ और LCA के उद्देश्य

कार्य RMQ (न्यूनतम क्वेरी सीमा) और LCA (कम से कम सामान्य पूर्वज)। RMQ से LCA, कार्टेशियन ट्री में कमी। एलसीए कार्य के ऑफ़लाइन संस्करण के लिए टारजन एल्गोरिदम। एलसीए कार्य के ऑनलाइन संस्करण के लिए सबसे सरल एल्गोरिदम: एक पूर्ण और विरल प्रतिक्रिया तालिका। फराह-कोल्टन-बेंडर एल्गोरिथ्म के लिए RM 1-RMQ समस्या। LCA समस्या को of 1-RMQ समस्या में कमी: यूलर ट्री ट्रैवर्सल।

व्याख्यान 11. ज्यामितीय खोज की समस्याएं

स्थान की समस्या, छुरा समस्या। अंतराल के पेड़। एक दो आयामी समस्या के लिए अंतराल की प्रणाली को कम करना। गलियारे में अंक खोजने का कार्य। प्राथमिकता खोज पेड़। एक आयत में अंक खोजने का कार्य। X के साथ खंडों का एक वृक्ष, प्रत्येक शीर्ष पर Y सूचियों के क्रम द्वारा समन्वित होता है। निर्माण के लिए जटिलता O (n log n) है और क्वेरी के लिए O (log ^ 2 n)। O (लॉग एन) में खोज समय को कम करना। एक साथ आदेशित सूचियों के समूह को खोजने का कार्य। आंशिक कैस्केडिंग।

व्याख्यान 12. रेखांकन में गतिशील कनेक्टिविटी

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