Algorithms and Powering Programming, Data Structures and Algorithms English Malayalam

Algorithms and PoweringYouTube↗ IA↗(long shot)
People & Blogs 982 views 4 likes 0 dislikes 30 Jan 2018

Programming, Data Structures and Algorithms 451 subscribers N/A YouTube↗

So, the course is about designing and analyzing algorithms and its instructive to actually

അൽഗോരിതംസ് കോഴ്സിന്റെ ഈ ആദ്യ പ്രഭാഷണത്തിലേക്ക് സ്വാഗതം, ഞാൻ മദ്രാസിലെ ഐഐടിയിൽ നിന്നുള്ള നാരായണസ്വാമിയാണ്. അൽ‌ഗോരിതം (algorithm) രൂപകൽപ്പന ചെയ്യുന്നതും വിശകലനം

ചെയ്യുന്നതും ഒരു അൽ‌ഗോരിതം (algorithm) എന്താണെന്ന് ആരംഭിക്കുന്നതിനുള്ള കോഴ്‌സ് (course) ആണ് ഇത്. എല്ലാ ഇൻ‌പുട്ടുകൾ‌ക്കും (input) അവസാനിക്കുന്ന ഘട്ടങ്ങളുടെ പരിമിത ശ്രേണിയാണ് അൽ‌ഗോരിതം

(algorithm). നമുക്കു അൽ‌ഗോരിതം (algorithm) ശരിയായി അറിയാം. ഒരു വിഭവം പാചകം ചെയ്യുന്നതിനുള്ള ഒരു പാചകക്കുറിപ്പ് ഒരു അൽഗോരിതം (algorithm)

start off with what an algorithm is. Algorithm is a finite sequence of steps that halts on all inputs. We are familiar with algorithms right.

ആണ്. ഗുണനം, 2 സംഖ്യകളെ ഗുണിക്കുന്നതിനുള്ള ഘട്ടങ്ങളുടെ ക്രമം ഒരു അൽഗോരിതം (algorithm)

If you think of it, a recipe to cook a dish is an algorithm.

ശരിയാണ്. ഏതെങ്കിലും പ്രോഗ്രാമിംഗ് (programming) ഭാഷയിൽ എഴുതിയ ഏതെങ്കിലും പ്രോഗ്രാം (program) നോക്കുകയാണെങ്കിൽ, അത് ഒരു അൽഗോരിതം

The multiplication, the sequence of steps to multiply 2 numbers is an algorithm right.

(algorithm) എൻ‌കോഡു (encode) ചെയ്യുന്നു. ഇത് ആവശ്യമാണെന്ന് ഞാൻ പറയുന്നു, കാരണം

And if you look at any program written in any programming language, its desired that

ഇത് പരിമിതമായ ഘട്ടങ്ങളിലൂടെ നിർത്തുന്നുവെന്ന് ഉറപ്പാക്കുന്നത് തികച്ചും വെല്ലുവിളി നിറഞ്ഞ ഒരു വ്യായാമമാണ്, എല്ലാ ഇൻപുട്ടുകളിലും

it encodes an algorithm. I say it is desired, because it is a fairly challenging exercise to ensure that it halts on a finite sequence of steps, halts on finite number of halts in a finite number of steps

(input) പരിമിതമായ ഘട്ടങ്ങളിൽ ഹാൾട്ട് (halt) ചെയ്യുന്നു. ഇപ്പോൾ, ഈ കോഴ്സിൽ (course) നമ്മൾ അഭിസംബോധന ചെയ്യുന്ന ചോദ്യം, എങ്ങനെ അൽഗോരിതം

on all inputs. Now, the question that we address in this course is how do we design algorithms, how

(algorithm) രൂപകൽപ്പന ചെയ്യുന്നു, അൽഗോരിതം (algorithm) ശരിയാണെന്ന് എങ്ങനെ ഉറപ്പാക്കുന്നു, കൂടാതെ പരിമിതമായ

do we ensure that algorithms are correct, and how do we also ensure that it halts on

എണ്ണം ഘട്ടങ്ങളിലുള്ള എല്ലാ ഇൻപുട്ടുകളിലും (input) ഇത് നിർത്തുന്നുവെന്ന് എങ്ങനെ ഉറപ്പാക്കുന്നു

all inputs in a finite number of steps.

എന്നതാണ്. ഇതിനകം തന്നെ പ്രോഗ്രാമിംഗ്

And for those of who may already know some programming it should not have infinite loops for example.

(programming) അറിയാവുന്നവർക്ക് അതിന് അനന്തമായ ലൂപ്പുകൾ (loop) ഉണ്ടാകരുത് എന്ന് അറിയാം . ഓരോ ഇൻപുട്ടിലെയും

And we also address the issue of minimizing the number of steps on every input.

(input) ഘട്ടങ്ങളുടെ എണ്ണം കുറയ്ക്കുന്നതിനുള്ള

This is not a very well stated goal. And this is one of the things that we will formalize as we go through this course.

പ്രശ്നവും നമ്മൾ പരിഹരിക്കുന്നു. ഇത് വളരെ നന്നായി പ്രഖ്യാപിച്ച ലക്ഷ്യമല്ല. ഈ കോഴ്‌സിലൂടെ (course) കടന്നുപോകുമ്പോൾ

These are the main foresight of this course.

ഞങ്ങൾ ഔ പചാരികമാക്കുന്ന ഒരു കാര്യമാണിത്.

Outline of the course is that we are going to have 10 one hour lectures.

കോഴ്‌സിന്റെ (course) രൂപരേഖ ഞങ്ങൾ ഒരു

Every week there will be 2 of them; and every lecture will be broken into approximately

മണിക്കൂർ ഉള്ള 10 പ്രഭാഷണങ്ങൾ നടത്താൻ പോകുന്നു

4 modules each of 15 minutes.

എന്നതാണ്. എല്ലാ ആഴ്ചയും അവയിൽ 2 എണ്ണം

