Randomized rounding
கணினி அறிவியல் மற்றும் செயல்பாட்டு ஆராய்ச்சியில், தோராயமான சுற்றமைப்பு என்பது தோராயமான வழிமுறைகளை வடிவமைப்பதற்கும் பகுப்பாய்வு செய்வதற்கும் பரவலாகப் பயன்படுத்தப்படும் அணுகுமுறையாகும். பல ஒருங்கிணைந்த உகப்பாக்கம் சிக்கல்கள் துல்லியமாக தீர்க்க கணக்கீட்டு ரீதியாக சிக்கலானவை (உகந்த தன்மைக்கு). இத்தகைய சிக்கல்களுக்கு, சீரற்ற ரவுண்டிங் வேகமான (பல்லுறுப்புக்கோவை நேரம்) தோராயமான வழிமுறைகளை வடிவமைக்கப் பயன்படுத்தப்படலாம்-அதாவது, எந்த உள்ளீடும் கொடுக்கப்பட்டால் தோராயமாக உகந்த தீர்வைத் தருவதாக உத்தரவாதம் அளிக்கப்படும் வழிமுறைகள். சீரற்ற வட்டத்தின் அடிப்படை யோசனை என்னவென்றால், சிக்கலை தளர்த்துவதற்கான உகந்த தீர்வை அசல் சிக்கலுக்கு தோராயமாக உகந்த தீர்வாக மாற்றுவதாகும். இதன் விளைவாக வரும் வழிமுறை பொதுவாக நிகழ்தகவு முறையைப் பயன்படுத்தி பகுப்பாய்வு செய்யப்படுகிறது. கண்ணோட்டம் அடிப்படை அணுகுமுறைக்கு மூன்று படிகள் உள்ளனஃ ஒரு முழு எண் நேரியல் நிரலாக (ஐஎல்பி) தீர்க்கப்பட வேண்டிய சிக்கலை உருவாக்குங்கள். ஐஎல்பியின் நேரியல் நிரலாக்க தளர்வுக்கு (எல்பி) உகந்த பின்னத் தீர்வை கணக்கிடுங்கள். எல். பி. யின் பின்ன கரைசலை ஐ. எல். பி. யின் முழு எண் கரைசலுக்குச் சுற்றவும். (இந்த அணுகுமுறை பொதுவாக நேரியல் நிரல்களுடன் பயன்படுத்தப்பட்டாலும், மற்ற வகையான தளர்வுகள் சில நேரங்களில் பயன்படுத்தப்படுகின்றன. எடுத்துக்காட்டாக, கோமேன்ஸ் மற்றும் வில்லியம்சனின் அரை வரையறுக்கப்பட்ட நிரலாக்க அடிப்படையிலான மேக்ஸ்-கட் தோராயமான வழிமுறையைப் பார்க்கவும்.) முதல் கட்டத்தில், பொருத்தமான முழு எண் நேரியல் நிரலைத் தேர்ந்தெடுப்பது சவால். நேரியல் நிரலாக்கத்துடன் பரிச்சயம், குறிப்பாக நேரியல் நிரல்கள் மற்றும் முழு எண் நேரியல் நிரல்களைப் பயன்படுத்தி மாடலிங், தேவைப்படுகிறது. பல சிக்கல்களுக்கு, கீழே உள்ள செட் கவர் எடுத்துக்காட்டில் உள்ளதைப் போல, ஒரு இயற்கையான முழு எண் நேரியல் நிரல் நன்றாக வேலை செய்கிறது. (முழு எண் நேரியல் நிரல் ஒரு சிறிய ஒருங்கிணைப்பு இடைவெளியைக் கொண்டிருக்க வேண்டும்; உண்மையில் சீரற்ற ரவுண்டிங் பெரும்பாலும் ஒருங்கிணைப்பு இடைவெளிகளில் வரம்புகளை நிரூபிக்க பயன்படுத்தப்படுகிறது. இரண்டாவது கட்டத்தில், உகந்த பின்னத் தீர்வை பொதுவாக எந்த நிலையான நேரியல் நிரலாக்க வழிமுறையையும் பயன்படுத்தி பல்லுறுப்புக்கோவை நேரத்தில் கணக்கிட முடியும். மூன்றாவது கட்டத்தில், பின்னத் தீர்வு ஒரு முழு எண் தீர்வாக மாற்றப்பட வேண்டும் (இதனால் அசல் சிக்கலுக்கான தீர்வு). இது பின்னத் தீர்வைச் சுற்றுவது என்று அழைக்கப்படுகிறது. இதன் விளைவாக வரும் முழு எண் கரைசல் (நிரூபிக்கக்கூடிய வகையில்) பின்ன கரைசலின் விலையை விட அதிக செலவு இல்லாததாக இருக்க வேண்டும். இது முழு எண் தீர்வின் விலை உகந்த முழு எண் தீர்வின் விலையை விட அதிகமாக இல்லை என்பதை உறுதி செய்யும். மூன்றாவது படி (ரவுண்டிங்) செய்ய பயன்படுத்தப்படும் முக்கிய நுட்பம் சீரற்றமயமாக்கலைப் பயன்படுத்துவதாகும், பின்னர் ரவுண்டிங் காரணமாக ஏற்படும் செலவு அதிகரிப்பை பிணைக்க நிகழ்தகவு வாதங்களைப் பயன்படுத்துவதாகும் (காம்பினடோரிக்கிலிருந்து நிகழ்தகவு முறையைப் பின்பற்றுகிறது). அதில், விரும்பிய பண்புகளுடன் தனித்துவமான கட்டமைப்புகள் இருப்பதைக் காட்ட நிகழ்தகவு வாதங்கள் பயன்படுத்தப்படுகின்றன. இந்த சூழலில், பின்வருவனவற்றைக் காட்ட ஒருவர் இத்தகைய வாதங்களைப் பயன்படுத்துகிறார்ஃ LP இன் எந்தவொரு பின்னத் தீர்வையும் கருத்தில் கொண்டால், நேர்மறை நிகழ்தகவுடன் சீரற்ற வட்ட செயல்முறை ஒரு முழு எண் தீர்வை உருவாக்குகிறது, இது சில விரும்பிய அளவுகோல்களின்படி தோராயமாக மதிப்பிடப்படுகிறது. இறுதியாக, மூன்றாவது படிநிலையை கணக்கீட்டு ரீதியாக திறமையானதாக மாற்ற, ஒன்று அதிக நிகழ்தகவுடன் தோராயமாக இருப்பதைக் காட்டுகிறது (இதனால் படி சீரற்றதாக இருக்க முடியும்) அல்லது ஒருவர் ரவுண்டிங் படிநிலையை திசைதிருப்புகிறார், பொதுவாக நிபந்தனைக்குட்பட்ட நிகழ்தகவுகளின் முறையைப் பயன்படுத்துகிறார். பிந்தைய முறை சீரற்ற ரவுண்டிங் செயல்முறையை ஒரு திறமையான தீர்மானிக்கும் செயல்முறையாக மாற்றுகிறது, இது ஒரு நல்ல முடிவை அடைவதற்கு உத்தரவாதம் அளிக்கிறது. எடுத்துக்காட்டுஃ செட் கவர் சிக்கல் செட் கவர் சிக்கலுக்கான தோராயமான வழிமுறையை வடிவமைக்க சீரற்ற ரவுண்டிங் எவ்வாறு பயன்படுத்தப்படலாம் என்பதை பின்வரும் எடுத்துக்காட்டு விளக்குகிறது. ஒரு பிரபஞ்சத்தின் மீது செட் கவர் எந்த நிகழ்வையும் சரிசெய்யவும். படி 1 க்கு, இந்த நிகழ்வுக்கான செட் கவர்க்கான நிலையான முழு எண் நேரியல் நிரலாக ஐபி இருக்கட்டும். படி 2 க்கு, LP என்பது IP இன் நேரியல் நிரலாக்க தளர்வாக இருக்கட்டும், மேலும் எந்தவொரு நிலையான நேரியல் நிரலாக்க வழிமுறையையும் பயன்படுத்தி LP க்கு உகந்த தீர்வை கணக்கிடுங்கள். இது உள்ளீட்டு அளவில் பல்லுறுப்புக்கோவை நேரத்தை எடுக்கும். எல். பி. க்கான சாத்தியமான தீர்வுகள் ஒவ்வொரு தொகுப்புக்கும் எதிர்மறை அல்லாத எடையை ஒதுக்கும் திசையன்கள் ஆகும், அதாவது, ஒவ்வொரு உறுப்புக்கும், உள்ளடக்கியது-- கொண்ட தொகுப்புகளுக்கு ஒதுக்கப்பட்ட மொத்த எடை குறைந்தது 1 ஆகும், அதாவது, உகந்த தீர்வு ஒரு சாத்தியமான தீர்வாகும், அதன் செலவு முடிந்தவரை சிறியது. எந்தவொரு செட் கவர் ஒரு சாத்தியமான தீர்வை வழங்குகிறது என்பதை நினைவில் கொள்க (எங்கு, இல்லையெனில்). இதன் செலவு செலவு சமம், அதாவது, வேறு வார்த்தைகளில் கூறுவதானால், நேரியல் நிரல் LP என்பது கொடுக்கப்பட்ட செட்-கவர் சிக்கலின் தளர்வு ஆகும். எல்பி-க்கு சாத்தியமான தீர்வுகளில் குறைந்தபட்ச செலவு இருப்பதால், உகந்த செட் கவர் செலவில் செலவு குறைந்த வரம்பாகும். சீரற்ற ரவுண்டிங் படி படி 3 இல், குறைந்தபட்ச-செலவு பின்ன தொகுப்பு அட்டையை சாத்தியமான முழு எண் தீர்வாக (உண்மையான தொகுப்பு அட்டையுடன் தொடர்புடையது) மாற்ற வேண்டும். ரவுண்டிங் படி, நேர்மறை நிகழ்தகவுடன், செலவின் ஒரு சிறிய காரணிக்குள் செலவைக் கொண்டிருக்க வேண்டும். பின்னர் (செலவு உகந்த செட் கவர் செலவில் குறைந்த வரம்பாக இருப்பதால்), செலவு உகந்த செலவின் ஒரு சிறிய காரணிக்குள் இருக்கும். ஒரு தொடக்க புள்ளியாக, மிகவும் இயற்கையான ரவுண்டிங் திட்டத்தைக் கவனியுங்கள்ஃ ஒவ்வொரு செட்டுக்கும், நிகழ்தகவுடன் எடுத்துக் கொள்ளுங்கள், இல்லையெனில் எடுத்துக் கொள்ளுங்கள். இந்த ரவுண்டிங் திட்டத்துடன், தேர்ந்தெடுக்கப்பட்ட செட்டுகளின் எதிர்பார்க்கப்படும் செலவு அதிகபட்சமாக, பின்ன காப்பீட்டின் செலவு ஆகும். இது நல்லது. துரதிர்ஷ்டவசமாக கவரேஜ் நன்றாக இல்லை. மாறிகள் சிறியதாக இருக்கும்போது, ஒரு உறுப்பு மூடப்படாத நிகழ்தகவு பற்றி எனவே உறுப்புகளின் ஒரு நிலையான பின்னம் மட்டுமே எதிர்பார்ப்பில் மூடப்படும். ஒவ்வொரு உறுப்பையும் அதிக நிகழ்தகவுடன் மறைக்க, நிலையான ரவுண்டிங் திட்டம் முதலில் பொருத்தமான காரணியால் ரவுண்டிங் நிகழ்தகவுகளை அளவிடுகிறது. இங்கே நிலையான ரவுண்டிங் திட்டம்ஃ ஒரு அளவுருவை சரிசெய்யவும். ஒவ்வொரு செட்டுக்கும், நிகழ்தகவுடன் எடுத்துக் கொள்ளுங்கள், இல்லையெனில் எடுத்துக் கொள்ளுங்கள். சாத்தியக்கூறுகளை அளவிடுவதன் மூலம் எதிர்பார்க்கப்படும் செலவு அதிகரிக்கிறது, ஆனால் அனைத்து கூறுகளின் பாதுகாப்பையும் சாத்தியமாக்குகிறது. அனைத்து உறுப்புகளும் பூஜ்ஜியமற்ற நிகழ்தகவுடன் நிரூபிக்கக்கூடிய வகையில் முடிந்தவரை சிறியதாக தேர்வு செய்வதே யோசனை. இங்கே ஒரு விரிவான பகுப்பாய்வு உள்ளது. லெம்மா (வட்டத் திட்டத்திற்கான தோராயமான உத்தரவாதம்) சரிசெய்யவும். நேர்மறையான நிகழ்தகவுடன், ரவுண்டிங் திட்டம் அதிகபட்சமாக ஒரு செட் செலவு காப்பீட்டைத் தருகிறது (இதனால் செலவு நேரங்கள் உகந்த செட் காப்பீட்டின் செலவு). (குறிப்புஃ கவனமாக அதை குறைக்கலாம்.) ஆதாரம் சீரற்ற ரவுண்டிங் திட்டத்தின் வெளியீடு பின்வரும் "மோசமான" நிகழ்வுகள் எதுவும் நிகழாத வரை விரும்பிய பண்புகளைக் கொண்டுள்ளதுஃ அதிகப்படியான செலவு, அல்லது சில உறுப்புகளுக்கு, ஈடுசெய்யத் தவறிவிட்டது. ஒவ்வொருவரின் எதிர்பார்ப்பும் அதிகபட்சமாக உள்ளது. எதிர்பார்ப்பின் நேரியல் மூலம், எதிர்பார்ப்பு அதிகபட்சமாக உள்ளது. எனவே, மார்கோவின் சமத்துவமின்மையால், மேலே உள்ள முதல் மோசமான நிகழ்வின் நிகழ்தகவு அதிகபட்சமாக உள்ளது. மீதமுள்ள மோசமான நிகழ்வுகளுக்கு (ஒவ்வொரு உறுப்புக்கும் ஒன்று), எந்தவொரு உறுப்புக்கும், உள்ளடக்கப்படாத நிகழ்தகவு (இது சமத்துவமின்மையைப் பயன்படுத்துகிறது, இது கடுமையானது) என்பதைக் கவனியுங்கள். எனவே, ஒவ்வொரு உறுப்புக்கும், உறுப்பு மூடப்படாத நிகழ்தகவு குறைவாக உள்ளது. யூனியன் கட்டுப்பாட்டிற்குள், மோசமான நிகழ்வுகளில் ஒன்று நிகழும் நிகழ்தகவு குறைவாக உள்ளது. எனவே, நேர்மறையான நிகழ்தகவுடன் மோசமான நிகழ்வுகள் எதுவும் இல்லை, மேலும் இது அதிகபட்ச செலவின் தொகுப்பாகும். நிபந்தனைக்குட்பட்ட நிகழ்தகவுகளின் முறையைப் பயன்படுத்தி கியூ. இ. டி விலகல் மேற்கண்ட குறிப்பு ஒரு செட் காஸ்ட் கவர் இருப்பதைக் காட்டுகிறது). இந்த சூழலில் நமது குறிக்கோள் ஒரு திறமையான தோராயமான வழிமுறையாகும், இது ஒரு இருப்பு ஆதாரம் மட்டுமல்ல, எனவே நாம் முடிக்கவில்லை. ஒரு அணுகுமுறை கொஞ்சம் அதிகரிக்க வேண்டும், பின்னர் வெற்றியின் நிகழ்தகவு குறைந்தபட்சம் 1/4 என்று சொல்லுங்கள். இந்த மாற்றத்தின் மூலம், சீரற்ற ரவுண்டிங் படிநிலையை ஒரு சில முறை மீண்டும் செய்வது அதிக நிகழ்தகவுடன் வெற்றிகரமான முடிவை உறுதிப்படுத்த போதுமானது. அந்த அணுகுமுறை தோராய விகிதத்தை பலவீனப்படுத்துகிறது. மேலே உள்ள இருப்பு ஆதாரத்தின் தோராய விகிதத்துடன் பொருந்தக்கூடிய ஒரு தீர்மானகரமான வழிமுறையை வழங்கும் ஒரு வித்தியாசமான அணுகுமுறையை நாம் அடுத்ததாக விவரிக்கிறோம். இந்த அணுகுமுறை நிபந்தனை சாத்தியக்கூறுகளின் முறை என்று அழைக்கப்படுகிறது. தீர்மானகரமான வழிமுறை சீரற்ற வட்டத் திட்டத்தைப் பின்பற்றுகிறதுஃ இது ஒவ்வொரு தொகுப்பையும் மாறி மாறி கருத்தில் கொண்டு தேர்வு செய்கிறது. ஆனால் ஒவ்வொரு தேர்வையும் தோராயமாக அடிப்படையாகக் கொள்வதற்குப் பதிலாக, தோல்வியின் நிபந்தனைக்குட்பட்ட நிகழ்தகவை, இதுவரை தேர்வுகள் கொடுக்கப்பட்ட நிலையில், 1 க்குக் கீழே வைத்திருக்க, இது தீர்மானகரமாக தேர்வு செய்கிறது. தோல்வியின் நிபந்தனை நிகழ்தகவை இணைத்தல் தோல்வியின் நிபந்தனை நிகழ்தகவை 1 க்கும் குறைவாக வைத்திருக்க ஒவ்வொரு மாறியையும் ஒவ்வொன்றாக அமைக்க முடியும். இதைச் செய்ய, தோல்வியின் நிபந்தனை நிகழ்தகவின் மீது நமக்கு ஒரு நல்ல கட்டுப்பாடு தேவை. அசல் இருப்பு ஆதாரத்தை செம்மைப்படுத்துவதன் மூலம் எல்லை வரும். அந்த ஆதாரம் சீரற்ற மாறியின் எதிர்பார்ப்பால் தோல்வியின் நிகழ்தகவை மறைமுகமாக கட்டுப்படுத்துகிறது, இறுதியில் கண்டுபிடிக்கப்படாத கூறுகளின் தொகுப்பு எங்கே. சீரற்ற மாறி சற்று மர்மமாகத் தோன்றலாம், ஆனால் இது நிகழ்தகவு ஆதாரத்தை ஒரு முறையான வழியில் பிரதிபலிக்கிறது. முதல் மோசமான நிகழ்வின் நிகழ்தகவை (செலவு மிக அதிகமாக உள்ளது) கட்டுப்படுத்த மார்கோவின் சமத்துவமின்மையைப் பயன்படுத்துவதிலிருந்து முதல் சொல் வருகிறது. செலவு மிக அதிகமாக இருந்தால் அது குறைந்தபட்சம் 1 க்கு பங்களிக்கிறது. இரண்டாவது சொல் இரண்டாவது வகையான மோசமான நிகழ்வுகளின் எண்ணிக்கையை கணக்கிடுகிறது (வெளிப்படுத்தப்படாத கூறுகள்). ஏதேனும் உறுப்பு கண்டுபிடிக்கப்படாமல் விட்டுவிட்டால் அது குறைந்தது 1 க்கு பங்களிக்கிறது. எனவே, 1 க்கும் குறைவான எந்தவொரு முடிவிலும், அனைத்து கூறுகளையும் உள்ளடக்கியிருக்க வேண்டும் மற்றும் லெம்மாவிலிருந்து விரும்பிய வரம்பை பூர்த்தி செய்ய வேண்டும். சுருக்கமாக, ரவுண்டிங் படி தோல்வியுற்றால், பின்னர். இது (மார்கோவின் சமத்துவமின்மையால்) தோல்வியின் நிகழ்தகவின் மேல் வரம்பைக் குறிக்கிறது. மேலே உள்ள வாதம் ஏற்கனவே லெம்மாவின் ஆதாரத்தில் மறைமுகமாக உள்ளது என்பதை நினைவில் கொள்க, இது கணக்கீட்டின் மூலமும் காட்டுகிறது. நிபந்தனை நிகழ்தகவுகளின் முறையைப் பயன்படுத்த, ரவுண்டிங் படி தொடரும்போது தோல்வியின் நிபந்தனை நிகழ்தகவை பிணைக்க வாதத்தை நீட்டிக்க வேண்டும். பொதுவாக, இது ஒரு முறையான வழியில் செய்யப்படலாம், இருப்பினும் இது தொழில்நுட்ப ரீதியாக கடினமாக இருக்கலாம். எனவே, ரவுண்டிங் படி செட் வழியாக மீண்டும் நிகழும்போது தோல்வியின் நிபந்தனை நிகழ்தகவு பற்றி என்ன? மார்கோவின் சமத்துவமின்மையால், ரவுண்டிங் படி தோல்வியடையும் எந்தவொரு முடிவிலும், தோல்வியின் நிபந்தனை நிகழ்தகவு அதிகபட்சமாக நிபந்தனைக்குட்பட்ட எதிர்பார்ப்பாகும். அசல் ஆதாரத்தில் நிபந்தனையற்ற எதிர்பார்ப்பை நாம் கணக்கிட்டதைப் போலவே, நிபந்தனைக்குட்பட்ட எதிர்பார்ப்பையும் அடுத்து கணக்கிடுகிறோம். சில மறு செய்கைகளின் முடிவில் ரவுண்டிங் செயல்முறையின் நிலையைக் கவனியுங்கள். இதுவரை கருதப்பட்ட தொகுப்புகளைக் குறிக்கலாம் (முதல் தொகுப்புகள்). (ஓரளவு ஒதுக்கப்பட்ட) திசையனைக் குறிக்கலாம் (எனவே இருந்தால் மட்டுமே தீர்மானிக்கப்படுகிறது). ஒவ்வொரு தொகுப்புக்கும், 1 ஆக அமைக்கப்படும் நிகழ்தகவைக் குறிக்கலாம். இன்னும் மூடப்படாத கூறுகளைக் கொண்டிருக்கட்டும். பின்னர் நிபந்தனைக்குட்பட்ட எதிர்பார்ப்பு, இதுவரை செய்யப்பட்ட தேர்வுகள் கொடுக்கப்பட்டுள்ளன, அதாவது, கொடுக்கப்பட்டுள்ளது, இது மறு செய்கைக்குப் பிறகு மட்டுமே தீர்மானிக்கப்படுகிறது. தோல்வியின் நிபந்தனைக்குட்பட்ட நிகழ்தகவை 1 க்கும் குறைவாக வைத்திருப்பது தோல்வியின் நிபந்தனைக்குட்பட்ட நிகழ்தகவை 1 க்கும் குறைவாக வைத்திருக்க, நிபந்தனைக்குட்பட்ட எதிர்பார்ப்பை 1 க்கும் குறைவாக வைத்திருக்க போதுமானது. இதைச் செய்ய, அதிகரிக்க வேண்டும் என்ற நிபந்தனை எதிர்பார்ப்பை வைத்திருக்க இது போதுமானது. இதைத்தான் அல்காரிதம் செய்யும். அது (எங்கே) என்பதை உறுதிப்படுத்த ஒவ்வொரு மறு செய்கையிலும் அமைக்கப்படும். மூன்றாம் மறு செய்கையில், அதை உறுதிப்படுத்த வழிமுறை எவ்வாறு அமைக்க முடியும்? இதன் விளைவாக வரும் மதிப்பைக் குறைக்கும் வகையில் இது வெறுமனே அமைக்க முடியும் என்று மாறிவிடும். ஏன் என்பதைப் பார்க்க, மறு செய்கை தொடங்கும் நேரத்தில் கவனம் செலுத்துங்கள். அந்த நேரத்தில், தீர்மானிக்கப்படுகிறது, ஆனால் இன்னும் தீர்மானிக்கப்படவில்லை---இது மறு செய்கையில் எவ்வாறு அமைக்கப்படுகிறது என்பதைப் பொறுத்து இரண்டு சாத்தியமான மதிப்புகளை எடுக்கலாம். அதன் மதிப்பைக் குறிக்கலாம். முறையே 0 அல்லது 1 ஆக அமைக்கப்பட்டுள்ளதா என்பதைப் பொறுத்து, இரண்டு சாத்தியமான மதிப்புகளைக் குறிக்கலாம். நிபந்தனைக்குட்பட்ட எதிர்பார்ப்பின் வரையறையின்படி, இரண்டு அளவுகளின் எடையுள்ள சராசரி எப்போதும் குறைந்தபட்சம் அந்த இரண்டு அளவுகளில் குறைந்தபட்சமாக இருப்பதால், அது பின்வருமாறு, இதன் விளைவாக வரும் மதிப்பைக் குறைக்கும் வகையில் அமைப்பது அதற்கு உத்தரவாதம் அளிக்கும். இதைத்தான் அல்காரிதம் செய்யும். விரிவாக, இதன் பொருள் என்ன? (மற்ற அனைத்து அளவுகளும் நிலையான நிலையில்) ஒரு செயல்பாடாகக் கருதப்படுவது ஒரு நேரியல் செயல்பாடாகும், மேலும் அந்த செயல்பாட்டில் உள்ள குணகம் எனவே, இந்த வெளிப்பாடு நேர்மறையாக இருந்தால் வழிமுறை 0 ஆகவும், இல்லையெனில் 1 ஆகவும் அமைக்கப்பட வேண்டும். இது பின்வரும் வழிமுறையை வழங்குகிறது. செட் கவர் உள்ளீட்டிற்கான சீரற்ற-சுற்று வழிமுறைஃ செட் சிஸ்டம், பிரபஞ்சம், செலவு திசையன் வெளியீடுஃ செட் கவர் (செட் கவர்க்கான நிலையான முழு எண் நேரியல் நிரலுக்கு ஒரு தீர்வு) ஒரு குறைந்தபட்ச-செலவு பின்ன தொகுப்பு அட்டையை கணக்கிடுங்கள் (எல்பி தளர்வுக்கு உகந்த தீர்வு). விடுங்கள். ஒவ்வொன்றாக விடுங்கள். ஒவ்வொருவருக்கும்ஃ செய்யட்டும். (இன்னும் தீர்மானிக்கப்படாத தொகுப்புகளைக் கொண்டுள்ளது.) பின்னர் செட் செய்தால், மற்றபடி செட் மற்றும். (இன்னும் மூடப்படாத கூறுகளைக் கொண்டுள்ளது.) திரும்பிப் பாருங்கள். லெம்மா (வழிமுறைக்கான தோராயமான உத்தரவாதம்) மேலே உள்ள வழிமுறை எந்தவொரு (பின்ன) தொகுப்பு அட்டையின் குறைந்தபட்ச செலவின் பெரும்பாலான நேரங்களில் செலவின் தொகுப்பை வழங்குகிறது. ஒவ்வொரு மறு செய்கையிலும் நிபந்தனைக்குட்பட்ட எதிர்பார்ப்பு அதிகரிக்காது என்பதை வழிமுறை உறுதி செய்கிறது. இந்த நிபந்தனை எதிர்பார்ப்பு ஆரம்பத்தில் 1 க்கும் குறைவாக இருப்பதால் (முன்பு காட்டப்பட்டுள்ளபடி), நிபந்தனை எதிர்பார்ப்பு 1 க்கும் குறைவாக இருப்பதை வழிமுறை உறுதி செய்கிறது. தோல்வியின் நிபந்தனைக்குட்பட்ட நிகழ்தகவு அதிகபட்சமாக நிபந்தனைக்குட்பட்ட எதிர்பார்ப்பாக இருப்பதால், இந்த வழியில் வழிமுறை தோல்வியின் நிபந்தனைக்குட்பட்ட நிகழ்தகவு 1 க்கும் குறைவாக இருப்பதை உறுதி செய்கிறது. எனவே, இறுதியில், அனைத்து தேர்வுகளும் தீர்மானிக்கப்படும்போது, வழிமுறை ஒரு வெற்றிகரமான முடிவை அடைகிறது. அதாவது, மேலே உள்ள வழிமுறை எந்தவொரு (பகுதியளவு) தொகுப்பு அட்டையின் குறைந்தபட்ச செலவின் பெரும்பாலான நேரங்களில் ஒரு தொகுப்பு செலவை வழங்குகிறது. குறிப்புகள் மேலே உள்ள எடுத்துக்காட்டில், வழிமுறை ஒரு சீரற்ற மாறியின் நிபந்தனை எதிர்பார்ப்பால் வழிநடத்தப்பட்டது. சில சந்தர்ப்பங்களில், ஒரு சரியான நிபந்தனை எதிர்பார்ப்புக்கு பதிலாக, சில நிபந்தனை எதிர்பார்ப்புகளில் மேல் வரம்பு (அல்லது சில நேரங்களில் குறைந்த வரம்பு) பயன்படுத்தப்படுகிறது. இது ஒரு அவநம்பிக்கையான மதிப்பீட்டாளர் என்று அழைக்கப்படுகிறது. நிகழ்தகவு முறையின் பிற பயன்பாடுகளுடன் ஒப்பீடு சீரற்ற ரவுண்டிங் படி இரண்டு விஷயங்களில் நிகழ்தகவு முறையின் பெரும்பாலான பயன்பாடுகளிலிருந்து வேறுபடுகிறதுஃ ரவுண்டிங் படியின் கணக்கீட்டு சிக்கலானது முக்கியமானது. இது ஒரு விரதம் மூலம் செயல்படுத்தப்பட வேண்டும் (எ. கா. பல்லுறுப்புக்கோவை நேரம்) வழிமுறை. சீரற்ற பரிசோதனையின் அடிப்படையிலான நிகழ்தகவு விநியோகம் என்பது சிக்கல் நிகழ்வின் தளர்வுக்கான தீர்வின் செயல்பாடாகும். தோராயமான வழிமுறையின் செயல்திறன் உத்தரவாதத்தை நிரூபிக்க இந்த உண்மை முக்கியமானது---அதாவது, எந்தவொரு சிக்கல் நிகழ்வுக்கும், வழிமுறை அந்த குறிப்பிட்ட நிகழ்வுக்கு உகந்த தீர்வை தோராயமாக வழங்கும் ஒரு தீர்வைத் தருகிறது. ஒப்பிடுகையில், ஒருங்கிணைப்பில் நிகழ்தகவு முறையின் பயன்பாடுகள் பொதுவாக கட்டமைப்புகளின் இருப்பைக் காட்டுகின்றன, அதன் அம்சங்கள் உள்ளீட்டின் பிற அளவுருக்களைப் பொறுத்தது. எடுத்துக்காட்டாக, துரானின் தேற்றத்தைக் கருத்தில் கொள்ளுங்கள், இது "சராசரி டிகிரி செங்குத்துகளைக் கொண்ட எந்தவொரு வரைபடமும் குறைந்தபட்சம் ஒரு சுயாதீனமான அளவைக் கொண்டிருக்க வேண்டும்" என்று கூறலாம். (துரானின் தேற்றத்தின் நிகழ்தகவு ஆதாரத்திற்கு இதைப் பார்க்கவும்.) இந்த எல்லை இறுக்கமாக இருக்கும் வரைபடங்கள் இருந்தாலும், அதை விட மிகப் பெரிய சுயாதீன தொகுப்புகளைக் கொண்ட வரைபடங்களும் உள்ளன. எனவே, ஒரு வரைபடத்தில் டுரானின் தேற்றத்தால் காட்டப்படும் சுயாதீன தொகுப்பின் அளவு, பொதுவாக, அந்த வரைபடத்திற்கான அதிகபட்ச சுயாதீன தொகுப்பை விட மிகவும் சிறியதாக இருக்கலாம். நேரியல் நிரலைத் தீர்க்காமல் நிபந்தனைக்குட்பட்ட நிகழ்தகவுகளின் சீரற்ற வட்டத்தின் முறையையும் பார்க்கவும். குறிப்புகள். மேலும் வாசிப்பு வழிமுறைகள் நிகழ்தகவு வாதங்கள்