நெறிமுறையின் யுத்திகள்: ஒரு மதிப்பெண் வினாக்கள், புத்தக வினா விடைகள் மற்றும் குறிப்புகள்

நெறிமுறையின் யுத்திகள் பற்றி

நடுத்தரம் ~90 நிமிடப் படிப்பு

நெறிமுறை (Algorithm) என்பது ஒரு கணக்கைத் தீர்க்கும் வரையறுக்கப்பட்ட படிகளின் தொகுப்பு. இது எந்த ஒரு நிரலாக்க மொழியையும் சாராமல் எழுதப்படுகிறது. மொழியைச் சாராததால், ஒரு வரி குறிமுறை எழுதும் முன்பே அது சரியானதா, எவ்வளவு வேகமாக இயங்கும் என்று சோதிக்கலாம். அதே நெறிமுறையை ஒரு குறிப்பிட்ட மொழியில் எழுதினால் அது நிரல் (Program).

பாடம் முழுவதும் இரண்டு கேள்விகள் வருகின்றன: நெறிமுறை எவ்வளவு நேரம் எடுக்கிறது? அதற்கு எவ்வளவு நினைவகம் தேவை? இவற்றுக்கு விடை காணும் கருவிகளை (சிக்கலான தன்மை, அணுகுமுறைக் குறியீடுகள்) பாடம் தருகிறது. பிறகு அவற்றை உண்மையான தேடல், வரிசையாக்க முறைகளில் பயன்படுத்துகிறது. வரிசைப்படுத்திய லிஸ்டில் இருமத் தேடல் ஏன் நேரியல் தேடலை விட வேகமானது, ஒரு முறை நேரத்தைச் சேமிக்க ஏன் அதிக நினைவகத்தைப் பயன்படுத்தலாம் என்பதை இதனால் பார்க்கலாம்.

தேர்வில் ஒரு சிறிய லிஸ்டில் நெறிமுறையைப் படிப்படியாகச் செய்து காட்டச் சொல்வார்கள்: இருமத் தேடலின் ஒவ்வொரு படியிலும் mid மதிப்பைக் கண்டுபிடிப்பது, குமிழி வரிசையாக்கத்தின் ஒவ்வொரு சுற்றுக்குப் பிறகும் லிஸ்டைக் காட்டுவது போன்றவை. 8 முதல் 10 எண்கள் கொண்ட லிஸ்டில் கையால் இவற்றைப் பயிற்சி செய்யுங்கள். ஒவ்வொரு அணுகுமுறைக் குறியீடும் எதைக் குறிக்கிறது, நினைவிருத்தல் என்றால் என்ன என்பதையும் படியுங்கள்.

நீங்கள் கற்பவை

• நெறிமுறையின் பண்புகளைப் பட்டியலிட்டு, நெறிமுறையையும் நிரலையும் வேறுபடுத்துதல்.
• நேரச் சிக்கலான தன்மை, இடச் சிக்கலான தன்மை, இட-நேர பரிமாற்றம் ஆகியவற்றை விளக்குதல்.
• Big O, Big Omega, Big Theta ஒவ்வொன்றும் எதைக் குறிக்கிறது என்று கூறுதல்.
• கொடுக்கப்பட்ட லிஸ்டில் நேரியல் தேடலையும் இருமத் தேடலையும் படிப்படியாகச் செய்து, ஒவ்வொரு படியிலும் mid மதிப்பைக் காட்டுதல்.
• குமிழி, தேர்ந்தெடுப்பு, செருகும் வரிசையாக்கங்களின் ஒவ்வொரு சுற்றுக்குப் பிறகும் லிஸ்டைக் காட்டுதல்.
• ஃபிபனாசி தொடரைக் கொண்டு இயங்கு நிரலாக்கத்தையும் நினைவிருத்தலையும் விளக்குதல்.

தொடங்குவதற்கு முன்

• மாறிகள், தரவு வகைகள், நிபந்தனைக் கூற்றுகள்.
• மடக்குகள், லிஸ்ட் மற்றும் அணி போன்ற எளிய தொகுப்புகள்.

நெறிமுறையின் யுத்திகள் — விரிவான விளக்கம்