And at the end of each module there will be some exercise for the learner to go out and try before the next module.

ഉണ്ടാകും; ഓരോ പ്രഭാഷണവും ഓരോ 15 മിനിറ്റിലും ഏകദേശം 4 മൊഡ്യൂളുകളായി (module) വിഭജിക്കും. ഓരോ

The contents of the course are as follows.

മൊഡ്യൂളിന്റെയും (module) അവസാനം പഠിതാവിന്

During the first week we will focus on fast arithmetic, during the second week we will

പുറത്തുപോയി അടുത്ത മൊഡ്യൂളിന് (module) മുമ്പായി ശ്രമിക്കുന്നതിന് കുറച്ച് വ്യായാമം ഉണ്ടാകും. കോഴ്‌സിന്റെ (course) ഉള്ളടക്കങ്ങൾ

work on algorithms for searching and sorting, the third week we will work on greedy algorithms,

ചുവടെ ചേർക്കുന്നു. ആദ്യ ആഴ്ചയിൽ‌ നമ്മൾ വേഗത്തിലുള്ള ഗണിതത്തിൽ‌ ശ്രദ്ധ കേന്ദ്രീകരിക്കും,

during the fourth week we will move slowly towards advanced techniques for designing algorithms and one of them to address quite a few problems as the dynamic programming

രണ്ടാമത്തെ ആഴ്ചയിൽ‌ തിരയുന്നതിനും തരംതിരിക്കുന്നതിനുമുള്ള അൽ‌ഗോരിതംസിൽ‌ (algorithms) പ്രവർത്തിക്കും, മൂന്നാം ആഴ്ച ഗ്രീഡി അൽ‌ഗോരിതംസിൽ‌ (greedy algorithm) പ്രവർ‌ത്തിക്കും, നാലാം ആഴ്ചയിൽ‌ അൽ‌ഗോരിതം

approach to design algorithms. And finally, we will come to challenging exercises which have immense practical applications

(algorithm) രൂപകൽപ്പന ചെയ്യുന്നതിനുള്ള നൂതന സാങ്കേതിക വിദ്യകളിലേക്ക് സാവധാനം നീങ്ങും ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

like string matching and identifying shortest paths in a network like a road network or

(dynamic programming) സമീപനമെന്ന നിലയിൽ കുറച്ച് പ്രശ്നങ്ങൾ

any transportation network for example.

പരിഹരിക്കുന്നതാണ് അവയിലൊന്ന്. അവസാനമായി, സ്ട്രിംഗ് (string) പൊരുത്തപ്പെടുത്തൽ,

So, lets start off with the ah.. contents of the first lecture which is all about fast

റോഡ് നെറ്റ്‌വർക്ക് (road network) അല്ലെങ്കിൽ ഏതെങ്കിലും ഗതാഗത ശൃംഖല പോലുള്ള ഒരു

arithmetic.

നെറ്റ്‌വർക്കിലെ (network) ഏറ്റവും ചെറിയ

Now, in these issues we make some minor assumptions which are often verifiable as being satisfied

പാതകളെ തിരിച്ചറിയുക തുടങ്ങിയ പ്രായോഗിക പ്രയോഗങ്ങളുള്ള വെല്ലുവിളി നിറഞ്ഞ വ്യായാമങ്ങളിലേക്ക് ഞങ്ങൾ വരും.

by most processors.

ആദ്യത്തെ പ്രഭാഷണത്തിലെ ഉള്ളടക്കങ്ങൾ അതിവേഗ

We assume that multiplication and addition of 2 integers can be done in unit time.

ഗണിതത്തെക്കുറിച്ചുള്ളതാണ്. ഇപ്പോൾ, ഈ പ്രശ്നങ്ങളിൽ ഞങ്ങൾ ചില ചെറിയ അനുമാനങ്ങൾ നടത്തുന്നു,

On most processors this is not a completely valid assumption because its either a 32 bit

അവ മിക്ക പ്രോസസ്സറുകളും (processor) തൃപ്തികരമാണെന്ന് സ്ഥിരീകരിക്കാം. 2 പൂർണ്ണസംഖ്യകളുടെ ഗുണനവും കൂട്ടിച്ചേർക്കലും യൂണിറ്റ് (unit) സമയത്ത്

integer or a 64 bit integer addition, or 128 bit integer addition or a finite number of

ചെയ്യാമെന്ന് ഞങ്ങൾ അനുമാനിക്കുന്നു. മിക്ക പ്രോസസ്സറുകളിലും (processor) ഇത് പൂർണ്ണമായും

bits addition that happens in unit time. But, for the purposes of understanding the challenge of designing algorithms to do fast arithmetic we relax this assumption and we assume that any 2 integers can be multiplied or added in unit time.

സാധുവായ ഒരു അനുമാനമല്ല, കാരണം ഇത് 32 ബിറ്റ് (bit) സംഖ്യ അല്ലെങ്കിൽ 64 ബിറ്റ് (bit) സംഖ്യ കൂട്ടിച്ചേർക്കൽ, അല്ലെങ്കിൽ 128 ബിറ്റ്

So, now, here is the simplest of exercises right which we can do very efficiently as

(bit) സംഖ്യ കൂട്ടിച്ചേർക്കൽ അല്ലെങ്കിൽ യൂണിറ്റ് (unit) സമയത്തിൽ സംഭവിക്കുന്ന പരിമിതമായ എണ്ണം ബിറ്റുകൾ (bit) കൂട്ടിച്ചേർക്കൽ എന്നിവയാണ്.

ah.. human beings and let us see how to convert this into a computer program.

എന്നാൽ, വേഗത്തിലുള്ള ഗണിതശാസ്ത്രത്തിനായി അൽ‌ഗോരിതം (algorithm) രൂപകൽപ്പന ചെയ്യുന്നതിലെ വെല്ലുവിളി

To convert it into a computer program we need to ensure that we understand the underlying

