Alqoritmin analizi və hazırlanması üsullarıMövzu planı

Mövzuda proqramlaşdırmanın və kompüter elmlərinin təməli olan alqoritm anlayışı, onun effektivliyini ölçmək üçün tətbiq edilən riyazi analiz metodları və ilkin axtarış mexanizmləri öyrənilir. Tələbələr alqoritmin sonluq, müəyyənlik və effektivlik kimi təməl xüsusiyyətlərini, həmçinin kodun resurslardan istifadə dərəcəsini təyin edən zaman və yaddaş mürəkkəbliyi anlayışlarını təhlil edirlər. Dərsin əsas hissəsində funksiyaların artım sürətini riyazi olaraq ifadə edən ən pis hal, ən yaxşı hal və orta hal asimptotik notasiyaları, həmçinin verilənlər çoxluğunda elementlərin ardıcıl yoxlanılmasına əsaslanan xətti axtarış alqoritminin iş prinsipi və mürəkkəbliyi praktiki olaraq araşdırılır.

Mövzuda mürəkkəb problemlərin kiçik alt problemlərə bölünərək həll edilməsi mexanizmi olan rekursiya prinsipi və nizamlanmış massivlərdə sürətli axtarışı təmin edən ikilik axtarış alqoritmi öyrənilir. Tələbələr funksiyanın özünü çağırması prosesini, rekursiv zənglərin yaddaşda idarə olunma prinsiplərini və sonsuz dövrün qarşısını alan təməl şərt anlayışını təhlil edirlər. Dərsin əsas hissəsində verilənlər çoxluğunu hər addımda yarıya bölərək axtarış sahəsini daraldan ikilik axtarışın məntiqi strukturu, onun rekursiv və iterativ reallaşdırılması, həmçinin bu alqoritmin zaman və yaddaş mürəkkəbliyinin asimptotik analizi praktiki olaraq araşdırılır.

Mövzuda kompüter elmlərində verilənlərin müəyyən nizamla düzülməsini təmin edən fundamental sıralama alqoritmləri öyrənilir. Tələbələr qonşu elementlərin müqayisəsinə və yer dəyişməsinə əsaslanan qabarcıq sıralaması, hər addımda ən kiçik elementi taparaq müvafiq mövqeyə yerləşdirən seçərək sıralama və kart oyunları məntiqi ilə işləyən daxil etməklə sıralama alqoritmlərinin iş prinsiplərini təhlil edirlər. Dərsin əsas hissəsində bu üç alqoritmin daxili dövrlər vasitəsilə vizual icra addımları, müqayisə və yerbəyeretmə sayları, həmçinin ən yaxşı, orta və ən pis ssenarilərdə zaman və yaddaş mürəkkəbliyi göstəriciləri analitik şəkildə araşdırılır.

Mövzuda böyük həcmli verilənlərin sürətli sıralanması üçün tətbiq edilən inkişaf etmiş alqoritmik yanaşmalar və optimallaşdırılmış sıralama texnikaları öyrənilir. Tələbələr mürəkkəb bir problemi daha kiçik alt problemlərə bölərək həll etməyə əsaslanan "Böl və Hökm Et" fəlsəfəsini təhlil edirlər. Dərsin əsas hissəsində bir dayaq nöqtəsi seçərək massivi iki hissəyə ayıran Quick Sort, verilənləri ikilik ağac strukturuna yığaraq nizamlayan Heap Sort və massivi tək element qalana qədər parçalayıb sonra nizamlı şəkildə birləşdirən Merge Sort alqoritmlərinin iş prinsipləri, həmçinin onların loqaritmik zaman mürəkkəbliyi göstəriciləri praktiki olaraq araşdırılır.

Mövzuda mürəkkəb və bir-birini təkrarlayan alt problemlərdən ibarət tapşırıqların optimal həlli üçün kompüter elmlərində geniş istifadə olunan dinamik proqramlaşdırma strategiyası öyrənilir. Tələbələr alqoritmin effektivliyini artırmaq üçün üst-üstə düşən alt problemlərin və optimal alt struktur prinsiplərinin rolunu təhlil edirlər. Dərsin əsas hissəsində hesablanmış nəticələrin yaddaşda saxlanaraq yuxarıdan-aşağıya doğru yenidən istifadə edilməsini təmin edən memoization texnikası və resursları aşağıdan-yuxarıya doğru bir cədvəl strukturunda toplayaraq iterativ həll quran tabulation metodu, həmçinin bu yanaşmaların zaman və yaddaş mürəkkəbliyinə təsiri praktiki olaraq araşdırılır.

Mövzuda dinamik proqramlaşdırmanın təməl prinsiplərinin klassik optimallaşdırma və kombinatorika tapşırıqlarına tətbiqi öyrənilir. Tələbələr verilən məbləği minimum sayda sikkə ilə formalaşdırmağı tələb edən Coin Change (Sikkə Dəyişdirmə) probleminin riyazi modelini və modelin vəziyyət keçidlərini təhlil edirlər. Dərsin əsas hissəsində isə müəyyən çəki tutumuna malik bir çantanı maksimum dəyər gətirəcək əşyalarla doldurmaq ssenarisini ifadə edən 0/1 Knapsack probleminin dynamic programming matrisi qurulur, əşyaların seçilmə və ya seçilməmə vəziyyətləri (0 və ya 1) üzərindən optimal həll alqoritminin qurulma mexanizmi praktiki olaraq araşdırılır.

Mövzuda optimallaşdırma problemlərinin həllində geniş istifadə olunan, hər bir addımda gələcək nəticələri nəzərə almadan yalnız cari an üçün ən yaxşı görünən seçimin edilməsinə əsaslanan Greedy alqoritmik paradiqması öyrənilir. Tələbələr lokal optimal seçimlərin qlobal optimal həllə gətirib çıxarma şərtlərini, həmçinin bu yanaşmanın dinamik proqramlaşdırma və digər alqoritmik strategiyalardan struktur fərqlərini təhlil edirlər. Dərsin əsas hissəsində Greedy metodunun işləmə mexanizmi, onun sürət və yaddaş baxımından üstünlükləri, eləcə də bu paradiqmanın uğurla tətbiq oluna bildiyi təməl riyazi və məntiqi modellər praktiki olaraq araşdırılır.

Mövzuda Greedy paradiqmasının ən məşhur tətbiqləri olan Fractional Knapsack və verilənlərin sıxılması üçün istifadə olunan Huffman kodlaşdırma alqoritmləri öyrənilir. Tələbələr əşyaların bölünərək çantaya yerləşdirilməsinə imkan verən Fractional Knapsack problemini və 0/1 Knapsack-dan fərqli olaraq burada Greedy yanaşmasının niyə qlobal optimal həlli təmin etdiyini təhlil edirlər. Dərsin əsas hissəsində isə simvolların tezliliyinə əsasən optimal ikilik ağac (Huffman Tree) quran, minimal yaddaş sərfiyyatı ilə məlumatların itkisiz sıxılmasını həyata keçirən Huffman kodlaşdırmasının qurulma mexanizmi və hər iki alqoritmin zaman mürəkkəbliyi praktiki olaraq araşdırılır.

Mövzuda real dünya şəbəkələrini, sosial əlaqələri və xəritələri modelləşdirmək üçün kompüter elmlərində tətbiq olunan qraf məlumat strukturu və onun üzərində aparılan fundamental axtarış alqoritmləri öyrənilir. Tələbələr qrafların proqram yaddaşında effektiv saxlanılma üsulları olan qonşuluq siyahısı və qonşuluq matrisi strukturlarını, onların yaddaş və sürət baxımından üstünlüklərini təhlil edirlər. Dərsin əsas hissəsində qrafın təpələrini səviyyə-səviyyə gəzərək ən qısa yolları tapan eninə axtarış və bir istiqamət üzrə mümkün qədər dərinə gedib sonra geriyə qayıdan dərinliyinə axtarış alqoritmlərinin iş prinsipləri praktiki olaraq araşdırılır.

Mövzuda qraf strukturları üzərində təyin olunmuş təpələr arasında ən optimal və ən qısa məsafələrin hesablanması üçün istifadə edilən fundamental alqoritmlər öyrənilir. Tələbələr mənfi çəkili tilləri olmayan qraflarda bir təpədən digər bütün təpələrə olan ən qısa yolları sürətlə tapan Dijkstra alqoritminin iş prinsipini təhlil edirlər. Dərsin əsas hissəsində isə mənfi çəkili tillərin mövcud olduğu vəziyyətlərdə çalışan, həmçinin qraf daxilində mənfi dövrlərin varlığını müəyyən edə bilən Bellman-Ford alqoritmi, hər iki yanaşmanın zaman mürəkkəbliyi və tətbiq sahələri praktiki olaraq araşdırılır.

