Yerevan State University Ijevan Branch

Մասնաճյուղում «Փնտրման և տեսակավորման դասական ալգորիթմներ: Ալգորիթմների ծրագրային ապահովման մշակում և բարդությունների գնահատում» թեմայով գիտական զեկուցում կարդաց ԵՊՀ դիսկրետ մաթեմատիկայի ամբիոնի ասպիրանտ Ներսես Խաչատրյանը

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) լրացուցիչ հիշողության դեպքում կարելի է տեսակավորումը ավելի կայուն անել։

Մասնաճյուղում «Փնտրման և տեսակավորման դասական ալգորիթմներ: Ալգորիթմների ծրագրային ապահովման մշակում և բարդությունների գնահատում» թեմայով գիտական զեկուցում կարդաց ԵՊՀ դիսկրետ մաթեմատիկայի ամբիոնի ասպիրանտ Ներսես Խաչատրյանը

Զեկուցումից հետո ուսանողներին առաջարկվեցին տրամաբանական խնդիրներ, որոնք քննարկվեցին մեծ ոգևորությամբ: