படிமுறைத் தீர்வு

படிமுறைத் தீர்வு (algorithm, அல்கோரிதம்) என்பது ஒரு தீர்வுமுறை. இது பொதுவாக ஒரு கேள்விக்கான விடையை அடைய, ஒரு திட்டத்துடன், முறைவகுத்து, படிப்படியாய், ஆனால் முடிவுடைய படிகளுடன்,நன்கு வரையறுக்கப்பட்ட குறியீட்டு மொழியில், கணிதச் சார்புகளுக்குத்  தீர்வு காணும் வழிமுறை ஆகும்."Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987:2)."an algorithm is a procedure for computing a function (with respect to some chosen notation for integers) ... this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1).

கணிதவியலிலும் கணினி அறிவியலிலும் அல்கோரிதம் ( ) என்பது நிறைவேற்ற வேண்டிய செயல்களின் தன்னிறைவான வரிசைமுறை ஆகும். அல்கோரிதம் கணக்கிடுதல், தரவு கையாளுதல், தன்னியக்கமாகச் சிந்தித்தல் ஆகிய எப்பணியையும் நிறைவேற்றலாம்.

தொடக்கநிலையில் இருந்தும் தொடக்க உள்ளீட்டில் இருந்தும் (ஒருவேளை வெற்றுச்சர நிலையில் இருந்தும் கூட)"An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973:5). கட்டளைகள் கணித்தலை விவரிக்கின்றன. இவை செயல்படுத்தப்படும்போது, வரம்புள்ள"A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'" (Knuth 1973:5). நன்கு வரையறுத்த எண்ணிக்கை கொண்ட தொடர்படிநிலைகளில் தொடர்ந்து செயல்பட, முடிவில் "வெளியீடு" பெறப்படுகிறது"An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5). இச்செயல்பாடு இறுதி முடியும் நிலையில் முற்றுகிறது. ஒருநிலையில் இருந்து மற்றொரு நிலைக்கன பெயர்வு கட்டாயமாக முந்தீர்மானீப்புத் தனமையோடு அமையவேண்டும் என்பதில்லை; தற்போக்கு அல்கோரிதவகைச் சார்ந்த சில அல்கோரிதங்கள் தற்போக்கிலான உள்ளீட்டைப் பயன்படுதுகின்றன.Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices . . . carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2.

அல்கோரிதம் எனும் கருத்தினம் பல நூற்றாண்டுகளாகவே நிலவியதே, என்றாலும் நிகழ்காலப் பொருளில் ஓரளவுக்கு அல்கோரிதம் சொல்லின் வழக்கு 1928 இல் டேவிடு இல்பெர்ட் முடிவெடுப்புச் சிக்கலுக்கான தீர்வைக் காண முயற்சிகள் மேற்கொண்டபோது தொடங்கியது எனலாம். பிந்தைய முறைப்படுத்தல் முயற்சிகள் "விளைவுமிகு கணக்கீட்டுதிறம்"Kleene 1943 in Davis 1965:274 அல்லது "விளைவுமிகு முறை" யை வரையறுக்க முயலுகையில் உருவாகின;Rosser 1939 in Davis 1965:225 இம்முறைப்படுத்தல் முயற்சிகளில் கியோதெல்- எர்பிரேண்டு–கிளீன்  மீள்சுழல் சார்புகளும்  (1930, 1934 , 1935) அலஞ்சோ சர்ச்சு அவர்களின் இலாம்டா கலனவியல் (1936) முயற்சியும் எமில் போசுட்டு அவர்களின் "உருவாக்கம் 1" (1936) சார்ந்த முயற்சியும் ஆலன் டூரிங் அவர்களின் டூரிங் எந்திரங்களுக்கான ( 1936–7, 1939) முயற்சிகளும் அடங்கும். அல்கோரிதங்களுக்கு நாம் கருதுவதற்கு நிகரான குறியீட்டு வறையரையை உருவாக்குவது இன்னமும் அறைகூவலான பணியாகவே உள்ளது.

வரலாறு

