Skip to content

Latest commit

 

History

History
50 lines (42 loc) · 4.91 KB

exam.md

File metadata and controls

50 lines (42 loc) · 4.91 KB
Raw

Підготовка до екзамену

Екзамен буде складатися з теоретичної та практичної частин. Теоретична буде за структурою аналогічна мідтерму, практична - написання коду.

Перший терм курсу

Теоретична частина
  • Поняття алгоритму та структури даних;
  • Big-O notation, часова та просторова складність. Лінійна, поліноміальна, логарифмічна складність;
  • Базові структури даних: стек, список, черга, словник (на основі хеш-таблиці);
  • Граф як структура даних, пошук в ширину та глибину;
  • Інші алгоритми на графах: пошук шляху (алгоритми Дейкстри та А*), кістякове дерево, максимальний потік;
  • Купа (heap) як структура даних;
  • Жадібні алгоритми;
  • Префіксні коди, кодування Гафмана;
  • Задача про покриття множини;
Практична частина

Почніть з того, що впевніться що можете за допомогою C#:

  • Створити клас;
  • Створювати та користуватися полями в класі;
  • Інстанціювати екзмепляри цього класу за допомогою оператора new та виклику конструктора;
  • Створювати публічні та приватні методи в класи, розумієте коли потрібно створювати перші та други;

Далі, згадайте як самостійно реалізовувати такі структури як список (на основі масиву), звʼязний список, словник (це має бути свіжим у памʼяті), купа. Ідеально буде якщо ви спробуєте без сторонньої допомоги та інтернету реалізувати ці структури.

Під кінець, продивіться декілька задач з числа тих, що ми розвʼязували на парі теоретично та спробуйте їх розвʼязати практично. Наприклад:

  • Маючи звʼязний список, знайдіть найбільш ефективним способом його серединний елемент;
  • Маючи купу, записану за допомогою масиву, видаліть з неї максимальний елемент та поверніть масив у стан валідної купи;
  • Маючи невідсортований масив чисел, перевірте, чи містить три числа a, b та с такі що a == b + 1, та b == c + 1

Другий терм курсу

Теоретична частина
  • Базові структури даних з попереднього терму - список, черга, словник, купа, стек;
  • BST, операції на ньому, обходи дерева, повороти;
  • Динамічне програмування;
  • Концепт Divide&Conquer;
  • Алгоритми сортування, базові, просунуті (mergesort, quicksort, heapsort) та спеціальні (count sort, radix sort);
  • Фільтр Блума;
  • Структури даних на основі дерев: AVL, Kd, R-дерева,
  • Суфіксне та префіксне дерева;
  • Базова класифікація (k-nearest);
  • Геометричні алгоритми, задача про опуклу оболонку;
  • Класи складності P, NP, NP-complete;

Повторіть завдання з мідтерму, проаналізуйте структури даних, що ми вивчали, за алгоритмом розглянутим на останній парі терму.

Практична частина
  1. Прогляньте практичні роботи курсу, згадайте задачі та підходи до розвʼязання;
  2. Продивіться задачі що ми розвʼязували на заняттях, ті де писали код і які розвʼязували теоретично, подумайте як їх можна вирішити практично;
  3. Повторіть базову роботу з класами яка потрібна для створення структур даних. Впевніться що знаєте як реалізовувати всі розглянуті нами структури даних.