ალგორითმი

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

მარტივი ალგორითმის ბლოკ-სქემა.

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

განმარტება

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

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

ისტორია

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

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

სისტემატური შესწავლა

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

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

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

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

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

ალგორითმის მაგალითები

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

• ჰანოის ალგორითმი — ცნობილი ამოცანა, რომელიც აჩვენებს რეკურსიულ პროგრამირებას.
• დახარისხების ალგორითმი ანუ როგორ დავახარისხოთ რიცხვები რაც შეიძლება სწრაფად.
• რვა ქალი — როგორ განვალაგოთ ჭადრაკის დაფაზე 8 ქალი ისე, რომ მა
• რეკურსიული ალგორითმი — რამდენიმე მარტივი უსასრული ალგორითმის გამოთვლაში წარმოდგენა.
• სემპლიქსური ალგორითმი, რაც ნამდვილი რიცხვების წრფივ ფუნქციას ამცირებს.

ალგორითმული სირთულე

კონკრეტული ალგორითმის გამოთვლაში არის მთავარი მათემატიკური ცნებები (აღნიშნული 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 პროგრამაც ეყრდნობა ასევე ევრისტიკულს რათა ამოიცნოს ის ინფორმაციული ვირუსი, რომელიც არ არის ცალკე კონკრეტულად გამოტოფილი მის ბაზაში.

გამოყენება

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

იხილეთ აგრეთვე

• ალ-ხორეზმი
• რეკურსიული ალგორითმი
• ალგორითმების სია
• ძებნის ალგორითმი
• ოპერაციული კვლევა
• კონტროლის სტრუქტურა

რესურსები ინტერნეტში

• Eléments d'Algorithmique ალგორითმის ელემენტები სრული წიგნი ალგორითმზე PDF
• სავარჯიშოები ალგორითმზე საფრანგეთის ნაკრების სავარჯიშოები ინფორმატიკის საერთაშორისო ოლიმპიადაზე.
• ალგორითმულის საწყისი კოდი დაარქივებული 2007-05-09 საიტზე Wayback Machine.
• ალგორითმის შესავალი დაარქივებული 2007-05-09 საიტზე Wayback Machine. , მაგალითები C-ის ენაზე
• ალგორითმის საწყისები

ალგორითმი ვიქსიკონში