அல்கோரிதம் என்னும் பெயர் 9 ஆவது நூற்றாண்டைச் சேர்ந்த அல் குவாரிழ்சிமி (al-Khwarizmi) அல்லது அல் கோவாரிழ்சிமி (Al-Khowarizmi) என்னும் பெயருடைய ஈரானிய கணிதவியலாளர் எழுதிய "இந்துக்களின் கணக்கிடும் கலை பற்றி அல்-குவாரிழ்சிமி" என்னும் பொருள் படும் நூலின் இலத்தீன் மொழிபெயர்ப்பு நூலாகிய "Algoritmi de numero Indorum" (ஆல்கரித்மி டி நுமரோ இந்தோரம்) என்னும் நூலின் தலைப்பில் இருந்து பெற்ற algorismus  (அல்கோரிஸ்மஸ்) என்ற இலத்தினச் சொல்லில் இருந்தும்  கிரேக்கச் சொல்லாகிய அரித்மோஸ்,( αριθμός) அதாவது "எண்" எனும் பொருள் உடைய சொல்லில் இருந்தும்  பெறப்பட்டது. ஆங்கிலத்திலிச்சொல் முதலில் 1230 இலும் பின் சாசரால்1391 இலும் கையாளப்பட்டுள்ளது. ஆங்கிலச் சொல் பிரெஞ்சுச் சொல்லில் இருந்து பெறப்பட்டதாகும். இந்த ஆங்கிலச் சொல்லுக்கு இப்போதைய பொருள் 19 ஆம் நூற்றாண்டில் தான் உருவாகியது.

மற்றொரு மிகப்பழைய பயன்பாடு 1240 இல்  Carmen de Algorismo எனும் தலைப்புள்ள கையேட்டில் வருகிறது. இக்கையேடு அலெக்சாந்திரே தெ வில்லெடியூ என்பவரால் இயற்றப்பட்டது. அது பின்வருமாறு தொடங்குகிறது:

இதன் மொழிபெயர்ப்பு பின்வருமாறு:

இந்தக் கவிதை சில நூறு அடிகள் கொண்டது. இது இந்தியத் தாயங்களைக் கொண்டு அல்லது இந்திய எண்களைக் கொண்டு புதிய முறையில் கணக்கிடும் கலையைச் சுருக்கமாக்க் கூறுகிறது.

வரையறை

 முறைசாரா வரையறை 
முறைசாரா வரையறையாக, " அல்கோரிதம் என்பது செயல்முறைகளின் வரிசைமுறையை துல்லியமாக வரையறுக்கும் விதிகளின் கணமாகும்." என வரையறுக்கலாம்.Stone 1973:4 எனவே இதில் அனைத்துக் கணினி நிரல்களும், எண்கணக்கீடு இல்லாதவையுங்கூட, அடங்கும். பொதுவாக, குறிப்பிட்ட வரம்புள்ள படிநிலைகளில் முடிவுறும் நிரல் எதுவுமே அல்கோரிதமே.Stone simply requires that "it must terminate in a finite number of steps" (Stone 1973:7–8).

அல்கோரிதத்துக்கான முன்வடிவமாக, இரு முற்றெண்களுக்கான பெருமப் பொது ஈவைக் காணும்  யூக்கிளிடின் அல்கோரிதத்தைக் கூறலாம்; எடுத்துகாட்டு முகப்பில் உள்ள பாய்வுப்படத்தில் விவரிக்கப்பட்டுள்ளது. பின்வரு பிரிவொன்றில் இது எடுத்துகாட்டகப் பயன்படுத்தப்பட்டுள்ளது.

