ლექცია 7, Scheduling

Example 7.6.6

უბრალოდ მაგალითი უნდა წაიკითხოთ. მაგალითი არის დილვორსის ლემის (Dilworth).
ლემა გვეუბნება, რომ n წევრიან ნაწილობრივ დალაგებაში გვაქვს (მინიმუმ) √n სიგრძის ჯაჭვი ან ანტიჯაჭვი. მაგალითში განხილულია 101 სტუდენტიანი დალაგება, რომლის მიხედვითაც გვაქვს 11 სიგრძის ჯაჭვი ან ანტიჯაჭვი.

problem 7.16 (a,c,d,e)

ადვილია, ფენებად დავალაგებთ და მარტივად იხსნება

problem 7.21

a) ყველაზე კარგ ვარიანტში, როცა პრერეკვიზიტები უბრალოდ არ გვაქვს, პირველ ჯერზე ვაკეთებთ პირველ p ცალ დავალებას. მეორე ჯერზე - შემდეგ p ცალს. და ასე ვაკეთებთ იქამდე, სანამ გასაკეთებელი არ დაგვრჩება p-ზე ნაკლები ან ტოლი დავალება. ამ დავალებების გაკეთებასაც ერთი ჯერი უნდა - ამიტომაა n/p ზევით დამრგვალებული

b) უნიკალურია იმ მხრივ, რომ შეგვიძლია განვიხილოთ, გვიწევს დავალებების ასე განაწილება:
პირველ t-1-ჯერ ვაკეთებთ t-1 ცალ დავალებას სათითაოდ. მე-t-e დროს ვაკეთებთ დარჩენილებს,თუ p>n - (t - 1), თუ არადა დაგვჭირდება კიდევ [(n-(t-1))/p] დრო (ზევით დამრგვალებული იგულისხმება).

c) უკვე დავწერეთ - [(n-(t-1))/p] + t-1

d) დაამტკიცეთ, რომ იგივე დრო სჭირდება ნებისმიერ გრაფს, რომელსაც აქვს t ზომის ჯაჭვი.

ვამტკიცებთ ინდუქციით:
ამ შემთხვევაში t-1-ის მაგივრად t გვიწერია, რადგან t არის ჯაჭვის ზომა.
t=2; დრო = [(n-(t-1))/p] + t = [(n-1)/p] + 2 - რაც შინაარსობრივად, სწორია - ორი ოპერაცია ჯაჭვს, დანარჩენი - დანარჩენს.

t=k; დრო = [(n-(k-1)/p] + k  - დავუშვათ, სწორია

t=k+1; დრო [(n-k)/p] + k+1 - მაშინ ესეც შინაარსობრივად სწორია - ჯაჭვს უნდა ერთით მეტი დრო, ხოლო დანარჩენ ელემენტების ერთით ნაკლები არიან.