დინამიური მასივი

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

ასეთ სტრუქტურას სხვადასხვა დასახელებით შეხვდებით – dynamic array, growable array, resizable array, dynamic table, mutable array, array list.

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

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

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

ასეთ გადაწყვეტაში მნიშვნელოვანია შეკითხვაზე პასუხი: რამდენჯერ უნდა გაიზარდოს მასივი გადაწერის წინ?

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

ოპტიმალურ ვარიანტად რიცხვი 2 არის მიღებული. ამ რიცხვს ზრდიან ამ ამცირებენ იმის მიხედვით მეტი მეხსიერების ხარჯი ურჩევნიათ თუ დროის.

სხვადასხვა პროგრამირების ენაში ან რეალიზაციაში ის ზოგჯერ განსხვავებულია – მაგალითად, ვექტორი c++-ში 2-ჯერ იზრდება, Java-ს ვექტორისთვისაც default მნიშვნელობა ეს რიცხვია, თუმცა პარამეტრის სახით არის და შეცვლა შეიძლება. Java-ს ArrayList-ის სტატიკური მასივი 3/2-ჯერ იზრდება. HashMap-ის მასივი 2-ჯერ. პითონის C-ის იმპლემენტაციაში რაღაც უცნაურად არის, 9/8 გამოდის საშუალოდ. ამ ბმულზეა კოდი. აქ კი მისი გარჩევა

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

Java-ში ArrayList და HashMap ობიექტებს კონსტრუქტორში გადაეცემა initialCapacity პარამეტრი. HashMap-ში არა მხოლოდ მასივის გადაწერა, არამედ ჰეშების თავიდან გენერაცია ხდება.

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

ზევით ვახსენეთ, რომ დინამიურ მასივში ამ გადაწერის საჭიროების შედეგად ზოგიერთი ელემენტის ჩამატების დროს O(1)-დან იზრდება O(n)-მდე, სადაც n მასივში არსებული ელემენტების რაოდენობაა. ამის მიუხედავად, ამორტიზებული ანალიზის შედეგად, დინამიურ მასივში ელემენტის ჩამატების დრო O(1)-ად არის მიჩნეული.

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

მოდი გამოვთვალოთ n ელემენტიანი დინამიური მასივის შევსების დრო:
თუ ჩავთვლით რომ ყოველ ჯერზე (როდესაც ორის ხარისხს მივაღწევთ) სტატიკური მასივი ორმაგდება, შეგვიძლია ელემენტების გადაწერის რაოდენობა ასე შევაფასოთ:
ბოლოდან მოვყვეთ. ბოლოს ყველას გადაწერა მოუწევს, იმის წინ მხოლოდ ნახევრის, იმის წინ მეოთხედის და ა.შ.
n + n/2 + n/4 + n/8 + … = n (1 + 1/2 + 1/4 + 1/8 + …) = 2n

ამ გადაწერებს მივუმატოთ თვითონ ელემენტების ჩასმაც და გამოვა 3n. შესაბამისად საშუალოს თუ ავიღებთ, თითოეული ელემენტის ჩასმისთვის გამოგვივა O(3) = O(1) დრო.

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

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

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

სრული სილაბუსი ამ ბმულზე შეგიძლიათ ნახოთ.

კურსი მჭიდროდ იქნება დაკავშირებული სხვადასხვა პროგრამირების შეჯიბრებებთან (GeOlymp, Codeforces, TopCoder…) და კოდები ავტომატურ რეჟიმში მატესტირებელი სისტემით გაიტესტება.

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

უდიდესი საერთო ქვემიმდევრობის პოვნის ამოცანა

წინა პოსტში მაგისტრატურის გამოცდა ვახსენე და დღეს მისთვის მოსამზადებლად მეორე ალგორითმს გავიხსენებ. ფსევდო კოდები და მაგალითები ისევ ”Introduction to Algorithms” წიგნიდან ავიღე 🙂

”უდიდესი საერთო ქვემიმდევრობის” (Longest Common Subsequence) პოვნა დინამიური პროგრამირების კიდევ ერთი კლასიკური ამოცანაა. ვთქვათ მოცემულია მიმდევრობები:

X = (A, B, C, B, D, A, B)
Y = (B, D, C, A, B, A)

ამ შემთხვევაში მათი ერთ-ერთი უდიდესი საერთო ქვემიმდევრობაა მიმდევრობა (B, C, B, A)

ცოტა უკეთ განვსაზღვროთ, თუ რა არის ქვემიმდევრობა:
ვთქვათ მოცემულია მიმდევრობა X = (x1, x2, … , xm).
Z = (z1, z2, …. , zk) არის მისი ქვევმიმდევრობა, თუ არსებობს (i1,i2..,ik) X-ის ინდექსების ისეთი მკაცრად ზრდადი მიმდევრობა, რომ ყველა j=1,2,… k მნიშვნელობისთვის სრულდებოდეს ტოლობა xij = zj.

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

ინტუიციურია, მაგრამ მაინც განვსაზღვროთ მიმდევრობის ”პრეფიქსის” ცნება. თუ მოცემული გვაქვს მიმდევრობა X = (x1, x2, … , xm), მისი i-ური პრეფიქსი იქნება X-ის პირველი i ცალი ელემენტისგან შემდგარი მიმდევრობა, ანუ Xi = (x1, x2, … , xi). რა თქმა უნდა i4 = (A,B,C,B). X0 ცარიელი მიმდევრობაა.

სანამ ამოცანის ამოხსნაზე გადავალთ ერთი პატარა თეორემა უნდა დავამტკიცოთ.
თეორემა:
მოცემულია X = (x1, x2, … , xm) და Y = (y1, y2, … , yn) მიმდევრობები. ხოლო Z = (z1, z2, … , zk) არის ამ მიმდევრობების უდიდესი საერთო ქვემიმდევრობა.
1. თუ xm = yn, მაშინ zk = xm = yn და Zk-1 არის Xm-1 და Yn-1 პრეფიქსების უსქ (უდიდესი საერთო ქვემიმდევრობა).
2. თუ xm !=yn, მაშინ zk != xm-დან გამომდინარეობს, რომ Z არის Xm-1 და Yn პრეფიქსების უსქ.
3. თუ xm !=yn მაშინ, zk != yn-დან გამომდინარეობს, რომ Z არის Xm და Yn-1 პრეფიქსების უსქ.

დამტკიცება საკმაოდ მარტივია.
1. დავუშვათ საწინააღმდეგო და ვთქვათ, რომ zk != xm. რადგან xm = yn, Z-ს შეგვიძლია მივამატოთ xm ელემენტიც. ამ შემთხვევაში კი გამოვა რომ უდიდესი საერთო ქვემიმდევრობა Z-ზე გრძელია და წინააღმდეგობას მივიღებთ. მოკლედ რომ ვთქვათ, თუ მოცემული მიმდევრობების ბოლო ელემენტები ერთნაირია, ის ელემენტი აუცილებლად იქნება უსქ-ის ბოლო ელემენტი.

დებულების მეორე ნაწილიც იგივე პრინციპით დავამტკიცოთ. ვთქვათ Zk-1 არ არის Xm-1 და Yn-1 პრეფიქსების უსქ. მაშინ იარსებებს რაიმე უსქ W, რომლის სიგრძეც k-1-ზე მეტია. მას რომ მივამატებთ xm = yn ელემენტს, ის k-ს გადააჭარბებს. ეს წინააღმდეგობაა.

2. რომ არსებობდეს Xm-1 და Y-ის უდიდესი საერთო ქვემიმდევრობა – W, რომლის ელემენტების რაოდენობა k-ზე მეტია, ის აგრეთვე იქნებოდა X-ის და Y-ის უსქ და თან Z-ს გადააჭარბებდა სიგრძეში. მოცემულობის მიხედვით კი Z არის X-ის და Y-ის უსქ.

3. მეორე პუნქტის ანალოგიურად მტკიცდება.

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

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

კონკრეტულად, შემოვიღოთ რიცხვითი ტიპის ორგანზომილებიანი მასივი c და მის [i][j] უჯრაში შევინახოთ Xi და Yj პრეფიქსების უსქ-ის სიგრძე.

როცა i ან j ნოლის ტოლია მაშინ c[i][j]-ის მნიშვნელობა ნოლის ტოლი იქნება რადგან საერთო ქვემიმდევრობაც ცარიელი გამოვა პრეფიქსის მსგავსად.

როცა i, j >0 და xi = yj, ეს ნიშნავს რომ Xi და Yi მიმდევრობების უსქ-ის სიგრძე ერთით მეტია ვიდრე Xi-1 და Yi-1 მიმდევრობების უსქ-ის სიგრძე, რადგან ერთი კიდევ ერთი საერთო ელემენტი დაემატა.

როცა i,j>0 და xi != yj, ეს ნიშნავს რომ უსქ-ის სიგრძე იგივეა რაც Xi-1 და Yj პრეფიქსების ან Xi და Yj-1 პრეფიქსების უსქ-ს ჰქონდა. ამიტომ ამ ორიდამ მაქსიმალური სიგრძისა ავირჩიოთ და მისი მნიშვნელობით შევავსოთ c[i][j] უჯრა.

საბოლოოდ ასეთი რეკურენტული ფორმულა მივიღეთ:

თუმცა საბოლოო პასუხი არა მხოლოდ უდიდესი საერთო ქვემიმდევრობის სიგრძეა, არამედ თვითონ ქვემიმდევრობა. ამიტომ შემოვიღოთ c-ის ზომის კიდევ ერთი დამატებითი ორგანზომილებიანი მასივი b, რომლის [i][j] უჯრაში შევინახავთ ხოლმე თუ რომელი მეთოდით შევავსეთ c[i][j].

ფსევდო კოდი ასე გამოიყურება:

კოდში კარგად ჩანს რომ ორი ჩადგმული ციკლი მუშაობს. მათგან ერთი m, ხოლო მეორე n ცალ იტერაციას აკეთებს. თითო უჯრის მნიშვნელობის გამოთვლა O(1) დროში ხდება. ანუ ალგორითმი O(mn) დროში მუშაობს, სადაც m და n მოცემული მიმდევრობების სიგრძეებია.

ვნახოთ როგორ შეავსებს ეს ფუნქცია მასივებს ჩვენს მაგალითზე დაყრდნობით:

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

ეს ფუნქცია O(m + n) დროში მუშაობს, რადგან ის ყოველ ჯერზე მინიმუმ ან i-ის ამცირებს ერთით, ან j-ის, ან საერთოდ ორივეს ერთად.

შევაფასოთ გამოყენებული მეხსიერებაც. ამ ალგორითმში ორი ცალი m x n ზომის მასივი გვაქვს, ამიტომ O(mn) მეხსიერებას ვიყენებთ. შეიძლება b მასივი საერთოდ გამოვტოვოთ, თუმცა მეხსიერების O(mn) შეფასება არ შეიცვლება.
საქმე იმაშია, რომ c[i][j] უჯრის მეზობელ c[i-1][j-i], c[i][j-1], c[i-1][j] უჯრებს თუ დავათვალიერებთ, მარტივად მივხვდებით რომელ მათგანზე დაყრნობით მივიღეთ c[i][j] მნიშვნელობა და აღარ დაგვჭირდება ამის b მასივში შენახვა.

განახლება კომენტარიდან:

Zuba Dalama:
ერთ-ერთი “real world” მაგალითია diff: http://en.wikipedia.org/wiki/Diff