பூல்சு (1974), செஃப்ரி (1999) ஆகிய இருவரின் ஆய்வு, பின்வருமாறு ஒரு முறைசாரா வரையறையைத் தருகிறது:

 எண்ணமுடியாத அளவுள்ள ஈறிலிக் கணத்தின் அனைத்து உறுப்பினர்களின் பெயர்களையும் ஒன்றன் பின் ஒன்றாக ஏதாவதொரு குறிவடிவில் எந்தவொரு மாந்தனாலும் வேகமாக அல்லது நீளமாக அல்லத் குறுகிய வடிவில் (அதாவது, மூலக்கூறிலோ, அனுக்களிலோ, மின்னன்களிலோ )எழுத முடியாது. ஆனால், மாந்தர்சில எண்ணவியலாத ஈறிக் கணங்களைப் பொறுத்தமட்டில், அதற்குச் சமமான பயனுள்ளதைச் செய்யமுடியும்: அந்தக் கணத்தின் n ஆம் உறுப்பினரைத் தீர்மானிக்கும் வெளிப்படையான கட்டளைகளை எந்தவொரு n மதிப்புக்கும் தரமுடியும். இந்தக் கட்டளைகள் எந்திரமோ அல்லது எளிய எண்முறை அல்லது குறிய்யிடு சார்ந்த கணிதவினைகள் மட்டுமே அறிந்தவரும் புரிந்து கொள்ளும்படி வெளிப்படையாக அமைதல் வேண்டும்.''Boolos and Jeffrey 1974,1999:19

 முறைமையாக்கம் அல்லது குறியீட்டாக்கம் 

கணினி தரவுகளைக் கையாள அல்கோரிதங்கள் கட்டாயமாக தேவைப்படுகின்றன. கணினி நிரல்கள் அனைத்தும் அல்கோரிதங்களால் ஆனவையே. இந்த அல்கோரிதங்கள் கணினி செயல்படுத்த வேண்டிய குறிப்பிட்ட பணிகளைக் குறிப்பிட்டமுறையில் நிறைவேற்றுவதற்கான கட்டளைகளை விவரிக்கின்றன. இப்பணிகள் பணியாளர்களின் சம்பளச் சரிபார்த்தலாகவோ மாணவர்களின் மதிப்பெண் அட்டைகளைச் சரிபார்த்தலாகவோ அமையலாம். எனவே, அல்கோரித்த்தைடூரிங் எந்திரத்தால் ஒப்புருவாக்க வல்ல செயல்களின் வரிசையாகக் கருதலாம். இக்கருத்துநிலையை மின்சுகியும் (1967) சேவேஜும் குருவேவிச்சும் (2000) உறுதிப்படுத்துகின்றனர்:

அல்கோரிதம் பற்றிய மாற்று கருத்துப்படிமங்களைப் புரிந்துகொள்ள சார்பு நிரல்மொழியாக்கம், ஏரண நிரல்மொழியாக்கம் கட்டுரைகளைக் கானலாம்.

 அல்கோரிதங்களின் உரைக்கோவை 

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

