ალგორითმები

ალგორითმები 

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

ტერმინი ალგორითმი მე–9 საუკუნის შუა აზიელი მოაზროვნის მუხამედ ბენ მუსა ალ-ხორეზმის სახელის ლათინურ ტრანსკრიფციას უკავშირდება (Algorithmi). როგორც ცნობილია, ალ–ხორეზმმა ჩამოაყალიბა არითმეტიკული მოქმედებების წესები. მისმა ტრაქტატმა არითემტიკაში და ალგებრაში, რომელიც მე–12 საუკუნეში ლათინურ ენაზე თარგმნეს, მნიშვნელოვანი გავლენა იქონია მათემატიკის განვითარებაზე დასავლეთ ევროპაში. აქედან გამომდინარე, თავდაპირველად ალგორითმის ქვეშ გულისხმობდნენ მრავალნიშნა რიცხვებზე მხოლოდ ოთხი არითმეტიკული მოქმედების შესრულების წესებს.

ამჟამად, ტერმინი ალგორითმი სხვადასხვა სახის, ცალკეული წესების, საზოგადო სახელია და იგი შემდეგნაირად არის განმარტებული: ალგორითმი გარკვეულ მითითებათა სასრული მიმდევრობაა, რომლის შესრულება საშუალებას გვაძლევს, მივიღოთ მოცემული ამოცანის ამონახსნი. ალგორითმი არის გამოსახულება, რომელიც შედგება მოქმედებების თანმიმდევრობისაგან და გამოთვლებით ამოცანის ამოხსნის საშუალებას იძლევა.

თუ ეს ოპერაციები ხორციელდება ნაწილ-ნაწილ, ასეთ ალგორითმს წყვეტილ ალგორითმს ეძახიან . თუ ოპერაციები ხორციელდება პარალელურად სხვადასხვა პროცესორზე, ალგორითმს პარალელურ ალგორითმს ეძახიან. თუ ოპერაციები სრულდება ერთ ქსელზე, ალგორითმს ეწოდება განაწილების ალგორითმი.

როგრამირებაში დინამიური მასივი ისეთი მონაცემთა სტრუქტურაა, რომელსაც ცვლადი სიგრძე აქვს, მასში ელემენტების ჩამატება / წაშლა და random access შეიძლება – ანუ მის ნებისმიერ ელემენტზე წვდომას ფიქსირებული დრო სჭირდება და მასივის მთლიან ზომაზე არ არის დამოკიდებული.

ასეთ სტრუქტურას სხვადასხვა დასახელებით შეხვდებით – dynamic array, growable array, resizable array, dynamic table, mutable array, array list.

random access-ის უზრუნველსაყოფად მასივისთვის მეხსიერების უწყვეტი ნაწილი გამოიყოფა, ანუ, მისი ელემენტები მეხსიერებაში ერთმანეთის მიყოლებით ინახება.
სტატიკური მასივის შემთხვევაში ეს პრობლემას არ წარმოადგენს, რადგან ჩვენ თავიდანვე ვეუბნებით სიგრძეს. დინამიურ მასივს კი სწორედ მაშინ ვიყენებთ, როდესაც წინასწარ არ შეგვიძლია ზომის განსაზღვრა. მაშინ რამხელა მეხსიერება უნდა გამოიყოს, რომ ელემენტები კვლავ მიყოლებით არსებულ ბაიტებში იქნას შენახული?

ცხადია, თავის დაზღვევის მიზნით დიდი მეხსიერების გამოყოფას აზრი არ აქვს. 20 ელემენტის შენახვისთვის მილიონი ბაიტი წინასწარ არ უნდა დარეზერვდეს ასეთი მასივისთვის, რომელიც შემდეგ ცარიელი დარჩება.

ბევრ პროგრამირების ენაში ეს პრობლემა შემდეგნაირად არის გადაწყვეტილი:
დინამიური მასივის უკან სტატიკური მასივი დგას, რომელიც დასაწყისში მცირე სიგრძის მითითებით იქმნება. როდესაც მასივი გაივსება და შემდეგ კვლავ შეეცდებიან მასში ელემენტის ჩამატებას, შეიქმნება უფრო დიდი ზომის სტატიკური მასივი, მასში გადაიწერება არსებული მასივის ელემენტები და ძველი წაიშლება. შესაბამისად, დინამიურ მასივში ზოგიერთი ელემენტის ჩამატებას შედარებით მეტი დრო მიაქვს.

ასეთ გადაწყვეტაში მნიშვნელოვანია შეკითხვაზე პასუხი: რამდენჯერ უნდა გაიზარდოს მასივი გადაწერის წინ?