ვისაც აინტერესებს თუ როგორაა რეალიზებული იხ. google–ის opensource პროექტი (წარმოდგენილია შემდეგ ენებზე: Java, JavaScript, Dart, C++, C#, Objective C, Lua და Python) http://code.google.com/p/google-diff-match-patch/
და მისი დოკუმენტაცია: http://neil.fraser.name/writing/diff/.

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

გადავწყვიტე წელს უნივერსიტეტში დავბრუნდე მაგისტრანტის სახით, მაგრამ ამისთვის ჯერ გამოცდა უნდა ჩავაბარო რამდენიმე დღეში. საკითხების სიაში დინამიური პროგრამირების კლასიკური ამოცანებიც შედის, რომელთაგან ერთ-ერთი ”მატრიცათა მიმდევრობის გადამრავლების” ამოცანაა (Matrix chain multiplication). ამ პოსტში მისი ამოხსნის შესახებ დავწერ. მაგალითები და ფსევდო კოდები Introduction to Algorithms წიგნიდან ავიღე.

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

აქ ვხედავთ, რომ გამრავლებისთვის აუცილებელია პირველი მატრიცის სვეტების რაოდენობა მეორე მატრიცის სტრიქონების რაოდენობას ემთხვეოდეს. შესაბამისად, თუ პირველი მატრიცის განზომილებებია p და q, ხოლო მეორე მატრიცის – q და r, მათი გადამრავლებისთვის pqr ცალი წრფივი გამრავლების ოპერაცია დაგვჭირდება.

მატრიცების გამრავლების ოპერაცია ასოციაციურია, ანუ (AB)C = A(BC), მაგრამ არა კომუტატური – AB ნამრავლის შედეგი შეიძლება არ იყოს BA ნამრავლის შედეგად მიღებული მატრიცის ტოლი.

ვთქვათ მოცემულია A1,A2,A3 მატრიცების მიმდევრობა, სადაც A1 მატრიცის განზომილებებია 10 x 100, A2 – 100 x 5,   A3 – 5 x 50. იმის მიხედვით, თუ რა თანმიმდევრობით გავამრავლებთ მატრიცებს, სხვადასხვა რაოდენობის ოპერაცია დაგვჭირდება, თუმცა ასოციაციურობის გამო საბოლოო შედეგი ყოველთვის ერთი და იგივე მატრიცა იქნება. მაგალითად:


Read more

Who dares, wins :D

რას მივუძვნიდი ამ პოსტს, თუ არა ჯეოლიმპს 🙂

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

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

სამ დღეს თუ გადაცდა ეს პროცესი, სასტიკად მძულს ის ამოცანა და ამოხსნა კი არა, გახსენებაც აღარ მინდა : ))

ჯეოლიმპში ის მომწონს, რომ საჩემო ამოცანებიც არის 😀 ჩემს ჭიასაც უხარია, როცა ნოლზე არ ვრჩები.

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

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

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

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

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

(თვითონ ხომ კარგს არ დაწერენ თავის თავზე.. :D)

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

ბოლო დროს ჩამოყალიბებული ტრადიციისამებრ ინტერნეტ-რაუნდის პარალელურად დასწრებული შეჯიბრიც ჩატარდება ერთ-ერთ სასწავლო დაწესებულებაში – ამ რაუნდში კონკრეტულად თბილისის სახელმწიფო უნივერსიტეტის XI კორპუსში, სადაც ადგილობრივი გამარჯვებულიც გამოვლინდება 🙂

ჰოდა, რომ მეუბნებით ხოლმე ზოგიერთები ტრასაზე როდის დავდგეთო, 😀 მობრძანდით კვირას (19-ში) და ამ არენაზე შევეჯიბროთ. its more fun.  მე დიდი ამომხსნელი არ ვარ, მაგრამ მაინც სახალისოა.

”ჯეოლიმპი” თბილისის სახელმწიფო უნივერსიტეტში
”ჯეოლიმპი” თბილისის სახელმწიფო უნივერსიტეტში