பயன்பாடு
படிமுறைத் தீர்வு முறையை அடிப்படைக் கணிதப் பாடங்களிளில் பயிற்றுவிப்பது வழக்கம் என்றாலும், இப்பெயரைத் தொடக்க நிலைகளில் ஆள்வதில்லை. அடிப்படை எண் கணிதத்தில் கூட்டல், கழித்தல், பெருக்கல், வகுத்தல் என்னும் செயற்பாடுகளை படிகளாகக் கொண்டு எண்கணிதக் கேள்விகளுக்குத் தீர்வு காண்பது பலரும் அறிந்தது. எடுத்துக்காட்டாக 253 என்னும் ஓர் எண்ணை 5 ஆல் வகுத்தால் மீதி எவ்வளவு, ஈவு எவ்வளவு என்னும் ஒரு கேள்வியை எடுத்துக்கொள்வோம். அல்கோரிதம் என்னும் படிநிலைத் தீர்முறைப்படி, முதலில் 5 ஐ 253 இல் இருந்து கழிப்போம். மீதம் இருக்கும் எண்ணாகிய, 248 ஐ (253 -5 = 248) 5 ஐ விட பெரியதாக இருந்தால், மீண்டும் ஒரு முறை மீதம் இருக்கும் எண்ணில் இருந்து 5 ஐக் கழிப்போம். என்று இப்படியாக, மீதம் இருக்கும் எண்ணில் இருந்து கழித்துக்கொண்டே வந்தால் (முடிவுடைய எண்ணிக்கையான படிநிலைகளில்) கடைசியில் எஞ்சி இருக்கும் எண் மீதி (மீதி = 3). எத்தனை முறை கழிக்க முடிந்தது என்பது ஈவு (50). இங்கு விரித்துக் கூறிய முறை ஓர் எளிய அல்கோரிதம் ஆகும். வேறு விதமாகக் கூறுவதென்றால், N, b ஆகியவற்றைத் தெரிந்த இயல் எண்கள் என்று கொள்வோம், (எடுத்துக்காட்டாக N = 253, b = 5). இப்பொழுது  என்று எழுத முடியும் என்று எடுத்துக்கொண்டால், தெரியாத A, C என்பனவற்றை, எவ்வாறு கண்டு பிடிப்பது என்பது கேள்வி. இதில் ஒரே ஒரு சமன்பாடு (எடுகோள்)தான் உள்ளது ஆனால் A, C ஆகிய தெரியாத இரண்டு எண்களை (அவை நிலவினால்) இந்த ஆல்கரித முறைவழி பெறுகின்றோம் என்பதனையும் உணர்தல் வேண்டும். இதே போல ஓர் இயல் எண் பகா எண்ணா ? எனக் கண்டுபிடித்தல் போன்ற பற்பல கேள்விகளுக்கும் அல்கோரித முறைகள் உள்ளன. தற்காலக் கணினிகளில் பற்பல தீர்வுகளுக்கும் பல்வேறு வகையான படிநிலைத் தீர்முறைத் முறைகள் வகுக்கப்படுகின்றன. பல சிக்கலான கேள்விகளுக்கு இப்படி படிப்படியாய் கணினிவழி கணக்கிட்டு, ஒப்பிட்டு, முடிவுசெய்து தீர்வு காண்பது பரவலாக பயன்பாட்டில் உள்ள முறை ஆகும். ஆனால் சில கேள்விகளுக்கு முடிவுடைய எண்ணிக்கையான படிநிலைகளில் தீர்வு காண்பது இயலாது. எவ்வகையான கேள்விகளுக்கு இப்படி திட்டமிட்ட, படிநிலைவழி எவற்றுக்கு முறையான தீர்வுகள் கிட்டும், எவற்றுக்குக் கிட்டாது, அவற்றை எவ்வாறு முன்கூட்டியே அறிவது முதலான கேள்விகள் முதன்மையானவை. யூக்கிளிடின் காலத்தில் இருந்தே தீர்வுகாண முடியாத கேள்விகளில் ஒன்றாக இருப்பது, கவராயம் (compass), அளவீடு குறிப்பிடாத ஒரு அளவுகோல்  இவற்றை மட்டும் கொண்டு எவ்வாறு ஒரு கோணத்தை மூன்று சமப் பங்காகப் பங்கிடுவதும் இதேபோல ஒரு குறிப்பிட்ட வட்டத்தின் பரப்பளவைக் கொண்ட கட்டத்தை (சதுரம்) வரைவது எவ்வாறு, என்பன முடிவில்லாதன. டாய்ட்சு கணிதவியலாளர் டேவிடு இல்பேர்ட்டின்  தீர்வுகானவேண்டிய 23 கேள்விகள் என்னும் முன்வைப்பும், ஆங்கிலக் கணிதவியலாளர் அலன் டூரிங்கின் ஆய்வின் பயனாய், படிநிலைத் தீர்முறைப்படி முடிவுபெறாத கேள்விகள் உள்ளன என்னும் முடிவும், குர்த் கியோதலின் நிறுவமுடியாத கேள்விகள் உண்டு எனும் கருதுகோள்களும் படிமுறைத்தீர்வு பற்றிய கேள்விகளில் மிகவும் பெயர்பெற்றவை.

மேலும் காண்க
ஏரணம்

மேற்கோள்கள்


பகுப்பு:கணித ஏரணம்
பகுப்பு:கணினி அறிவியல்
பகுப்பு:சிக்கல் தீர்வு
பகுப்பு:நிரலாக்கம்