2015թ. նոյեմբերի 5-ին ԵՊՀ ԻՄ-ի բնական գիտությունների ֆակուլտետում «Փնտրման և տեսակավորման դասական ալգորիթմներ: Ալգորիթմների ծրագրային ապահովման մշակում և բարդությունների գնահատում» թեմայով գիտական զեկուցում կարդաց ԵՊՀ դիսկրետ մաթեմատիկայի ամբիոնի ասպիրանտ Ներսես Խաչատրյանը, ում հրավիրել էր մասնաճյուղի ծրագրավորման և ինֆորմացիոն տեխնոլոգիաների ամբիոնը:
Ներկայացվեց, որ տեսակավորման ալգորիթմները գնահատվում են կատարման արագությամբ և հիշողության օգտագործման արդյունավետությամբ, դիտարկվեցին կիրառական խնդիրների օրինակներ, որոնց համար A ալգորիթմի կատարման ժամանակը ուղիղ համեմատական է f(n) ֆունկցիային:
Վերլուծվեցին նույն խնդիրը լուծող տարբեր ալգորիթմների էֆեկտիվության համեմատության հնարավորությունները:
Մանրամասն ներկայացվեցին տեսակավորման ալգորիթմները.
• Պղպջակների մեթոդ (անգլ՝ Bubble sort), ալգորիթմի դժվարությունը` O(n2), ինդեքսի յուրաքանչյուր զույգի համար իրականացվում է փոխանակում, եթե էլեմենտները տեղաբաշխված են ոչ հերթականությամբ։
• Կոկտեյլային տեսակավորում (Cocktail sort, bidirectional bubble sort), ալգորիթմի դժվարությունը` O(n2):
• Բլոկային տեսակավորում (տեսակավորում Bucket sort) ալգորիթմի դժվարությունը` O(n), պետք է O(k) լրացուցիչ հիշողություն և տեսակավորվող տվյալների էության իմացություն, «տեղափոխել» և «համեմատել» ֆունկցիաների սահմանների մեջ։
• Հաշվարկող տեսակավորում (Counting sort) ալգորիթմի բարդությունը ` O(n+k), անհրաժեշտ է O(n+k) լրացուցիչ հիշողություն:
• Միաձուլման տեսակավորում (Merge sort) ալգորիթմի բարդությունը` O(n log n), անհրաժեշտ է O(n) լրացուցիչ հիշողություն, շարել ցանկի առաջին և երկրորդ մասը առանձին, իսկ հետո միաձուլել հաջորդականացված ցանկերը։
• Ծառային տեսակավորում (անգլ.՝ Tree sort) ալգորիթմի բարդությունը` O(n log n), անհրաժեշտ է O(n) լրացուցիչ հիշողություն։
• Ընտրանքային տեսակավորում (Selection sort) ալգորիթմի բարդությունը ` O(n2), ամենամեծ կամ ամենափոքր էլեմենտի փնտրում և տեղադրում հաջորդականացված ցանկի վերջում կամ սկզբում:
• Շելլի տեսակավորում (Shell sort) ալգորիթմի դժվարությունը ` O(n log2 n) և փորձ լավացնելու մուտքային տեսակավորում:
• Խմբային տեսակավորում (Heapsort) ալգորիթմի բարդությունը՝ O(n log n), վերածել ցանկը խմբի, վերցնել ամենամեծ էլեմենտը և ավելացնել ցանկի վերջում։
• Արագ տեսակավորում (Quicksort), հիշողության նվազագույն ծախս, ալգորիթմի բարդությունը` O(n log n), միջին ժամանակը, O(n2) վատագույն դեպք. լայն տարածում ունի որպես ամենաարագը դասավորելու մեծ պատահական ցանկերի համար՝ բաժանելով 2 մասի սկզբնական տվյալները, այնպես, որ առաջին կեսի ցանկացած էլեմենտ դասավորված է երկրորդ կեսի ցանկացած էլեմենտի համեմատ։ Հետո ալգորիթմը օգտագործել ռեկուրսիվ ամեն կեսում։ O(n) լրացուցիչ հիշողության դեպքում կարելի է տեսակավորումը ավելի կայուն անել։
Զեկուցումից հետո ուսանողներին առաջարկվեցին տրամաբանական խնդիրներ, որոնք քննարկվեցին մեծ ոգևորությամբ:
