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

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

14.02.2022 წყლული

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

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

ყველაზე ხშირად, ალგორითმები ფასდება საჭირო მეხსიერების, შესრულებული ოპერაციების რაოდენობის, ამოხსნის დროის ან გამოთვლითი შეცდომით. ეს მახასიათებლები ხშირად დამოკიდებულია პრობლემის პარამეტრებზე (განზომილებებზე) და არაწრფივია. ამიტომ, ალგორითმების თეორიაში არის მიმართულება ალგორითმების ეფექტურობის შეფასების ფუნქციების ასიმპტოტური შეფასებით: საჭირო მეხსიერება, გამოთვლის დრო და ა.შ. ამ შემთხვევაში, ფუნქციის ყველაზე მნიშვნელოვანი პარამეტრი განისაზღვრება და ფუნქციის ქცევა შეისწავლება პარამეტრის მნიშვნელობების მატებასთან ერთად. კვლევის მსვლელობისას ისინი ცდილობენ დაადგინონ პარამეტრზე განსახილველი ალგორითმის მახასიათებლების მნიშვნელობების დამოკიდებულების ბუნება. ის შეიძლება იყოს წრფივი (ანუ n პარამეტრის პროპორციული), ლოგარითმული (ანუ log n-ის პროპორციული), კვადრატული (ანუ პროპორციული n 2-ის) და ა.შ. ალგორითმების ასიმპტოტური შეფასებების შედარებით, რომლებიც წყვეტენ ერთსა და იმავე პრობლემას, შეგიძლიათ აირჩიოთ უფრო ეფექტური ალგორითმი. ისინი ამბობენ, რომ ზოგიერთი პარამეტრის მნიშვნელობა T(n) არის n x რიგის, თუ არსებობს დადებითი მუდმივები k და n o ისეთი, რომ ყველა n³n o-სთვის მოქმედებს T(n) ≤ k n x უტოლობა.

დავუშვათ, რომ n არის რიცხვითი მონაცემების რაოდენობა, რომელიც მიღებულია რამდენიმე სხვადასხვა ალგორითმის შეყვანისას (A 1, A 2, A 3, A 4, A 5), რომლებიც ასრულებენ გამოთვლებს იმავე სიჩქარით - 1000 ოპერაცია წამში, მაგრამ აქვთ განსხვავებული. ასიმპტომური შეფასებები. ცხრილი 1.8 აჩვენებს n-ის მნიშვნელობებს, რომელთა დამუშავება ამ ალგორითმებს შეუძლიათ 1 წამში, 1 წუთში და 1 საათში (მნიშვნელობები დამრგვალებულია ქვევით უახლოეს მთელ რიცხვამდე). 1.3 ცხრილის მონაცემები ნათლად აჩვენებს, რომ ალგორითმის შესრულება (ანუ დამუშავებული მონაცემების რაოდენობა ერთეულ დროში) მნიშვნელოვნად არის დამოკიდებული ასიმპტომური შეფასების ფუნქციის ბუნებაზე.

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

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

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

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

ფონი

ეფექტურობის მნიშვნელობა შესრულების დროზე ხაზგასმული იყო ადა ლავლეისის მიერ 1843 წელს ჩარლზ ბაბეჯის მექანიკურ ანალიტიკურ ძრავასთან დაკავშირებით:

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

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

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

„დამკვიდრებულ საინჟინრო დისციპლინებში 12%-იანი გაუმჯობესება ადვილად მიიღწევა და არასდროს მიიჩნიეს აკრძალვით და მე მჯერა, რომ იგივე უნდა იყოს პროგრამირებაშიც“.

Მიმოხილვა

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

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

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

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

თეორიული ანალიზი

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

