Ինչպես յուրացնել ալգորիթմները

Հաշվիչ համակարգերի կողմից ինչ-որ գործողության կատարման համար, նախ պետք է հասկացնել վերջինիս, թե ինչպես դա անել: Անհրաժեշտ է գրել ծրագիր՝ քայլ առ քայլ բացատրությամբ, թե համակարգիչն ինչ առաջադրանքներ և ինչպես պետք է կատարի: Հենց այս հարցում էլ մեզ օգնում են ալգորիթմները:

Ալգորիթմ տերմինը ստեղծվել է պարսիկ հռչակավոր մաթեմատիկոս Ալ-Խորեզմիի կողմից, և ներկայացնում է քայլ առ քայլ հաշվարկային գործընթաց, ֆունկցիայի հաշվարկման որոշակի լավ սահմանված արդյունավետ մեթոդ, որը բերում է ցանկալի արդյունքի ստացմանը: Այն կիրառվում է հաշվարկներում, տվյալների մշակման և մտահանգումների ավտոմատացման ժամանակ։

Սկսելով նախնական վիճակից և արված մուտքային տվյալներից, ունենալով գործողությունները բացատրող հրահանգավորում, դրանք կատարելով ստացվում է վերջնական արդյունք։ Մի վիճակից մյուսին անցումը պարտադիր չէ, որ լինի խիստ կանխատեսելի և որոշակի` որոշ ալգորիթմներ միավորում են պատահական մուտքեր։
Յուրաքանչյուր խնդիր լուծելու համար կարող են գոյություն ունենալ նպատակին հասցնող բազմաթիվ ալգորիթմներ։ Ալգորիթմների արդյունավետության մեծացումը ժամանակակից ինֆորմատիկայի խնդիրներից մեկն է։

Ալգորիթմի նախագծումը վերաբերում է խնդրի լուծման և ալգորիթմների կառուցման մեթոդին կամ մաթեմատիկակական գործընթացին, որոնք նաև կոչվում են ալգորիթմների նախագծման շաբլոններ:

Ալգորիթմների մշակման կարևորագույն ասպեկտներից է ռեսուրսների արդյունավետությունը՝ կատարման ժամանակը, հիշողության օգտագործման ծավալը և այլն:

Ալգորիթմների իմացությունը էական նշանակություն ունի արդյունավետ համակարգչային ծրագրերի նախագծման և մշակման համար: Այս հոդվածում ես կցանկանայի կիսվել համալսարանում ալգորիթմներ ուսումնասիրելու իմ փորձով և խոսել այն մասին, թե ինչպես դա ինձ օգնեց իմ ուսման և կարիերայի ընթացքում:

Ալգորիթմների մշակման բնորոշ քայլերն են․

• Խնդրի սահմանումը
• Մոդելի մշակումը
• Ալգորիթմի հստակեցում
• Ալգորիթմի մշակում
• Ալգորիթմի ճշգրտության ստուգում
• Ալգորիթմի վերլուծություն
• Ալգորիթմի գործարկում
• Ծրագրի ստուգում
• Փաստաթղթերի պատրաստում

Ծանոթացումը

Ես սկսեցի կոդավորել, երբ դեռ ավագ դպրոցում էի: Իմ առաջին քայլերն արեցի՝ Visual Basic-ում հաշվիչներ ու լուսացույցներ ստեղծելով։ Հետագայում տիրապետեցի HTML-ին և Java-ին։ Այդ ժամանակ ես դեսկտոպ և վեբ հավելվածներ էի մշակում։ Եվ ես ուղղակի կոդ էի գրում՝ առանց ներքին տրամաբանության մասին անգամ մտածելու:

Համալսարան ընդունվելով՝ համակարգչային գիտությունների մասնագիտությամբ, արդեն երկրորդ կուրսում սկսեցի ուսումնասիրել տվյալների կառուցվածքները և ալգորիթմները: Դա պարտադիր դասընթաց էր, ուստի բոլորը պետք է անցնեին այն։

Ծրագրավորողից՝ մշակող

Տվյալների կառուցվածքների և ալգորիթմների ուսումնասիրությունը շրջադարձային էր համակարգչային ծրագրավորման իմ ըմբռնման մեջ. ես այժմ ավելի շատ մտածում էի որպես ինժեներ-մշակող, այլ ոչ որպես պարզապես ծրագրավորող: Ինչո՞ւ եմ դա ասում: Ահա մի քանի օրինակներ.

Օրինակ 1. տեսակավորման/սորտավորման ալգորիթմներ

Պատկերացրեք, որ առցանց խանութի համար հավելված ենք պատրաստում և ցանկանում ենք, որ օգտվողները կարողանան դիտել ապրանքները գնի աճման կամ նվազման կարգով: Դա անելու համար ապրանքները պետք է տեսակավորվեն ըստ գնի։ Եթե ​​ես սկսնակ ծրագրավորող լինեի, ես կավելացնեի գներ զանգվածի(կամ ցուցակի) մեջ, իրենց ինդեքսների արժեքներով և պարզապես կկանչեի զանգվածի մեջ ներկառուցված sort() մեթոդը: Ի՞նչ է իրականում կատարվում sort() մեթոդի ներսում: Երբ ես նախկինում հավելվածներ էի ստեղծում, գաղափար անգամ չունեի այս մասին:

Տեսակավորման ալգորիթմները հիմնային այն թեմաներից են, որն առաջին հերթին են ուսումնասիրում համալսարանի տվյալների կառուցվածքների և ալգորիթմների կուրսերի ժամանակ:

Սորտավորման ալգորիթմներ են.

• Մուտքային տեսակավորում (Insertion sort) , ալգորիթմի բարդությունը՝ O(n²)։
• Ընտրանքային տեսակավորում (Selection sort) ալգորիթմի բարդությունը՝ O(n²):
• Արագ տեսակավորում (Quicksort), հիշողության նվազագույն ծախս, ալգորիթմի բարդությունը՝ O(n log n) միջին ժամանակը, O(n²) վատագույն դեպք:
• Պղպջակային տեսակավորում (անգլ.՝ Bubble sort ) , ալգորիթմի դժվարություն՝ O(n²)
• Միաձուլման տեսակավորում (Merge sort) ալգորիթմի բարդությունը` O(n log n)

