Бакалавърски програми - Каталог 2020/2021 | Информационни технологии | CITB308

CITB308 Структури от данни

Анотация:

Курсът разглежда основни алгоритми и структури от данни. Набляга се на практическите аспекти при реализацията на основни структури от данни, използвайки езика за програмиране C++. Някои от сновните структури от данни, които се разглеждат в курса са свързани списъци, стекове, опашки и вектори, както и по-сложни като двоични дървета за търсене, и речници. Също така курса обхваща основни алгоритми за сортиране, като се набляга на тяхното сравнение и приложение.

http://nikolay.kirov.be/2020/CITB308/index.html

прочети още
Към курсовете на програмата График Виртуално обучение
Информационни технологии

Преподавател(и):

доц. Николай Киров  д-р
доц. Методи Трайков  д-р

Описание на курса:

Компетенции:

Успешно завършилите курса студенти:

1) Знаят:

• Стекове, опашки, свързани списъци и рекурсия.

• Абстрактния тип „дърво“, основни алгоритми върху дървета, двоични дървета, структури от данни за представяне на дървета.

• Абстрактния тип „приоритетна опашка“.

• Абстрактния тип „речник“. Хеш-таблици , подредени речници.

• Дървета за двоично търсене, АВЛ-дървета, многопосочни дървета, (2,4) дървета, червено-черни дървета.

• Абстрактен тип „множество“, долна граница на сортиране на базата на сравнения, сравнение на алгоритми за сортировка.

2) Могат:

• Да използват рекурсия, стекове, опашки, свързани списъци, двусвързани опашки.

• Да използват STL вектори, списъци и последователности.

• Да реализират приоритетна опашка, използвайки последователност. Да реализират структурата от данни Heap.

• Да реализират алгоритмите за сортировка Quick Sort, Bucket Sort, Radix Sort.

• Да използват дървета, сравнение на символни низове, търсене на подобие в символни низове.
Предварителни изисквания:
CITB107 Програмиране на

CITB205 Обектно-ориентирано програмиране (С++)

Форми на провеждане:
Редовен

Учебни форми:
Лекция

Език, на който се води курса:
Български

Теми, които се разглеждат в курса:

  1. Език за програмиране С++ Базисни елементи, изрази, функции, класове, Наследственост и полиморфизъм, шаблони, обработка на изключения
  2. Анализ на алгоритми Време за изпълнение, псевдокод, анализ на алгоритми, асимптотичната нотация, асимптотичен анализ
  3. Стек, опашка и дек Стек, опашка, свързан списък, дек
  4. Вектори, списъци и редици Вектори, списъци, редици, метод на мехурчето с редици, итератори, Йерархия от редични абстрактни типове данни (АТД).
  5. Тест 1 / Практическа работа
  6. Дървета Дървета АТД, базови алгоритми за дървета. Двоични дървета, структури от данни за представяне на дървета.
  7. Приоритетна опашка Приоритетна опашка АТД, реализиране на приоритетна опашка с редица. Хип, реализиране на приоритетна опашка като хип.
  8. Тест 2 / Контролна работа
  9. Речници Речник АТД, наредени речници. Хеширане.
  10. Търсещи дървата Двоични търсещи дървета, AVL-дървета. Multi-Way търсещи дървета, (2,4)-дървета, червено-черни дървета.
  11. Тест 3 / Контролна работа

Литература по темите:

Учебник:Michael Goodrich, Roberto Tamassia, David M. Mount, Data Structures and Algorithms in C++, Wiley, 2004.

[Библиотека на НБУ: Ч 681.325.3 / G 64 и Moodlе NBU]

Michael Goodrich, Roberto Tamassia, David M. Mount, Data Structures and Algorithms in C++, Wiley, Second edition, 2011. [Moodle NBU]

Средства за оценяване:

Лекции - 3 теста за текущо оценяване и тест и писмено изложение за финално оценяване

Упражнения - Две практически контролни работи по време на семестъра, които представляват разработка на програми на C++ по зададена задача и 2 домашни работи за текущо оценяване. Практически изпит за финално оценяване.

http://nikolay.kirov.be/2020/CITB308/index.html