ლექცია 23, Sums & Asymptotics

 ეს ლექციაც ვიკადრე :)



ამ ლექციაში მთელი მუღამი ისაა, რომ იცოდეთ 4 სახის მიმართება ფუნქციებს შორის:
პატარა o, დიდი O, ~ (რა ქვია არ ვიცი და ტოლობას დავუძახებ) და Θ (ზეტა - theta).

ტოლობა ~

თუ 2 ფუნქცია იზრდება თანაბარი სისწრაფით, ანუ f(x)/g(x) = 1 უსასრულოდ დიდი x-ებისთვის, მაშინ f~g და g~f.

პატარა o.

თუ f(x)/g(x) = 0, როცა x მიისწრაფის პლიუს უსასრილობისკენ, მაშინ:

f(x) = o(g(x))

იგივეა რაც ვთქვათ, რომ g(x) უფრო სწრაფად იზრდება

დიდი O

თუ f(x)≤ cg(x) რაღაც c კონსტანტისთვის, მაშინ f = O(g)

მაგალითად, 100*x^2 = O(x^2). თუ c>=100, მაშინ 100*x^2<=c*x^2.

იგი შეგვიძლია ასეც განვსაზღვროთ: f(x)/g(x) < ∞. ანუ x-ის ზრდასთან ერთად ფუნქციათა შეფარდება უსასრულოდ არ იზრდება.

და ზეტა Θ

ფორმალურად f = Θ(g) iff  f = O(g) and g = O(f).

არაფორმალურად, თუ ორი ფუნქციის ტოლობა დამოკიდებულია კონსტანტებზე, მაშინ მათ შორის დამოკიდებულებას ასახავს ზეტა.

მაგ: თუ T(n) = 10*n^3 − 20*n^2 +1. მაშინ T(n) = Θ(n^3)

ეს ყველაფერი თუ ვიცით, ლექცია რთული არაა

Problem 15.7

ადვილი ამოცანაა, თითოეული შემთხვევისთვის შეაფარდებთ f(x)-ს g(x)-თან და პირიქით და დაადგენთ მიმართებას.

Problem 15.8 (b,c)

b) არის თუ არა ნაწილობრივი დალაგება R მიმართება ფუნქციებს შორის, თუ f R g მაშინ და მხოლოდ მაშინ, თუ f(x)=o(g(x))

იმისთვის, რომ ეს იყოს ნაწილობრივი დალაგება, უნდა სრულდებოდეს ასიმეტრიულობა და ტრანზიტულობა.
დავიწყოთ ტრანზიტულობით. ამ პირობის დასაკმაყოფილებლად, თუ
f(x) = o(g(x)) და g(x) = o(k(x), მაშინ f(x) = o(k(x))

თუ f(x) = o(g(x)), მაშინ g(x) უფრო სწრაფად იზრდება, ვიდრე f(x).
თუ g(x) = o(k(x)), მაშინ k(x) უფრო სწრაფად იზრდება, ვიდრე g(x).
ლოგიკურია, რომ k(x) უფრო სწრაფად იზრდება, ვიდრე f(x).
ტრანზიტულობა დაცულია. ახლა შევამოწმოთ ასიმეტრიულობა.

ასიმეტრიულობა ნიშნავს, რომ თუ f(x) = o(g(x)) მაშინ g(x) =/= o(f(x)), რაც გვისრულდება - g(x) ვერ გაიზრდება f(x)-ზე ერთდროულად უფრო სწრაფად და უფრო ნელა.

ორივე პირობა სრულდება, ანუ გვაქვს ნაწილობრივი დალაგება.

c) დაამტკიცეთ, რომ f ~ g მაშინ და მხოლოდ მაშინ, თუ f = g + h, სადაც h რაღაც ფუნქციაა: h=o(g).

ესე იგი, ვინაიდან h=o(g), გამოდის, რომ g ბევრად უფრო სწრაფად იზრდება, ვიდრე h და ძალიან დიდი რიცხვებისთცის, h/g=0, ანუ g-სთან შედარებით, იგი ნულია. შესაბამისად, თუ f = g + 0 ----> f = g. თუ ორი ფუნქცია ტოლია, მათი შეფარდება ყოველთვის 1 იქნება. თუ ფუნქციათა შეფარდება 1-ია, ისინი ტოლები არიან.

Problem 15.10 (a,b)

Let f, g be nonnegative real-valued functions such that f(x)= ∞ (უსასრულოდ დიდი x-ებისთვის) and f ∼ g.

ა) მოიყვანეთ f და g-ს ისეთი მაგალითები, რომ NOT(2^f ∼ 2^g).
f(x) = x^2 და g(x) = 2*x. მაშინ f ბევრად უფრო სწრაფად გაიზრდება.

ბ) Prove that log f ∼ log g.
თუ f~g ეს ნიშნავს რომ f/g->1.
გავალოგარითმოთ ორივე მხარე log(f/g)->0
log(f/g) იშლება როგორც log(f) - log(g).
log(f) - log(g) -> 0
log(f) -> log(g). გავყოთ ორივე მხარე log(g)-ზე და მივიღებთ, რომ
log(f) / log(g) ->1

მადლობა random citizen-ს.


ესეც ასე ხალხო, მთელი დისკრეტული მათემატიკა ავტვირთეთ. მართალია ცოტა შეგვაგვიანდა და 3-4 ამოცანა ამოუხსნელია, მაგრამ დიდი უმრავლესობა ამ საიტზე დევს. აბა თქვენ იცით, წარმატებები.