മനസിലാക്കുന്നതിനായി ഞങ്ങൾ ഈ അനുമാനത്തിൽ ഇളവ് വരുത്തുന്നു, കൂടാതെ ഏതെങ്കിലും

mathematics first, we come up with an algorithm, and then you can choose your favorite programming

2 പൂർണ്ണസംഖ്യകളെ ഗുണിതമാക്കാനോ യൂണിറ്റ്

language to convert the algorithm into a program.

സമയത്തിൽ ചേർക്കാനോ കഴിയുമെന്ന് ഞങ്ങൾ

This is how algorithms and programming are very closely connected.

അനുമാനിക്കുന്നു. അതിനാൽ, ഇപ്പോൾ, ലളിതമായ വ്യായാമങ്ങൾ ഇവിടെ നമുക്ക് വളരെ കാര്യക്ഷമമായി

So, whenever you want to solve a problem, when you want to write a program to solve a problem, we go out and try to design an algorithm.

ചെയ്യാൻ കഴിയും. ഇത് എങ്ങനെ ഒരു കമ്പ്യൂട്ടർ

When we try to design an algorithm we try to go out and understand the kind of inputs that we process and identify the appropriate mathematical logical steps to that part it

പ്രോഗ്രാമിലേക്ക് (computer program) പരിവർത്തനം ചെയ്യാമെന്ന് നോക്കാം. ഇത് ഒരു കമ്പ്യൂട്ടർ പ്രോഗ്രാമിലേക്ക് (computer program) പരിവർത്തനം ചെയ്യുന്നതിന്, അടിസ്ഥാന ഗണിതശാസ്ത്രം ആദ്യം

that play an important role in the algorithm. And then ensure that the algorithm is is a good algorithm; in the sense, that it terminates

മനസിലാക്കുന്നുവെന്ന് ഉറപ്പാക്കേണ്ടതുണ്ട്, ഞങ്ങൾ ഒരു അൽഗോരിതം (algorithm) കൊണ്ടുവരുന്നു, തുടർന്ന് അൽഗോരിതം (algorithm) ഒരു പ്രോഗ്രാമിലേക്ക്

on all inputs, and it uses as few as steps possible; it uses as few resources as possible. These are all the parameters that we will try to quantify as we progress through this

(program) പരിവർത്തനം ചെയ്യുന്നതിന് നിങ്ങളുടെ പ്രിയപ്പെട്ട പ്രോഗ്രാമിംഗ് (programming) ഭാഷ തിരഞ്ഞെടുക്കാം. ഇങ്ങനെയാണ് അൽ‌ഗോരിതംസും പ്രോഗ്രാമിംഗും

course.

തമ്മിൽ ബന്ധപ്പെട്ടിരിക്കുന്നത്.

Coming back to fast arithmetic, lets consider the simplest of problems; lets consider the question where the input to a program is 2 positive integers, x and n.

നിങ്ങൾ ഒരു പ്രശ്നം പരിഹരിക്കാൻ ആഗ്രഹിക്കുമ്പോഴെല്ലാം, ഒരു പ്രശ്നം പരിഹരിക്കാൻ ഒരു പ്രോഗ്രാം (program) എഴുതാൻ നിങ്ങൾ ആഗ്രഹിക്കുമ്പോൾ, ഒരു അൽഗോരിതം (algorithm) രൂപകൽപ്പന ചെയ്യാൻ ശ്രമിക്കുന്നു. ഒരു

And the goal is to design an algorithm that will calculate x to the power of n that is the nth power of the given integer x right.

അൽ‌ഗോരിതം (algorithm) രൂപകൽപ്പന ചെയ്യാൻ‌ ശ്രമിക്കുമ്പോൾ‌, പ്രോസസ്സ് (process) ചെയ്യുന്ന ഇൻ‌പുട്ടുകൾ‌ (input) മനസിലാക്കാനും അൽ‌ഗോരിതം ഒരു പ്രധാന പങ്ക് വഹിക്കുന്ന ആ ഭാഗത്തേക്ക് ഉചിതമായ ഗണിതശാസ്ത്രപരമായ

Now, lets look at a bit of mathematics, right; very simple mathematics which all of us are

ലോജിക്കൽ‌ (logical) ഘട്ടങ്ങൾ‌ തിരിച്ചറിയാനും

very familiar with, that the definition of x to the power of n is x to the power of n minus 1 that is the n minus 1th power of x, multiplied by x.

ശ്രമിക്കുന്നു. അൽ‌ഗോരിതം (algorithm) ഒരു നല്ല അൽ‌ഗോരിതം (algorithm) ആണെന്ന് ഉറപ്പാക്കുക; ഇത് എല്ലാ ഇൻ‌പുട്ടുകളിലും (input) അവസാനിക്കുന്നു, മാത്രമല്ല ഇത് സാധ്യമായത്ര

And there is always a boundary condition that x to the power of n is 1 if n equals 0, right. So, this requires a bit of correction.

ഘട്ടങ്ങൾ മാത്രമേ ഉപയോഗിക്കുന്നുള്ളൂ; ഇത് കഴിയുന്നത്ര കുറച്ച് റിസോഴ്സുകൾ (resource) ഉപയോഗിക്കുന്നു. ഈ കോഴ്സിലൂടെ (course)

There is an error there right; this must be 1.

പുരോഗമിക്കുമ്പോൾ കണക്കാക്കാൻ ശ്രമിക്കുന്ന പാരാമീറ്ററുകൾ (parameter) ഇവയാണ്.

So, this is the number 1 and not the 0.

വേഗത്തിലുള്ള ഗണിതത്തിലേക്ക് മടങ്ങിവരാം ലളിതമായ പ്രശ്‌നം നോക്കാം ; ഒരു പ്രോഗ്രാമിലേക്കുള്ള (program) ഇൻപുട്ട് (input) 2 പോസിറ്റീവ് (positive)

This mathematical definition of x power n gives us a desired algorithmic idea.