நெறிமுறையின் யுத்திகள்: அலகு 4 இன் முக்கியக் கருத்துகள்

நெறிமுறையின் பண்புகள்

நெறிமுறை என்பது ஒரு குறிப்பிட்ட பணியைச் செய்வதற்கான வரையறுக்கப்பட்ட கட்டளைகளின் தொகுப்பு. பாடநூல் அதன் பண்புகளைப் பட்டியலிடுகிறது: உள்ளீடு, வெளியீடு, முடிவுறு தன்மை (வரையறுக்கப்பட்ட படிகளுக்குப் பிறகு முடிய வேண்டும்), தெளிவுத் தன்மை (ஒவ்வொரு படியும் தெளிவாக, இருபொருள் இன்றி இருக்க வேண்டும்), செயல்திறன், சரித்தன்மை, எளிமை, சாத்தியத்தன்மை, பெயர்வுத்திறன், எந்த நிரலாக்க மொழியையும் இயக்க அமைப்பையும் சாராத தன்மை.

சிக்கலான தன்மையும் பகுப்பாய்வும்

ஒரு நெறிமுறை அது பயன்படுத்தும் நேரத்தையும் இடத்தையும் கொண்டு மதிப்பிடப்படுகிறது. நேரச் சிக்கலான தன்மை (Time Complexity) என்பது பணியை முடிக்க எடுக்கும் படிகளின் எண்ணிக்கை. இடச் சிக்கலான தன்மை (Space Complexity) என்பது தேவையான நினைவகம். இதில் நிலையான பகுதி (குறிமுறை, எளிய மாறிகள், மாறிலிகளுக்கு) மற்றும் உள்ளீட்டைப் பொறுத்து மாறும் மாறும் பகுதி என இரண்டு உண்டு. பகுப்பாய்வு இரண்டு வழிகளில் செய்யப்படுகிறது. முன்னறி மதிப்பீடுகள் (A priori estimates) என்பது செயலி வேகம் போன்ற காரணிகளை மாறிலியாகக் கொள்ளும் கோட்பாட்டுப் பகுப்பாய்வு. பின்னறி சோதனை (A posteriori testing) என்பது அளவீடு: நெறிமுறையை இயக்கி, இயங்கும் நேரம், பயன்படுத்திய நினைவகம் போன்ற உண்மையான புள்ளிவிவரங்கள் சேகரிக்கப்படுகின்றன.

இட-நேர பரிமாற்றம் (Space-Time Tradeoff) என்பது அதிக நினைவகத்தைப் பயன்படுத்திக் குறைந்த நேரத்தில் கணக்கைத் தீர்ப்பது, அல்லது நீண்ட நேரம் எடுத்துக்கொண்டு மிகக் குறைந்த நினைவகத்தில் தீர்ப்பது.

அணுகுமுறைக் குறியீடுகள்

உள்ளீட்டின் அளவு அதிகரிக்கும்போது இயங்கும் நேரம் எப்படி வளர்கிறது என்பதை இந்தக் குறியீடுகள் (Asymptotic Notations) விவரிக்கின்றன. Big O மோசமான நிலையை, அதாவது மேல் எல்லையைக் குறிக்கிறது. Big Omega (Ω) Big O வுக்கு எதிரானது; கீழ் எல்லையை, அதாவது சிறந்த நிலையைக் குறிக்கிறது. கீழ் எல்லையும் மேல் எல்லையும் ஒன்றாக இருக்கும்போது Big Theta (Θ) பயன்படுகிறது: O(n log n) ஆகவும் Ω(n log n) ஆகவும் உள்ள நெறிமுறை Θ(n log n) ஆகும். எனவே சிறந்த நிலையிலும் மோசமான நிலையிலும் அதன் இயங்கும் நேரம் எப்போதும் n log n போலவே வளரும்.

தேடல்

