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

Դասախոս` Արմեն Կոստանյան
Դասերը` Շաբաթական 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 ժամ)