Mövzuda bütün mümkün namizəd həlləri sistematik şəkildə araşdıraraq, yanlış və ya yararsız istiqamətləri erkən mərhələdə müəyyən edib geri qayıtma prinsipinə əsaslanan backtracking alqoritmik yanaşması və kombinator tapşırıqlar öyrənilir. Tələbələr axtarış fəzasının ağac strukturu formasında modelləşdirilməsini və budaqların kəsilməsi mexanizmini təhlil edirlər. Dərsin əsas hissəsində şahmat taxtasında vəzirlərin bir-birini vurmayacaq şəkildə yerləşdirilməsini tələb edən N-Queens tapşırığı, qrafın bütün təpələrindən yalnız bir dəfə keçməklə qapalı dövrə quran Hamiltonian Cycle problemi və verilmiş çoxluğun bütün mümkün alt çoxluqlarının yaradılmasını təmin edən Subset generation alqoritmlərinin iş prinsipləri praktiki olaraq araşdırılır.

Mövzuda mürəkkəb hesablama və optimallaşdırma problemlərinin qısa zamanda həll edilməsi üçün təsadüfiliyin gücündən istifadə edən randomizə alqoritmlər və NP-tam sinfinə aid olan çətin məsələlərə ağlabatan vaxtda optimala yaxın həll təklif edən təqribi alqoritmlər öyrənilir. Tələbələr dayaq elementinin təsadüfi seçilməsi ilə ən pis ssenari riskini aradan qaldıran Randomized QuickSort alqoritmini və təsadüfi seçmələr vasitəsilə mürəkkəb riyazi sahələri və ehtimalları hesablayan Monte Carlo metodunun təməl prinsiplərini təhlil edirlər. Dərsin əsas hissəsində isə NP-tam problemlərdən biri olan, qrafdakı bütün tilləri əhatə edəcək minimal sayda təpələrin tapılmasını tələb edən Vertex Cover tapşırığı və bu tapşırıq üçün 2-qat təqribi optimal həll təklif edən Greedy əsaslı yanaşmanın iş mexanizmi praktiki olaraq araşdırılır.

Mövzuda hesablama cəhətdən ağır və böyükölçülü alqoritmlərin icra sürətini artırmaq üçün müasir çoxnüvəli mərkəzi prosessor (CPU) arxitekturasından maksimum dərəcədə səmərəli istifadə prinsipləri və multiprocessing (çoxprosesli işləmə) paradiqması öyrənilir. Tələbələr tək bir nüvənin limitlərini aşaraq, tapşırıqları müstəqil yaddaş sahəsinə malik paralel proseslərə bölməyin yollarını və bunun multithreading (çoxaxınlı işləmə) yanaşmasından struktur fərqlərini təhlil edirlər. Dərsin əsas hissəsində CPU intensivliyi yüksək olan alqoritmik proseslərin fərqli fiziki nüvələrə paylanması, proseslərarası əlaqə (IPC) mexanizmləri, məlumatların sinxronizasiyası və Amdal qanunu vasitəsilə əldə edilə biləcək maksimum sürətlənmə həddinin hesablanması praktiki olaraq araşdırılır.

Mövzuda kompüter elmlərinin və riyaziyyatın ən fundamental həll olunmamış suallarından biri olan P qarşıdır NP problemini başa düşmək üçün mürəkkəblik sinifləri və qeyri-müəyyənlik prinsipləri öyrənilir. Tələbələr deterministik polinomial vaxtda həll olunan məsələlərin daxil olduğu P sinfini və həlli qeyri-deterministik maşınlarda polinomial vaxtda tapılan, lakin təklif olunan həllin doğruluğu deterministik olaraq tez yoxlanıla bilən NP sinfini təhlil edirlər. Dərsin əsas hissəsində isə ən azı NP-dəki bütün məsələlər qədər çətin olan NP-hard kateqoriyası, həm NP, həm də NP-hard şərtlərini ödəyərək bu sinfin ən mürəkkəb nüvəsini təşkil edən NP-complete anlayışları və onların arasındakı keçidləri təmin edən reduksiya üsulları praktiki olaraq araşdırılır.

Mövzuda semestr boyu keçirilən bütün fundamental və təkmil alqoritmik mövzuların, o cümlədən rekursiv və ikilik axtarış sistemlərinin, sıralama texnikalarının, dinamik proqramlaşdırma metodlarının, qraf və ən qısa yol alqoritmlərinin, eləcə də backtracking, randomizə, çoxprosesli hesablama və NP mürəkkəblik siniflərinin hərtərəfli təkrarı həyata keçirilir. Tələbələr müxtəlif alqoritmlərin zaman və yaddaş mürəkkəbliyinin asimptotik analizini yenidən nəzərdən keçirirlər. Dərsin əsas hissəsində real imtahan ssenarilərinə uyğun analitik məsələlərin həlli, tipik proqramlaşdırma xətalarının analizi, kod optimallaşdırılması strategiyaları və nəzəri sualların cavablandırılması metodikası praktiki olaraq araşdırılır.