இரு கிளை மரம் – பாகம் 2

ஏற்கெனவே இரு கிளை மரம் என்பதன் அமைப்பையும், வரிசையாக அணுகுதல் முறைகள் பற்றியும் சென்ற அத்தியாயத்தில் பார்த்தோம்.

இரு கிளை மரம் : வேர் ‘2’. இலை நுனிகள் ‘2’, ‘5’, ’11’, ‘4’.

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

இது போன்ற மரங்களில் உள்ள அதிக பட்ச அடுக்கு நிலைகளை எண்ணலாம் ? இந்த மரத்தின் இலை நுனிகள் எத்தனை ? இவற்றை எப்படி அணுகுவது ?

  1. நேர் வரிசையில் அணுகுதலை ஏற்கனேவே பெற்றுவிட்டோம். இதன் அடிப்படையில் தன் -முன் (pre-order traversal) என்பதை நிரல் படுத்தலாம்:
  2. நிரல்பாகம் தன்முன்_வரிசையில்_எடு(வேர்,ப)பதிப்பி “%d,”, வேர்[“மதிப்பு”]
    பின்இணை( ப, வேர்[“மதிப்பு”] )@( வேர்[“இடது_நுனி”] != [] ) ஆனால்
    தன்முன்_வரிசையில்_எடு( வேர்[“இடது_நுனி”] , ப)
    முடி

    @( வேர்[“வலது_நுனி”] != [] ) ஆனால்
    தன்முன்_வரிசையில்_எடு( வேர்[“வலது_நுனி”] , ப)
    முடி

    பின்கொடு ப
    முடி

  3. தன் பின் வரிசையில் அணுகுதலை இதே போல் எழுதலாம் :

 

நிரல்பாகம் தன்பின்_வரிசையில்_எடு(வேர்,ப)

@( வேர்[“இடது_நுனி”] != [] ) ஆனால்
தன்பின்_வரிசையில்_எடு( வேர்[“இடது_நுனி”] , ப)
முடி

@( வேர்[“வலது_நுனி”] != [] ) ஆனால்
தன்பின்_வரிசையில்_எடு( வேர்[“வலது_நுனி”] , ப)
முடி

பதிப்பி “%d,”, வேர்[“மதிப்பு”]
பின்இணை( ப, வேர்[“மதிப்பு”] )

பின்கொடு ப
முடி

மரம் உயரம்

மரம் தரவு வடிவத்தின் உயரம் என்பதை  எப்படி கண்டு பிடிப்பது ? இதனை induction என்ற கணிமை கூற்றினால் ஏற்கெனவே ‘வரிசையில் அணுகுதல்’ என்ற அல்கோரிதம் செய்தது போலவே அணுகலாம்.

  1. மரத்தில் 1 நுனி மட்டும் இருந்தால் அது வெறும் வேர் மட்டுமே உள்ளே மரம். இதன் உயரம் 1.
  2. மரம் என்பதற்கு 2, அல்லது 3 நுனிகள் இருந்தால் இதன் உயரம் 2.
  3. மரம் என்பதன் உயரம் அதன் உயரமான இடது கிளை நுனி அல்லது வலது கிளை நுனி என்பதன் மேல் ஒன்று கூடியது:
    1.  மரம் உயரம் = max ( வலது மரம் உயரம் , இடது மரம் உயரம்) + 1

மேல் கண்டா 3 கோட்பாடுகளை கொண்டு நம்மால் ஒரு அல்கோரிதம் எழுதலாம்,

#height of tree

நிரல்பாகம் தன்_உயரம்(வேர்)
இடது_உயரம் = 0
வலது_உயரம் = 0
@( வேர்[“இடது_நுனி”] != [] ) ஆனால்
இடது_உயரம் = தன்_உயரம்( வேர்[“இடது_நுனி”])
முடி

  @( வேர்[“வலது_நுனி”] != [] ) ஆனால்
வலது_உயரம்= தன்_உயரம்( வேர்[“வலது_நுனி”])
முடி

   பின்கொடு max( இடது_உயரம்,வலது_உயரம்) + 1
முடி

ஒரு மரம் என்பதற்கு அதன் இலை நுனிகளை எப்படி எடுப்பது  ?

