Irakli Koiava

Voronoi Diagram ვორონოის დიაგრამა ( Voronoi Diagram ) არის სივრცის დაყოფის ერთერთი გზა. თუ მოცემული გვაქვს m ელემენტიანი წერტილების(პირობითად ვუწოდოთ მათ გენერატორები) მიმდევრობა n განზომილებიან სივრცეში მაშინ შეგვიძლია სივრცე დავყოთ ისეთ m რეგიონებად, სადაც ყოველ გენერატორს შეესაბამება ერთ რეგიონი და სრულდება პირობა: ყოველი რეგიონის ნებისმიერი წერტილისათვის მისი შესაბამისი გენერატორი არის უახლოესი მოცემულ m გენერატორს შორის. წერტილები რომლებიც თანაბრად არიან დაშორებული 2 გენერატორიდან შეადგენენ სეგმენტებს(segments). წერტილები რომლებიც თანაბრად არიან დაშორებული 3 (ან მეტი) წერტილიდან ეწოდებათ ვორონოის კვანძები(nodes). სახელი ვორონოი მოდის ცნობილი უკრაინელი მათემატიკოსის გიორგი ვორონოის გვარიდან. ვორონოის დიაგრამა არის პრაქტიკულად იგივე რაც დელონის ტრიანგულაცია . სურათზე ნაჩვენებია ვორონოის დიაგრამა ორგანზომილებიან სივრცეში. შავი ფერის წერტილებით აღნიშნულია გენერატორები. ვორონოის რეგიონები გაფერადებულია სხვადასხვა ფერით. ვორონოის დიაგრემებს ძალიან ფართო გამოყენება აქვს კომპიუტერ

Delta Encoding         დელტა კოდირება არის მონაცემთა ტრანსფორმაციის მეთოდი რომელიც მონაცემებს ინახავს საწყისი მონაცემების სხვაობების სახით. ის არ განეკუთვნება მონაცემთა შეკუმშვის ჯგუფს, თუმცა აქტიურად გამოიყენება შეკუმშვისას როგორც მონაცემთა პირველადი ტრანსფორმაციის მეთოდი, ამის გამო მას დელტა შეკუმშვასაც( delta compression ) უწოდებენ. ვთქვათ მოცემული გვაქვს A={ a 1 , a 2 , ..., a n } მიმდევრობა, მაშინ დელტა კოდირების საშუალებით მიიღება B = { b 1 , b 2 , ... , b n } მიმდევრობა რომლის ნებისმიერი b i - წევრი  უდრის (A i -A i-1 )-ს, სადაც i იცვლება 1-დან n-მდე. სწორედ მისი ასეთი ფუნქციონალობის გამო მნიშვნელობათა სიმრავლე იზრდება 2-ჯერ. თუმცა მას გააჩნია კარგი თვისებებიც რომელიც ამ მეთოდს აქტუალურობას უნარჩუნებს. პირველი კარგი თვისება არის ის რომ მისი იმპლემენტაცია არის ძალიან ადვილი(რაც სტატიის ბოლოს მოყვანილ კოდში კარგად ჩანს). მეორე ყველაზე მთავარი მისი თვისება არის ის რომ თუკი დავაკვირდებით მონაცემთა განაწილების სტატისტიკას ვნახავთ რომ ის ამცირებს მონაცემთა გაბნევის მაჩვენებელს .

Heap Sort         დალაგება გროვებით როგორც სათაურიდანაც კარგად ჩანს დაფუძნებულია გროვებზე . გროვებით სორტირების პრინციპი შემდეგია: პირველ რიგში ჩვენ ვაგებთ გროვას, რასაც ჭირდება O(n) დრო. შემდეგ ვაგდებთ მაქსიმუმს(გროვის ძირს) გროვიდან, გადაგვაქვს დალაგებული მასივის თავში(ამას ჭირდება O(log()) დრო) და ამ პროცესს ვიმეორებთ მანამ, სანამ გრობვა არ დაცარიელდება. პრაქტიკულად გროვის დალაგება ხდება იგივე მასივის ბოლოში რომელშიც მოწესრიგებულია თავად გროვა. დროის ეს შეფასება არის ბევრად უფრო სტაბილური ვიდრე ჩქარი დალაგებისას სადაც უარეს შემთხვევაში დრო O(n^2)-მდეც კი ადის, რაც გროვებში არასდროს ხდება. თუმცა შემთხვევითი რიცხვებისათვის ის უფრო ნელია ჩქარ დალაგებასთან შედარებით. ქვემოთ მოცემულ სურათზე ნაჩვენებია გროვებით დალაგების ალგორითმის მუშაობის პროცესი ანიმაციურად.         მოვიყვანოთ ალგორითმის განხორციელების კონკრეტული მაგალითი. პროგრამული კოდი დაწერილია C -ზე: void  Heapify (  int  k ,  int  a [],  int  N ) {   int  v ;   int  leftChild ,  rightChild ,  maxValu

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