സംഖ്യകളായ x, n ആണ്. Xn കണക്കാക്കുന്ന ഒരു അൽ‌ഗോരിതം (algorithm) രൂപകൽപ്പന ചെയ്യുക

And this is implemented in any programming language using a loop control structure whichever programming language it is, we can use a counter control loop.

എന്നതാണ് ലക്ഷ്യം, ഇപ്പോൾ, കുറച്ച് ഗണിതശാസ്ത്രത്തിലേക്ക് നോക്കാം, നമുക്കെല്ലാവർക്കും വളരെ പരിചിതമായ വളരെ ലളിതമായ ഗണിതശാസ്ത്രം, Xn എന്നതിന്റെ നിർവചനം (x-1) n*x ആണ്

എല്ലായ്പ്പോഴും ഒരു ബൗണ്ടറി കണ്ടീഷൻ

As in this case where we use an almost C like a syntax right where you see a variable called

(boundary condition) ഉണ്ട്. വ്യവസ്ഥയുണ്ട്, Xn =1 if n=0 ഇതിന് അൽപ്പം

counter which is of integer type.

തിരുത്തൽ ആവശ്യമാണ്. അവിടെ ഒരു പിശക്

And we initialize the value which is going to store the variable value to contain the value 1.

ഉണ്ട്; ഇത് 1 ആയിരിക്കണം. ഇത് നമ്പർ 1 ആണ്, 0 അല്ല.

And then here is a loop which has an initial value which sets counter to be equal to 0 and runs for n iterations.

Xn ന്റെ ഈ ഗണിത നിർവചനം നമുക്ക് ആവശ്യമുള്ള അൽഗോരിതം (algorithm) ആശയം നൽകുന്നു. ഏത് പ്രോഗ്രാമിംഗ്

At the end of each iteration it increases counter by 1, and value is multiplied by x;

(programming) ഭാഷയിലും ഇത് ഒരു ലൂപ്പ് (loop) നിയന്ത്രണ

at the end of it value is returned right.

ഘടന ഉപയോഗിച്ച് നടപ്പിലാക്കുന്നു, നമുക്ക് ഒരു കൗണ്ടർ

Now, this is quite a simple program right, and lets just run a small example, right.

കൺട്രോൾ ലൂപ്പ് (counter control loop) ഉപയോഗിക്കാം. ഇവിടെ ഇന്റിജെർ (integer) തരത്തിലുള്ള കൗ ണ്ടർ

So, for example, lets say I want to evaluate 4 to the power of 3 right. So, this is done in 3 iterations; initially value is equal to 1 value is equal to 1, and

(counter) എന്ന വേരിയബിൾ (variable) കാണുന്നു. മൂല്യം 1 ഉൾക്കൊള്ളുന്നതിനായി വേരിയബിൾ (variable) ഞങ്ങൾ സമാരംഭിക്കുന്നു. തുടർന്ന് ഇവിടെ ഒരു പ്രാരംഭ മൂല്യമുള്ള ഒരു ലൂപ്പ് (loop) ഉണ്ട്,

counter takes a range of values which is 0, 1 and 2 right. Now, when control enters the iteration for the first time counter is equal to 0, and

അത് കൗണ്ടറിനെ (counter) 0 ന് തുല്യമായി സജ്ജമാക്കുകയും n ആവർത്തനത്തിനായി പ്രവർത്തിക്കുകയും ചെയ്യുന്നു. ഓരോ ആവർത്തനത്തിൻറെയും അവസാനം അത് കൗണ്ടർ (counter) 1 വർദ്ധിപ്പിക്കുകയും

then so this is the table of values, value becomes 4.

മൂല്യം x കൊണ്ട് ഗുണിക്കുകയും ചെയ്യുന്നു; അതിന്റെ അവസാനം മൂല്യം റിട്ടേൺ (return) ചെയ്യുന്നു..

At the end of this counter is incremented by 1, then value becomes 16 right, and value

ഇത് വളരെ ലളിതമായ ഒരു പ്രോഗ്രാം (program) ആണ്, ഒരു ചെറിയ ഉദാഹരണം പ്രവർത്തിപ്പിക്കാം.

becomes 64 in the third iteration that is when counter is equal to 2. At the end of this counter becomes 3, control exits from the loop. And the final value is returned and that is 64 right.

ഉദാഹരണത്തിന്, 34 വിലയിരുത്താൻ ഞാൻ ആഗ്രഹിക്കുന്നുവെന്ന് പറയാം. ഇത് 3 ആവർത്തനങ്ങളിൽ ചെയ്യുന്നു; തുടക്കത്തിൽ മൂല്യം 1 ന് തുല്യമാണ് 1, കൗണ്ടർ (counter) 0, 1, 2 മൂല്യങ്ങളുടെ ഒരു ശ്രേണി എടുക്കുന്നു. ഇപ്പോൾ, നിയന്ത്രണം

As you can see, the correctness of this algorithm comes from this formal mathematical definition

ആദ്യമായി ആവർത്തനത്തിലേക്ക് പ്രവേശിക്കുമ്പോൾ കൗണ്ടർ (counter) 0 ന് തുല്യമാണ്, ഇത് മൂല്യങ്ങളുടെ

which is exactly what is implemented in the loop in the program.

പട്ടികയാണ്, മൂല്യം 4 ആയി മാറുന്നു. ഈ കൗണ്ടറിന്റെ (counter) അവസാനം 1 വർദ്ധിപ്പിക്കുകയും

And its clear that this algorithm is indeed correct.

മൂല്യം 16 ആയി മാറുകയും മൂന്നാമത്തെ ആവർത്തനത്തിൽ

However, we are not interested just in the correctness, but we are also interested in

മൂല്യം 64 ആകുകയും ചെയ്യുന്നു, അതായത്

how many arithmetic operations are performed. And that is really the focus of the next part on this small example right.

കൗ ണ്ടർ (counter) 2 ന് തുല്യമാകുമ്പോൾ. ഈ കൗ ണ്ടറിന്റെ (counter)

