Generalized distributive law
பொதுமைப்படுத்தப்பட்ட விநியோக விதி (ஜிடிஎல்) என்பது விநியோகச் சொத்தின் பொதுமைப்படுத்தலாகும், இது ஒரு பொதுவான செய்தி அனுப்பும் வழிமுறையை உருவாக்குகிறது. இது தகவல் கோட்பாடு, டிஜிட்டல் தகவல்தொடர்புகள், சமிக்ஞை செயலாக்கம், புள்ளிவிவரங்கள் மற்றும் செயற்கை நுண்ணறிவு சமூகங்களில் பல ஆசிரியர்களின் பணியின் தொகுப்பாகும். சட்டம் மற்றும் வழிமுறை ஆகியவை ஸ்ரீநிவாஸ் எம். அஜி மற்றும் ராபர்ட் ஜே. மெக்லிஸ் ஆகியோரால் அதே தலைப்பில் அரை பயிற்சியில் அறிமுகப்படுத்தப்பட்டன. "கணிதத்தில் விநியோக விதி என்பது பெருக்கல் மற்றும் கூட்டல் செயல்பாடுகள் தொடர்பான சட்டமாகும், இது குறியீடாகக் கூறப்பட்டுள்ளது, அதாவது, மோனோமியல் காரணி விநியோகிக்கப்படுகிறது, அல்லது தனித்தனியாகப் பயன்படுத்தப்படுகிறது, இருமக் காரணியின் ஒவ்வொரு சொல்லுக்கும், இதன் விளைவாக தயாரிப்பு ஏற்படுகிறது"-பிரிட்டானிக்கா வரையறையிலிருந்து கவனிக்கப்படுவதால், ஒரு எண்கணித வெளிப்பாட்டிற்கு விநியோக விதியைப் பயன்படுத்துவது அதில் உள்ள செயல்பாடுகளின் எண்ணிக்கையைக் குறைக்கிறது. முந்தைய எடுத்துக்காட்டில் செயல்பாடுகளின் மொத்த எண்ணிக்கை மூன்றிலிருந்து (இரண்டு பெருக்கல்கள் மற்றும் ஒரு கூட்டல்) இரண்டாகக் குறைக்கப்பட்டது (ஒரு பெருக்கம் மற்றும் ஒரு கூட்டல்). விநியோக விதியின் பொதுமைப்படுத்தல் வேகமான வழிமுறைகளின் ஒரு பெரிய குடும்பத்திற்கு வழிவகுக்கிறது. இதில் எஃப்எஃப்டி மற்றும் விட்டர்பி வழிமுறை அடங்கும். பின்வரும் எடுத்துக்காட்டில் இது மிகவும் முறையான முறையில் விளக்கப்பட்டுள்ளதுஃ எங்கே மற்றும் உண்மையான மதிப்புள்ள செயல்பாடுகள், மற்றும் (சொல்லுங்கள்) இங்கே நாம் முடிவைப் பெற சுயாதீன மாறிகள் (,, மற்றும்) ஐ "ஓரங்கட்டுகிறோம்". நாம் கணக்கீட்டு சிக்கலைக் கணக்கிடும்போது, ஒவ்வொரு ஜோடிக்கும், மும்மடங்கு காரணமாக சொற்கள் இருப்பதை நாம் காணலாம், அவை ஒவ்வொரு படிநிலையிலும் ஒரு கூட்டல் மற்றும் ஒரு பெருக்கத்துடன் மதிப்பீட்டில் பங்கேற்க வேண்டும். எனவே, தேவைப்படும் மொத்த கணக்கீடுகளின் எண்ணிக்கை. எனவே மேற்கண்ட செயல்பாட்டின் அறிகுறியற்ற சிக்கலானது. சமன்பாட்டின் RHS க்கு விநியோகச் சட்டத்தை நாம் பயன்படுத்தினால், பின்வருவனவற்றைப் பெறுவோம்ஃ இது எங்கே மற்றும் எங்கே ஒரு தயாரிப்பு என்று விவரிக்கப்படலாம் என்பதைக் குறிக்கிறது. எனவே, தேவைப்படும் மொத்த கணக்கீடுகளின் எண்ணிக்கை. எனவே கணக்கீட்டின் அறிகுறியற்ற சிக்கலானது இருந்து குறைகிறது. விநியோக விதியைப் பயன்படுத்துவது கணக்கீட்டு சிக்கலைக் குறைக்கிறது என்பதை இது ஒரு எடுத்துக்காட்டு மூலம் காட்டுகிறது, இது ஒரு "வேகமான வழிமுறையின்" நல்ல அம்சங்களில் ஒன்றாகும். வரலாறு தீர்க்க விநியோகச் சட்டத்தைப் பயன்படுத்திய சில சிக்கல்களை பின்வருமாறு தொகுக்கலாம். டிகோடிங் வழிமுறைகள் ஒரு ஜிடிஎல் போன்ற வழிமுறை குறைந்த அடர்த்தி சமநிலை-சரிபார்ப்பு குறியீடுகளை டிகோடிங் செய்ய கேலஜரால் பயன்படுத்தப்பட்டது. கேலஜரின் படைப்பின் அடிப்படையில் டேனர் டேனர் வரைபடத்தை அறிமுகப்படுத்தினார் மற்றும் கேலஜர்களின் பணியை செய்தி அனுப்பும் வடிவத்தில் வெளிப்படுத்தினார். தோல் பதனிடும் வரைபடம் விட்டர்பி வழிமுறையை விளக்கவும் உதவியது. கான்வொல்யூஷனல் குறியீடுகளின் விட்டர்பியின் அதிகபட்ச சாத்தியக்கூறு டிகோடிங் ஜிடிஎல் போன்ற பொதுத்தன்மையின் வழிமுறைகளையும் பயன்படுத்தியது என்பதை ஃபோர்னி கவனித்துள்ளார். 2. முன்னோக்கி-பின்னோக்கி வழிமுறை மார்கோவ் சங்கிலியில் உள்ள நிலைகளைக் கண்காணிப்பதற்கான ஒரு வழிமுறையாக முன்னோக்கி பின்தங்கிய வழிமுறை உதவியது. மேலும் இது ஜெனரலிட்டி 3 போன்ற ஜி. டி. எல் இன் வழிமுறையும் பயன்படுத்தப்பட்டது. செயற்கை நுண்ணறிவு செயற்கை நுண்ணறிவில் உள்ள பல சிக்கல்களைத் தீர்க்க சந்தி மரங்கள் என்ற கருத்து பயன்படுத்தப்பட்டுள்ளது. பக்கெட் நீக்குதல் என்ற கருத்தும் பல கருத்துகளைப் பயன்படுத்தியது. எம்பிஎஃப் சிக்கல் எம்பிஎஃப் அல்லது ஒரு தயாரிப்பு செயல்பாட்டை ஓரங்கட்டுவது ஒரு பொதுவான கணக்கீட்டு சிக்கலாகும், இது சிறப்பு வழக்கில் தனித்துவமான ஹடாமார்ட் உருமாற்றத்தின் கணக்கீடு, நினைவகம் இல்லாத சேனலில் ஒரு நேரியல் குறியீட்டின் அதிகபட்ச நிகழ்தகவு டிகோடிங் மற்றும் மேட்ரிக்ஸ் சங்கிலி பெருக்கம் போன்ற பல பாரம்பரிய சிக்கல்களை உள்ளடக்கியது. சேர்ப்புகள் மற்றும் பெருக்கங்கள் பொதுமைப்படுத்தப்படும் சூழ்நிலைகளுக்கு இது பொருந்தும் என்பதில் ஜி. டி. எல் இன் சக்தி உள்ளது. இந்த நடத்தையை விளக்குவதற்கு ஒரு பரிமாற்ற செமிரிங் ஒரு நல்ல கட்டமைப்பாகும். இது ஆபரேட்டர்கள் "" மற்றும் "" எங்கே மற்றும் ஒரு பரிமாற்ற மோனாய்டுகள் மற்றும் விநியோகச் சட்டம் கொண்ட ஒரு தொகுப்பில் வரையறுக்கப்படுகிறது. ஒரு வரையறுக்கப்பட்ட தொகுப்பு மற்றும் எங்கே போன்ற மாறிகள் இருக்கட்டும். இங்கே. என்றால் மற்றும், விடுங்கள்,, மற்றும் விடுங்கள். ஒரு செயல்பாடு வரையறுக்கப்படுகிறது என்று வைத்துக்கொள்வோம், அங்கு ஒரு பரிமாற்ற செமிரிங் உள்ளது. மேலும், அவை உள்ளூர் களங்கள் மற்றும் உள்ளூர் கர்னல்கள் என்றும் அழைக்கப்படுகின்றன. இப்போது உலகளாவிய கர்னல் பின்வருமாறு வரையறுக்கப்படுகிறதுஃ எம். பி. எஃப் சிக்கலின் வரையறைஃ ஒன்று அல்லது அதற்கு மேற்பட்ட குறியீடுகளுக்கு, உலகளாவிய கர்னலின்-மார்ஜினலைசேஷனின் மதிப்புகளின் அட்டவணையை கணக்கிடுங்கள், இது வரையறுக்கப்பட்ட செயல்பாடாகும். வெளிப்படையான வழியில் புறநிலை செயல்பாட்டின் கணக்கீட்டுக்கு செயல்பாடுகள் தேவை என்பதை இது கவனிக்க முடியும். ஏனென்றால், புறநிலை செயல்பாட்டின் கணக்கீட்டில் சேர்க்கைகள் மற்றும் பெருக்கங்கள் தேவைப்படுகின்றன. அடுத்த பிரிவில் விளக்கப்பட்டுள்ள ஜிடிஎல் வழிமுறை இந்த கணக்கீட்டு சிக்கலைக் குறைக்கும். எம். பி. எஃப் சிக்கலுக்கு பின்வருபவை ஒரு எடுத்துக்காட்டு. மற்றும் போன்ற மாறிகளாக இருக்கட்டும். இங்கே மற்றும். இந்த மாறிகளைப் பயன்படுத்தி கொடுக்கப்பட்ட செயல்பாடுகள் மற்றும் நாம் கணக்கிட வேண்டும் மற்றும் வரையறுக்க வேண்டும்ஃ இங்கே உள்ளூர் களங்கள் மற்றும் உள்ளூர் கர்னல்கள் பின்வருமாறு வரையறுக்கப்படுகின்றனஃ புறநிலை செயல்பாடு எங்கே மற்றும் புறநிலை செயல்பாடு எங்கே. உண்மையான மதிப்புமிக்க செயல்பாடு எங்கே மற்றும் எங்கே என்பதை மற்றொரு எடுத்துக்காட்டைக் கவனியுங்கள். இப்போது, எம். பி. எஃப் சிக்கலைக் கருத்தில் கொள்வோம், அங்கு பரிமாற்ற செமிரிங் சாதாரண கூட்டல் மற்றும் பெருக்கத்துடன் கூடிய உண்மையான எண்களின் தொகுப்பாக வரையறுக்கப்படுகிறது மற்றும் உள்ளூர் களங்கள் மற்றும் உள்ளூர் கர்னல்கள் பின்வருமாறு வரையறுக்கப்படுகின்றனஃ இப்போது உலகளாவிய கர்னல் உள்ளூர் கர்னல்களின் பெருக்கலாக வரையறுக்கப்படுவதால், அது மற்றும் உள்ளூர் களத்தில் புறநிலை செயல்பாடு இது செயல்பாட்டின் ஹடாமார்ட் உருமாற்றம். எனவே ஹடாமார்ட் உருமாற்றத்தின் கணக்கீடு எம். பி. எஃப் சிக்கலின் ஒரு சிறப்பு வழக்கு என்பதை நாம் காணலாம். மேலே விவரிக்கப்பட்டுள்ளபடி எம். பி. எஃப் சிக்கல் பல பாரம்பரிய சிக்கல்களின் சிறப்பு நிகழ்வுகளை உருவாக்குகிறது என்பதை நிரூபிக்க மேலும் எடுத்துக்காட்டுகள் நிரூபிக்கப்படலாம், அதன் விவரங்களை ஜி. டி. எல் இல் காணலாம்ஃ எம். பி. எஃப் சிக்கலைத் தீர்ப்பதற்கான ஒரு வழிமுறை கொடுக்கப்பட்ட தொகுப்பின் கூறுகளுக்கு இடையே ஒரு உறவைக் கண்டுபிடிக்க முடிந்தால், நம்பிக்கை பரப்புதல் என்ற கருத்தை அடிப்படையாகக் கொண்டு எம். பி. எஃப் சிக்கலைத் தீர்க்க முடியும், இது "செய்தி அனுப்புதல்" நுட்பத்தின் சிறப்பு பயன்பாடாகும். தேவையான உறவு என்னவென்றால், கொடுக்கப்பட்ட உள்ளூர் களங்களின் தொகுப்பை ஒரு சந்திப்பு மரமாக ஒழுங்கமைக்க முடியும். வேறு வார்த்தைகளில் கூறுவதானால், மரத்தின் செங்குத்துகள் போன்ற கூறுகளுடன் ஒரு வரைபட கோட்பாட்டு மரத்தை உருவாக்குகிறோம், அதாவது எந்த இரண்டு தன்னிச்சையான செங்குத்துகளுக்கும், இந்த இரண்டு செங்குத்துகளுக்கும் இடையில் ஒரு விளிம்பு உள்ளது, பின்னர் தொடர்புடைய லேபிள்களின் குறுக்கீடு, அதாவது, ஒவ்வொரு உச்சியிலும் உள்ள லேபிளின் துணைக்குழுவாகும். எடுத்துக்காட்டாக, எடுத்துக்காட்டு 1: பின்வரும் ஒன்பது உள்ளூர் களங்களைக் கவனியுங்கள்ஃ மேலே கொடுக்கப்பட்டுள்ள உள்ளூர் களங்களின் தொகுப்புக்கு, ஒருவர் அவற்றை கீழே காட்டப்பட்டுள்ளபடி ஒரு சந்தி மரமாக ஒழுங்கமைக்கலாம்ஃ இதேபோல் பின்வருவன போன்ற மற்றொரு தொகுப்பு கொடுக்கப்பட்டால் எடுத்துக்காட்டு 2: பின்வரும் நான்கு உள்ளூர் களங்களைக் கவனியுங்கள்ஃ பின்னர் இந்த உள்ளூர் களங்களுடன் மட்டுமே மரத்தை உருவாக்குவது சாத்தியமில்லை, ஏனெனில் இந்த மதிப்புகளின் தொகுப்புக்கு மேலே உள்ள தொகுப்பின் எந்த இரண்டு மதிப்புகளுக்கும் இடையில் வைக்கக்கூடிய பொதுவான களங்கள் இல்லை. இருப்பினும், கீழே காட்டப்பட்டுள்ளபடி இரண்டு போலி களங்களைச் சேர்த்தால், புதுப்பிக்கப்பட்ட தொகுப்பை ஒரு சந்தி மரத்தில் ஒழுங்கமைப்பது சாத்தியமாகவும் எளிதாகவும் இருக்கும். 5., 6. இதேபோல் இந்த களங்களின் தொகுப்புக்கு, சந்திப்பு மரம் கீழே காட்டப்பட்டுள்ளது போல் தெரிகிறதுஃ பொதுமைப்படுத்தப்பட்ட விநியோக விதி (ஜிடிஎல்) வழிமுறை உள்ளீடுஃ உள்ளூர் களங்களின் தொகுப்பு. வெளியீடுஃ கொடுக்கப்பட்ட களங்களின் தொகுப்புக்கு, சிக்கலைத் தீர்க்க தேவையான குறைந்தபட்ச செயல்பாடுகளின் எண்ணிக்கை கணக்கிடப்படுகிறது. எனவே, சந்தி மரத்தில் ஒரு விளிம்பால் இணைக்கப்பட்டிருந்தால், இருந்து ஒரு செய்தி ஒரு செயல்பாட்டால் கொடுக்கப்பட்ட மதிப்புகளின் தொகுப்பு/அட்டவணையாகும்ஃஃ. அனைத்து செயல்பாடுகளுடனும் தொடங்குவதற்கு, அதாவது. கொடுக்கப்பட்ட மரத்தில் உள்ள அனைத்து சேர்க்கைகளுக்கும், ஒரே மாதிரியாக வரையறுக்கப்படுகிறது, மேலும் ஒரு குறிப்பிட்ட செய்தி புதுப்பிக்கப்படும்போது, அது கீழே கொடுக்கப்பட்டுள்ள சமன்பாட்டைப் பின்பற்றுகிறது. = எங்கே என்றால் அது மரத்தில் அருகிலுள்ள உச்சியில் உள்ளது. இதேபோல் ஒவ்வொரு உச்சிக்கும் ஒரு நிலை உள்ளது, இது செயல்பாட்டிலிருந்து மதிப்புகளைக் கொண்ட அட்டவணையாக வரையறுக்கப்படுகிறது, செய்திகளை ஒரே மாதிரியாக 1 ஆகத் தொடங்குவது போலவே, நிலை உள்ளூர் கர்னலாக வரையறுக்கப்படுகிறது, ஆனால் புதுப்பிக்கப்படும் போதெல்லாம், இது பின்வரும் சமன்பாட்டைப் பின்பற்றுகிறதுஃ வழிமுறையின் அடிப்படை செயல்பாடு கொடுக்கப்பட்ட உள்ளூர் களங்களின் தொகுப்புக்கு உள்ளீடாக, ஒரு சந்தி மரத்தை உருவாக்க முடியுமா என்பதைக் கண்டுபிடிப்போம், தொகுப்பை நேரடியாகப் பயன்படுத்துவதன் மூலமோ அல்லது முதலில் தொகுப்பில் போலி களங்களைச் சேர்ப்பதன் மூலமோ, பின்னர் சந்தி மரத்தை உருவாக்குவதன் மூலமோ, கட்டுமான சந்திப்பு சாத்தியமில்லை என்றால், கொடுக்கப்பட்ட சமன்பாடு சிக்கலைக் கணக்கிடுவதற்கான படிகளின் எண்ணிக்கையைக் குறைக்க வழி இல்லை என்று வழிமுறை வெளியீடு, ஆனால் எங்களிடம் சந்திப்பு மரம் இருந்தால், வழிமுறை செய்திகளை அட்டவணைப்படுத்த வேண்டும் மற்றும் நிலைகளை கணக்கிட வேண்டும், இவற்றைச் செய்வதன் மூலம் எங்கே படிகள் என்பதை நாம் அறியலாம். செய்தி அனுப்புதல் மற்றும் நிலை கணக்கீட்டின் திட்டமிடல் இங்கே நாம் பேசப் போகும் இரண்டு சிறப்பு நிகழ்வுகள் உள்ளன, அவை ஒற்றை வெர்டெக்ஸ் சிக்கல், இதில் புறநிலை செயல்பாடு ஒரு உச்சியில் மட்டுமே கணக்கிடப்படுகிறது, இரண்டாவது அனைத்து வெர்டிஸஸ் சிக்கலாகும், அங்கு குறிக்கோள் அனைத்து உச்சிகளிலும் புறநிலை செயல்பாட்டைக் கணக்கிடுவதாகும். ஒற்றை-வெர்டெக்ஸ் சிக்கலில் இருந்து தொடங்குவோம், ஜிடிஎல் ஒவ்வொரு விளிம்பையும் இலக்கு உச்சியை நோக்கி இயக்குவதன் மூலம் தொடங்கும். இங்கே செய்திகள் இலக்கு வைக்கப்பட்ட உச்சியை நோக்கிய திசையில் மட்டுமே அனுப்பப்படுகின்றன. அனைத்து வழிநடத்தப்பட்ட செய்திகளும் ஒரு முறை மட்டுமே அனுப்பப்படுகின்றன என்பதை நினைவில் கொள்க. இலக்கு முனையை நோக்கி செல்லும் இலை முனைகளிலிருந்து (டிகிரி 1 ஆக இருக்கும்) செய்திகள் தொடங்கப்படுகின்றன. இந்த செய்தி இலைகளிலிருந்து அதன் பெற்றோருக்குச் செல்கிறது, பின்னர் அங்கிருந்து அவர்களின் பெற்றோருக்குச் செல்கிறது, மேலும் அது இலக்கு உச்சியை அடையும் வரை செல்கிறது. இலக்கு முனை அதன் அனைத்து அண்டை நாடுகளிலிருந்தும் அனைத்து செய்திகளையும் பெறும்போது மட்டுமே அதன் நிலையை கணக்கிடும். நமக்கு நிலை கிடைத்தவுடன், நமக்கு பதில் கிடைத்துவிட்டது, எனவே வழிமுறை முடிவடைகிறது. எடுத்துக்காட்டாக, மேலே கொடுக்கப்பட்டுள்ள உள்ளூர் களங்களின் தொகுப்பிலிருந்து கட்டப்பட்ட ஒரு சந்தி மரத்தைக் கருத்தில் கொள்வோம். எடுத்துக்காட்டு 1 இலிருந்து தொகுப்பு, இப்போது இந்த களங்களுக்கான திட்டமிடல் அட்டவணை (இலக்கு முனை இருக்கும் இடத்தில்). எனவே ஒற்றை வெர்டெக்ஸ் ஜிடிஎல்-க்கான சிக்கலை எண்கணித செயல்பாடுகளாகக் காட்டலாம் (குறிப்புஃ மேற்கண்ட சமன்பாட்டிற்கான விளக்கம் பின்னர் கட்டுரையில் விளக்கப்பட்டுள்ளது). இதன் அளவு (அதாவது. v க்கு அருகிலுள்ள செங்குத்துகளின் எண்ணிக்கை). ஆல்-வெர்டிஸஸ் சிக்கலைத் தீர்க்க, நாம் ஜிடிஎல்-ஐ பல வழிகளில் திட்டமிடலாம், அவற்றில் சில இணையான அமலாக்கமாகும், அங்கு ஒவ்வொரு சுற்றிலும், ஒவ்வொரு மாநிலமும் புதுப்பிக்கப்பட்டு, ஒவ்வொரு செய்தியும் ஒரே நேரத்தில் கணக்கிடப்பட்டு அனுப்பப்படுகிறது. இந்த வகையான செயல்பாட்டில் நிலைகளும் செய்திகளும் மரத்தின் விட்டத்திற்கு சமமான சுற்றுகளின் எண்ணிக்கைக்குப் பிறகு உறுதிப்படுத்தப்படும். இந்த கட்டத்தில் செங்குத்துகளின் அனைத்து நிலைகளும் விரும்பிய புறநிலை செயல்பாட்டிற்கு சமமாக இருக்கும். இந்த சிக்கலுக்கான ஜி. டி. எல்-ஐ திட்டமிடுவதற்கான மற்றொரு வழி தொடர் செயல்படுத்தலாகும், இது ஒற்றை வெர்டெக்ஸ் சிக்கலைப் போன்றது, தவிர, தேவையான தொகுப்பின் அனைத்து செங்குத்துகளும் அவற்றின் அனைத்து அண்டை நாடுகளிலிருந்தும் அனைத்து செய்திகளையும் பெற்று அவற்றின் நிலையைக் கணக்கிடும் வரை நாம் வழிமுறையை நிறுத்துவதில்லை. எனவே இந்த செயல்பாட்டிற்குத் தேவையான எண்கணிதத்தின் எண்ணிக்கை பெரும்பாலான எண்கணித செயல்பாடுகளாகும். ஒரு சந்தி மரத்தை உருவாக்குவது ஒரு சந்திப்பு மரத்தை உருவாக்குவதற்கான திறவுகோல் உள்ளூர் கள வரைபடத்தில் உள்ளது, இது செங்குத்துகளுடன் கூடிய எடையுள்ள முழுமையான வரைபடமாகும். ஒவ்வொரு உள்ளூர் களத்திற்கும் ஒன்று, வரையறுக்கப்பட்ட விளிம்பின் எடையைக் கொண்டுள்ளது. இருந்தால், அதில் உள்ளது என்று நாம் கூறுகிறோம். (அதிகபட்ச எடை கொண்ட மரத்தின் எடை) குறிக்கப்படுகிறது, இது n என்பது அந்த தொகுப்பில் உள்ள உறுப்புகளின் எண்ணிக்கை மூலம் வரையறுக்கப்படுகிறது. மேலும் தெளிவு மற்றும் விவரங்களுக்கு, தயவுசெய்து இவற்றைப் பார்க்கவும். திட்டமிடல் தேற்றம் உச்சி செட் மற்றும் விளிம்பு செட் கொண்ட ஒரு சந்திப்பு மரமாக இருக்கட்டும். இந்த வழிமுறையில், செய்திகள் எந்த விளிம்பிலும் இரு திசைகளிலும் அனுப்பப்படுகின்றன, எனவே விளிம்பு தொகுப்பு E ஐ வரிசைப்படுத்தப்பட்ட ஜோடி செங்குத்துகளின் தொகுப்பாக நாம் கூறலாம்/கருதலாம். எடுத்துக்காட்டாக, படம் 1 இலிருந்து பின்வருமாறு வரையறுக்கப்படலாம் குறிப்புஃ மேலே ஒரு செய்தி மரத்தில் பயணிக்கக்கூடிய அனைத்து திசைகளையும் உங்களுக்கு வழங்குகிறது. ஜிடிஎல்-க்கான அட்டவணை அதன் துணைக்குழுக்களின் வரையறுக்கப்பட்ட வரிசையாக வரையறுக்கப்படுகிறது. இது பொதுவாக {} ஆல் குறிக்கப்படுகிறது, வழிமுறையை இயக்கும் சுற்றில் புதுப்பிக்கப்பட்ட செய்திகளின் தொகுப்பு எங்கே. சில குறியீடுகளை வரையறுத்த/பார்த்த பிறகு, தேற்றம் கூறுவதை விரும்புவதைப் பார்ப்போம், நமக்கு ஒரு அட்டவணை வழங்கப்படும்போது, அதனுடன் தொடர்புடைய செய்தி ட்ரெல்லிஸ் வெர்டெக்ஸ் தொகுப்புடன் ஒரு வரையறுக்கப்பட்ட இயக்கப்பட்ட வரைபடமாக இருக்கும், இதில் ஒரு பொதுவான உறுப்பு குறிக்கப்படுகிறது, பின்னர் செய்தி கடந்து சென்ற பிறகு, உச்சியில் உள்ள நிலை வரையறுக்கப்பட்ட நோக்கமாக இருக்கும் மற்றும் கணக்கீட்டு சிக்கலுக்கு ஒரு பாதை இருந்தால் இங்கே கணக்கீட்டிற்குத் தேவையான கணித செயல்பாடுகளின் எண்ணிக்கையின் அடிப்படையில் எம். பி. எஃப் சிக்கலைத் தீர்ப்பதற்கான சிக்கலை விளக்க முயற்சிக்கிறோம். அதாவது. சாதாரண முறையைப் பயன்படுத்தி கணக்கிடும்போது தேவைப்படும் செயல்பாடுகளின் எண்ணிக்கையையும் (இங்கே சாதாரண முறையால் ஜிடிஎல் கருத்துகளைப் பயன்படுத்தாத குறுகிய முறைகளில் செய்தி அனுப்புதல் அல்லது சந்திப்பு மரங்களைப் பயன்படுத்தாத முறைகள் மூலம் நாம் அர்த்தப்படுத்துகிறோம்) மற்றும் பொதுமைப்படுத்தப்பட்ட விநியோகச் சட்டத்தைப் பயன்படுத்தி செயல்பாடுகளின் எண்ணிக்கையையும் ஒப்பிடுகிறோம். எடுத்துக்காட்டுஃ பின்வரும் வெளிப்பாட்டை நாம் கணக்கிட வேண்டிய எளிய வழக்கைக் கவனியுங்கள். இந்த வெளிப்பாட்டை அப்பாவித்தனமாக மதிப்பிடுவதற்கு இரண்டு பெருக்கங்களும் ஒரு கூட்டலும் தேவை. விநியோக விதியைப் பயன்படுத்தி வெளிப்படுத்தப்படும் போது வெளிப்பாட்டை ஒரு எளிய தேர்வாக எழுதலாம், இது செயல்பாடுகளின் எண்ணிக்கையை ஒரு கூட்டல் மற்றும் ஒரு பெருக்கமாகக் குறைக்கிறது. மேலே விளக்கப்பட்ட உதாரணத்தைப் போலவே, ஜிடிஎல்-ஐப் பயன்படுத்துவதன் மூலம் முடிந்தவரை குறைவான செயல்பாடுகளைச் செய்ய சமன்பாடுகளை வெவ்வேறு வடிவங்களில் வெளிப்படுத்துவோம். முந்தைய பிரிவுகளில் விளக்கப்பட்டுள்ளபடி, சந்தி மரங்களின் கருத்தைப் பயன்படுத்தி சிக்கலைத் தீர்க்கிறோம். இந்த மரங்களைப் பயன்படுத்துவதன் மூலம் பெறப்படும் உகப்பாக்கம் மரங்களில் ஒரு அரை குழு சிக்கலைத் தீர்ப்பதன் மூலம் பெறப்பட்ட உகப்பாக்கத்துடன் ஒப்பிடத்தக்கது. எடுத்துக்காட்டாக, எண்களின் குழுவின் குறைந்தபட்சத்தைக் கண்டறிய, நம்மிடம் ஒரு மரம் இருந்தால், உறுப்புகள் அனைத்தும் மரத்தின் அடிப்பகுதியில் இருந்தால், குறைந்தபட்சம் இரண்டு உருப்படிகளை இணையாக ஒப்பிடலாம், இதன் விளைவாக குறைந்தபட்சம் பெற்றோருக்கு எழுதப்படும். இந்த செயல்முறை மரத்தின் மேல் பரப்பப்படும்போது குறைந்தபட்ச உறுப்புகளின் குழு வேரில் காணப்படும். செய்தி அனுப்புதலைப் பயன்படுத்தி சந்தி மரத்தைத் தீர்ப்பதற்கான சிக்கலானது பின்வருமாறு நாம் முன்பு பயன்படுத்திய சூத்திரத்தை பின்வரும் வடிவத்திற்கு மீண்டும் எழுதுகிறோம். v உச்சியிலிருந்து---- செய்தி சமன்பாட்டிற்கு அனுப்பப்பட வேண்டிய செய்திக்கான ஈக்யூஎன் இது. இதேபோல் v உச்சியின் நிலையை கணக்கிடுவதற்கான சமன்பாட்டை பின்வருமாறு மீண்டும் எழுதுகிறோம். நம்மிடம் ஒரு விளிம்பு உள்ளது என்று வைத்துக்கொள்வோம், செய்தி சமன்பாட்டைப் பயன்படுத்தி செய்தியைக் கணக்கிடுகிறோம். கணக்கிடுவதற்கு சேர்த்தல்கள் மற்றும் பெருக்கங்கள் தேவைப்படுகின்றன. (நாம் இதைப் பிரதிநிதித்துவப்படுத்துகிறோம்.) ஆனால் இதற்கு பல சாத்தியங்கள் இருக்கும். எனவே முழு செய்திக்கும் சேர்த்தல்கள் மற்றும் பெருக்கங்கள் தேவைப்படும் மரத்தின் விளிம்புகளை நோக்கி ஒரு செய்தியை அனுப்ப தேவையான மொத்த எண்கணித செயல்பாடுகளின் எண்ணிக்கை சேர்த்தல்கள் மற்றும் பெருக்கங்களாக இருக்கும். அனைத்து செய்திகளும் அனுப்பப்பட்டவுடன் வழிமுறை நிலை கணக்கீட்டுடன் முடிவடைகிறது நிலை கணக்கீட்டிற்கு அதிக பெருக்கங்கள் தேவைப்படுகின்றன. இவ்வாறு நிலையைக் கணக்கிடத் தேவையான கணக்கீடுகளின் எண்ணிக்கை கீழே உள்ள சேர்த்தல்கள் மற்றும் பெருக்கங்கள் என கொடுக்கப்பட்டுள்ளது எனவே கணக்கீடுகளின் எண்ணிக்கையின் மொத்த எண்ணிக்கை---- எங்கே ஒரு விளிம்பு மற்றும் அதன் அளவு வரையறுக்கப்படுகிறது மேலே உள்ள சூத்திரம் நமக்கு மேல் வரம்பைக் கொடுக்கிறது. எனவே, விளிம்பின் சிக்கலை நாம் வரையறுத்தால், படம் 1 இல் வரையறுக்கப்பட்டுள்ள சிக்கலுக்கான விளிம்பின் சிக்கலை நாம் இப்போது பின்வருமாறு கணக்கிடுகிறோம் என்று எழுதலாம். (இங்கே நேரடி முறை மூலம் நாம் செய்தி அனுப்புதலைப் பயன்படுத்தாத முறைகளைக் குறிக்கிறோம். நேரடி முறையைப் பயன்படுத்தி எடுக்கப்பட்ட நேரம் ஒவ்வொரு முனையிலும் செய்தியைக் கணக்கிடுவதற்கும், ஒவ்வொரு முனைகளின் நிலையைக் கணக்கிடுவதற்கும் சமமாக இருக்கும்.) இப்போது நாம் அனைத்து-வெர்டெக்ஸ் சிக்கலைக் கருத்தில் கொள்கிறோம், அங்கு செய்தி இரு திசைகளிலும் அனுப்பப்பட வேண்டும் மற்றும் இரு முனைகளிலும் நிலை கணக்கிடப்பட வேண்டும். இது எடுக்கும், ஆனால் முன்கூட்டிய கணக்கீட்டின் மூலம் பெருக்கங்களின் எண்ணிக்கையை குறைக்கலாம். இங்கே உச்சியின் அளவு உள்ளது. Ex: எண்களுடன் ஒரு தொகுப்பு இருந்தால். அனைத்து டி தயாரிப்புகளையும் வெளிப்படையானதை விட அதிகபட்ச பெருக்கங்களுடன் கணக்கிட முடியும். அளவுகளை முன்கூட்டியே கணக்கிடுவதன் மூலம் இதைச் செய்கிறோம், இது பெருக்கங்களை எடுக்கும். பின்னர் நம்மிடம் உள்ளதைத் தவிர மற்ற அனைத்தின் பெருக்கத்தையும் குறிக்கிறது என்றால், மொத்தத்தை உருவாக்கும் மற்றொரு பெருக்கங்கள் தேவைப்படும் சந்தி மரத்தின் கட்டுமானத்திற்கு வரும்போது நாம் அதிகம் செய்ய முடியாது, தவிர நம்மிடம் பல அதிகபட்ச எடை பரவலான மரம் இருக்கலாம், மேலும் குறைந்த எடையுடன் பரவலான மரத்தை நாம் தேர்வு செய்ய வேண்டும், சில நேரங்களில் இது சந்திப்பு மரத்தின் சிக்கலைக் குறைக்க ஒரு உள்ளூர் களத்தைச் சேர்ப்பதைக் குறிக்கலாம். உள்ளூர் களங்களை ஒரு சந்தி மரமாக வெளிப்படுத்த முடியும் போது மட்டுமே ஜிடிஎல் சரியானது என்று தோன்றலாம். ஆனால் சுழற்சிகள் மற்றும் பல மறு செய்கைகள் இருக்கும் சந்தர்ப்பங்களில் கூட செய்திகள் தோராயமாக புறநிலை செயல்பாட்டிற்கு சமமாக இருக்கும். குறைந்த அடர்த்தி சமநிலை-சரிபார்ப்பு குறியீடுகளுக்கான கேலஜர்-டேனர்-வைபர்க் வழிமுறை குறித்த சோதனைகள் இந்த கூற்றை ஆதரிக்கின்றன. குறிப்புகள் தகவல் கோட்பாடு வழிமுறைகள் வரைகலை மாதிரிகள் டிஜிட்டல் சமிக்ஞை செயலாக்கம்