Lecture 1. Introduction

1. Տվյալների կառուցվածքներ

Ներածություն

2. Գրականություն

1. H.T.Cormen, C.E.Leiserson, R.L.Rivest,C.Stein Introduction to
Algorithms.Third Edition. The MIT Press. 2009.
2. Топп У., Форд У. Структуры данных в С ++, М., Бином, 2000 г.
3. Кнут Д. Искусство программирования, том 1, изд-во Вильямс,
М., 2000 г.
4. Ахо А. И др. Структуры данных и алгоритмы, изд-во Вильямс,
М., 2000 г.
5. Каррано Ф., Причард Дж. Абстракция данных и решение задач
на C++. Стены и зеркала. Изд-во Вильямс, М., 2003 г.
6. Ս.Գ. Սարգսյան, Ա.Ս.Հովակիմյան, Կ.Ս.Դարբինյան,
Ս.Ա.Ավետիսյան, Ն.Հ.Իսպիրյան. Տվյալների կառուցվածքներ ,
ուսումնական ձեռնարկ, ԵՊՀ, 2010թ.:
2

3. Ի՞նչ է ծրագիրը

• Program= A Set of Instructions
• Program=Data Structures + Algorithms
• Data Structure = A Container stores Data
• Algoirthm = Logic + Control
3

4. Ինչպիս՞ի ալգորիթմներ

Countless – անվերջ քանակությամբ
Algorithm Strategies
• Greedy- ագահ
• Divide and Conquer- բաժանիր և տիրիր
• Dynamic Programming- դինամիկ ծրագրավորում
• Searching - որոնում
• Sorting - կարգավորում
4

5. Լավագույն ալգորիթմներ և տվյալների կառուցվածքներ

• Must Meet Requirement- բավարարում են
պահանջներին
• High Performance- ապահովում են բարձր
կատարողականություն
• Low RAM footprint – պահանջում են մինիմալ
հիշողություն
• Easy to implement – հեշտ իրականացվող են
5

6. Հիմնական գաղափարներ

• System Life Cycle- համակարգի կյանքի ցիկլ
• Algorithm Specification- ալգորիթմի սպեցիֆիկացիա
• Data Abstraction- տվյալների աբստրակցիա
• Performance Analysis- կատարողականության
վերլուծություն
• Performance Measurement- կատարողականության
չափում
6

7. Ծրագրային համակարգի կյանքի ցիկլ

• Requirements – պահանջների ձևակերպում
• Analysis –վերլուծություն
• Design – նախագծում
• Coding – կոդավորում
• Verification- վերիֆիկացիա
➢Program Proving- ճշտության ապացույց
➢Testing - թեստավորում
➢Debugging- -ճշգրտում, կարգաբերում
• Maintenance – շահագործում, աջակցում
7

8. Ալգորիթմի սպեցիֆիկացիա

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

9. Օրինակ. Բինար որոնում կարգավորված զանգվածում

[0]
[1]
[2]
[3]
[4]
[5]
[6]
8
14
26
30
43
50
52
left right middle list[middle] : searchnum
0
6
3
30
<
43
4
6
5
50
>
43
4
4
4
43
==
43
0
6
3
30
>
18
0
2
1
14
<
18
2
2
2
26
>
18
2
1
-
Ծրագրի հատված
while( left<=right) {
middle = (left + right) / 2;
if (searchnum < list[middle])
right = middle - 1;
else if (searchnum == list[middle])
return middle;
else left = middle + 1;
}
9

10. Տվյալների աբստրակցիա Data abstraction

• Տվյալների աբստրակտ տիպը (ՏԱՏ, Abstract Data Type ADT ) տվյալների մաթեմատիկական մոդելն է և այն
գործողությունների համախումբը, որոնք կարելի է
կատարել այդ տվյալների նկատմամբ:
• Տվյալների աբսրակտ տիպերում տվյալների և
գործողությունների նկարագրությունը առանձնացված
է տվյալների ներկայացման ձևերից և
գործողությունների ծրագրային իրակացումից:
10

11. Գործողություններ տվյալների աբստրակտ տիպերի նկատմամբ

• Add – տարրի ավելացում
• Index – ըստ ինդեքսի
• Key – ըստ բանալու
• Position - ըստ դիրքի
• Priority – ըստ նախապատվության
• Find – տարրի որոնում
• Get – հասանելիություն տարրին
• Change - տարրի փոփոխում
• Delete - տարրի հեռացում
11

12. ՏԱՏ-ի օրինակներ

• Աբստրակտ գծային ցուցակ – Abstract List
• Մոդելը՝ նույնատիպ տարրերի հաջորդականություն
• Գործողություններ՝ տարրի ավելացում/հեռացում որոշակի
դիրքում
• Պահունակ – Stack
• Մոդելը՝ նույնատիպ տարրերի հաջորդականություն,
պահունակի «գագաթի» գաղափար
• Գործողություններ՝ տարրի ավելացում պահունակի գագաթում,
տարրի հեռացում պահունակի գագաթից
• Հերթ – Queue
• Մոդելը՝ նույնատիպ տարրերի հաջորդականություն, հերթի
«սկզբի» և «վերջի» գաղափարներ
• Գործողություններ՝ տարրի ավելացում հերթի վերջում, տարրի
հեռացում հերթի սկզբից
12

13. ՏԱՏ-ի օրինակներ (շար.)

• Նախապատվությամբ հերթ – Priority Queue
• Մոդելը՝ նույնատիպ տարրերի հաջորդականություն, տարրի
«նախապատվության» գաղափար
• Գործողություններ՝ տարրի ավելացում հերթի վերջում,
ամենաբարձր նախապատվությամբ տարրի հեռացում
• Տարրերի բազմություն – Set
• Մոդելը՝ նույնատիպ տարրերի բազմություն
• Գործողություններ՝ տարրի ավելացում/հեռացում,
բազմությունների միավորում /հատում
• Գրաֆ– Graph
• Մոդելը՝ G=(V,E) գագաթների և կողերի բազմություն
• Գործողություններ՝ գագաթի/կողի ավելացում/հեռացում,
կապակցված բաղադրիչների որոշում և այլն
13

14. ADT-ի նկարագրություն

• ADT-ի անուն
• Տվյալների սպեցիֆիկացիա` մաթ.մոդել
• Գործողություն 1
• մուտք - input
• նախապայման- precondition
• պրոցես- process
• ելք- output
• վերջնապայման - postcondition
• բացառություն -exception
• Գործողություն 2
14

15. Օրինակ

ADT Abstract List
Տվյալների սպեցիֆիկացիա` մաթ.մոդել
InsertElem (item, pos)- տարրի ավելացում pos դիրքում
• մուտք - item, pos
• նախապայման – pos-ի թույլատրելի արժեք
• պրոցես- տարրի ավելացում
• ելք- չկա
• վեջնապայման – ավելացված տարրով ցուցակ
• բացառություն - pos-ի անթույլատրելի արժեք
15

16. Տվյալների կառուցվածքներ

• Տվյալների կառուցվածքներն աբստրակտ տիպերի
տվյալների ներկայացման եղանակներն են, որոնք
աջակցվում են ծրագրավորման լեզուներում:
• Աբստրակտ տիպերի տվյալների համար
սահմանած գործողությունների իրականացումը
պայմանավորված է տվյալների ներկայացման
ձևով:
16

17. Հիմնական տվյալների կառուցվածքներ Common Data Structures

• Array - զանգված
• Linked List- կապակցված ցուցակ
• Tree – ծառ
• Binary Tree –բինար ծառ
• Heap- բուրգ
• Hash Table – հեշ-աղյուսակ
17