As we just mentioned, the algorithm is correct because of the mathematical ah.. formulation of ah.. power of a particular number. As well as efficiency goes, we measure efficiency as the number of arithmetic operations which are performed.

അവസാനം 3 ആകുമ്പോൾ, നിയന്ത്രണം ലൂപ്പിൽ (loop) നിന്ന് പുറത്തുകടക്കുന്നു. അവസാന മൂല്യം തിരികെ നൽകി, അത് 64 നിങ്ങൾക്ക് കാണാനാകുന്നതുപോലെ, ഈ അൽ‌ഗോരിത്തിന്റെ (algorithm) കൃത്യത ഈ fഔ പചാരിക

And in this case, there are only multiplications.

And its quite easy to see that every iteration there is a single multiplication that is performed. Therefore, for n iterations there are n operations right. So, lets just go back to our program.

ഗണിതശാസ്ത്ര നിർവചനത്തിൽ നിന്നാണ് വരുന്നത്, ഇത് പ്രോഗ്രാമിലെ (program) ലൂപ്പിൽ (loop) കൃത്യമായി നടപ്പിലാക്കുന്നു. ഈ അൽ‌ഗോരിതം (algorithm) തീർച്ചയായും ശരിയാണെന്ന് വ്യക്തമാണ്. എന്നിരുന്നാലും,

You look at this. There are n iterations.

കൃത്യതയിൽ മാത്രം ഞങ്ങൾക്ക് താൽപ്പര്യമില്ല,

Every iteration has an iteration number which is captured by counter.

എത്ര ഗണിത പ്രവർത്തനങ്ങൾ നടത്തുന്നുവെന്നതിലും

Counter takes a range of values between 0 to n minus 1.

ഞങ്ങൾക്ക് താൽപ്പര്യമുണ്ട്.

And in every iteration the value is updated by a single arithmetic operation which is

ഈ ചെറിയ ഉദാഹരണത്തിൽ അടുത്ത ഭാഗത്തിന്റെ ശ്രദ്ധാകേന്ദ്രം അതാണ്. നമ്മൾ ഇപ്പോൾ

a multiplication.

സൂചിപ്പിച്ചതുപോലെ, ഗണിതശാസ്ത്രപരമായ

Therefore, the number of multiplications that are associated with this program is exactly n where n is the power of x that we want to compute right.

രൂപീകരണം. ഒരു പ്രത്യേക സംഖ്യയുടെ പവർ (power). അൽഗോരിതം (algorithm) ശരിയാണ്. കാര്യക്ഷമതയ്‌ക്കൊപ്പം, നിർവ്വഹിക്കുന്ന ഗണിത പ്രവർത്തനങ്ങളുടെ

There are also a couple of additions which happen.

എണ്ണമായി കാര്യക്ഷമത അളക്കുന്നു. ഈ സാഹചര്യത്തിൽ,

So, where ah.. counter gets increased at every step; thats one addition that happens in every iteration.

ഗുണനങ്ങൾ മാത്രമേയുള്ളൂ. ഓരോ ആവർത്തനത്തിലും ഒരൊറ്റ ഗുണനം നടക്കുന്നുണ്ട്. അതിനാൽ, n ആവർത്തനങ്ങൾക്ക്

But, we are not interested in counting that because that is more ah.. a structural exercise,

n പ്രവർത്തനങ്ങൾ ഉണ്ട് . പ്രോഗ്രാമിലേക്ക് (program) മടങ്ങാം. നിങ്ങൾ

and we are interested just counting, interested in counting the number of multiplications.

ഇത് നോക്കുക. N ആവർത്തനങ്ങളുണ്ട്. ഓരോ ആവർത്തനത്തിനും ഒരു ആവർത്തന നമ്പർ ഉണ്ട്, അത് കൗ ണ്ടർ

Lets address the question as how to reduce the number of arithmetic operations which

(counter) പിടിച്ചെടുക്കുന്നു. കൗണ്ടർ‌ (counter) 0 മുതൽ

are performed in computing the power. So, here is the next approach which is very interesting. And this is the technique that you can use even to compute the higher powers of matrices, not just numbers.

n - 1 വരെയുള്ള മൂല്യങ്ങളുടെ ഒരു ശ്രേണി എടുക്കുന്നു. കൂടാതെ ഓരോ ആവർത്തനത്തിലും മൂല്യം ഒരു ഗണിത പ്രവർ‌ത്തനത്തിലൂടെ അപ്‌ഡേറ്റു (update) ചെയ്യുന്നു, അത് ഒരു ഗുണനമാണ്. അതിനാൽ, ഈ പ്രോഗ്രാമുമായി

So, in this case, we want to compute the nth power of x, in other words we want to compute

(program) ബന്ധപ്പെട്ടിരിക്കുന്ന ഗുണനങ്ങളുടെ എണ്ണം n ആണ്, ഇവിടെ n എന്നത് കണക്കാക്കാൻ ആഗ്രഹിക്കുന്ന

x power n. And the observation that we make that is that x power n is given by x square raised to the

x ന്റെ പവർ (power) ആണ് കുറച്ച് കൂട്ടിച്ചേർക്കലുകളും സംഭവിക്കുന്നു. ഓരോ ഘട്ടത്തിലും കൗ ണ്ടർ (counter) വർദ്ധിക്കുന്നു; എല്ലാ ആവർത്തനത്തിലും

power of n minus 1 by 2 right if n is odd, and multiplied by x.

സംഭവിക്കുന്ന ഒരു കൂട്ടിച്ചേർക്കൽ. പക്ഷേ, അത് കണക്കാക്കാൻ ഞങ്ങൾക്ക് താൽപ്പര്യമില്ല, കാരണം അത് കൂടുതൽ ഘടനാപരമായ ഒരു വ്യായാമമാണ്,

Its very easy to do the arithmetic - 2 times n minus 1 by 2; 2 times n minus 1 by 2 is