Սրանք տարածված սորտավորման ալգոիթմներից մի քանիսն են միայն, ավելի մանրամասն սորտավորման ալգորիթմներին և դրանց տեսակներին կանդրադառնանք հետագայում:

Ուսումնասիրելով տարբեր տեսակավորման ալգորիթմներ՝ ես հասկացա, որ յուրաքանչյուր առաջադրանք կարիք ունի իր համար հատուկ տեսակավորման ալգորիթմի կիրառման: Տեսակավորման բոլոր ալգորիթմները տարբերվում են ժամանակի բարդությամբ, որը կախված է տվյալների չափից: Դրանց կատարման ժամանակն ամենակարևորն է հավելվածներ մշակելիս, նույնիսկ եթե դա ընդամենը մի քանի վայրկյան է: Նաև ես իմացա ներքին տեսակավորման ալգորիթմների (տարրերը տեղում դասավորելու) և արտաքին տեսակավորման ալգորիթմների մասին (տեսակավորելիս տարրերի համար լրացուցիչ պահեստային տարածք է պահանջվում): Այս ամենն ինձ ստիպեց ուշադիր դիտարկել յուրաքանչյուր կոնկրետ հավելվածի համար տեսակավորման ալգորիթմների ընտրությունը՝ հաշվի առնելով ժամանակի և հիշողության սահմանափակումները:

Օրինակ 2. մաթեմատիկական արտահայտությունների սինտաքսային վերլուծություն

Հաշվիչի կամ էլեկտրոնային աղյուսակների (օրինակ՝ MS Excel) մեջ որևէ մաթեմատիկական արտահայտություն մուտքագրելուց, մենք միանգամից ստանում ենք ավտոմատ կերպով հաշվարկված պատսխան: Երբևէ մտածե՞լ եք, թե ինչպես է հաշվարկվում այս արտահայտությունը: Բայց ահա, մենք խնդիր ունենք մշակել ծրագրային ապահովում՝ աղյուսակների հետ աշխատելու և արտահայտությունների փարսեր/վերլուծիչ իրականացնելու համար: Հենց նման խնդրի հանդիպելու ժամանակ էլ ես իմացա հանրահայտ սորոտավորման կայանի(Shunting-yard) ալգորիթմի մասին: Այստեղ օգտագործվում է հերթ՝ արժեքները պահելու համար, և սթեք՝ օպերատորներին պահելու համար: Ես ծանոթացա իրական հավելվածների հետ, որոնք օգտագործում են տվյալների կառուցվածքներ, ինչպիսիք են հերթերն ու սթեքերը (ես դրանք ուսումնասիրել եմ տվյալների կառուցվածքների և ալգորիթմների դասընթացում) և հասկացա դրանց հիմքում ընկած տրամաբանությունը: Ես հպարտությունից պայթում, երբ կարողացա ինքնուրույն իրականացնել սորտավորման կայանի ալգորիթմը, չնայած որ շատ էին նմանատիպ այլ լուծումները:

Օրինակ 3. ցուցակներ, հավաքածուներ, բառարաններ

Ամեն անգամ, երբ անհրաժեշտ է պահպանել արժեքների մի փունջ, ես օգտագործում եմ ցուցակները: Նախկինում ես չէի մտածում, թե արդյոք անհրաժեշտ է պահել հերթականությունը, կամ կրկնօրինակներ թույլ տալ. ես պարզապես օգտագործում էի ցուցակները ամեն ինչի համար: Իմանալով, որ ցուցակներից բացի, կան նաև բառարաններ և հավաքածուներ, հասկացա, որ այս ամենը կարելի է կիրառել տարբեր սցենարներում։ Այսպիսով, տվյալ իրավիճակում ճիշտ ընտրություն կատարելով և նախապատվությունը տալով, ասենք, բառարանին, կարող եք իրականում արագացնել կոդի կատարումը։ Օրինակ, եթե դուք պետք է ստուգեք տարրի պատկանելիությունը բազմությանը, դա շատ ավելի արագ կլինի անել հավաքածուում կամ բառարանում (սա պահանջում է մշտական ​​ժամանակ), քան ցուցակների օգտագործման դեպքում (այն ժամանակ է պահանջում ցուցակի երկարությանը համաչափ): Բացի այդ, ցուցակները թույլ են տալիս կրկնօրինակներ, մինչդեռ հավաքածուները՝ ոչ:

Սրանք բոլորը օրինակներ են իմ փորձից, որոնք ցույց են տալիս մտածելակերպի և մոտեցումների անցումը ծրագրավորողականից դեպի ինժեներ-մշակողի: Երբ ես ընտում էի ավելի հարմար տվյալների կառուցվածքը կամ ավելի արագ ալգորիթմը, իմ կոդի կատարման մեջ զգալի բարելավում էր նկատվում: Եվ այսպես!

Ինչի՞ց սկսել

Ծրագրավորման կոնցեպտների և հասկացությունների ուսումնասիրում

Նախքան ալգորիթմների ուսումնասիրությունը սկսելը, ես խորհուրդ կտայի տիրապետել ծրագրավորման այնպիսի հասկացություններին, ինչպիսիք են փոփոխականները, ֆունկցիաները, դասերը և հատկապես օբյեկտ կողմնորոշված ծրագրավորման(OOP) հասկացությունները: Սա կլինի ձեր հիմքը համակարգչային գիտության ավելի առաջադեմ հասկացություններ հասկանալու համար:

Ալգորիթմների և դրանց սկզբունքների ուսումնասիրում

Բացի իմ ուսումնական կուրսի նյութից, ես նաև ինքնուսուցմամբ էի զբաղվում «Ալգորիթմների ներածություն»Թոմաս Հ. Կորմեն, Չարլզ Է. Լեյզերսոն, Ռոնալդ Ռիվեստ, Քլիֆֆորդ Շտայն գրքով: Կարելի է սկսել ամենապարզ հասկացություններից.

• Ժամանակային և տարողականության բարդությունների վերլուծություն
• “O” մեծատառ և “o” փոքրատառ տերմիններ
• Ռեկուրսիաներ
• Տվյալների հիմնային տիպեր, ինչպիսիք են զանգվածները, մատրիցաները, կապակցված ցանկեր, սթեքեր, հերթեր, ծառեր և այլն
• Հիմնական ալգորիթմներ, ինչպիսիք են որոնման և սորտավորման ալգորիթմները

Ժամանակային և տարողականության բարդությունների վերլուծությունը շատ կարևոր թեմա է, որին պետք է տիրապետել ալգորիթմներ վերլուծելու համար: Այնուհետև կարող եք անցնել ավելի առաջադեմ ալգորիթմների, ինչպիսիք են գրաֆային ալգորիթմները:

Ամենակարևորը հստակ հասկանալն է, թե ինչ է կատարվում ալգորիթմի ներսում։ Ես վերցնում էի պարզ օրինակներ և կիրառում էի ալգորիթմ՝ տեսնելու, թե ինչ է տեղի ունենում յուրաքանչյուր քայլում: Օրինակների միջոցով աշխատելն օգնեց ինձ ավելի լավ հասկանալ, թե ինչ է կատարվում ալգորիթմում, և ես երբեք ստիպված չէի անգիր անել այս ալգորիթմները: Եթե ​​ինձ խնդրեն գրել պսեվդոկոդ ալգորիթմի համար, ես հեշտությամբ կարող եմ այն ​​կապել օրինակի հետ և մշակել յուրաքանչյուր քայլը՝ անգիր անելու փոխարեն:

Լիարժեք խորանալ կոդի մեջ

Դասընթացի ընթացքում մեզ հանձնարարեցին զրոյից իրականացնել տվյալների տարբեր կառուցվածքներ՝ օգտագործելով դրանց հիմնական գործողությունները: Օրինակ՝ երկուական որոնման ծառեր (BST) C ++-ում՝ ներդրման, ջնջելու, որոնման օպերացիաներով, հետաձգված ընտրանքի անցումով և հերթական ընտրանքի անցումով: անհրաժեշտ էր ստեղծել BST կլաս և իրագործել այս բոլոր գործողությունները ֆունկցիաների տեսքով: Նույնիսկ առաջարկվել է համեմատել որոշակի գործողությունների կատարման ժամանակը տարբեր չափերի տվյալների հավաքածուների հետ: Դա մեծ փորձ էր: Ես շատ բան սովորեցի այս գործունեությունից և սկսեցի ավելի լավ գլուխ հանել օպերացիաներից: Այս գործնական ուսուցման գործընթացը օգնեց ինձ ավելի լավ հասկանալ ալգորիթմների կոնցեպտները:

Կարելի է սկսել ծրագրավորման լեզուներից, որոնք սպասարկում են OOP. լավագույն ընտրություններից մեկը կարող է լինել C++, Java կամ Python-ը, հատկապես, եթե դուք սկսնակ եք:

Ռեսուրսներ

Օնլայն ռեսուրսներ

Օնլայն տարրբերակով կարելի է զարգացնել հմտությունները ալգորիթների և տվյալների կառուցվածքների մասին հետևյալ աղբյուրներից.

1. Coursera: «Ալգորիթմեր» բաժին, «Տվյալների կառուցվածքներ և ալգորիթմներ» բաժին, «Ալգորիթմներ, մաս I», «Ալգորիթմներ, մաս II».
2. MIT Open Courseware: «Ալգորիթմների ներածություն».
3. Khan Academy: «Ալգորիթմներ».
4. Udacity: «Ալգորիթմների ներածություն», «Ալգորիթմների և տվյալների կառուցվածքների ներածություն», «Տվյալների կառուցվածքներ և ալգորիթմներ», «Ալգորիթմների ներածություն ուսանոցների համար», «Հաշվարկներ, բարդություններ և ալգորիթմներ».
5. edX: «Ալգորիթմներ. նախագծում և վերլուծում. մաս 1», «Ալգորիթմներ. նախագծում և վերլուծում. մաս 2», «Ալգորիթմներ և տվյալների կառուցվածքներ», «Ալգորիթմներ. նախագծում և տեխնիկա», «Ալգորիթմներ. նախագծում և անալիզ», «Գրաֆային ալգորիթմներ».
6. Data Science Tutorials
7. Data Structures and Algorithms
8. Code Monk – Be a better programmer կամ Notes in HackerEarth

և շատ ուրիշ հարթակներ: Առավել լավ ընկալման համար, ցանկալի է նաև կատարել այդ կուրսերի շրջանակում բերված պրակտիկ օրինակներն ու առաջադրանքները:

Ալգորիթմների ինտերակտիվ վիզուալիզացման միջոցներ և գործիքներ

Բացի վերը նշված ռեսուրսներից, կարելի է օգտվել ալգորիթմների պատկերավորման հարթակներից, ինչպիսիք են.

1. Տվյալների կառուցվածքների վիզուալիզացիա.
2. Ալգորիթմների վիզուալիզացիա.
3. VisuAlgo.
4. Սորտավորման ալգորիթմների վիզուալ պատկերավորում
5. Ալգորիթմների անիմացիա.
6. Ալգորիթմների վիզուալիզացիա և վիզուալ պատկերավորում.

Ամրապնդող վարժություններ

Տիրապետելով հիմունքներին, կարող եք անցնել գործնական պարապմունքների, համախմբելով վարժություններում ընդգրկված նյութը։ Ահա այն հարթակները, որտեղ կարող եք գտնել տարբեր դժվարության մակարդակների շատ լավ խնդիրներ.

1. «Project Euler».
2. HackerRank.
3. CodeChef.
4. Coderbyte.
5. Exercism.
6. Codewars.
7. LeetCode.

Որքան շատ պրակտիկ առաջադարնքներ լուծեք, այնքան ավելի հիմնային կլինեն ձեր գիտելիքները: Այսպես դուք կկարողանաք տեսական հմտությունները կիրառել ռեալ խնդիրների լուծման մեջ:

Ռեալիցացիա

