ვარიანტი 2

Question 1

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

Answer 1

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

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

Question 2

დაწერე, რას ნიშნავს ალგორითმის კორექტულობა?

Answer 2

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

Question 3

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

Answer 3

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

Question 4

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

Answer 4

ციკლური სტრუქტურის ალგორითმი წარმოადგენს ალგორითმს, რომლის ერთ-ერთი ნაწილის მრავალჯერ შესრულება ხდება, ხოლო თვითონ იმ ნაწილს, რომელიც მრავალჯერ სრულდება ეწოდება ციკლი. ჩვეულებრივ ციკლის მსვლელობისაც გვაქვს რაღაც ცვლადი რომელიც თანმიმდევრობით იცვლება და ციკლის თავიდან დაწყებისას ყოველ ჯერზე ხდება ამ ცლადის რაიმე მნიშვნელობასთან შედარება, რათა შევძლოთ ციკლიდან გამოსვლა და „გზის“ გაგრძელება.
ამის მაგალითი შეიძლება იყო, ალგორითმი რომელიც მიწოდებული string ცვლადში დაითვლის რამდენი სიტყვაა. თუკი ალგორითმი შედგენილი იქნება შემდეგი სახით:
for (int i = 0; i < my_string_var.length; i++)
{
if (my_string_var[i] == ‘ ‘) //არის თუ არა ამ ინდექსზე ჩაწერილი სიმბოლო: გამოტოვება (Space)
{
words++; //წინასწარ გვქონდა შექმნილი ცვლადი words რომლის მნიშვნელობა თავიდან იყო 0.
}
}
ეს ალგორითმი დაითვლის მოცემულ string-ში გამოტოვებებს და რა რიცხვსაც მიიღებს, ბოლოში გვეცოდინება რომ წინადადებაში არის ამ რიცხვს + 1 სიტყვა (მაგალითად, თუ 1 გამოტოვებაა მხოლოდ წინადადებაში, ესე იგი 2 სიტყვაა სულ).
მართალია, ეს კოდი უფრო C# კოდს ჰგავს, თუმცა პრინციპი იგივეა.

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

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

Question 5

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

Answer 5

ალგორითმების ანალიზი შეიძლება გავაკეთოთ შემდეგი მიზეზების გამო:

• ორი ალგორითმის ერთმანეთთან შესადარებლად
• მოცემული ალგორითმის ყოფა-ქცევის დასადგენად
• ალგორითმში შემავალი მნიშვნელობების/პარამეტრების შესასწავლად

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

Question 6

ჩამოთვალე რიცხვთა მასივების დახარისხების ალგორითმების ტიპები.

Answer 6

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

Question 7

განმარტე, რა არის გრაფი და ჩამოთვალე მისი ძირითადი თვისებები

Answer 7

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

Question 8

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

Answer 8

ნახაზზე მოცემულია არაორიენტირებული გრაფი.
V(1, 2, 3, 4, 5, 6) და E((1,2), (1,5), (2,5), (3,6)).
მწვერვალები 1, 2 და 5 ერთმანეთთან დაკავშირებულია შესაბამისი წიბოებით. აგრეთვე მწვერვალები 3 და 6-იც. მწვერვალი 4 კი იზოლირებულია.
ამასთანავე, E სიმრავლე არის წყვილების დაუხარისხებელი სიმრავლე, ამიტომ გრაფი არაორიენტირებულია.