#find leaves
நிரல்பாகம் இலை_நுனிகளை_எடு(வேர்,ப)
இடது_காலி = 0
@( வேர்[“இடது_நுனி”] != [] ) ஆனால்
இலை_நுனிகளை_எடு( வேர்[“இடது_நுனி”] , ப)
இல்லை
இடது_காலி = 1
முடி
வலது_காலி = 0
@( வேர்[“வலது_நுனி”] != [] ) ஆனால்
இலை_நுனிகளை_எடு( வேர்[“வலது_நுனி”] , ப)
இல்லை
வலது_காலி = 1
முடி
@( வலது_காலி && இடது_காலி) ஆனால்
பதிப்பி “%d,”, வேர்[“மதிப்பு”]
பின்இணை( ப, வேர்[“மதிப்பு”] )
முடி
பின்கொடு ப
முடி

இதே போல, ஒரு மரம் தரவு வடிவத்தில் ஒரு குறிப்பிட்ட மதிப்பு உள்ளதா என்று  எப்படி சொல்லுவது ? தேடல் என்பது நமக்கு இந்த செயல்புரியும் அல்கோரிதம்

# search for value
நிரல்பாகம் மரம்_தேடு(வேர்,மதிப்பு)
வலது = 0
இடது = 0
@( வேர்[“இடது_நுனி”] != [] ) ஆனால்
இடது = மரம்_தேடு ( வேர்[“இடது_நுனி”] , மதிப்பு )
முடி
@( வேர்[“வலது_நுனி”] != [] ) ஆனால்
வலது = மரம்_தேடு ( வேர்[“வலது_நுனி”] ,மதிப்பு )
முடி
@( வலது || இடது ) ஆனால்
பின்கொடு (வலது || இடது)
முடி

பின்கொடு வேர்[“மதிப்பு”] == மதிப்பு
முடி

மதிப்பு1 = 10
மதிப்பு2 = 1000
உள்ளதா1 = மரம்_தேடு(வேர், மதிப்பு1 )
உள்ளதா2 = மரம்_தேடு(வேர், மதிப்பு2 )
பதிப்பி மதிப்பு1, உள்ளதா1
பதிப்பி மதிப்பு2, உள்ளதா2

இந்த நிரல்களை நீங்கள் இங்கு எழில் மொழியில் காணலாம்.

 

 

தமிழில் அல்கொரிதம் (Algorithm) / செயல்முரை நூல் தொகுப்பு

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