აღვნიშნოთ, რომ ისევ კომპრომისს ვეძებთ დროის და მეხსიერების ხარჯვას შორის. თუ თითო-თითოდ გავზრდით მასივს, ყოველ ახალ ელემენტზე მთელი მასივის გადაწერა დროს წაიღებს, ხოლო თუ რამდენჯერმე დავაგრძელებთ, შეიძლება დიდი ზომის მეხსიერება ცარიელი დაგვრჩეს.

ოპტიმალურ ვარიანტად რიცხვი 2 არის მიღებული. ამ რიცხვს ზრდიან ამ ამცირებენ იმის მიხედვით მეტი მეხსიერების ხარჯი ურჩევნიათ თუ დროის.

სხვადასხვა პროგრამირების ენაში ან რეალიზაციაში ის ზოგჯერ განსხვავებულია – მაგალითად, ვექტორი c++-ში 2-ჯერ იზრდება, Java-ს ვექტორისთვისაც default მნიშვნელობა ეს რიცხვია, თუმცა პარამეტრის სახით არის და შეცვლა შეიძლება. Java-ს ArrayList-ის სტატიკური მასივი 3/2-ჯერ იზრდება. HashMap-ის მასივი 2-ჯერ. პითონის C-ის იმპლემენტაციაში რაღაც უცნაურად არის, 9/8 გამოდის საშუალოდ. ამ ბმულზეა კოდი. აქ კი მისი გარჩევა

თუ პროგრამისტისთვის წინასწარ არის ცნობილი მინიმუმ რამხელა მასივი დასჭირდება, შეუძლია ეს გაითვალისწინოს და დინამიური მასივი თავიდანვე იმხელა შეიქმნას.
მაგალითად c++-ის vector-ს აქვს ფუნქცია reserve რომლითაც წინასწარ შეიძლება მეხსიერების რეზერვირება.

Java-ში ArrayList და HashMap ობიექტებს კონსტრუქტორში გადაეცემა initialCapacity პარამეტრი. HashMap-ში არა მხოლოდ მასივის გადაწერა, არამედ ჰეშების თავიდან გენერაცია ხდება.

წარმადობისთვის ამ პარამეტრის წინასწარ მითითება უმჯობესია. რამდენიმე ექსპერიმენტი ჩავატარე და მართლაც მივიღე დროში სხვაობა, თუმცა ჩემს ჩვეულებრივ ამოცანებში ასეთი სხვაობა უმნიშვნელოა. ბოლო ბოლო ლოგარითმული რაოდენობით ხდება მასივის გადაწერა და მილიონის შემთხვევაშიც კი ეს სულ რაღაც 20-ია. თუ მილიწამები მნიშვნელოვანია, იქ ღირებული იქნება ასეთი ოპტიმიზაცია.

ზევით ვახსენეთ, რომ დინამიურ მასივში ამ გადაწერის საჭიროების შედეგად ზოგიერთი ელემენტის ჩამატების დროს O(1)-დან იზრდება O(n)-მდე, სადაც n მასივში არსებული ელემენტების რაოდენობაა. ამის მიუხედავად, ამორტიზებული ანალიზის შედეგად, დინამიურ მასივში ელემენტის ჩამატების დრო O(1)-ად არის მიჩნეული.

თვითონ ამორტიზებული ანალიზის არსი იმაში მდგომარეობს, რომ ალგორითმის მუშაობის შეფასებისას გათვალისწინებული იქნას ის სწრაფი ოპერაციებიც, რომელიც ყველაზე ცუდი შემთხვევების მუშაობის დროს აბათილებენ. ალგორითმის შესრულების დროის შეფასებისას worst-case სცენარს ვიღებთ ხოლმე, თუმცა შეიძლება რომ დასამუშავებელ ინფორმაციაში მხოლოდ რაღაც პროპორციით იყოს მძიმე ოპერაციები. შესაბამისად, თუ ჩვენ ყველა ოპერაციას გავითვალისწინებთ შეფასების დროს, შესაძლოა მუშაობის დრო გაცილებით ნაკლები გამოვიდეს, ვიდრე რაოდენობა გამრავლებული ყველაზე დიდ დროზე.

მოდი გამოვთვალოთ n ელემენტიანი დინამიური მასივის შევსების დრო:
თუ ჩავთვლით რომ ყოველ ჯერზე (როდესაც ორის ხარისხს მივაღწევთ) სტატიკური მასივი ორმაგდება, შეგვიძლია ელემენტების გადაწერის რაოდენობა ასე შევაფასოთ:
ბოლოდან მოვყვეთ. ბოლოს ყველას გადაწერა მოუწევს, იმის წინ მხოლოდ ნახევრის, იმის წინ მეოთხედის და ა.შ.
n + n/2 + n/4 + n/8 + … = n (1 + 1/2 + 1/4 + 1/8 + …) = 2n

