ვარიანტი 1

Question 1

რა არის ალგორითმი და ჩამოთვალე რა მოთხოვნებს უნდა აკმაყოფილებდეს იგი?

Answer 1

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

1. სასრულობა – ალგორითმი უნდა გულისხმობდეს სასრული ნაბიჯების შედეგ დამთავრებას.
2. განსაზღვრულობა – ალგორითმის ყოველი ბიჯი უნდა იყოს ზუსტად განსაზღვრული, მაგალითად რომელიმე დაპროგრამების ენაზე.
3. შემავალი მონაცემები (input ): თუ ალგორითმს განვიხილავთ როგორც ფუნქციას, რომელიც ამოცანას შეუსაბამებს მის პასუხს, მაშინ შემავალი მონაცემები წარმოადგენენ არგუმენტს ალგორითმისთვის, ხოლო ამოცანისთვის _ ამომწურავ დახასიათებას.
4. გამომავალი მონაცემები (output ): ესაა მონაცემები, რომლებსაც ვღებულობთ ალგორითმის მუშაობის დამთავრების შემდეგ.

Question 2

ალგორითმის ჩაწერის მეთოდები

Answer 2

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

Question 3

რას ნიშნავს ალგორითმის ანალიზი?

Answer 3

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

Question 4

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

Answer 4

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

Question 5

ალგორითმის რამდენ დროითი სირთულეს იცნობთ და განმარტე რას ნიშნავს თითოეული

Answer 5

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

1) ალგორითმის შესრულების მაქსიმალური დრო ანუ შემავალი მონაცემების მიხედვით ბიჯების მაქსიმალური რაოდენობა
2) ალგორითმის შერულების მინიმალური დრო ანუ შემავალი მონაცემების მიხედვით ბიჯების მინიმალური რაოდენობა
3) ალგორითმის შესრულების საშუალო დრო ანუ შემავალი მონაცემები მიხედვით ბიჟების მინიმალური და მაქსიმალური რაოდენობის გასაშუალება. ეს პრინციპი გვხვდება ყველაზე ხშირად.

Question 6

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

Answer 6

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

Question 7

განმარტე, რა არის ორიენტირებული და არაორიენტირებული გრაფები .

Answer 7

გრაფები არის ისეთი სიმრავლეები რომელთა წარმოდგენაც შეიძლება სამგანზომილებიან სივრცეში წერტილების სახით რომელბიც ერტმანეთთან დაკავშირებულნი არიან მონაკვეთებით ან არ არიან დაკავშირებულნი. სივრცეში განლაგებულ წერთილებს უწოდებენ გრაფების მწვერვალებს ხოლო მათ შემაერთებელ მონაკვეთებს გრაფების წიბოებს. გრაფები ხშირად გამოიყენება დისკრეტულ მათემათიკაში და პროგრამირებაში. გრაფების წარმოდგენა შეიძლება V(მწვერვალების) და E(წიბოები) იმრავლეების სახით G=(V;E). იმ შემთხვევაშ თუ E სიმრავლე არის დახარისხებული გრაფს უწოდებენ ორიენტირებულს ხოლო თუ არ არის დახარისხებული არაორიენტირებულს.

Question 8

ნახაზზე ნაჩვენებია გრაფის ერთ-ერთი მაგალითი. დაწერე, თუ როგორია ეს გრაფი
დაწერე, თუ როგორია ეს გრაფი და ნახაზის მიხედვით ჩაწერე V და E სიმრავლები მათემატიკურად.

Answer 8

ნახაზზე მოცემულია ორიენტირებული გრაფი. თუ ჩავწერთ V და E სიმრავლეებს მათემატიკურად გამოვა:
V=(1,2,3,4,5,6)
E={(1;2)(2,2)(2,5)(4,5)(5,4)(2,4)(6,3)(4,1)} სადაც E(2,2) არის ციკლური გრაფი