Alan M. Turing : கணிமையின் பிதாமகன் / Father of Modern Computing Theory ( http://en.wikipedia.org/wiki/Alan_Turing )

இதில் கீழ்க்கண்டவற்றை பற்றியும் எழுதனும்.

0. GCD, Factorial
1. Binary Search
2. Sorting
3. Recursion
4. Graph notation
5. DFS
6. BFS

இதில் தரவு-அமைப்புகைள (Data Structures) பற்றியும் எழுதனும்.

0. Stacks
1. Queues
2. Linked lists
3. Binary Trees
4. Graphs

Github, Wikibooks தளங்கள் ஒன்றை விருப்பத் தேர்வு செய்யலாம்.https://github.com/thamizha/ezhil-book

எழில் மொழியிலும் இதனை எ.கா உருவாக்கலாம்.

நேரம் படிக்கும் கெடியாரம் – பாகம் 2

நேரம் படிக்கும் கெடியாரம் பலன்கள்

ஒரு ஆறு மணி நேரம் வேலை செய்து, பிரியா அவர்கள் குரல் அளித்தும், ஓப்பன் தமிழ் நிரல் தொகுப்பில் to_audio.py என்ற நிரல் வழியாக எண்கள் படிக்கும் ஒலி உருவாக்கியால் தயாரித்த 1000.45 success_Arun_Vekataswamy_8184568429எண் பேசியவாறு கீழே காணலாம்:

  1. ஆண் குரல் : 1000.45
  2. பெண் குரல்: 1000.45

அன்புடன்,
-முத்து

நேரம் படிக்கும் கெடியாரம்

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

Speaking Clock Speaking Clock

முதலில் இது என்ன செய்ய வேண்டும் என்பதை தீர்மானம் செய்யலாம்.

  1.  நேரம் சரியாக காட்ட வேண்டும்
  2.  நேரம் எண்களை சொற்களாக மாற்றனும்
  3.  நேரம் சரியாக படிக்க வேண்டும்

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

import datetime, time
time_as_string = time.ctime()
# access only the date
today = datetime.date.today()
dnt_now = datetime.datetime.now()
# access hour, minute, second and microsecond fields
dnt_now.hour, dnt_now.minute, dnt_now.second, dnt_now.microsecond

முதல் வேலை சரியாக முடிந்தது.

இப்போது, ஓப்பன் தமிழ் நிரல் தொகுப்பில் தசம எண்களின் வார்த்தைவடிவாக சொல்கிரது  எ.கா. 1001.45 -> ‘ஓர் ஆயிரத்தி ஒன்று புள்ளி நான்கு ஐந்து’. பைத்தான் (Python language) மொழியில் கீழ்கண்டவாரு எழுதினால்

import tamil
actual_IN2 = tamil.numeral.num2tamilstr(1001.45)
#gives -> ஓர் ஆயிரத்தி ஒன்று புள்ளி நான்கு ஐந்து

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

  1. units = (u’பூஜ்ஜியம்’, u’ஒன்று’, u’இரண்டு’, u’மூன்று’, u’நான்கு’, u’ஐந்து’, u’ஆறு’, u’ஏழு’, u’எட்டு’, u’ஒன்பது’, u’பத்து’) # 0-10
  2. teens = (u’பதினொன்று’, u’ பனிரண்டு’, u’பதிமூன்று’, u’பதினான்கு’, u’பதினைந்து’,u’பதினாறு’, u’பதினேழு’, u’பதினெட்டு’, u’பத்தொன்பது’) # 11-19
  3. tens = (u’பத்து’, u’இருபது’, u’முப்பது’, u’நாற்பது’, u’ஐம்பது’,u’அறுபது’, u’எழுபது’, u’எண்பது’, u’தொன்னூறு’) # 10-90
  4. tens_suffix = (u’இருபத்தி’, u’முப்பத்தி’, u’நாற்பத்தி’, u’ஐம்பத்தி’, u’அறுபத்தி’, u’எழுபத்தி’, u’எண்பத்தி’, u’தொன்னூற்றி’) # 10+-90+
  5. hundreds = ( u’நூறு’, u’இருநூறு’, u’முன்னூறு’, u’நாநூறு’,u’ஐநூறு’, u’அறுநூறு’, u’எழுநூறு’, u’எண்ணூறு’, u’தொள்ளாயிரம்’) #100 – 900
  6. hundreds_suffix = (u’நூற்றி’, u’இருநூற்றி’, u’முன்னூற்று’, u’நாநூற்று’, u’ஐநூற்று’, u’அறுநூற்று’, u’எழுநூற்று’, u’எண்ணூற்று’,u’தொள்ளாயிரத்து’) #100+ – 900+
  7. one_thousand_prefix = u’ஓர்’
  8. thousands = (u’ஆயிரம்’,u’ஆயிரத்தி’)
  9. one_prefix = u’ஒரு’
  10. lakh = (u’இலட்சம்’,u’இலட்சத்தி’)
  11. crore = (u’கோடி’,u’கோடியே’)

இதை எனக்கு யாரேனும் எனக்கு ரெக்காட் செய்து தந்தால் மகிழ்ச்சி. ஓப்பன்-தமிழ் கிட்ஹப் வழி அனுகவும்.

இப்போது பைத்தான் வழி கிடைத்த தேதி, நேரம் தகவல்களை நாம் ஓப்பன் தமிழ் வழியாக சொற்களாக மாற்றலாம். பின்னர் இவற்றின் (சொற்களை) ஒலி கொப்புகளை சேர்த்தால் இதுவே “பேசும் கேடியாரம்” ஆகும்.

வாங்க பழகலாம் – பங்களிக்கலாம்

Contributing to open-tamil : பங்களிக்கலாம்

You may have heard of open-tamil, the free Tamil text processing tools library for Python 2 and 3. If you want to join the project please fo

success_Arun_Vekataswamy_8184568429

llow the  directions.

  1. Create a github account from http://www.github.com, and send me your handle via email (ezhillang -AT- gmail.com)
  2. Learn about git – version control system (use Google if you don’t follow anything)
  3. Clone the repository from instructions at https://github.com/arcturusannamalai/open-tamil
  4. You should be all setup now; cd to the repository and try to install open-tamil locally in your Python setup
  5. Run the command, ‘python setup.py build’ first
  6. Upon success run the command, ‘python setup.py install’
  7. You may have to use sudo permissions in Linux if you are not using virtualenv

To use open-tamil, and understand the functions you may read the docs from blog post, and example code,

  1. Blog post on open-tamil (most important functions) : https://ezhillang.wordpress.com/2014/01/26/open-tamil-text-processing-%E0%AE%89%E0%AE%B0%E0%AF%88-%E0%AE%AA%E0%AE%95%E0%AF%81%E0%AE%AA%E0%AF%8D%E0%AE%AA%E0%AE%BE%E0%AE%AF%E0%AF%8D%E0%AE%B5%E0%AF%81/
  2. Example code using open-tamil package – try example code in directory called examples under the root of repo : https://github.com/arcturusannamalai/open-tamil/tree/master/examples

Hopefully you can get started on open-tamil with these resources. If not always leave a comment, drop an email @gmail.com for ezhillang, or tweet to me @ezhillang.

Anbudan,

-Muthu

Open-Tamil porting for Python 3 and Python 2

For a long time Open-Tamil package was envisioned and supported for both Python 3 and Python 2. Now in work done during last weekend (during harsh Boston winter what better than sit indoors and code away?) I have made the following changes,

  1. source code compatible for both Python 3 and Python 2,
  2. pass unittests on Python 2.6, 2.7, 3.3 and 3.4 with Travis-CI testing , and running successfully on Windows and Linux

This is still development bleeding edge software so please feel free to poke and play, and file bugs. Let us know if you are using open-tamil in your work.

-Muthu

ஹானொய் இன் கோபுரம் (Tower of Hanoi)

ஹனோய் கோபுரம் அறிமுக கணினி அறிவியலில் ஒரு சிறந்த பிரச்சனை. (Tower of Hanoi is a classic introductory computer science problem) see: http://en.wikipedia.org /wiki/Tower_of_Hanoi

பிரச்சனை நோக்கம், பின்வரும் நிலைமைகளின் கீழ், அச்சு # 3 மது # 1, முதல் வட்டுகள் அனைத்து நகர்த்த உள்ளது

R1: ஒரு சிறிய வட்டு பெரிய வட்டு மேல் உட்கார முடியாது
R2: நீங்கள் தற்காலிக அச்சு இரண்டு அச்சு ஏதாவது பயன்படுத்தலாம்
R3: நீங்கள் செய்ய முடியும் நகர்வுகள் எண்ணிக்கை இல்லை

Goal of the problem is to move all of disks from peg #1, to peg #3, under the following conditions,

  1. R1: Only a smaller disk can sit on top of the larger disk
  2. R2: You may use any of two pegs as temporary store
  3. R3: There is no limit on number of moves you can make
Tower of Hanoi (Ref: http://en.wikipedia.org/wiki/Tower_of_Hanoi)
Tower of Hanoi
(Ref: http://en.wikipedia.org/wiki/Tower_of_Hanoi)

How can you solve this problem ?

  1.  Let us reduced the size of the problem to 1 disk on the peg #1.
  2. We can make a drawing like [1,0,0].
  3. We can simply move the disk 1 from peg #1 to peg #3, and we have completed the problem!
  4. That was easy. [0,0,1].
  1. For 2 disks how do you solve it?
  2. We initially have [1 2, 0, 0]. we want to get to [0,0,1 2]
  3. By moving smaller disk 1 from peg #1, to peg #2, we have [2, 1, 0].
  4. Now your situation is same as problem with 1-disk on peg #1, and 1-disk on peg #2 which we will ignore temporarily.
  5. Next we can move either of disks from peg #1 or peg #2 to peg #3. However the rule, R1, requires us to move the peg #1 disk as it is the larger disk and it should go at bottom.
  6. Now your configuration is like, [0,1,2]
  7. Clearly the final step is to move disk #1 from peg #2 to peg #3, on top of the existing disk #2. Now your configuration is [0,0,1 2]. Solved!

So what does the general solution look like, for n-disks? Well the problem has a dynamic-programming structure, where solving smaller problems, inductively, leads to solution of the larger problem.

  1. Here, you need to move all n-1 smaller disks from peg #1 to peg #2,  and to do that, you will use peg #3 as temporary.
  2. Once you have achieved this, you have to move disk-n from peg #1 to peg #3.
  3. Now move (1,2, … n-1) disks from peg #2 to peg #3 using the peg #1 as intermediate.

This is a recursive solution and harder to visualize at first reading, but you will eventually get the hang of it.

Move 1,2,3 disks from peg #1 to peg #2, with peg #3 as intermediate. Move disk 4 from peg #1 to peg #4. Then move all disks from peg #2 to peg #3 using peg #1 as intermediate.
Move 1,2,3 disks from peg #1 to peg #2, with peg #3 as intermediate. Move disk 4 from peg #1 to peg #4. Then move all disks from peg #2 to peg #3 using peg #1 as intermediate.

The follow program describes the Ezhil program solution to Tower of Hanoi problem,

# (C) 2013 Ezhil Language Project
# Tower of Hanoi – recursive solution

நிரல்பாகம் ஹோனாய்(வட்டுகள், முதல்அச்சு, இறுதிஅச்சு,வட்டு)

@(வட்டுகள் == 1 ) ஆனால்
பதிப்பி  “வட்டு ” + str(வட்டு) + “ஐ \t  (” + str(முதல்அச்சு) + ”  —> ” +  str(இறுதிஅச்சு)+ “) அச்சிற்கு நகர்த்துக.”
இல்லை

@( [“இ”, “அ”,  “ஆ”]  இல் அச்சு ) ஒவ்வொன்றாக
@( (முதல்அச்சு != அச்சு)  && (இறுதிஅச்சு  != அச்சு) ) ஆனால்
நடு = அச்சு
முடி

முடி

# solve problem for n-1 again between src and temp pegs                      ஹோனாய்(வட்டுகள்-1, முதல்அச்சு,நடு,வட்டுகள்-1)

# move largest disk from src to destination
ஹோனாய்(1, முதல்அச்சு, இறுதிஅச்சு,வட்டுகள்)

# solve problem for n-1 again between different pegs
ஹோனாய்(வட்டுகள்-1, நடு, இறுதிஅச்சு,வட்டுகள்-1)
முடி
முடி

ஹோனாய்(4,”அ”,”ஆ”,0)

Try this program online, at, ezhillang.org Alternative solution by @tshrinivasan can be found towers_of_hanoi.n

Solution is illustrated in Fig. 2, with following output,

வட்டு 1ஐ       (அ  —> இ) அச்சிற்கு நகர்த்துக.
வட்டு 2ஐ       (அ  —> ஆ) அச்சிற்கு நகர்த்துக.
வட்டு 1ஐ       (இ  —> ஆ) அச்சிற்கு நகர்த்துக.
வட்டு 3ஐ       (அ  —> இ) அச்சிற்கு நகர்த்துக.
வட்டு 1ஐ       (ஆ  —> அ) அச்சிற்கு நகர்த்துக.
வட்டு 2ஐ       (ஆ  —> இ) அச்சிற்கு நகர்த்துக.
வட்டு 1ஐ       (அ  —> இ) அச்சிற்கு நகர்த்துக.
வட்டு 4ஐ       (அ  —> ஆ) அச்சிற்கு நகர்த்துக.
வட்டு 1ஐ       (இ  —> ஆ) அச்சிற்கு நகர்த்துக.
வட்டு 2ஐ       (இ  —> அ) அச்சிற்கு நகர்த்துக.
வட்டு 1ஐ       (ஆ  —> அ) அச்சிற்கு நகர்த்துக.
வட்டு 3ஐ       (இ  —> ஆ) அச்சிற்கு நகர்த்துக.
வட்டு 1ஐ       (அ  —> இ) அச்சிற்கு நகர்த்துக.
வட்டு 2ஐ       (அ  —> ஆ) அச்சிற்கு நகர்த்துக.
வட்டு 1ஐ       (இ  —> ஆ) அச்சிற்கு நகர்த்துக.

I hope you had fun!