Գրեք աշխատանքային կոդ, պատրաստ և անհրաժեշտության դեպքում վրիպազերծված: Դուք պետք է կարողանաք զրոյից գրել տվյալների կառուցվածք կամ ալգորիթմ՝ պարզապես նայելով թղթի կտորին: Եթե ​​ինչ-որ կետում փակուղու եք հանդիպել, ապա միգուցե ինչ-որ բան բաց եք թողել և պետք է վերադառնաք առաջին քայլին:

Տվյալների կառուցվածքների մասին սովորելը հիմնականում վերաբերում է դրանց ըմբռնմանը, այլ ոչ միայն իրականացմանը: Դա պայմանավորված է նրանով, որ տվյալների կառուցվածքը մանիպուլյացիայի ենթարկելը որոշակի խնդրին համապատասխանելու համար պահանջում է հասկանալ, թե ինչպես է աշխատում այդ տվյալների կառուցվածքը: Այսպիսով, կարևոր չէ, թե ինչ լեզվով է գրված տվյալների կառուցվածքը։ Փոխարենը, փորձեք պատկերացնել, թե ինչպես է այն աշխատում՝ օգտագործելով թղթի կտոր և մատիտ:

Չհանձնվեք ու դադար չտաք!

Նույնիսկ , եթե ամեն ինչ ձեզ դժվար է թվում, չհանձնվե՛ք: Պարտության ընդունումը, հանձնվելու որոշումը խանգարում է գրեթե յուրաքանչյուր ծրագրավորողի, բայց միայն նրանք, ովքեր կամքի ուժ ունեն չհանձնվելու, ինչ-որ բանի կհասնեն որպես ծրագրավորող։

• Կարդացեք այլ ծրագրավորողների կոդը: Դուք չպետք է անմիտ կերպով պատճենեք և տեղադրեք կոդը, այլ ավելի շուտ փորձեք հասկանալ լուծման հիմնական գաղափարը: Այնուհետև փակեք կոդը և փորձեք գրել ձեր սեփական լուծումը՝ հիմնվելով ձեր նոր կարդացածի վրա, բայց առանց կոդին նայելու: Սա շատ կարևոր է, քանի որ միայն եթե ձեզ հաջողվի լուծել խնդիրը այս կերպ, կարող եք վստահ լինել, որ իսկապես հասկանում եք, թե ինչպես է ամեն ինչ աշխատում:
• Բոլոր առաջադրանքները, որոնց հետ դուք կառընչվեք, հիմնականում ունեն իրար նման խնդիրներ: Այսպիսով, ալգորիթմների և տվյալների կառուցվածքների հետ քրտնաջան աշխատանքի ընթացքում դուք կսովորեք, թե ինչպես լուծել խնդիրներ, որոնք ժամանակին ձեզ անլուծելի էին թվում:

Մրցակցեք

Կարծիք կա, որ մրցակցությունը լավագույն փորձն է: Նման միջոցառումները ձեզ կօգնեն սովորել ավելի լավ կառավարել ինքներդ ձեզ սթրեսային իրավիճակներում, ինչպես նաև կստուգեն, թե որքանով եք ծանոթ կոնկրետ թեմայի հետ: Յուրաքանչյուր մրցույթից հետո համոզվեք, որ հասկանում եք և լուծում եք ցանկացած խնդիր, որը չեք լուծել մրցույթի ընթացքում: Դա ամենակարևորն է։

Ամփոփում

Հոդվածն ամփոփենք տասը առաջարկությունների ցանկով բոլոր նրանց համար, ովքեր սկսում են սովորել ալգորիթմներ.

1. Սկսեք սովորելով հիմունքները
2. Հստակ պատկերացում կազմեք, թե ինչ է կատարվում ալգորիթմում
3. Ուսումնասիրեք և զարգացրեք ալգորիթմի յուրաքանչյուր քայլը օրինակներով
4. Մանրակրկիտ ուսումնասիրեք բարդության անալիզը
5. Փորձեք ինքներդ իրականացնել ալգորիթմները
6. Կարևոր ամեն ինչի մասին նշում կատարեք, որպեսզի հետագայում վերդառնաք դրանց
7. Անցեք առցանց դասընթացներ ուսումնական հարթակներում
8. Հետևեք հայտնի համալսարանների կողմից հրապարակված առցանց դասախոսություններին
9. Ամրապնդեք այն, ինչ սովորել եք վարժություններում
10. Եթե վարժությունների ընթացքում դժվար առաջադրանքների եք հանդիպում, մի հուսահատվեք: Վարժությունն ավարտելուց հետո կարող եք կարդալ հատուկ հրահանգները և հասկանալ, թե որտեղ եք բլոկավորվել

Սկզբնաղբյուր՝ How to be Good at Algorithms?