Დანიშნულება	სახელი	მაგალითები
O(1) (\displaystyle O(1)\,)	მუდმივი	რიცხვის ლუწი თუ კენტის დადგენა. მუდმივი ზომის საძიებო ცხრილის გამოყენებით. შესაბამისი ჰეშის ფუნქციის გამოყენება ელემენტის შესარჩევად.
O (log ⁡ n) (\displaystyle O(\log n)\,)	ლოგარითმული	ელემენტის პოვნა დალაგებულ მასივში ორობითი ძიების ან დაბალანსებული ხის გამოყენებით, მსგავსი ოპერაციების ორნომიალურ გროვაზე.
O(n) (\displaystyle O(n)\,)	ხაზოვანი	ელემენტის პოვნა დაუხარისხებელ სიაში ან გაუწონასწორებელ ხეში (უარეს შემთხვევაში). ორის დამატება ნ-ბიტი რიცხვები ბოლოდან ბოლომდე გადატანის გამოყენებით.
O (n log ⁡ n) (\displaystyle O(n\log n)\,)	კვაზიწრფივი, ლოგარითმულად წრფივი	გამოთვალეთ სწრაფი ფურიეს ტრანსფორმაცია, ჰეფსორტი, სწრაფი დალაგება (საუკეთესო და საშუალო შემთხვევა), შერწყმის დალაგება
O (n 2) (\displaystyle O(n^(2))\,)	კვადრატი	გამრავლება ორი ნციფრული რიცხვები მარტივი ალგორითმის გამოყენებით, ბუშტების დალაგება (ყველაზე ცუდი შემთხვევა), ჭურვის დალაგება, სწრაფი დალაგება (უარესი შემთხვევა), შერჩევის დალაგება, ჩასმის დალაგება
O (c n) , c > 1 (\displaystyle O(c^(n)),\;c>1)	ექსპონენციალური	დინამიური პროგრამირების გამოყენებით მოგზაური გამყიდველის პრობლემის (ზუსტი) გადაწყვეტის პოვნა. ამომწურავი ძიების გამოყენებით ორი ლოგიკური დებულების ეკვივალენტის დადგენა

ვერიფიკაციის ტესტები: შესრულების გაზომვა

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

ზოგიერთი საორიენტაციო ტესტი უზრუნველყოფს სხვადასხვა შედგენისა და ინტერპრეტაციის ენების შედარებით ანალიზს, როგორიცაა Roy Longbottom's PC Benchmark Collection, და კომპიუტერული ენის საორიენტაციო თამაშიადარებს პროგრამირების ზოგიერთ ენაში ტიპიური ამოცანების განხორციელების შესრულებას.

განხორციელების საკითხები

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

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

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

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

რესურსის გამოყენების გაზომვა

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

ორი ყველაზე მნიშვნელოვანი განზომილებაა:

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

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

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

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

გადაცემის ზომა: გამტარუნარიანობა შეიძლება იყოს შემზღუდველი ფაქტორი. შეკუმშვა შეიძლება გამოყენებულ იქნას გადაცემული მონაცემების რაოდენობის შესამცირებლად. გრაფიკის ან გამოსახულების ჩვენებამ (როგორიცაა Google-ის ლოგო) შეიძლება გამოიწვიოს ათიათასობით ბაიტის გადატანა (ამ შემთხვევაში 48K). შეადარეთ ეს სიტყვა "გუგლის" ექვსი ბაიტის გადაცემას.
გარე მეხსიერება: მეხსიერება საჭიროა დისკზე ან სხვა გარე შენახვის მოწყობილობაზე. ეს მეხსიერება შეიძლება გამოყენებულ იქნას დროებითი შესანახად ან სამომავლო გამოყენებისთვის.
Რეაგირების დრო: ეს პარამეტრი განსაკუთრებით მნიშვნელოვანია რეალურ დროში აპლიკაციებისთვის, სადაც კომპიუტერი სწრაფად უნდა რეაგირებდეს გარე მოვლენებზე.
Საკუთრების საერთო ღირებულება: პარამეტრი მნიშვნელოვანია, როდესაც ის გამიზნულია ერთი ალგორითმის შესრულებაზე.

დრო

თეორია

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

მეხსიერება

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

მეხსიერების გამოყენების ოთხი ასპექტია:

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

ადრეულ ელექტრონულ კომპიუტერებსა და სახლის კომპიუტერებს ჰქონდათ შედარებით მცირე სამუშაო მეხსიერების მოცულობა. ამრიგად, 1949 წელს EDSAC-ს ჰქონდა მაქსიმალური სამუშაო მეხსიერება 1024 17-ბიტიანი სიტყვით, ხოლო 1980 წელს Sinclair ZX80 გამოვიდა 1024 ბაიტი სამუშაო მეხსიერებით.

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

ქეში (ხშირად სტატიკური RAM) - მუშაობს CPU-სთან შედარებით სიჩქარით
ძირითადი ფიზიკური მეხსიერება (ხშირად დინამიური RAM) - მუშაობს ოდნავ ნელა ვიდრე CPU
ვირტუალური მეხსიერება (ხშირად დისკზე) - იძლევა უზარმაზარი მეხსიერების ილუზიას, მაგრამ მუშაობს ათასობით ჯერ უფრო ნელა ვიდრე RAM.

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

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

