EITC/IS/CCTF გამოთვლითი სირთულის თეორიის საფუძვლები

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

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

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

კიდევ ერთი მნიშვნელოვანი რესურსი არის კომპიუტერის მეხსიერების რაოდენობა, რომელიც საჭიროა ალგორითმების შესასრულებლად.

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

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

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

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

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

უარეს შემთხვევაში სირთულე არის მთელი სირთულის ჯამი ყველა ზომის n შეყვანისთვის, ხოლო საშუალო შემთხვევის სირთულე არის მთელი სირთულის ჯამი n ზომის ყველა შეყვანისთვის (ეს აზრი აქვს, რადგან მოცემული ზომის შესაძლო შეყვანის რაოდენობა არის სასრული). როდესაც ტერმინი „სირთულე“ გამოიყენება შემდგომი განმარტების გარეშე, მხედველობაში მიიღება ყველაზე უარესი დროის სირთულე.

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

ამ მიზეზების გამო, ყველაზე მეტი ყურადღება ექცევა სირთულის ქცევას მაღალი n-ისთვის, ანუ მის ასიმპტომურ ქცევას, როდესაც n უახლოვდება უსასრულობას. შედეგად, დიდი O აღნიშვნა ჩვეულებრივ გამოიყენება სირთულის აღსანიშნავად.

გამოთვლითი მოდელები

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

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

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

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

მაშინაც კი, თუ ასეთი გამოთვლითი მოდელი ამჟამად არ არის პრაქტიკული, მას აქვს თეორიული მნიშვნელობა, განსაკუთრებით P = NP პრობლემასთან დაკავშირებით, რომელიც სვამს კითხვას, არის თუ არა სირთულის კლასები, რომლებიც წარმოიქმნება "პოლინომიური დროის" და "არადეტერმინისტული პოლინომიური დროის" გამოყენებით, როგორც მინიმუმ ზედა. საზღვრები იგივეა. დეტერმინისტულ კომპიუტერზე NP-ალგორითმის სიმულაცია მოითხოვს "ექსპონენციალურ დროს". თუ ამოცანის ამოხსნა შესაძლებელია მრავალწევრულ დროში არადეტერმინისტულ სისტემაზე, ის მიეკუთვნება NP სირთულის კლასს. თუ საკითხი არის NP-ში და არ არის ადვილი ვიდრე ნებისმიერი სხვა NP პრობლემა, ნათქვამია, რომ ის არის NP-სრული. Knapsack-ის პრობლემა, მოგზაური გამყიდველის პრობლემა და ლოგიკური დაკმაყოფილების პრობლემა არის ყველა NP-სრული კომბინატორიული პრობლემები. ყველაზე ცნობილ ალგორითმს აქვს ექსპონენციალური სირთულე ყველა ამ პრობლემისთვის. თუ რომელიმე ამ ამოცანის ამოხსნა შესაძლებელია პოლინომიურ დროში დეტერმინისტულ მანქანაზე, მაშინ ყველა NP ამოცანები შეიძლება გადაწყდეს მრავალწევრულ დროშიც და დადგინდეს P = NP. 2017 წლის მდგომარეობით, ფართოდ არის ვარაუდი, რომ P NP, რაც გულისხმობს, რომ NP პრობლემების ყველაზე უარესი სიტუაციები ფუნდამენტურად რთულია გადასაჭრელად, ანუ, გაცილებით მეტი დრო სჭირდება, ვიდრე ნებისმიერი შესაძლო დრო (ათწლეულები) საინტერესო შეყვანის ხანგრძლივობის გათვალისწინებით.

პარალელური და განაწილებული გამოთვლები

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

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

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

კვანტური გამოთვლა

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

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

პრობლემის სირთულე (ქვედა საზღვრები)

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

შედეგად, ნებისმიერი სირთულე, რომელიც მოცემულია დიდი O ნოტაციით, წარმოადგენს როგორც ალგორითმის, ასევე თანმხლები პრობლემის სირთულეს.

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

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

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

დახარისხების ალგორითმისთვის საჭირო შედარებების რაოდენობას აქვს Ω(nlogn) არაწრფივი ქვედა ზღვარი. შედეგად, საუკეთესო დახარისხების ალგორითმები ყველაზე ეფექტურია, რადგან მათი სირთულე არის O(nlogn). ის ფაქტი, რომ არსებობს n! n ნივთის ორგანიზების გზები ამ ქვედა ზღვარს მივყავართ. რადგან ყოველი შედარება ყოფს n-ის ამ კოლექციას! შეკვეთები ორ ნაწილად, N შედარებების რაოდენობა, რომელიც საჭიროა ყველა ბრძანების გასარჩევად, უნდა იყოს 2N > n!, რაც გულისხმობს O(nlogn) სტერლინგის ფორმულით.

პრობლემის სხვა პრობლემამდე შემცირება არის საერთო სტრატეგია შემცირებული სირთულის შეზღუდვების მისაღებად.

ალგორითმის შემუშავება

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

ხშირი გაუგებრობაა, რომ მურის კანონის შედეგად, რომელიც პროგნოზირებს თანამედროვე კომპიუტერული ენერგიის ექსპონენციალურ ზრდას, ალგორითმების სირთულის შეფასება ნაკლებად აქტუალური გახდება. ეს არასწორია, რადგან გაზრდილი სიმძლავრე იძლევა უზარმაზარი რაოდენობის მონაცემების (დიდი მონაცემების) დამუშავების საშუალებას. მაგალითად, ნებისმიერი ალგორითმი კარგად უნდა ფუნქციონირებდეს წამზე ნაკლებ დროში რამდენიმე ასეული ჩანაწერის სიის ანბანურად დახარისხებისას, როგორიცაა წიგნის ბიბლიოგრაფია. მეორეს მხრივ, მილიონი ჩანაწერისთვის (მაგალითად, დიდი ქალაქის ტელეფონის ნომრები), ძირითადი ალგორითმები, რომლებიც საჭიროებენ O(n2) შედარებებს, უნდა შეასრულონ ტრილიონი შედარება, რასაც დასჭირდება სამი საათი 10 სიჩქარით. მილიონი შედარება წამში. მეორე მხრივ, სწრაფი დახარისხება და შერწყმის დალაგება მოითხოვს მხოლოდ nlogn შედარებებს (როგორც პირველის საშუალო სირთულის, მეორესთვის ყველაზე უარეს შემთხვევაში). ეს აწარმოებს დაახლოებით 30,000,000 შედარებას n = 1,000,000-ისთვის, რასაც დასჭირდება მხოლოდ 3 წამი წამში 10 მილიონი შედარებისთვის.

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