ალგორითმი

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

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

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

განმარტება[რედაქტირება]

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

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

ისტორია[რედაქტირება]

ალგორითმები, რომელთა შესახებ ამომწურავი განმარტებები არის აღმოჩენილი, გამოყენებულია ჯერ ჯიდევ უძველესი(ბაბილონის) პერიოდიდან ვაჭრობასა თუ ბეგარასთან დაკავშირებულ გამოთვლებში. ყველაწე ცნობილი ალგორითმი ეს არის ევკლიდეს მე-7 წიგნში „ელემენტები“. ის საშუალებას გვაძლევს ვიპოვოთ ორი რიცხვის ყველაზე დიდი საერთო გამყოფი. აღსანიშნავიამ რომ ის შეიცავს იტერაციას და 1 და 2 გამონათქვამი აჩვენებს კრებადობას.

სისტემატური შესწავლა[რედაქტირება]

ალგორითმმა სისტემატური სახე მიიღო სპარსი მათემატიკოსის ალ-ხორეზმის მიერ (780-850). ის იყო ავტორი წიგნისა „ალგებრა და ბალანსირება“, რომელიც აღწერს ალგებრული გამოთვლების მეთოდებს.

არაბი მეცნიერი ავეროესი (1126-1198) მსჯელობის შედეგად ხვეწავს თეზას ალგორითმის მიმდინარეობის პარალელურად. იმავე პერიოდში, XII საუკუნეში ბერმა ადელარდ დე ბათმა შემოიტანა ლათინური ტერმინი „ალგორისმუს“ (ალ-ხორეზმის სახელის გავლენით).

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

აღსანიშნავია, ადა ლავლეისისა (ბაირონის ქალიშვილი) და შარლ ბაბაჟის ასისტენტის, მიერტერმინი ალგორითმის გამოყენება.

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

ალგორითმის მაგალითები[რედაქტირება]

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

ალგორითმული სირთულე[რედაქტირება]

კონკრეტული ალგორითმის გამოთვლაში არის მთავარი მათემატიკური ცნებები (აღნიშნული 0(f(n)), სადაც f არის n-ის მათემატიკური ფუნქცია, ცვლადი, რომელიც გამოხატავს ინფორმაციის გარკვეულ რაოდენობას (ბიტებში, ჩანაწერის რაოდენობაში და ა.შ), რომელიც მანიპულირებს ალგორითმში ხშირად გვხვდება შემდეგი ტიპის სირთულეები:

ჩამონათვალი სირთულის ტიპი
O(1) მუდმივი სირთულე (არ არის დამოკიდებული მონაცემის ზომაზე)
O(log(n)) ლოგარითმული სირთულე
O(n) წრფივი განტოლება
O(n log(n)) ნახევრად-წრფივი განტოლება
O(n^{2}) კვადრატული სირთულე
O(n^{3}) კუბური სირთულე
O(n^p) პოლინომური სირთულე
O(n^{\log(n)}) ნახევრად პოლინომური სირთულე
O(2^{n}) ექსპონენციალური განტოლება
O(n!) ფაქტორიალი

მათემატიკურ დეტალების განხილვის გარეშე შეიძლება ვთქვათ, რომ როდესაც ვითვლით ალგორითმის სირთულეს, ვეძებთ გავიგოთ 2 მნიშვნელოვანი მონაცემი: თავდაპირველად, საბაზისო ინსტრუქციების რაოდენობის ზრდა დასამუშავებელ მონაცემებთან მიმათებაში (მაგ.: დახარისხების ალგორითმში დასახარისხებელი ხაზების რაოდენობა), შემდეგ გამოთვლებისათვის საჭირო მეხსიერების რაოდენობის შეფასება.

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

სტატიაში სირთულის თეორიაზე ვნახავთ სირთულის სხვა შეფასებებს, რომლებიც ზემოთ ჩამოთვლილ საკითხებზე უფრო შორს მიდიან და რომლებიც ყოფენ ამოცანებს (და არა ალგორითმებს) სირთულის კლასებად.

რამდენიმე მინიშნება ალგორითმის შედეგიანობაზე[რედაქტირება]

ხშირად, ალგორითმის შედეგიანობა განისაზღვრება მხოლოდ ასიმპტომატიური ხერხით ე.ი. n-პარამეტრის დიდი მნიშვნელობით. როდესაც ეს პარამეტრი საკმარისად პატარაა, რეალურად მაღალი სირთულის ალგორითმი შეიძლება იყოს უფრო შედეგიანი. ამგვარად, 30 ხაზიანი ცხრილის დასახარისხებლად (ეს პატარა ზომის პარამეტრია) არ არის საჭირო ისეთი ალგორითმის გამოყენება, როგორიცაა სწრაფი დახარისხება (დახარისხების ერთ-ერთი შედეგიანი ალგორითმი), ყველაზე მარტივი დალაგების ალგორიტმიც საკმარისად შედეგიანი იქნება.

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

სხვა გასათვალისწინებელი პარამეტრია ალგორითმის ადგილმდებარეობა. მაგალითად, ვირტუალური მეხსიერების სისტემისათვის, რომელსაც ცოტა მეხსიერება აქვს (შედარებით მონაცემთა რაოდენობასთან) სწრაფი დახარისხების მეთოდით იქნება უფრო შედეგიანი, ერთიანი დახარისხებით, რადგან პირველი გაივლის მხოლოდ ერთხელ მეხსიერების თითოეულ ელემენტზე, მაშინ როდესაც მეორე აღწევს მეხსიერებას წყვეტილ რეჟიმში (ეს კი ზრდის ვირტუალური მეხსიერების swapping-ის რისკს).

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

ევრისტიკული მეთოდი[რედაქტირება]

ზოგიერთი ამოცანისთვის ალგორითმები რეალურ დროში შედეგის მისაღებად ბევრად უფრო დიდ სირთულეს ხვდებიან, თუნდაც ფენომენალური შესაძლებლობების გამოთვლების გამოყენებისას. ასე თანმიმდევრული მცდელობებით მივდივართ გამოსავლის პოვნისაკენ, რომელიც ძალიან ახლოსაა ოპტიმქლურ გამოსავალთან. ვინაიდან ყველა კომბინაციის გამოყენაბა შეუძლებელია, მხოლოდ ზოგიერთი სტრატეგიული არჩევანი უნდა გაკეთდეს. ეს არჩევანი, რომელიც ზოგადად დამოკიდებულია ამოსახსნელ ამოცანაზე, იმას რასაც ვეძახით ევრისტიკულ მეთოდს (heuristique). ასე, რომ ამ მეთოდის მიზანი არ არის ყველა შესაძლო კომბინაციის გამოცდა, სანამ არ მოიძებნება ის, რომელიც ამოცანის ამოხსნას პასუხობს, რათა მოძებნილ იქნას მიახლოებული ამოხსნა(რომელიც ზოგ შემთხვევაში) რეალურ დროში. ამგვარად, ჭადრაკის თამაშისას სვლებს (ყველა რომ არ ჩამოთვალო) საერთო აქვს ევრისტიკულ მეთოდთან, რაც განისაზღვრება მოთამაშის გამოცდილებით. ზოგი antivirus პროგრამაც ეყრდნობა ასევე ევრისტიკულს რათა ამოიცნოს ის ინფორმაციული ვირუსი, რომელიც არ არის ცალკე კონკრეტულად გამოტოფილი მის ბაზაში.

გამოყენება[რედაქტირება]

იხილეთ აგრეთვე[რედაქტირება]

რესურსები ინტერნეტში[რედაქტირება]