ეფექტური ალგორითმების მაგალითები

პროგრამირების ამჟამინდელი მდგომარეობის კრიტიკა

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

მაისი აცხადებს:

ფართოდ გავრცელებულ სისტემებში, ინსტრუქციის შესრულების განახევრებამ შეიძლება გააორმაგოს ბატარეის ხანგრძლივობა, ხოლო დიდი მონაცემები იძლევა უკეთესი ალგორითმების შესაძლებლობას: ოპერაციების რაოდენობის შემცირება N x N-დან N x log(N-მდე) აქვს ძლიერი ეფექტი დიდი N-ისთვის... N-ისთვის. =30 მილიარდი, ეს ცვლილებები 50 წლიანი ტექნოლოგიური გაუმჯობესების მსგავსია.

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

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

იხილეთ ასევე

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

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

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

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

მსგავსი დოკუმენტები

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

კურსის სამუშაო, დამატებულია 07/07/2013

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

ნაშრომი, დამატებულია 08/12/2017

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

რეზიუმე, დამატებულია 27/11/2012

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

ნაშრომი, დამატებულია 16/07/2014

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

კურსის სამუშაო, დამატებულია 21/06/2013

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

ტესტი, დამატებულია 16/12/2012

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

კურსის სამუშაო, დამატებულია 25/06/2013

ეფექტური ალგორითმების შექმნის ძირითადი პრინციპები

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

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

1. შესაძლებელია თუ არა პრობლემის ნაწილის გადაჭრა? შესაძლებელია თუ არა დანარჩენი პრობლემის გადაჭრა ზოგიერთი პირობის უგულებელყოფით?
2. შესაძლებელია თუ არა პრობლემის გადაჭრა განსაკუთრებული შემთხვევებისთვის? შესაძლებელია თუ არა ისეთი ალგორითმის შემუშავება, რომელიც გამოიმუშავებს გადაწყვეტას, რომელიც აკმაყოფილებს პრობლემის ყველა პირობას, მაგრამ რომლის შეყვანის მონაცემები შემოიფარგლება ყველა შეყვანილი მონაცემების ზოგიერთი ქვეჯგუფით?
3. არის თუ არა რაიმე დაკავშირებული პრობლემასთან, რაც კარგად არ არის გასაგები? თუ შევეცდებით უფრო ღრმად ჩავუღრმავდეთ პრობლემის ზოგიერთ მახასიათებელს, შევძლებთ თუ არა ვისწავლოთ ის, რაც დაგვეხმარება გადაჭრის გადაწყვეტაში?
4. არის თუ არა მსგავსი პრობლემის ცნობილი გადაწყვეტა? შესაძლებელია თუ არა მისი გადაწყვეტის შეცვლა განსახილველი პრობლემის გადასაჭრელად? შესაძლებელია თუ არა, რომ ეს პრობლემა ცნობილი გადაუჭრელი პრობლემის ექვივალენტური იყოს?

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

ზოგადად, აწევის მეთოდები კლასიფიცირდება როგორც "უხეში". მათ ახსოვთ რაღაც მიზანი და ცდილობენ ყველაფერი გააკეთონ, სადაც შეუძლიათ, მიზანთან მიახლოების მიზნით. ეს მათ გარკვეულწილად „შორსმჭვრეტელებს“ ხდის. აწევის მეთოდის შორსმჭვრეტელობა კარგად ჩანს შემდეგი მაგალითით. დავუშვათ, ჩვენ უნდა ვიპოვოთ ფუნქციის მაქსიმუმი ზე =/(X),წარმოდგენილი გრაფიკით (ნახ. 2.15). თუ არგუმენტის საწყისი მნიშვნელობა x = a,მაშინ ასვლის მეთოდი მისცემს მისწრაფებას უახლოეს მიზნამდე, ე.ი. წერტილის ფუნქციის მნიშვნელობამდე x = b,ხოლო ამ ფუნქციის ნამდვილი მაქსიმუმი არის = c. Ამ შემთხვევაში

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

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

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