ამ გადაწერებს მივუმატოთ თვითონ ელემენტების ჩასმაც და გამოვა 3n. შესაბამისად საშუალოს თუ ავიღებთ, თითოეული ელემენტის ჩასმისთვის გამოგვივა O(3) = O(1) დრო.

გამოწენებული წყარო elles blog.

თანმიმდევრული, საფეხურებრივი პროცედურა, რომლის საშუალებითაც ვპოულობთ სწორ პასუხს კონკრეტული ტიპის პრობლემის გადასაჭრელად. დღეისათვის თანამედროვე ენაში გამოიყენება ტერმინი algorithm, რომელიც „მეთოდს, წესს“ გულისხმობს და სხვადასხვა სახის, ცალკეული წესების კრებითი სახელია. ეს არის გამოსახულება, რომელიც მოქმედებების თანმიმდევრობისგან შედგება და გამოთვლებით ამოცანის ამოხსნის საშუალებას იძლევა. ალგორითმის გამოყენება უფრო ეფექტურია კარგად განსაზღვრული პრობლემის გადასაჭრელად, სადაც მკაფიოდ არის გამოკვეთილი საწყისი მდგომარეობა და მიზანი. ის ნაკლებად ეფექტურად მუშაობს ბუნდოვნად განსაზღვრული პრობლემის შემთხვევაში, როცა ალგორითმის ნაცვლად ევრისტიკული მეთოდი გამოიყენება.

მაგალითად, ამოსახსნელი გაქვთ განტოლება ×2+×-12=0. თუ ალგებრის წესები იცით და მათ სწორად გამოიყენებთ, აუცილებლად შეძლებთ x-ის სწორი მნიშვნელობის (ანუ 3-ისა და -4-ის) მიღებას. ალგორითმის გამოყენება საკეტის დავიწყებული კოდის მოძებნაშიც დაგეხმარებათ, თუ თანმიმდევრულად ცდით ციფრების სხვადასხვა კომბინაციას. ამ შემთხვევაში საკეტს აუცილებლად გახსნით, თუმცა ამისათვის, სავარაუდოდ, დიდი დრო დაგჭირდებათ, ვინაიდან ამ მაგალითში (წინა მაგალითისგან განსხვავებით) ნაკლებად განსაზღვრული სიტუაცია გვაქვს.

ალგორითმი, როგორც წესი, უნდა აკმაყოფილებდეს შემდეგ მოთხოვნებს: (1) სასრულობა ანუ ალგორითმი უნდა გულისხმობდეს სასრული ნაბიჯების შემდეგ დამთავრებას; (2) განსაზღვრულობა ანუ ალგორითმის ყოველი ბიჯი უნდა იყოს ზუსტად განსაზღვრული, (3) შემავალი მონაცემები (input) ანუ მკაფიოდ უნდა იყოს მოცემული საწყისი მდგომარეობა, ამომწურავად უნდა იყოს დახასიათებული მოცემული ამოცანა და (4) გამომავალი მონაცემები (output) ანუ განსაზღვრული უნდა იყოს,  რას ვიღებთ ალგორითმის მუშაობის დასრულების შემდეგ.

ალგორითმის ცნების წარმოშობა IX საუკუნის შუააზიელი მოაზროვნის, ცნობილი მეცნიერის აბუ ჯაფარ მუჰამედ იბნ მუსა ალ-ხორეზმი ალ-მაჯუსის (783-850 წწ) სახელის ლათინურ ტრანსკრიფციას უკავშირდება. ხორეზმი დღვანდელი უზბეკეთის ტერიტორიაზე მდებარეობს, ხოლო ალ-ხორეზმი სიტყვა სიტყვით „ხორეზმში მცხოვრებს“ ნიშნავს. XII საუკუნეში ლათინურად ითარგმნა ალ-ხორეზმის მიერ არითმეტიკასა და ალგებრაში არაბულ ენაზე შექმნილი ტრაქტატები, რომლებიდანაც ევროპელი მეცნიერები თვლის ინდურ პოზიციურ ათობით სისტემასა და ამ სისტემაში თვლის მეთოდებს გაეცნენ. ალ-ხორეზმის არითმეტიკული ტრაქტატის ლათინური თარგმანი იწყებოდა სიტყვებით: „Dixit algorizmi…“ ანუ „და თქვა ალხორიზმმა...“ აქედან გამომდინარე, თავდაპირველად, სიტყვა „ალგორითმი“ ათობითი პოზიციური სისტემისა და არითმეტიკული ოპერაციების ალგორითმის ანუ წესების აღწერისთვის გამოიყენებოდა, ხოლო მოგვიანებით — ნებისმიერ ალგორითმის აღსანიშნად. 

გამოყენებული ლიტერატურა: 

გერიგი, ზიმბარდო (2009). ფსიქოლოგია და ცხოვრება, თსუ. თბილისი.