Friday 7 March 2014

(#5)Pigeonhole Principle

Pigeonhole Principle


පරවියන් රඳවා තබනු ලබන කුඩා කුටි  Pigeonholes  ලෙස හඳුන්වයි.අපි  n පරවියන් ප්‍රමාණයක් m Pigeonholes ප්‍රමාණයකට දමන්නේනම්  n > m  වෙයිනම් අඩු තරමින් එක Pigeonhole එකක හෝ පරවියන් එකකට වැඩියෙන් රැදී සිටිය යුතුය. මෙය Pigeonhole principle  ලෙස හැඳින්වෙයි.

මෙය සම්භාවිතා මූලධර්ම ඇසුරෙන් මෙලෙස පැහැදිලි කරගතහැකිය. n පරවියන් ප්‍රමාණයක් අහඹු ලෙස m Pigeonholes ප්‍රමාණයකට 1/m  යන ඒකාකාර සම්භාවිතාවකින් යුතුව දමන්නේ නම් එක Pigeonhole එකක හෝ පරවියන් එකකට වඩා රඳවා තබාගැනීමේ සම්භාවිතාව   
      1 – ( mn/mnවෙයි.
       මෙහි  mn  = mCn   වෙයි.

මෙලෙස එක Pigeonhole එකකට පරවියන් එකකට වඩා යොමුවීමක් collision එකක් ලෙස හඳුන්වයි. මෙමෙ මූලධර්මය අපි hash tables වලටද යෝදාගන්නෙමු.පහත උදාහරණයෙන් පැහැදිලිකරගනිමු.

  • What is the probability that no two hash keys collide(එකම storage location එකකට hash keys දෙකක් යොමුවීම.)?

මෙහිදී අසනු ලබන්නේ keys දෙකක් එකම slot එකකට යොමු නොවීමේ සම්භාවීතාවයි.
 h(k) = k mod 5
slots  5ක් ඇති table එකක් සලකමු.

  • පළමු item එක දැමීමේදී slot 5ම හිස් නිසා collide වීමක් සිදු නොවේ.එම නිසා collide නොවීමේ සම්භාවිතාව = 5/5 = 1 වෙයි.
  • දෙවන item එක දැමීමේදී හිස්ව ඇත්තේ slot 4ක් පමණි.එම නිසා collide වීමේ සම්භාවිතාව  1/5 කි.
  • එමනිසා collide නොවීමේ සම්භාවිතාව  = 4/5 ක්  වෙයි.
මෙලෙස,
  • 3 වන item එක දැමීමේදී collide නොවීමේ සම්භාවිතාව  = 3/5
  • 4වන item එක දැමීමේදී collide නොවීමේ සම්භාවිතාව  = 2/5
  • 5 වන item එක දැමීමේදී collide නොවීමේ සම්භාවිතාව  = 1/5
එමනිසා collide නොවීමේ මුළු සම්භාවිතාව = 5/5 * 4/5 * 3/5 * 2/5 * 1/5
                                                                         = 0.0384

එමනිසා keys 5ක් add කිරීමේදී එක collision එකක්
හෝ ඇති වීමේ සම්භාවිතාව  = 1- P5  = 1- 0.0384 = 0.9616

Collisions

hashing  වලදී මෙම collision ඇති කිරීම මගින් keys ප්‍රමාණයට වඩා slots අඩුවෙන් ඇති table එකක වුවද අපිට සියලුම keys store කරගතහැකිය. එමගින් අවශ්‍යකරන memory space එක අඩුකරගතහැකිය. යම්කිසි hash table එකක ඇතිවන collisions ප්‍රමාණය අවම වෙයිනම් hash table එක හොඳින් ක්‍රියා කරන්නේයැයි කියනු ලැබේ.එමගින් O(1) search time එකක් ලබාගතහැකිය.මෙහි worste case එක O(n) විය හැකිය.එය දුර්වල hash table එකක් ලෙස හඳුන්වයි.එමෙන්ම මෙම collisions විසඳා ගැනීමටද අප ක්‍රමවේදයන් කිහිපයක් අනුගමනය කරයි.

Handling the Collisions

i.Open Addressing
ii.Chaining
iii.Bucket Addressing



Sunday 2 March 2014

(#4) Variables ,Data types ,Data type convertion

අප ලියන programme වලදී අපිට විවිධාකාරයේ data store කර තබාගැනීමට සිදුවෙයි.මෙවැනි data එකක් store කිරීම සඳහා memory space එකක් වෙන්කරගැනීම variable එකක් declare කිරීම ලෙස හැඳින්වෙයි.එලෙස වෙන් කරන ලද memory space එකක් තුළ data එකක් store කිරීම variable එකක් assign කිරීම ලෙස හැඳින්වෙයි.මෙහිදී විවිධාකාර data store කිරීම සඳහා විවිධාකාර වූ data types යොදා ගනියි.

Assigning Values to Variables:

අනෙකුත් languages වලමෙන් python වල variable එක මුලින් declare කර පසුව assign කිරීමක් සිදු කල නොහැකිය.variable එක declare කරන අවස්ථාවේම value එකද assign කල යුතුය.එමෙන්ම variable එකෙහි data type එක අපට define කල නොහැකි අතර අප එයට assign කරන value එක අනුව compiler එක මගින් data type එක හඳුනාගැනීම සිදු කරයි.

syntax:

variableName = value

උදා:

#!/usr/bin/python

counter = 100          # An integer assignment
miles   = 1000.0       # A floating point
name    = "John"       # A string

print counter
print miles
print name
Output:

100
1000.0
John

Multiple Assignment:

එකවර variables කිහිපයකට වුවද එකම අගය assign කල හැක.
උදා:
a = b = c = 1
පහත උදාහරණයේදී 
a=1
b=2
c="john"
ලෙස අගයන් assign වීම සිදුවෙයි.
 a, b, c = 1, 2, "john"

Standard Data Types:

python වල ප්‍රධාන data types 5ක් පවතියි.


  • Numbers
  • String
  • List
  • Tuple
  • Dictionary

Python Numbers:

මෙම data type එක සංක්‍යාත්මක අගයන් store කිරීම සඳහා යොදා ගනියි.

var1 = 1
var2 = 10
ඔබට del   යන key word එක යොදාගෙන assign කරනලද variables delete කිරීමද සිදු කල හැකිය.
del var1[,var2[,var3[....,varN]]]]
ඔබට මෙම key word එක යොදාගනිමින් object එකකට වඩා වැඩි ගණනක් වුවද delete කල හැක.
del var
del var_a, var_b
මෙහිදී numeric datatypes වර්ග හතරකි.
  • int (signed integers)
  • long (long integers [can also be represented in octal and hexadecimal])
  • float (floating point real values)
  • complex (complex numbers)

Examples:

Here are some examples of numbers:
intlongfloatcomplex
1051924361L0.03.14j
100-0x19323L15.2045.j
-7860122L-21.99.322e-36j
0800xDEFABCECBDAECBFBAEl32.3+e18.876j
-0490535633629843L-90.-.6545+0J
-0x260-052318172735L-32.54e1003e+26J
0x69-4721885298529L70.2-E124.53e-7j

Python Strings:

string එකක් assign කිරීමේදී single quotation හෝ double quotation යොදාගත යුතුය. (+) ලකුණ මගින් string දෙකක් join කල හැකි අතර (*) ලකුණ මගින් එකම string එක කිහිප වාරයක් print කරගත හැකිය.
#!/usr/bin/python

str = 'Hello World!'

print str          # Prints complete string
print str[0]       # Prints first character of the string
print str[2:5]     # Prints characters starting from 3rd to 5th
print str[2:]      # Prints string starting from 3rd character
print str * 2      # Prints string two times
print str + "TEST" # Prints concatenated string
This will produce the following result:
Hello World!
H
llo
llo World!
Hello World!Hello World!
Hello World!TEST

Python Lists:

එකම variable එකක් තුළ data කිහිපයක් store කරගැනීමට list එකක් භාවිතා කරයි.

syntax:
list = [item1,item2, item3]

#!/usr/bin/python

list = [ 'abcd', 786 , 2.23, 'john', 70.2 ]
tinylist = [123, 'john']

print list          # Prints complete list
print list[0]       # Prints first element of the list
print list[1:3]     # Prints elements starting from 2nd till 3rd 
print list[2:]      # Prints elements starting from 3rd element
print tinylist * 2  # Prints list two times
print list + tinylist # Prints concatenated lists
This will produce the following result:
['abcd', 786, 2.23, 'john', 70.200000000000003]
abcd
[786, 2.23]
[2.23, 'john', 70.200000000000003]
[123, 'john', 123, 'john']
['abcd', 786, 2.23, 'john', 70.200000000000003, 123, 'john']

Python Tuples:

tuples , list වලටම සමාන data type එකක් වන අතර නමුත් tuple එකක් assign කල පසු එයට අලුතින් data add කිරීම හෝ තිබෙන data delete කිරීමක් සිදුකල නොහැක.නමුත් list එකක assign කරන data වලට අමතරව අලුතින් data add කිරීම මෙන්ම තිබෙන data delete කිරීමද සිදු කල හැකිය.

syntax:
tuple = (item1,item2, item3) මෙයට සාමාන්‍ය වරහන යොදාගනී.

#!/usr/bin/python

tuple = ( 'abcd', 786 , 2.23, 'john', 70.2  )
tinytuple = (123, 'john')

print tuple           # Prints complete list
print tuple[0]        # Prints first element of the list
print tuple[1:3]      # Prints elements starting from 2nd till 3rd 
print tuple[2:]       # Prints elements starting from 3rd element
print tinytuple * 2   # Prints list two times
print tuple + tinytuple # Prints concatenated lists
This will produce the following result:
('abcd', 786, 2.23, 'john', 70.200000000000003)
abcd
(786, 2.23)
(2.23, 'john', 70.200000000000003)
(123, 'john', 123, 'john')
('abcd', 786, 2.23, 'john', 70.200000000000003, 123, 'john')
Following is invalid with tuple, because we attempted to update a tuple, which is not allowed. Similar case is possible with lists:
#!/usr/bin/python

tuple = ( 'abcd', 786 , 2.23, 'john', 70.2  )
list = [ 'abcd', 786 , 2.23, 'john', 70.2  ]
tuple[2] = 1000    # Invalid syntax with tuple
list[2] = 1000     # Valid syntax with list

Python Dictionary:

dictionary එකක් යනු එකවර data විශාල ප්‍රමාණයක් store කරගත් හැකි data type එකකි.එය table එකකට සමාන වෙයි.
dictionary එක assign කිරීම සඳහා {} යොදාගන්නා අතර එයට data add කිරීම සඳහා [] යොදාගනියි.
උදා:

#!/usr/bin/python

dict = {}
dict['one'] = "This is one"
dict[2]     = "This is two"

tinydict = {'name': 'john','code':6734, 'dept': 'sales'}


print dict['one']       # Prints value for 'one' key
print dict[2]           # Prints value for 2 key
print tinydict          # Prints complete dictionary
print tinydict.keys()   # Prints all the keys
print tinydict.values() # Prints all the values
This will produce the following result:
This is one
This is two
{'dept': 'sales', 'code': 6734, 'name': 'john'}
['dept', 'code', 'name']
['sales', 6734, 'john']
Dictionaries have no concept of order among elements. It is incorrect to say that the elements are "out of order"; they are simply unordered.

Data Type Conversion:

එක් data type එකකින් assign කර ඇති data එකක් තවත් data type එකක් බවට පරිවර්තනය කල හැක.ඒ සඳහා python වල සකසන ලද විශේෂ functions කිහිපයක් පවතී. ඒවා පහත දැක්වෙයි.

FunctionDescription
int(x [,base])
Converts x to an integer. base specifies the base if x is a string.
long(x [,base] )
Converts x to a long integer. base specifies the base if x is a string.
float(x)
Converts x to a floating-point number.
complex(real [,imag])
Creates a complex number.
str(x)
Converts object x to a string representation.
repr(x)
Converts object x to an expression string.
eval(str)
Evaluates a string and returns an object.
tuple(s)
Converts s to a tuple.
list(s)
Converts s to a list.
set(s)
Converts s to a set.
dict(d)
Creates a dictionary. d must be a sequence of (key,value) tuples.
frozenset(s)
Converts s to a frozen set.
chr(x)
Converts an integer to a character.
unichr(x)
Converts an integer to a Unicode character.
ord(x)
Converts a single character to its integer value.
hex(x)
Converts an integer to a hexadecimal string.
oct(x)
Converts an integer to an octal string.




(#3)Basic Syntax

Python Identifiers:

programming වලදී යම්කිසි object එකක් හැඳින්වීමට යොදාගන්නා නමක් පොදුවේ
Identifier එකක් ලෙස හඳුන්වයි.මෙය variable එකක් function එකක් class එකක් හෝ object එකක් විය හැකිය.මේවාට නම් ලබාදීමේදී අපට කැමති නම් ලබාදිය නොහැකි අතර ඒ සඳහා නීති මාලාවක් පවතියි.ඒවා පහත ලෙස වෙයි
  • identifier එකක් ආරම්භ කළ යුත්තේ ඉංග්‍රීසි capital (A-Z) අකුරකින් simple (a-z) අකුරකින් හෝ underscore(_) එක මගින් පමණි වෙනත් කිසිඳු character එකකින් ආරම්භ කළ නොහැක.
  • එක අකුරක් පමණක් වුවද identifier එකට ප්‍රමාණවත් වෙයි.තවත් අකුරු යොදන්නේ නම් ඒ සඳහා අකුරු underscore එක මෙන්ම 0 සිට 9 දක්වා වූ ඕනෑම ඉලක්කමක් හෝ ඉලක්කම් කිහිපයක් වුවද ඇතුලත් කල හැක.
  • පෙර කී අකුරු හා symbols හැරුණු විට වෙනත් කිසිම character එකක් identifiers හැදින්වීමට යොදාගත නොහැක.
identifiers case sensitive වෙයි . එනම් capital හා simple අකුරු වෙනස් වශයෙන් සලකයි.Man හා man යනු එකිනෙකට වෙනස් identifiers දෙකක් වෙයි.
 
identifiers නම් කිරීමේදී බලපාන තවත් නීති.
  • class name එකක පළමු අකුර capital විය යුතු අතර අනෙක් සියළුම අකුරු simple විය යුතුය.
  • identifier එකක් underscore එකකින් ආරම්භ කරයිනම් එය private identifier එකක් ලෙස සලකයි.
  • identifier එකක් underscore දෙකකින් ආරම්භ කරයිනම් එය strongly private identifier එකක් ලෙස හඳුන්වයි.
key words ලෙස වෙන්කර ඇති වචන කිහිපයක් ඇති අතර ඒවා identifiers ලෙස භාවිතා කල නොහැක.
පහත දැක්වෙන්නේ එම වචනයි.
andexecnot
assertfinallyor
breakforpass
classfromprint
continueglobalraise
defifreturn
delimporttry
elifinwhile
elseiswith
exceptlambdayield

Lines and Indentation:

python වල code blocks වෙන් කිරීමට වරහන් හෝ කමා භාවිතා නොකරයි.එම සියල්ල වෙන් කිරීම indentation වලින් සිදුකරන අතර එම නිසා නිවැරදිව indentation තැබීම ඉතා වැදගත් වෙයි.

එකම කොටසට අයිතිවෙන හැම code line එකකටම සමාන indentation එකක් තිබිය යුතුය.
උදා;

if True:
    print "True"
else:
  print "False"
මෙය නිවැරදිය.

if True:
    print "Answer"
    print "True"
else:
    print "Answer"
  print "False"
නමුත් ඉහත else එක යටතේ ඇති code lines දෙකෙහි indentation දෙක එකිනෙකට වෙනස් නිසා error එකක් පෙන්වයි.කෙසේ වෙතත් IDLE එක භාවිතයේදී එය නිවැරදි තැනට curser එක auto යොමු කරන නිසා ඒ ගැන වැඩි වශයෙන් බියවිය යුතු නැත.

Quotation in Python:

python වල වචන වාක්‍ය ආදී strings දැක්වීමේදී single quotation (') එක හෝ double quotation (") එක යන දෙකෙන් ඕනෑම එකක් භාවිතා කල හැකි අතර මේ දෙකෙන් එකක් හෝ නොදමයි නම් error එකක් පෙන්වයි.
word = 'word'
sentence = "This is a sentence."
paragraph = """This is a paragraph. It is
made up of multiple lines and sentences."""

Comments in Python:

මෙහි ඇතුලත් වන්නේ single line comments පමණි. comment කල යුතු හැම වාක්‍යයක් ඉදිරියෙන්ම # ලකුණ යෙදිය යුතුය.
#!/usr/bin/python

# First comment
print "Hello, Python!";  # second comment
This will produce the following result:
Hello, Python!
A comment may be on the same line after a statement or expression:
name = "Madisetti" # This is again comment
You can comment multiple lines as follows:
# This is a comment.
# This is a comment, too.
# This is a comment, too.
# I said that already.