მოდით მივუდგეთ ამ პრობლემას სამუშაო უკანა მეთოდის გამოყენებით. ბოლოდან რა მანძილზე შეიძლება უდაბნოს გადაკვეთა ზუსტად იგივე რაოდენობის საწვავით? რომტანკები? მოდით განვიხილოთ ეს კითხვა რომ= 1,2, 3,... სანამ არ ვიპოვით ასეთ მთელ რიცხვს P,Რა პსავსე ტანკები საშუალებას გაძლევთ გადალახოთ მთელი 1000 კილომეტრიანი უდაბნო. ამისთვის რომ= 1 პასუხი არის 500 კმ = 500 ლ (წერტილი IN),როგორც ნაჩვენებია ნახ. 2.16.

ბრინჯი. 2.16.

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

მოდი ვიჩვენოთ, რომ რომ= 2, ე.ი. არის ორი სავსე ავზი (1000 ლ). ეს სიტუაცია ილუსტრირებულია ნახ. 2.16. რა არის jCj-ის მაქსიმალური მნიშვნელობა ისე, რომ 1000 ლიტრი საწვავით დაწყებული წერტილიდან (500 - Xj), შესაძლებელი იყოს საკმარისი საწვავის გადატანა მოგზაურობის დასასრულებლად, როგორც რომ= 1. მისაღები მნიშვნელობის განსაზღვრის ერთი გზა X (არის შემდეგი. წერტილზე (500 - Xj) ვავსებთ საწვავს, მივდივართ X (კილომეტრები წერტილამდე INდა ჩაასხით მთელი საწვავი საცავში, გარდა იმ ნაწილისა, რომელიც საჭიროა წერტილის დასაბრუნებლად (500 - Xj). ამ დროს ავზი ცარიელი ხდება. ახლა ჩვენ ვავსებთ მეორე ავზს, მივდივართ Xj კილომეტრამდე IN, აიღეთ INსაწვავი დარჩა იქ და დან IN C-ზე მივდივართ სავსე ტანკით. გავლილი მთლიანი მანძილი შედგება სამი სეგმენტისგან X (კილომეტრი და ერთი სეგმენტი მზესიგრძე 500 კმ. მაშასადამე, განტოლებიდან 3x t + 500 = 1000 ვპოულობთ მის ამოხსნას Xj = 500/3. ამრიგად, ორი ავზი (1000 ლ) გაძლევთ საშუალებას იმოგზაუროთ Z> 2 = 500 +x (= 500(1 + 1/3) კმ.

განვიხილოთ k = 3. რა წერტილიდან შეიძლება 1500 ლიტრი საწვავით გასვლა, რომ ჯიპმა შეძლოს 1000 ლიტრი წერტილის მიტანა (500 - x))? ვიპოვოთ x 2-ის უდიდესი მნიშვნელობა ისეთი, რომ წერტილიდან 1500 ლიტრი საწვავის დატოვებით (500 - Xj - x 2), შეგვიძლია მივაწოდოთ 1000 ლიტრი წერტილიდან (500 - Xj). ვტოვებთ წერტილს (500 - Xj - x 2), მივდივართ (500 - x), გადავიტანთ ყველა საწვავს x 2 ლიტრის გარდა და ცარიელი ავზით ვუბრუნდებით წერტილს (500 - Xj - x 2). ამ პროცედურის გამეორებით მგზავრობაში დავხარჯავთ 4x2 ლიტრს და დავტოვებთ (1000 - 4x2) ლიტრს წერტილში (500 - x ლ). ახლა წერტილში (500 - Xj - x 2) დარჩა ზუსტად 500 ლიტრი. ჩვენ ვავსებთ ბოლო 500 ლიტრს და მივდივართ წერტილამდე (500 - Xj), რაზეც დავხარჯეთ x 2 ლიტრი.

წერტილში ყოფნისას (500 - Xj) მგზავრობისას ვხარჯავთ 5x 2 ლიტრ საწვავს. აქ სულ დარჩენილია (1500 - 5x 2) ლიტრი. ეს რაოდენობა უნდა იყოს 1000 ლ-ის ტოლი, ე.ი. x 2 = 500/5. აქედან ვასკვნით, რომ 1500 ლიტრი გაძლევთ საშუალებას მართოთ

ინდუქციურად უკუღმა მუშაობის პროცესის გაგრძელებით, მივიღებთ ამას პსაწვავის ავზები გავლის საშუალებას გვაძლევს დნკილომეტრი, სადაც დნ = 500(1 +1/3 + 1/5 + ... + 1/(2პ - 1)).

ჩვენ უნდა ვიპოვოთ ყველაზე მცირე მნიშვნელობა P,რომელიც დნ> 1000. მარტივი გამოთვლები აჩვენებს, რომ n = 7 გვაქვს დ?= 997,5 კმ, ე.ი. შვიდი ავზი, ანუ 3500 ლიტრი საწვავი მოგცემთ მოგზაურობის საშუალებას

977,5 კმ. სრული მერვე ავზი - ეს საჭიროზე მეტი იქნება წერტილიდან 3500 ლიტრის ტრანსპორტირებისთვის აწერტილამდე, რომელიც მდებარეობს
22,5 კმ (1000 - 977,5) A-დან მკითხველს ეძლევა შესაძლებლობა დამოუკიდებლად გადაამოწმოს, რომ 337,5 ლიტრი საკმარისია 3500 ლიტრი საწვავის 22,5 კმ ნიშნულამდე მიტანისთვის. ამგვარად, I-დან C-მდე მანქანით უდაბნოს გადაკვეთისთვის საჭიროა 3837,5 ლიტრი საწვავი.

ახლა საწვავის ტრანსპორტირების ალგორითმი შეიძლება წარმოდგენილი იყოს შემდეგნაირად. ჩვენ ვიწყებთ A, 3837,5 ლიტრიანი. აქ მხოლოდ იმდენი საწვავია, რომ 3500 ლიტრი ეტაპობრივად გადაიტანოს ნიშნულამდე

22,5 კმ, სადაც ჯიპი საბოლოოდ ცარიელი ავზით და 7 სრული შევსებისთვის საკმარისი საწვავით დასრულდება. ეს საწვავი საკმარისია 3000 ლიტრის გადასატანად 22,5 + 500/13 კმ წერტილამდე. A,სადაც მანქანის ავზი ისევ ცარიელი იქნება. შემდგომი ტრანსპორტირება ჯიპს მიიყვანს წერტილამდე, რომელიც მდებარეობს 22,5 + 500/13 + 500/11 კმ-ზე. A,მანქანის ცარიელი ავზით და 2500ლ საწყობში.

ასე ვაგრძელებთ, წინ მივდივართ უკან მუშაობის შედეგად ჩატარებული ანალიზის წყალობით. მალე ჯიპი 500(1 - 1/3) კმ ნიშნულზე იქნება 1000 ლიტრი საწვავით. შემდეგ ადგილზე გადავიტანთ 500 ლიტრ საწვავს IN,ჩავასხათ ისინი მანქანის ავზში და გავუჩერდეთ წერტილამდე თან(ნახ. 2.17).

ბრინჯი. 2.17.

მათთვის, ვინც იცნობს უსასრულო სერიებს, გაითვალისწინეთ ეს დᲘქ არის პ-კენტი ჰარმონიული რიგის ნაწილობრივი ჯამი. ვინაიდან ეს სერია განსხვავდება, ალგორითმი შესაძლებელს ხდის ნებისმიერი უდაბნოს გადაკვეთას. შეეცადეთ შეცვალოთ ეს ალგორითმი, რათა დატოვოთ საკმარისი საწვავი უდაბნოს სხვადასხვა წერტილში, რათა დაბრუნდეთ წერტილში ა.

ჩნდება კითხვა, შესაძლებელია თუ არა 1000 კილომეტრის გავლა 3837,5 ლიტრზე ნაკლები საწვავის გამოყენებით. თურმე არ შეგიძლია. ამ განცხადების მტკიცებულება საკმაოდ რთულია. თუმცა, შემდეგი, საკმაოდ დამაჯერებელი არგუმენტის მოყვანა შეიძლება. ცხადია, ჩვენ ვმოქმედებთ საუკეთესო გზაამისთვის რომ= 1. როცა რომ= 2 გეგმა გამოიყენება რომ= 1 და შემდეგ გააქტიურებულია საწვავის მეორე ავზი, რათა რაც შეიძლება შორს იყოს წერტილიდან IN.საწყისი წინაპირობა ამისთვის რომტანკები არის ის, რომ ჩვენ ვიცით, როგორ ვიმოქმედოთ საუკეთესო შემთხვევაში (რომ - 1) ტანკები და რაც შეიძლება შორს გადადით უკან დახმარებით Ჯანმოტანკი.

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