മാത്രമല്ല എണ്ണാൻ ഞങ്ങൾ താൽപ്പര്യപ്പെടുന്നു, ഗുണനങ്ങളുടെ എണ്ണം എണ്ണാൻ താൽപ്പര്യമുണ്ട്. പവർ കമ്പ്യൂട്ടിംഗിൽ (power computing) നടത്തുന്ന ഗണിത പ്രവർത്തനങ്ങളുടെ എണ്ണം എങ്ങനെ കുറയ്ക്കാം

എന്ന ചോദ്യത്തെ അഭിസംബോധന ചെയ്യാം.

equal to n minus 1 thats what happen in happens in the exponent.

അടുത്ത സമീപനം വളരെ രസകരമാണ്. അക്കങ്ങൾ

And then there is a multiplication by x. Observe that when n is odd, n minus 1 is even; therefore, n minus 1 is then divisible by

മാത്രമല്ല, മെട്രിക്സിലെ (matrix) ഉയർന്ന പവർ (power) കണക്കുകൂട്ടാൻ പോലും നിങ്ങൾക്ക് ഉപയോഗിക്കാവുന്ന

സാങ്കേതികതയാണിത്. ഈ സാഹചര്യത്തിൽ,

So, therefore, the left hand side is an integer; you get the value n minus 1.

x- ന്റെ nth പവർ കണക്കുകൂട്ടാൻ ഞങ്ങൾ ആഗ്രഹിക്കുന്നു,

And then you multiply by x.

മറ്റൊരു വിധത്തിൽ പറഞ്ഞാൽ xn കണക്കുകൂട്ടാൻ

Therefore, this is basically x power n minus 1 multiplied by x when n is odd; when n is even its very clear, its x square whole power n by 2.

ഞങ്ങൾ ആഗ്രഹിക്കുന്നു. നമ്മൾ നിരീക്ഷിക്കുന്ന നിരീക്ഷണം, xn നൽകുന്നത് (x2 )(n-1/2)*x ആണ്, n ഒറ്റ സംഖ്യ ആണെങ്കിൽ. അരിത്മെറ്റിക് (arithmetic)

So, here is a trick which is recursive repeated squaring right. Its repeated squaring of what? Lets see that now. Remember, that initially we have the value we have the value x, and earlier in the first

ചെയ്യുന്നത് വളരെ എളുപ്പമാണ് - 2 * (n -1)/ 2; 2 * (n -1)/ 2 എന്നത് n - 1 ന് തുല്യമാണ്, അതാണ് എക്‌സ്‌പോണന്റിൽ (exponent) സംഭവിക്കുന്നത്. അതിനുശേഷം x കൊണ്ട് ഒരു ഗുണനം ഉണ്ട്.

iteration we computed, in in the iteration numbered 1 we computed the value x square. And remember that in the next iteration we computed the value x cube, instead we do something

N ഒറ്റ സംഖ്യ ആവുമ്പോൾ n - 1 ഇരട്ടസംഖ്യയാണ് ; അതിനാൽ, n- 1 നെ 2 കൊണ്ട് ഹരിക്കാം. അതിനാൽ,

which is slightly cleverer and compute x power 4 right which is x square whole power 2 which

ഇടത് വശത്ത് ഒരു പൂർണ്ണസംഖ്യയാണ്; നിങ്ങൾക്ക് n -1 എന്ന മൂല്യം ലഭിക്കും.

is x power 4.

എന്നിട്ട് നിങ്ങൾ x കൊണ്ട് ഗുണിക്കുന്നു.

And then we compute, we square the value of x power 4 in the fourth iteration, right.

ഇത് അടിസ്ഥാനപരമായി x(n-1)*x ആണ്, ഒറ്റ സംഖ്യ ആവുമ്പോൾ ; n ഒറ്റ ഇരട്ട സംഖ്യ ആവുമ്പോൾ

That is the iteration numbered 3 that is zero; the first iteration, the second iteration

( x2 )(n/2) ആണ് ആവർത്തിച്ചുള്ള സ്‌ക്വറിംഗ് (squaring) ചെയ്യാൻ ഒരു ട്രിക്ക്

and the third iteration, we compute x power 8.

(trick) ഇതാ., തുടക്കത്തിൽ നമുക്ക് x എന്ന മൂല്യമുണ്ട്,

The fourth iteration we square the value computed in the previous iteration.

നേരത്തെ കണക്കാക്കിയ ആദ്യ ആവർത്തനത്തിലും,

So, we get x power 16, and so on. So, what is the whole idea?

x2 മൂല്യം ഞങ്ങൾ കണക്കാക്കി. അടുത്ത ആവർത്തനത്തിൽ

The whole idea is very simple. We compute the square of the previous term right; in other words, the kth term in the

ഞങ്ങൾ x3 ന്റെ മൂല്യം കണക്കുകൂട്ടി, പകരം ഞങ്ങൾ അല്പം ബുദ്ധിപരമായ എന്തെങ്കിലും ചെയ്യുന്നു,

sequence is x power 2 power k. So, lets write this down. In the kth iteration, we would have computed x power 2 power k.

ഒപ്പം x പവർ 4 കണക്കുകൂട്ടുക, അത് (X 2)2 ആണ്. നാലാമത്തെ ആവർത്തനത്തിലെ x4 ന്റെ മൂല്യം ഞങ്ങൾ

And for what value of k is; so what we want to compute is x square whole to the power

കണക്കാക്കുന്നു. അതാണ് മൂന്നാമത്തെ ആവർത്തനം; ആദ്യ ആവർത്തനം, രണ്ടാമത്തെ ആവർത്തനം, മൂന്നാമത്തെ ആവർത്തനം, ഞങ്ങൾ x8 കണക്കാക്കുന്നു. നാലാമത്തെ ആവർത്തനം മുമ്പത്തെ ആവർത്തനത്തിൽ