நேரியல் தேடல் (Linear Search) அல்லது வரிசைமுறைத் தேடல், மதிப்பு கிடைக்கும் வரை அல்லது லிஸ்ட் முடியும் வரை ஒவ்வொரு உறுப்பையும் ஒன்றன்பின் ஒன்றாகச் சோதிக்கிறது. லிஸ்ட் வரிசைப்படுத்தப்பட்டிருக்க வேண்டியதில்லை; மோசமான நிலை O(n). இருமத் தேடல் (Binary Search) அல்லது பாதி-இடைவெளித் தேடல், வரிசைப்படுத்திய அணியில் மட்டுமே வேலை செய்யும். அது mid = low + (high - low) / 2 மூலம் நடு உறுப்பைக் கண்டுபிடிக்கிறது. தேடும் மதிப்பு நடு மதிப்பை விடப் பெரியது என்றால் low = mid + 1; சிறியது என்றால் high = mid - 1. ஒவ்வொரு படியும் தேடும் பகுதியைப் பாதியாக்குவதால் O(log n) ஒப்பீடுகள் போதும். இருமத் தேடல் பிரித்து வெல்லும் (divide and conquer) அணுகுமுறையைப் பின்பற்றுகிறது.

வரிசையாக்கம்

குமிழி வரிசையாக்கம் (Bubble Sort) அடுத்தடுத்த உறுப்புகளின் ஒவ்வொரு இணையையும் ஒப்பிட்டு, தவறான வரிசையில் இருந்தால் இடம் மாற்றுகிறது. இடமாற்றம் தேவைப்படாத வரை சுற்றுகளைத் திரும்பச் செய்கிறது. தேர்ந்தெடுப்பு வரிசையாக்கம் (Selection Sort) வரிசைப்படுத்தாத பகுதியில் மிகச் சிறிய உறுப்பைக் கண்டுபிடித்து, அந்தப் பகுதியின் முதல் உறுப்புடன் இடம் மாற்றுகிறது. செருகும் வரிசையாக்கம் (Insertion Sort) அடுத்த உறுப்பை எடுத்து அதன் சரியான இடத்தில் செருகி, ஒவ்வொரு உறுப்பாக வரிசைப்படுத்திய பகுதியை உருவாக்குகிறது.

இயங்கு நிரலாக்கம்

ஒரு கணக்கை ஒன்றுக்கொன்று மேற்பொருந்தும் சிறிய துணைக் கணக்குகளாகப் பிரிக்க முடியும்போது இயங்கு நிரலாக்கம் (Dynamic Programming) பயன்படுகிறது. இல்லையென்றால் அதே துணைக் கணக்கு பலமுறை தீர்க்கப்படும். ஒவ்வொரு துணைக் கணக்கின் விடையும் சேமிக்கப்பட்டு மீண்டும் பயன்படுத்தப்படுகிறது. இவ்வாறு சேமிப்பது நினைவிருத்தல் (Memoization) எனப்படும்: அதிகச் செலவான செயற்கூறு அழைப்புகளின் விடைகள் சேமிக்கப்பட்டு, அதே உள்ளீடுகள் மீண்டும் வரும்போது நேரடியாகத் தரப்படுகின்றன. பாடநூலின் எடுத்துக்காட்டு ஃபிபனாசி தொடர்; ஏனெனில் fib(5) க்கு fib(3) ஒருமுறைக்கு மேல் தேவைப்படுகிறது.

தவிர்க்க வேண்டிய பொதுவான தவறுகள்

• குறியீடுகளின் பொருளை மாற்றிச் சொல்லுதல். Big O மேல் எல்லை (மோசமான நிலை); Big Omega கீழ் எல்லை (சிறந்த நிலை).
• Big Theta வை சராசரி நிலை என்று சொல்லுதல். Big Theta என்றால் மேல் எல்லையும் கீழ் எல்லையும் ஒன்று; எனவே சிறந்த நிலையிலும் மோசமான நிலையிலும் வளர்ச்சி வீதம் ஒன்றே.
• வரிசைப்படுத்தாத லிஸ்டில் இருமத் தேடல் செய்தல். அணி முதலில் வரிசைப்படுத்தப்பட்டிருந்தால் மட்டுமே இருமத் தேடல் வேலை செய்யும்; இல்லையென்றால் நேரியல் தேடலைப் பயன்படுத்துங்கள்.
• இருமத் தேடலைப் படிப்படியாகச் செய்யும்போது low அல்லது high ஐ mid + 1 அல்லது mid - 1 ஆக மாற்றாமல் mid ஆகவே மாற்றுதல். நடு உறுப்பு ஏற்கனவே சோதிக்கப்பட்டுவிட்டது; எனவே அதை விலக்க வேண்டும்.

