Դասախոս`	Արմեն Կոստանյան
Դասերը`	Շաբաթական 1 դասախոսություն, 1 գործնական

Կարճ Նկարագրություն

Դիտարկվում են մի շարք ոչ գծային տվյալների կառուցվածքներ (բինար և բինոմիալ բուրգեր, որոնման ծառեր, hash-աղյուսակներ, B-ծառեր, չհատվող բազմությունների համակարգեր): Հատուկ ուշադրություն է դարձվում գործողությունների բարդության գնահատականներին և կիրառություններին: Դասընթացը ներառում է դիտարկվող կառուցվածքների իրականացում C++ լեզվով:

Պահանջները

Նախնական գիտելիքներ: Դասընթացը ենթադրում է

• պարզագույն տվյալների կառուցվածքների իմացություն (զանգված, կապակցված ցուցակ, պահունակ, հերթ, առաջնայնություններով հերթ),
• C++ լեզվի հիմնական հասկացությունների իմացություն (տվյալների տիպեր, հրահանգներ, զանգվածներ, ցուցիչներ, ֆունկցիաներ, դասեր, գործողությունների գերաբեռնում):
• մաթեմատիկական անալիզի հիմնական հասկացությունների իմացություն:

Տնային աշխատանքներ: Շաբաթական տնային աշխատանքներ:

Գնահատումը

• 10% կազմվում է դասերին մասնակցությունից և դրսևորած ակտիվությունից,
• 40%-ը` տնային աշխատանքների կատարումից,
• 25%-ը` առաջին գրավոր քննությունից:
• 25%-ը` երկրորդ գրավոր քննությունից:

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

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001
2. Robert Sedgewick. Algorithms in C++. Parts 1-4. Fundamentals. Data Structures. Sorting. Searching. Addison-Wesley, 1999
3. H. M. Deitel, P. J. Deitel. C++: How to program. Prentice Hall, 3rd edition, 2001.

Բովանդակություն
Դասախոսություններ
1. Ներածություն: Բինար ծառի հասկացություն: Բինար ծառի շրջանցումներ: (2 ժամ)
2. Բինար բուրգի (Binary Heap) հասկացություն: Առաջնայնություններով հերթի մոդելավորում բինար բուրգի միջոցով: (2 ժամ)
3. Որոնման բինար ծառեր: Որոնման, ավելացման, հեռացման գործողություններ: Բարդության գնահատականներ: (4 ժամ)
4. Բալանսավորված բինար ծառի հասկացություն: Կարմիր-սև ծառեր (Red-Black Trees): Բալանսավորում տարրի ավելացումից և հեռացումից հետո որոնման կարմիր-սև ծառում: (4 ժամ)
5. Տվյալների կառուցվածքի ընդլայնում: Դինամիկ վիճակագրության ծառեր` տարրի կարգահամարի որոշման և կարգահամարով տարրի որոշման ալգորիթմներ: Միջակայքերի ծառեր: (4 ժամ)
6. Hash -աղյուսակներ: Բաց և փակ հեշավորում: Որոնման, ավելացման և հեռացման գործողություններ: Բարդության գնահատականներ: (4 ժամ)
7. Բինոմիալ բուրգեր (Binomial Heaps): Գործողություններ բինոմիալ բուրգերի հետ: Բարդության գնահատականներ: (4 ժամ)
8. B-ծառեր: Որոնման, ավելացման և հեռացման գործողություններ: Բարդության գնահատականներ: (4 ժամ)
9. Չհատվող բազմությունների համակարգեր (Disjoint-Set Data Structures): Ցուցակի և անտառի միջոցով ներկայացման ձևեր: Բարդության գնահատականներ: (4 ժամ)

Գործնական պարապմունքներ
1. Բուրգի իրականացում C++ լեզվով: (2 ժամ)
2. Որոնման բինար ծառի իրականացում C++ լեզվով: (4 ժամ)
3. Որոնման կարմիր-սև ծառի իրականացում C++ լեզվով: (4 ժամ)
4. Որոնման կարմիր-սև ծառերում կարգային վիճակագրության գործողությունների իրականացում C++ լեզվով: (2 ժամ)
5. Փակ Hash-աղյուսակի իրականացում C++ լեզվով: (3 ժամ)
6. Բաց Hash աղյուսակի իրականացում C++ լեզվով: (3 ժամ)
7. Բինոմիալ բուրգի իրականացում C++ լեզվով: (4 ժամ)
8. B- ծառի իրականացում C++ լեզվով: (4 ժամ)
9. Ցուցակների միջոցով չհատվող բազմությունների համակարգի իրականացում C++ լեզվով: (3 ժամ)
10. Անտառի միջոցով չհատվող բազմությունների համակարգի իրականացում C++ լեզվով: (3 ժամ)