കണക്കാക്കിയ മൂല്യത്തിന്റെ സ്‌ക്വയർ (square) ചെയ്യുന്നു.

of n by 2 right.

അതിനാൽ, നമുക്ക് x16 ലഭിക്കുന്നു, അങ്ങനെ.

So, what we do is we compute, we perform this operation of repeated squaring of the value

അതിനാൽ, മുഴുവൻ ആശയവും എന്താണ്? മുഴുവൻ ആശയവും വളരെ ലളിതമാണ്. മുമ്പത്തെ പദത്തിന്റെ

computed in the previous iteration right till 2 power k and n by 2, are one and the same,

സ്‌ക്വയർ ഞങ്ങൾ കണക്കാക്കുന്നു; മറ്റൊരു വിധത്തിൽ പറഞ്ഞാൽ, ശ്രേണിയിലെ kth പദം (x 2 ) k ആണ്.

at which point of time starting from x square we would have computed x square to the power of n by 2. That is, we calculate the value right of x power n by repeated squaring, and the termination

ഇത് എഴുതാം. Kth ആവർത്തനത്തിൽ, ഞങ്ങൾ (x 2 ) k കണക്കുകൂട്ടും. K യുടെ മൂല്യം എന്താണ്; അതിനാൽ നമുക്ക് കണക്കുകൂട്ടാൻ

condition is when 2 power k where k is the iteration number becomes equal to n by 2,

ആഗ്രഹിക്കുന്നത് x (x 2 ) k . അതിനാൽ, നമ്മൾ ചെയ്യുന്നത് നമ്മൾ കണക്കുകൂട്ടുകയാണ്,

assuming that we start with x square right.

മുമ്പത്തെ ആവർത്തനത്തിൽ കണക്കാക്കിയ മൂല്യത്തിന്റെ

For what value of k is 2, for what value of k is this equation satisfied, right, that 2 power k becomes equal to n by 2 right? So, for k equals log n to the base 2 minus 1.

ആവർത്തിച്ചുള്ള സ്ക്വയറിംഗിന്റെ പ്രവർത്തനം 2k n/2 വരെ ഞങ്ങൾ നടത്തുന്നു, ഇത് ഒന്നുതന്നെയാണ്, ഏത് സമയത്താണ് x സ്ക്വയറിൽ നിന്ന് ആരംഭിക്കുന്നത് (x 2 ) n/2 കണക്കാക്കുമായിരുന്നു.

അതായത്, ആവർത്തിച്ചുള്ള സ്ക്വയറിംഗിലൂടെ

For the value k equals log n to the base 2 minus 1 right, k equals n by 2. And let us do a small exercise here to get an idea as to what we are talking about right.

(squaring) xn ന്റെ മൂല്യം ഞങ്ങൾ കണക്കാക്കുന്നു, കൂടാതെ 2 k . ഇവിടെ k ആണ് ആവർത്തന സംഖ്യ

Consider the case when n is a power of 2. So, lets assume that the number that is given is x; consider the case when the number is x, and we want to compute, say, x to the power of 64. So, lets write down the sequence.

n /2 ന് തുല്യമാകുമ്പോൾ, നമ്മൾ x2 ആരംഭിക്കുന്നുവെന്ന് അനുമാനിക്കുന്നു. K യുടെ ഏത് മൂല്യത്തിന് 2 ആണ്, k ന്റെ ഏത് മൂല്യത്തിന് ഈ സമവാക്യം തൃപ്തികരമാണ്,

We start off with x square, then we compute x power 4, then we compute x power 8, then

2 k n /2 ന് തുല്യമായി മാറുന്നു? അതിനാൽ,

we compute x power 16, we compute x power 32, and finally we compute x power 64 right.

k=log 2 n -1 മൂല്യത്തിന് k =n / 2 ആവുന്നു. നമ്മൾ സംസാരിക്കുന്നതിനെക്കുറിച്ച് ഒരു ആശയം ലഭിക്കുന്നതിന്

Observe that at every step the exponent keeps getting doubled.

ഒരു ചെറിയ വ്യായാമം ചെയ്യാം. N 2 ന്റെ പവർ

The most important concept here is that the exponent doubles at every step.

(power) ആയിരിക്കുന്ന കേസ് പരിഗണിക്കുക. നൽകിയിരിക്കുന്ന സംഖ്യ x ആണെന്ന് അനുമാനിക്കാം; x64 കണക്കുകൂട്ടാൻ ഞങ്ങൾ ആഗ്രഹിക്കുന്നു.

In each iteration, and we started off with x square right, and we wanted x to the 64,

സീക്വൻസ് (sequence) എഴുതാം . ഞങ്ങൾ x2 ആരംഭിക്കുന്നു, തുടർന്ന് ഞങ്ങൾ x4 കണക്കുകൂട്ടുന്നു, തുടർന്ന് ഞങ്ങൾ x8 കണക്കുകൂട്ടുന്നു, തുടർന്ന് ഞങ്ങൾ x16 കണക്കുകൂട്ടുന്നു,

ഞങ്ങൾ x32 കണക്കുകൂട്ടുന്നു, ഒടുവിൽ x64 കണക്കാക്കുന്നു.

x to the power of 64, and observe that the number of iterations is 1, the second iteration,

ഓരോ ഘട്ടത്തിലും എക്‌സ്‌പോണന്റ് (exponent) ഇരട്ടിയാകുന്നത് നിരീക്ഷിക്കുക. എക്‌സ്‌പോണന്റ് (exponent) ഓരോ ഘട്ടത്തിലും

the third iteration, the fourth iteration and the fifth iteration right.

ഇരട്ടിയാകുന്നു എന്നതാണ് ഇവിടെ ഏറ്റവും പ്രധാനപ്പെട്ട ആശയം. ഓരോ ആവർത്തനത്തിലും,

And it is very clear that log 64 to the base 2 is 6 right because 2 power 6 is 64 right;