இவற்றை பயிற்சித் தேர்வு மூலம் சோதித்துப் பாருங்கள்; பிறகு விடையுடன் கூடிய வினாக்கள் பகுதியில் விரிவான விளக்கத்தைப் படியுங்கள்.

அடிக்கடி கேட்கப்படும் கேள்விகள்

நெறிமுறைக்கும் நிரலுக்கும் என்ன வேறுபாடு?

நெறிமுறை என்பது எந்த நிரலாக்க மொழியையும் சாராமல் எழுதப்படும், கணக்கைத் தீர்க்கும் படிப்படியான முறை. நிரல் என்பது அதே நெறிமுறையை ஒரு குறிப்பிட்ட மொழியின் இலக்கணப்படி, கணினி இயக்கக்கூடிய வகையில் எழுதியது.

இருமத் தேடல் நேரியல் தேடலை விட ஏன் வேகமானது?

நேரியல் தேடல் ஒவ்வொரு உறுப்பையும் சோதிக்க நேரலாம்; n உறுப்புகளுக்கு n ஒப்பீடுகள் வரை ஆகும், அதாவது O(n). இருமத் தேடல் வரிசைப்படுத்திய அணியை ஒவ்வொரு படியிலும் பாதியாக்குகிறது; 1000 உறுப்புகள் கொண்ட லிஸ்டுக்குச் சுமார் 10 ஒப்பீடுகளே போதும், அதாவது O(log n). ஆனால் அணி வரிசைப்படுத்தப்பட்டிருக்க வேண்டும்.

இட-நேர பரிமாற்றம் என்றால் என்ன?

நேரத்துக்கும் நினைவகத்துக்கும் இடையே தேர்வு செய்வது. நினைவிருத்தல் செய்வது போலக் கூடுதல் தரவை நினைவகத்தில் சேமித்து நெறிமுறையை வேகமாக இயங்க வைக்கலாம்; அல்லது மிகக் குறைந்த நினைவகத்தைப் பயன்படுத்தி நீண்ட இயங்கும் நேரத்தை ஏற்கலாம்.

அணுகுமுறைக் குறியீடுகள் நமக்கு என்ன சொல்கின்றன?

உள்ளீட்டின் அளவுடன் நெறிமுறையின் இயங்கும் நேரம் எப்படி வளர்கிறது என்பதை அவை விவரிக்கின்றன. Big O மேல் எல்லையை (மோசமான நிலை), Big Omega கீழ் எல்லையை (சிறந்த நிலை) தருகின்றன. இரண்டு எல்லைகளும் ஒன்றாக இருக்கும்போது Big Theta பயன்படுகிறது; எ.கா. O(n log n) ஆகவும் Ω(n log n) ஆகவும் உள்ள நெறிமுறை.

நினைவிருத்தல் என்றால் என்ன?

நினைவிருத்தல் என்பது அதிகச் செலவான செயற்கூறு அழைப்புகளின் விடைகளைச் சேமிக்கும் உகப்பாக்க நுட்பம். அதே உள்ளீடுகளுடன் செயற்கூறு மீண்டும் அழைக்கப்படும்போது, மறுபடி கணக்கிடாமல் சேமித்த விடை தரப்படுகிறது. இயங்கு நிரலாக்கத்தைத் திறனுள்ளதாக்குவது இதுவே.

இயங்கு நிரலாக்கம் பிரித்து வெல்லும் முறையிலிருந்து எப்படி வேறுபடுகிறது?

இரண்டும் கணக்கைச் சிறிய துணைக் கணக்குகளாகப் பிரிக்கின்றன. இருமத் தேடல் போன்ற பிரித்து வெல்லும் முறையில் துணைக் கணக்குகள் தனித்தனியானவை. இயங்கு நிரலாக்கத்தில் துணைக் கணக்குகள் மேற்பொருந்துகின்றன; எனவே ஃபிபனாசி தொடரில் போல, அவற்றின் விடைகள் மீண்டும் தீர்க்கப்படாமல் சேமிக்கப்பட்டு மீண்டும் பயன்படுத்தப்படுகின்றன.