EITC/IS/CCTF கம்ப்யூடேஷனல் காம்ப்ளெக்சிட்டி தியரி ஃபண்டமெண்டல்ஸ் என்பது கணினி அறிவியலின் அடிப்படைகளின் தத்துவார்த்த அம்சங்களில் ஐரோப்பிய ஐடி சான்றிதழ் திட்டமாகும், இது இணையத்தில் பரவலாகப் பயன்படுத்தப்படும் கிளாசிக்கல் சமச்சீரற்ற பொது-விசை குறியாக்கவியலின் அடிப்படையாகும்.
EITC/IS/CCTF கம்ப்யூடேஷனல் காம்ப்ளெக்ஸிட்டி தியரி ஃபண்டமெண்டல்ஸின் பாடத்திட்டமானது, கணினி அறிவியலின் அடித்தளங்கள் மற்றும் கணக்கீட்டு மாதிரிகள் அடிப்படைக் கருத்துகளான நிர்ணயம் மற்றும் தீர்மானமற்ற வரையறுக்கப்பட்ட நிலை இயந்திரங்கள், வழக்கமான மொழிகள், சூழல் இல்லாத இலக்கணங்கள் மற்றும் மொழிகளின் கோட்பாடு, ஆட்டோமேட்டா கோட்பாடு, டூரிங் போன்ற அடிப்படைக் கருத்துகளை உள்ளடக்கியது. இந்த EITC சான்றிதழுக்கான குறிப்பாக விரிவான வீடியோ செயற்கையான உள்ளடக்கத்தை உள்ளடக்கிய பின்வரும் கட்டமைப்பிற்குள் அடிப்படை பாதுகாப்பு பயன்பாடுகளுக்கான இயந்திரங்கள், சிக்கல்களைத் தீர்மானித்தல், மறுநிகழ்வு, தர்க்கம் மற்றும் அல்காரிதமிக்ஸ் சிக்கலானது.
ஒரு அல்காரிதத்தின் கணக்கீட்டு சிக்கலானது, அதை இயக்க தேவையான வளங்களின் அளவு. நேரம் மற்றும் நினைவக வளங்கள் சிறப்பு கவனம் செலுத்தப்படுகின்றன. சிக்கலின் சிக்கலானது அதைத் தீர்ப்பதற்கான சிறந்த வழிமுறைகளின் சிக்கலானது என வரையறுக்கப்படுகிறது. அல்காரிதம்களின் பகுப்பாய்வு என்பது வெளிப்படையாக கொடுக்கப்பட்ட அல்காரிதம்களின் சிக்கலான தன்மை பற்றிய ஆய்வு ஆகும், அதேசமயம் கணக்கீட்டு சிக்கலான கோட்பாடு என்பது சிறந்த அறியப்பட்ட அல்காரிதம்களுடன் கூடிய சிக்கல் தீர்வுகளின் சிக்கலான ஆய்வு ஆகும். இரண்டு களங்களும் பின்னிப் பிணைந்துள்ளன, ஏனெனில் ஒரு அல்காரிதத்தின் சிக்கலானது அது தீர்க்கும் சிக்கலின் சிக்கலுக்கு எப்போதும் மேல் தடையாக இருக்கும். மேலும், திறமையான அல்காரிதம்களை உருவாக்கும் போது தீர்க்கப்பட வேண்டிய சிக்கலின் சிக்கலுடன் ஒரு குறிப்பிட்ட அல்காரிதத்தின் சிக்கலான தன்மையை ஒப்பிடுவது அடிக்கடி அவசியம். பெரும்பாலான சூழ்நிலைகளில், சிக்கலின் சிரமம் தொடர்பான ஒரே தகவல், மிகவும் திறமையான அறியப்பட்ட நுட்பங்களின் சிக்கலான தன்மையைக் காட்டிலும் குறைவாக உள்ளது. இதன் விளைவாக, அல்காரிதம் பகுப்பாய்வு மற்றும் சிக்கலான கோட்பாடு ஆகியவற்றுக்கு இடையே நிறைய ஒன்றுடன் ஒன்று உள்ளது.
சிக்கலான கோட்பாடு கணினி அறிவியலுக்கான அடிப்படையாக கணக்கீட்டு மாதிரிகளின் அடித்தளங்களில் மட்டுமல்ல, நவீன நெட்வொர்க்குகளில், குறிப்பாக இணையத்தில் பரவலாகப் பரப்பப்படும் கிளாசிக்கல் சமச்சீரற்ற குறியாக்கவியலின் (பொது-விசை குறியாக்கவியல் என்று அழைக்கப்படும்) அடித்தளங்களிலும் முக்கியமானது. பொது-விசை குறியாக்கம் சில சமச்சீரற்ற கணித சிக்கல்களின் கணக்கீட்டு கடினமான அடிப்படையிலானது, எடுத்துக்காட்டாக, பெரிய எண்களை அதன் முதன்மை காரணிகளாக காரணியாக்குதல் (இந்த செயல்பாடு சிக்கலான கோட்பாடு வகைப்பாட்டில் ஒரு கடினமான பிரச்சனையாகும், ஏனெனில் தீர்க்க திறமையான கிளாசிக்கல் அல்காரிதம்கள் இல்லை. இது சிக்கலின் உள்ளீட்டு அளவை அதிகரிப்பதன் மூலம் அதிவேகமாக இல்லாமல் பல்லுறுப்புக்கோவையாக அளவிடப்படுகிறது, இது அசல் பெரிய எண்ணைக் கொடுக்க அறியப்பட்ட முதன்மைக் காரணிகளைப் பெருக்குவதன் மிக எளிய தலைகீழ் செயல்பாட்டிற்கு முரணானது). பொது-விசை குறியாக்கவியலின் கட்டமைப்பில் இந்த சமச்சீரற்ற தன்மையைப் பயன்படுத்துதல் (பொது விசைக்கு இடையேயான கணக்கீட்டு சமச்சீரற்ற தொடர்பை வரையறுப்பதன் மூலம், இது ஒரு தனிப்பட்ட விசையிலிருந்து எளிதாகக் கணக்கிடப்படலாம், அதே நேரத்தில் தனிப்பட்ட விசையானது பொது விசையிலிருந்து எளிதாக கணினியாக இருக்க முடியாது, ஒருவர் பொதுவில் முடியும் பொது விசையை அறிவித்து, தரவின் சமச்சீரற்ற குறியாக்கத்திற்கு மற்ற தகவல் தொடர்பு பக்கங்களை இயக்கவும், பின்னர் இணைக்கப்பட்ட தனிப்பட்ட விசையுடன் மட்டுமே மறைகுறியாக்க முடியும், மூன்றாம் தரப்பினருக்கு கணக்கீடு செய்ய முடியாது, இதனால் தகவல்தொடர்பு பாதுகாப்பானது).
கணக்கீட்டு சிக்கலான கோட்பாடு முக்கியமாக கணினி அறிவியல் மற்றும் அல்காரிதமிக்ஸ் முன்னோடிகளின் சாதனைகளின் அடிப்படையில் உருவாக்கப்பட்டது, ஆலன் டூரிங் போன்றவர், இரண்டாம் உலகப் போரில் நட்பு நாடுகளை வென்றதில் ஆழமான பங்கைக் கொண்டிருந்த நாஜி ஜெர்மனியின் எனிக்மா மறைக்குறியீட்டை உடைப்பதில் அவரது பணி முக்கியமானது. கிரிப்டோகிராஃபிக் அமைப்புகளை மீறுவதற்கும், பொதுவாக ராணுவ முக்கியத்துவம் வாய்ந்த, மறைகுறியாக்கப்பட்ட தகவல்தொடர்பு உள்ளடக்கங்களை அணுகுவதற்கும், மறைந்திருக்கும் தகவலை வெளிக்கொணர, தரவுகளை பகுப்பாய்வு செய்யும் (முக்கியமாக மறைகுறியாக்கப்பட்ட தகவல்தொடர்பு) கணக்கீட்டு செயல்முறைகளை வகுத்து தானியங்குபடுத்துவதை நோக்கமாகக் கொண்ட குறியாக்க பகுப்பாய்வு பயன்படுத்தப்பட்டது. இது கிரிப்டனாலிசிஸ் ஆகும், இது முதல் நவீன கணினிகளின் வளர்ச்சியை ஊக்குவித்தது (ஆரம்பத்தில் இது குறியீட்டு முறிவின் மூலோபாய இலக்குக்குப் பயன்படுத்தப்பட்டது). பிரிட்டிஷ் கொலோசஸ் (முதல் நவீன மின்னணு மற்றும் நிரல் கணினியாகக் கருதப்படுகிறது) போலந்து "வெடிகுண்டு", எனிக்மா மறைக்குறியீடுகளை உடைப்பதில் உதவுவதற்காக மரியன் ரெஜெவ்ஸ்கி வடிவமைத்த ஒரு மின்னணு கணக்கீட்டு சாதனம், மற்றும் போலந்து உளவுத்துறையால் கிரேட் பிரிட்டனிடம் ஒப்படைக்கப்பட்டது. 1939 இல் ஜெர்மனியால் போலந்து ஆக்கிரமிக்கப்பட்ட பிறகு கைப்பற்றப்பட்ட ஜெர்மன் எனிக்மா குறியாக்க இயந்திரம். இந்த சாதனத்தின் அடிப்படையில் ஆலன் டூரிங் அதன் மேம்பட்ட எண்ணை உருவாக்கி ஜெர்மன் மறைகுறியாக்கப்பட்ட தகவல்தொடர்புகளை வெற்றிகரமாக முறியடித்தார், இது பின்னர் நவீன கணினிகளாக உருவாக்கப்பட்டது.
ஒரு அல்காரிதத்தை இயக்க தேவையான ஆதாரங்களின் அளவு உள்ளீட்டின் அளவைப் பொறுத்து மாறுபடும் என்பதால், சிக்கலானது பொதுவாக f(n) செயல்பாடாக வெளிப்படுத்தப்படுகிறது, இங்கு n என்பது உள்ளீட்டு அளவு மற்றும் f(n) என்பது மோசமான சிக்கலானது ( அளவு n இன் அனைத்து உள்ளீடுகளிலும் தேவைப்படும் வளங்களின் அதிகபட்ச அளவு) அல்லது சராசரி-கேஸ் சிக்கலானது (அளவு n இன் அனைத்து உள்ளீடுகளிலும் உள்ள வளங்களின் சராசரி அளவு). அளவு n இன் உள்ளீட்டில் தேவைப்படும் அடிப்படை செயல்பாடுகளின் எண்ணிக்கை பொதுவாக நேரச் சிக்கலாகக் குறிப்பிடப்படுகிறது, இங்கு அடிப்படை செயல்பாடுகள் ஒரு குறிப்பிட்ட கணினியில் நிலையான நேரத்தை எடுத்துக்கொள்வதாகவும், வேறு கணினியில் இயங்கும் போது நிலையான காரணியால் மட்டுமே மாறுவதாகவும் நம்பப்படுகிறது. அளவு n இன் உள்ளீட்டில் ஒரு அல்காரிதம் தேவைப்படும் நினைவகத்தின் அளவு விண்வெளி சிக்கலானது என அழைக்கப்படுகிறது.
நேரம் என்பது பொதுவாகக் கருதப்படும் வளமாகும். "சிக்கலானது" என்ற சொல் தகுதி இல்லாமல் பயன்படுத்தப்படும் போது, அது பொதுவாக நேரத்தின் சிக்கலைக் குறிக்கிறது.
காலத்தின் பாரம்பரிய அலகுகள் (வினாடிகள், நிமிடங்கள் மற்றும் பல) சிக்கலான கோட்பாட்டில் பயன்படுத்தப்படுவதில்லை, ஏனெனில் அவை தேர்ந்தெடுக்கப்பட்ட கணினி மற்றும் தொழில்நுட்பத்தின் முன்னேற்றத்தை மிகவும் நம்பியுள்ளன. எடுத்துக்காட்டாக, இன்று ஒரு கணினி 1960 களில் இருந்து ஒரு கணினியை விட கணிசமாக விரைவாக ஒரு அல்காரிதத்தை இயக்க முடியும், இருப்பினும், இது அல்காரிதத்தின் உள்ளார்ந்த தரத்தை விட கணினி வன்பொருளில் தொழில்நுட்ப முன்னேற்றங்கள் காரணமாகும். சிக்கலான கோட்பாட்டின் குறிக்கோள், அல்காரிதம்களின் உள்ளார்ந்த நேரத் தேவைகளை அல்லது அல்காரிதம் எந்த கணினியிலும் விதிக்கும் அடிப்படை நேர வரம்புகளை அளவிடுவதாகும். கணக்கீட்டின் போது எத்தனை அடிப்படை செயல்பாடுகள் செய்யப்படுகின்றன என்பதைக் கணக்கிடுவதன் மூலம் இது நிறைவேற்றப்படுகிறது. இந்த நடைமுறைகள் பொதுவாக படிகள் என்று குறிப்பிடப்படுகின்றன, ஏனெனில் அவை ஒரு குறிப்பிட்ட கணினியில் நிலையான நேரத்தை எடுத்துக்கொள்கின்றன (அதாவது, அவை உள்ளீட்டின் அளவு பாதிக்கப்படாது).
மற்றொரு முக்கியமான ஆதாரம், அல்காரிதம்களை செயல்படுத்த தேவையான கணினி நினைவகத்தின் அளவு.
அடிக்கடி பயன்படுத்தப்படும் மற்றொரு ஆதாரம் எண்கணித செயல்பாடுகளின் அளவு. இந்த சூழ்நிலையில், "எண்கணித சிக்கலானது" என்ற சொல் பயன்படுத்தப்படுகிறது. ஒரு கணக்கீட்டின் போது நிகழும் எண்களின் பைனரி பிரதிநிதித்துவத்தின் அளவின் மேல் கட்டுப்பாடு தெரிந்தால், நேர சிக்கலானது பொதுவாக ஒரு நிலையான காரணி மூலம் எண்கணித சிக்கலின் விளைபொருளாகும்.
ஒரு கணக்கீட்டின் போது பயன்படுத்தப்படும் முழு எண்களின் அளவு பல முறைகளுக்கு கட்டுப்படுத்தப்படவில்லை, மேலும் எண்கணித செயல்பாடுகளுக்கு ஒரு குறிப்பிட்ட நேரம் தேவை என்று கருதுவது நம்பத்தகாதது. இதன் விளைவாக, நேர சிக்கலானது, பிட் சிக்கலானது என்றும் அழைக்கப்படுகிறது, இது எண்கணித சிக்கலை விட கணிசமாக அதிகமாக இருக்கலாம். ஒரு nn முழு எண் மேட்ரிக்ஸின் தீர்மானிப்பதைக் கணக்கிடுவதில் உள்ள எண்கணித சிரமம், எடுத்துக்காட்டாக, நிலையான நுட்பங்களுக்கான (காசியன் எலிமினேஷன்) O(n^3) ஆகும். கணக்கீட்டின் போது குணகங்களின் அளவு அதிவேகமாக விரிவடையும் என்பதால், அதே முறைகளின் பிட் சிக்கலானது n இல் அதிவேகமாக உள்ளது. இந்த நுட்பங்கள் மல்டி-மாடுலர் எண்கணிதத்துடன் இணைந்து பயன்படுத்தப்பட்டால், பிட் சிக்கலானது O(n^4) ஆகக் குறைக்கப்படும்.
பிட் சிக்கலானது, முறையான சொற்களில், ஒரு அல்காரிதத்தை இயக்க தேவையான பிட்களின் செயல்பாடுகளின் எண்ணிக்கையைக் குறிக்கிறது. இது பெரும்பாலான கணக்கீட்டு முன்னுதாரணங்களில் ஒரு நிலையான காரணி வரை தற்காலிக சிக்கலான தன்மைக்கு சமம். கணினிகளுக்கு தேவைப்படும் இயந்திர வார்த்தைகளின் செயல்பாடுகளின் எண்ணிக்கை பிட் சிக்கலுக்கு விகிதாசாரமாகும். கணக்கீட்டின் யதார்த்தமான மாதிரிகளுக்கு, நேர சிக்கலானது மற்றும் பிட் சிக்கலானது ஒரே மாதிரியாக இருக்கும்.
வரிசைப்படுத்துதல் மற்றும் தேடுதல் ஆகியவற்றில் பெரும்பாலும் கருதப்படும் ஆதாரம் உள்ளீடுகளின் ஒப்பீடுகளின் அளவு. தரவு நன்கு ஒழுங்கமைக்கப்பட்டிருந்தால், இது நேர சிக்கலின் நல்ல குறிகாட்டியாகும்.
அனைத்து சாத்தியமான உள்ளீடுகளிலும், ஒரு அல்காரிதத்தில் உள்ள படிகளின் எண்ணிக்கையை எண்ணுவது சாத்தியமற்றது. ஒரு உள்ளீட்டின் சிக்கலானது அதன் அளவுடன் உயர்வதால், அது பொதுவாக உள்ளீட்டின் அளவு n (பிட்களில்) செயல்பாடாகக் குறிப்பிடப்படுகிறது, எனவே சிக்கலானது n இன் செயல்பாடாகும். இருப்பினும், அதே அளவிலான உள்ளீடுகளுக்கு, அல்காரிதத்தின் சிக்கலானது கணிசமாக மாறுபடும். இதன் விளைவாக, பல்வேறு சிக்கலான செயல்பாடுகள் வழக்கமாகப் பயன்படுத்தப்படுகின்றன.
மோசமான-நிலை சிக்கலானது என்பது அனைத்து அளவு n உள்ளீடுகளுக்கான அனைத்து சிக்கலான கூட்டுத்தொகையாகும், அதே சமயம் சராசரி-வழக்கு சிக்கலானது அனைத்து அளவு n உள்ளீடுகளுக்கான அனைத்து சிக்கலான கூட்டுத்தொகையாகும் (இது அர்த்தமுள்ளதாக இருக்கிறது, ஏனெனில் கொடுக்கப்பட்ட அளவின் சாத்தியமான உள்ளீடுகளின் எண்ணிக்கை வரையறுக்கப்பட்ட). "சிக்கலானது" என்ற சொல் மேலும் வரையறுக்கப்படாமல் பயன்படுத்தப்படும்போது, மோசமான நேர சிக்கலானது கணக்கில் எடுத்துக்கொள்ளப்படுகிறது.
மோசமான மற்றும் சராசரி-வழக்கு சிக்கலானது சரியாக கணக்கிட கடினமாக உள்ளது. மேலும், இந்த துல்லியமான மதிப்புகள் சிறிய நடைமுறை பயன்பாட்டைக் கொண்டிருக்கின்றன, ஏனெனில் இயந்திரம் அல்லது கணக்கீடு முன்னுதாரணத்தில் ஏதேனும் மாற்றம் சிக்கலில் சிறிது மாறுபடும். மேலும், n இன் சிறிய மதிப்புகளுக்கு வளப் பயன்பாடு முக்கியமல்ல, எனவே சிறிய nக்கான குறைந்த சிக்கலைக் காட்டிலும் செயல்படுத்த எளிதானது.
இந்தக் காரணங்களுக்காக, அதிக nக்கான சிக்கலான நடத்தைக்கு அதிக கவனம் செலுத்தப்படுகிறது, அதாவது n முடிவிலியை நெருங்கும் போது அதன் அறிகுறியற்ற நடத்தை. இதன் விளைவாக, சிக்கலான தன்மையைக் குறிக்க பெரிய O குறியீடு பொதுவாகப் பயன்படுத்தப்படுகிறது.
கணக்கீட்டு மாதிரிகள்
ஒரு கணக்கீட்டு மாதிரியின் தேர்வு, ஒரு யூனிட் நேரத்தில் செய்யப்படும் அத்தியாவசிய செயல்பாடுகளைக் குறிப்பிடுவது, சிக்கலைத் தீர்மானிப்பதில் முக்கியமானது. கணக்கீட்டு முன்னுதாரணம் குறிப்பாக விவரிக்கப்படாதபோது இது சில நேரங்களில் மல்டிடேப் டூரிங் இயந்திரம் என்று குறிப்பிடப்படுகிறது.
கணக்கீட்டின் ஒரு நிர்ணய மாதிரியானது, இயந்திரத்தின் அடுத்தடுத்த நிலைகள் மற்றும் செய்ய வேண்டிய செயல்பாடுகள் முந்தைய நிலையால் முழுமையாக வரையறுக்கப்படும். சுழல்நிலை செயல்பாடுகள், லாம்ப்டா கால்குலஸ் மற்றும் டூரிங் இயந்திரங்கள் ஆகியவை முதல் தீர்மானிக்கும் மாதிரிகள். ரேண்டம்-அணுகல் இயந்திரங்கள் (ரேம்-மெஷின்கள் என்றும் அழைக்கப்படுகின்றன) நிஜ-உலக கணினிகளை உருவகப்படுத்துவதற்கான ஒரு பிரபலமான முன்னுதாரணமாகும்.
கணக்கீட்டு மாதிரி வரையறுக்கப்படாதபோது, மல்டிடேப் ட்யூரிங் இயந்திரம் பொதுவாகக் கருதப்படுகிறது. மல்டிடேப் ட்யூரிங் இயந்திரங்களில், பெரும்பாலான அல்காரிதம்களுக்கான ரேம் மெஷின்களில் இருக்கும் நேரச் சிக்கலானது, நினைவகத்தில் தரவு எவ்வாறு சேமிக்கப்படுகிறது என்பதில் கணிசமான கவனம் தேவைப்பட்டாலும், இந்தச் சமமான நிலையை அடைய வேண்டும்.
கணிப்பீட்டின் சில படிகளில், தீர்மானிக்கப்படாத டூரிங் இயந்திரங்கள் போன்ற, நிர்ணயம் செய்யாத கணினி மாதிரியில் பல்வேறு தேர்வுகள் செய்யப்படலாம். சிக்கலான கோட்பாட்டில், அனைத்து சாத்தியமான விருப்பங்களும் ஒரே நேரத்தில் பரிசீலிக்கப்படுகின்றன, மேலும் தீர்மானிக்கப்படாத நேர சிக்கலானது சிறந்த தேர்வுகள் எப்போதும் செய்யப்படும்போது தேவைப்படும் நேரமாகும். இதை வேறுவிதமாகக் கூறினால், கணக்கீடு தேவையான அளவு (ஒரே மாதிரியான) செயலிகளில் ஒரே நேரத்தில் செய்யப்படுகிறது, மேலும் தீர்மானிக்கப்படாத கணக்கீட்டு நேரம் என்பது கணக்கீட்டை முடிக்க முதல் செயலி எடுக்கும் நேரமாகும். இந்த இணையான தன்மையானது குவாண்டம் கம்ப்யூட்டிங்கில் சிறப்பு குவாண்டம் அல்காரிதம்களை இயக்கும் போது சூப்பர்போஸ் செய்யப்பட்ட சிக்கிய நிலைகளைப் பயன்படுத்துவதன் மூலம் பயன்படுத்தப்படலாம், உதாரணமாக சிறிய முழு எண்களின் ஷோரின் காரணியாக்கம் போன்றது.
அத்தகைய கணக்கீட்டு மாதிரி தற்போது நடைமுறையில் இல்லாவிட்டாலும், அது கோட்பாட்டு முக்கியத்துவம் வாய்ந்தது, குறிப்பாக P = NP சிக்கல் தொடர்பாக, சிக்கலான வகுப்புகள் "பல்நோக்கு நேரம்" மற்றும் "தீர்மானமற்ற பல்லுறுப்புக்கோவை நேரத்தை" குறைந்தபட்சம் மேல் எனப் பயன்படுத்தி உருவாக்கப்படுமா என்று கேட்கிறது. எல்லைகள் ஒன்றே. ஒரு உறுதியான கணினியில், NP-அல்காரிதத்தை உருவகப்படுத்துவதற்கு "அதிவேக நேரம்" தேவைப்படுகிறது. நிர்ணயம் செய்யாத அமைப்பில் ஒரு பணியை பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்க முடிந்தால், அது NP சிரம வகுப்பைச் சேர்ந்தது. ஒரு சிக்கல் NP இல் இருந்தால் மற்றும் வேறு எந்த NP பிரச்சனையையும் விட எளிதாக இல்லை என்றால், அது NP-நிறைவு என்று கூறப்படுகிறது. நாப்சாக் பிரச்சனை, பயண விற்பனையாளர் பிரச்சனை மற்றும் பூலியன் திருப்தித்தன்மை பிரச்சனை அனைத்தும் NP-முழுமையான கூட்டு பிரச்சனைகள். மிகவும் நன்கு அறியப்பட்ட அல்காரிதம் இந்த எல்லா சிக்கல்களுக்கும் அதிவேக சிக்கலைக் கொண்டுள்ளது. இந்தச் சிக்கல்களில் ஏதேனும் ஒன்றைப் பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்கமான இயந்திரத்தில் தீர்க்க முடிந்தால், அனைத்து NP சிக்கல்களும் பல்லுறுப்புக்கோவை நேரத்திலும் தீர்க்கப்படும், மேலும் P = NP நிறுவப்படும். 2017 ஆம் ஆண்டு நிலவரப்படி, P NP, NP சிக்கல்களின் மோசமான சூழ்நிலைகளைத் தீர்ப்பது அடிப்படையில் கடினமானது என்று பரவலாகக் கருதப்படுகிறது, அதாவது, சுவாரஸ்யமான உள்ளீடு நீளம் கொடுக்கப்பட்ட சாத்தியமான கால இடைவெளியை விட (பத்தாண்டுகள்) அதிக நேரம் எடுக்கும்.
இணையான மற்றும் விநியோகிக்கப்பட்ட கணினி
இணையான மற்றும் விநியோகிக்கப்பட்ட கம்ப்யூட்டிங் என்பது ஒரே நேரத்தில் செயல்படும் பல செயலிகளில் செயலாக்கத்தைப் பிரிப்பதை உள்ளடக்கியது. பல்வேறு மாதிரிகள் இடையே உள்ள அடிப்படை வேறுபாடு செயலிகளுக்கு இடையே தரவுகளை அனுப்பும் முறையாகும். செயலிகளுக்கிடையேயான தரவு பரிமாற்றம் பொதுவாக இணையான கணினியில் மிக விரைவாக இருக்கும், அதேசமயம் விநியோகிக்கப்பட்ட கணினியில் செயலிகளுக்கு இடையேயான தரவு பரிமாற்றம் நெட்வொர்க் முழுவதும் செய்யப்படுகிறது, இதனால் கணிசமாக மெதுவாக இருக்கும்.
N செயலிகளில் ஒரு கணக்கீடு ஒரு செயலியில் எடுக்கும் நேரத்தின் குறைந்தபட்சம் N ஆல் அளவை எடுக்கும். உண்மையில், சில துணைப் பணிகளை இணையாகச் செய்ய முடியாது மற்றும் சில செயலிகள் மற்றொரு செயலியின் முடிவுக்காகக் காத்திருக்க வேண்டியிருக்கும் என்பதால், இந்த கோட்பாட்டளவில் சிறந்த பிணைப்பு ஒருபோதும் அடையப்படாது.
ஒரு செயலியில் ஒரே கணக்கீட்டைச் செய்வதற்குத் தேவைப்படும் நேரத்திற்கு முடிந்தவரை, செயலிகளின் எண்ணிக்கையின் மூலம் நேரத்தைக் கணக்கிடும் தயாரிப்பு, அல்காரிதம்களை உருவாக்குவதே முக்கிய சிக்கலான சிக்கலாகும்.
குவாண்டம் கணக்கீடு
குவாண்டம் கணினி என்பது குவாண்டம் இயக்கவியல் அடிப்படையிலான கணக்கீட்டு மாதிரியைக் கொண்ட கணினி ஆகும். சர்ச்-டூரிங் ஆய்வறிக்கை குவாண்டம் கணினிகளுக்கு உண்மையாக உள்ளது, இது குவாண்டம் கணினியால் தீர்க்கக்கூடிய எந்தவொரு சிக்கலையும் டூரிங் இயந்திரம் மூலம் தீர்க்க முடியும் என்பதைக் குறிக்கிறது. இருப்பினும், சில பணிகள் கோட்பாட்டளவில் ஒரு குவாண்டம் கம்ப்யூட்டரைப் பயன்படுத்தி தீர்க்கப்படக் கூடும். ஒரு நடைமுறை குவாண்டம் கணினியை எவ்வாறு உருவாக்குவது என்பது யாருக்கும் தெரியாததால், தற்போதைக்கு, இது கண்டிப்பாக கோட்பாட்டு ரீதியானது.
குவாண்டம் கம்ப்யூட்டர்களால் தீர்க்கப்படக்கூடிய பல்வேறு வகையான சிக்கல்களை ஆராய குவாண்டம் சிக்கலான கோட்பாடு உருவாக்கப்பட்டது. குவாண்டம் கணினி தாக்குதல்களுக்கு எதிர்ப்புத் தெரிவிக்கும் கிரிப்டோகிராஃபிக் நெறிமுறைகளை உருவாக்கும் செயல்முறையான பிந்தைய குவாண்டம் கிரிப்டோகிராஃபியில் இது பயன்படுத்தப்படுகிறது.
சிக்கலின் சிக்கலான தன்மை (குறைந்த வரம்புகள்)
கண்டுபிடிக்கப்படாத நுட்பங்கள் உட்பட, சிக்கலைத் தீர்க்கக்கூடிய அல்காரிதம்களின் சிக்கலான தன்மை சிக்கலின் சிக்கலானது. இதன் விளைவாக, சிக்கலின் சிக்கலானது அதைத் தீர்க்கும் எந்த வழிமுறையின் சிக்கலுக்கும் சமம்.
இதன் விளைவாக, பெரிய O குறியீட்டில் கொடுக்கப்பட்ட எந்த சிக்கலான தன்மையும் அல்காரிதம் மற்றும் அதனுடன் வரும் சிக்கல் இரண்டின் சிக்கலான தன்மையைக் குறிக்கிறது.
மறுபுறம், சிக்கலின் சிக்கலில் அற்பமான குறைந்த வரம்புகளைப் பெறுவது பெரும்பாலும் கடினம், மேலும் அவ்வாறு செய்வதற்கு சில உத்திகள் உள்ளன.
பெரும்பாலான சிக்கல்களைத் தீர்க்க, அனைத்து உள்ளீட்டுத் தரவையும் படிக்க வேண்டும், இது தரவின் அளவிற்கு விகிதாசார நேரத்தை எடுக்கும். இதன் விளைவாக, இத்தகைய சிக்கல்கள் குறைந்தபட்சம் நேரியல் சிக்கலானது அல்லது பெரிய ஒமேகா குறியீட்டில், Ω(n) இன் சிக்கலானது.
கணினி இயற்கணிதம் மற்றும் கணக்கீட்டு இயற்கணித வடிவியல் போன்ற சில சிக்கல்கள் மிகப் பெரிய தீர்வுகளைக் கொண்டுள்ளன. வெளியீடு எழுதப்பட வேண்டும் என்பதால், சிக்கலானது வெளியீட்டின் அதிகபட்ச அளவைக் கட்டுப்படுத்துகிறது.
வரிசையாக்க அல்காரிதத்திற்கு தேவையான ஒப்பீடுகளின் எண்ணிக்கையானது Ω(nlogn) இன் நேரியல் அல்லாத குறைந்த வரம்பைக் கொண்டுள்ளது. இதன் விளைவாக, சிறந்த வரிசையாக்க வழிமுறைகள் மிகவும் திறமையானவை, ஏனெனில் அவற்றின் சிக்கலானது O(nlogn) ஆகும். n உள்ளன என்பது உண்மை! n விஷயங்களை ஒழுங்கமைப்பதற்கான வழிகள் இந்த குறைந்த வரம்பிற்கு வழிவகுக்கிறது. ஏனெனில் ஒவ்வொரு ஒப்பீடும் n இன் இந்த தொகுப்பை பிரிக்கிறது! ஆர்டர்கள் இரண்டு துண்டுகளாக, அனைத்து ஆர்டர்களையும் வேறுபடுத்துவதற்கு தேவையான N ஒப்பீடுகளின் எண்ணிக்கை 2N > n! ஆக இருக்க வேண்டும், இது ஸ்டிர்லிங்கின் சூத்திரத்தின் மூலம் O(nlogn) ஐக் குறிக்கிறது.
சிக்கலை மற்றொரு சிக்கலாகக் குறைப்பது சிக்கலான கட்டுப்பாடுகளைக் குறைப்பதற்கான பொதுவான உத்தியாகும்.
அல்காரிதம் மேம்பாடு
ஒரு அல்காரிதத்தின் சிக்கலான தன்மையை மதிப்பிடுவது வடிவமைப்பு செயல்பாட்டின் ஒரு முக்கிய அங்கமாகும், ஏனெனில் இது எதிர்பார்க்கப்படும் செயல்திறன் பற்றிய பயனுள்ள தகவலை வழங்குகிறது.
நவீன கணினி சக்தியின் அதிவேக வளர்ச்சியை முன்னறிவிக்கும் மூரின் சட்டத்தின் விளைவாக, அல்காரிதம்களின் சிக்கலான தன்மையை மதிப்பிடுவது குறைவான பொருத்தமாகிவிடும் என்பது அடிக்கடி தவறாகப் புரிந்து கொள்ளப்படுகிறது. இது தவறானது, ஏனெனில் அதிகரித்த சக்தியானது பாரிய அளவிலான தரவுகளை (பெரிய தரவு) செயலாக்க அனுமதிக்கிறது. எடுத்துக்காட்டாக, ஒரு புத்தகத்தின் நூலியல் போன்ற சில நூற்றுக்கணக்கான உள்ளீடுகளின் பட்டியலை அகரவரிசைப்படி வரிசைப்படுத்தும்போது எந்த அல்காரிதமும் ஒரு நொடிக்கும் குறைவான நேரத்தில் நன்றாகச் செயல்பட வேண்டும். மறுபுறம், ஒரு மில்லியன் உள்ளீடுகளுக்கு (உதாரணமாக, ஒரு பெரிய நகரத்தின் தொலைபேசி எண்கள்), O(n2) ஒப்பீடுகள் தேவைப்படும் அடிப்படை அல்காரிதம்கள் ஒரு டிரில்லியன் ஒப்பீடுகளைச் செய்ய வேண்டும், இது 10 வேகத்தில் மூன்று மணிநேரம் எடுக்கும். ஒரு வினாடிக்கு மில்லியன் ஒப்பீடுகள். மறுபுறம், Quicksort மற்றும் merge வரிசைக்கு, nlogn ஒப்பீடுகள் மட்டுமே தேவை (முந்தையவற்றின் சராசரி-வழக்கு சிக்கலானது, பிந்தையவற்றின் மோசமான-நிலை சிக்கலானது). இது n = 30,000,000 க்கு சுமார் 1,000,000 ஒப்பீடுகளை உருவாக்குகிறது, இது ஒரு வினாடிக்கு 3 மில்லியன் ஒப்பீடுகளில் 10 வினாடிகள் மட்டுமே எடுக்கும்.
இதன் விளைவாக, சிக்கலை மதிப்பிடுவது பல திறமையற்ற அல்காரிதம்களை செயல்படுத்துவதற்கு முன் நீக்குவதற்கு அனுமதிக்கலாம். சாத்தியமான அனைத்து மாறுபாடுகளையும் சோதிக்காமல், சிக்கலான அல்காரிதங்களை நன்றாகச் சரிசெய்யவும் இது பயன்படுத்தப்படலாம். சிக்கலான படிமுறையின் மிகவும் விலையுயர்ந்த படிகளைத் தீர்மானிப்பதன் மூலம் செயலாக்கத்தின் செயல்திறனை அதிகரிப்பதற்கான முயற்சியில் கவனம் செலுத்துவதற்கு சிக்கலான ஆய்வு அனுமதிக்கிறது.
சான்றிதழ் பாடத்திட்டத்துடன் உங்களைப் பற்றி விரிவாக அறிந்துகொள்ள, கீழே உள்ள அட்டவணையை விரிவுபடுத்தி பகுப்பாய்வு செய்யலாம்.
EITC/IS/CCTF கணக்கீட்டு சிக்கலான கோட்பாடு அடிப்படைகள் சான்றளிப்பு பாடத்திட்டம் வீடியோ வடிவத்தில் திறந்த அணுகல் செயற்கையான பொருட்களைக் குறிப்பிடுகிறது. கற்றல் செயல்முறை ஒரு படிப்படியான கட்டமைப்பாக (நிரல்கள் -> பாடங்கள் -> தலைப்புகள்) தொடர்புடைய பாடத்திட்ட பகுதிகளை உள்ளடக்கியது. டொமைன் நிபுணர்களுடன் வரம்பற்ற ஆலோசனையும் வழங்கப்படுகிறது.
சான்றிதழின் செயல்முறை பற்றிய விவரங்களுக்கு சரிபார்க்கவும் எப்படி இது செயல்படுகிறது.
முதன்மை ஆதரவு பாடத்திட்ட வாசிப்பு பொருட்கள்
எஸ். அரோரா, பி. பராக், கணக்கீட்டு சிக்கலானது: ஒரு நவீன அணுகுமுறை
https://theory.cs.princeton.edu/complexity/book.pdf
இரண்டாம் நிலை ஆதரவு பாடத்திட்ட வாசிப்பு பொருட்கள்
ஓ. கோல்ட்ரீச், சிக்கலான கோட்பாடு அறிமுகம்:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
தனித்த கணிதத்தில் ஆதரவு பாடத்திட்ட வாசிப்பு பொருட்கள்
ஜே. ஆஸ்ப்னஸ், தனித்த கணிதம் பற்றிய குறிப்புகள்:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
வரைபடக் கோட்பாட்டின் ஆதரவான பாடத்திட்ட வாசிப்புப் பொருட்கள்
ஆர். டீஸ்டல், வரைபடக் கோட்பாடு:
https://diestel-graph-theory.com/
EITC/IS/CCTF கணக்கீட்டு சிக்கலான கோட்பாடு அடிப்படைகள் திட்டத்திற்கான முழுமையான ஆஃப்லைன் சுய-கற்றல் தயாரிப்பு பொருட்களை PDF கோப்பில் பதிவிறக்கவும்
EITC/IS/CCTF ஆயத்த பொருட்கள் - நிலையான பதிப்பு
EITC/IS/CCTF ஆயத்த பொருட்கள் - மறுஆய்வு கேள்விகளுடன் விரிவாக்கப்பட்ட பதிப்பு