ഞങ്ങൾ x2 ആരംഭിച്ചു,, ആവർത്തനങ്ങളുടെ എണ്ണം 1, രണ്ടാമത്തെ ആവർത്തനം, മൂന്നാമത്തെ ആവർത്തനം, നാലാമത്തെ ആവർത്തനം, അഞ്ചാമത്തെ ആവർത്തനം വലത്. log 2 64 6 ആണെന്ന് വളരെ

minus 1 because we started off with x square right, and minus 1 right, this is 5. Therefore, there are 5 iterations.

വ്യക്തമാണ്, കാരണം 2 പവർ 6 64 ആണ്; -1 കാരണം ഞങ്ങൾ x2 ആരംഭിച്ചു, -1 വലത്, ഇത് 5 ആണ്. അതിനാൽ,

In the zeroth iteration its x square, in the iteration numbered 1- x power 4, iteration

5 ആവർത്തനങ്ങളുണ്ട്. പൂജ്യ ആവർത്തനത്തിൽ x2, ഒന്നാം ആവർത്തനത്തിൽ

numbered 2 its x power 8, iteration numbered 3 its x power 16, iteration numbered 4 it is 35, iteration number 5 – 64, x power 64 is calculated; and at the end of it for

x4 , ആവർത്തനം 2 x8 , ആവർത്തനം 3 x16 , ആവർത്തന സംഖ്യ 4, x3 2 , ആവർത്തന നമ്പർ 5 - x64 കണക്കാക്കുന്നു; അതിന്റെ അവസാനം log2 n -1 ഘട്ടങ്ങൾ; ശരിയായ

powers of 2 in log n to the base 2; minus 1 steps; the correct value is calculated;

മൂല്യം കണക്കാക്കുന്നു; n 2 ന്റെ പവർ (power) ആണ്. ഇത് ഞങ്ങളെ ഇവിടെ വ്യായാമത്തിലേക്ക്

when very importantly n is a power of 2.

കൊണ്ടുവരുന്നു. ആവർത്തിച്ചുള്ള സ്ക്വറിംഗ് അൽഗോരിതം

So, this brings us to the exercise here.

(squaring algorithm) നടപ്പിലാക്കാൻ ഒരു സി പ്രോഗ്രാം (program) എഴുതുന്നത് ഒരു വിദ്യാർത്ഥിയെന്ന

As a student it is very instructive to write a C program to implement the repeated squaring algorithm.

നിലയിൽ വളരെ പ്രബോധനപരമാണ്. പ്രത്യേകിച്ചും, n ന്റെ പവർ (power) 2 അല്ലാത്തപ്പോൾ ലൂപ്പ് (loop) എഴുതുക

In particular, the challenge here is to write down the loop when n is not a power of 2. And this is very interesting. So, let me give you a hint as to how to go about this. Let us assume that n is, instead of 64, let us assume that n is 65, and let us write 65

എന്നതാണ് ഇവിടെയുള്ള വെല്ലുവിളി. ഇത് വളരെ രസകരമാണ്. ഇതിനെക്കുറിച്ച് എങ്ങനെ അറിയാമെന്നതിനെക്കുറിച്ചുള്ള ഒരു സൂചന ഞാൻ തരാം. N എന്നത് 64 എന്നതിനുപകരം, n 65 ആണെന്ന് കരുതുക, കൂടാതെ 65 ബൈനറി വലതുവശത്ത്

in binary right.

എഴുതാം. ഇത് 1 0 0 0 0 0 ആയിരിക്കും, തുടർന്ന്

It would be 1 0 0 0 0 0 followed by 1 right is 65, right.

1 . മൂല്യം 1 സംഭാവന ചെയ്യുന്നു, ഇത് 2 പവർ 0, 2 പവർ 1, 2 പവർ 2, 2 പവർ 3, 2 പവർ 4, 2 പവർ

So, this is contributes the value 1, this is 2 power 0, 2 power 1, 2 power 2, 2 power 3, 2 power 4, 2 power 5, 2 power 6 right. So, this is 64 plus 1, in binary this is 65. What we want to do is we want to compute x power 65.

5, 2 പവർ 6. ഇത് 64 + 1 ആണ്, ബൈനറിയിൽ (binary) ഇത് 65 ആണ്. x പവർ 65 കണക്കുകൂട്ടാൻ ഞങ്ങൾ ആഗ്രഹിക്കുന്നു. നിങ്ങൾ ഇത് ശ്രദ്ധാപൂർവ്വം

And if you write this carefully, this is equal to x power 64 plus 1; this is x power 64 multiplied

എഴുതുകയാണെങ്കിൽ, ഇത് x പവർ 64+ 1 ന് തുല്യമാണ്; ഇത് x64* x ആണ്. എക്‌സ്‌പോണന്റ് (exponent) 2 ന്റെ പവർ (power)

by x power 1 right.

ആവുമ്പോൾ കേസ് (case) എങ്ങനെ കൈകാര്യം

And we already know how to handle the case when the exponent is a power of 2; here also the exponent is a power of 2; recall that 1 is 2 power 0 right.

ചെയ്യണമെന്ന് ഞങ്ങൾക്കറിയാം; ഇവിടെയും എക്‌സ്‌പോണന്റ് (exponent) 2 ന്റെ പവർ (power) ആണ് ; 1 എന്നത് 2 0 ആണ്.

And we know how to handle this.

ഇത് എങ്ങനെ കൈകാര്യം ചെയ്യണമെന്ന് ഞങ്ങൾക്കറിയാം.

And this is a hint for you to complete the algorithm when n is not a power of 2 and implement

N 2 ന്റെ പവർ (power) അല്ലാത്തപ്പോൾ അൽ‌ഗോരിതം (algorithm) പൂർ‌ത്തിയാക്കി സി പ്രോഗ്രാമിംഗ് (C programming) ഭാഷയിൽ‌ നടപ്പിലാക്കുന്നതിനുള്ള

it in the C programming language.

ഒരു സൂചനയാണിത്.