Деякі структури даних та основні операцї над ними (масиви, купа, стек, дек, черга)

Маси́в — впорядкований набір фіксованої кількості однотипних елементів, що зберігаються в послідовно розташованих комірках оперативної пам'яті, мають порядковий номер і спільне ім'я, що надає користувач.(Відсортовувати, присвоювати елементи в комірки, переставляти елементи і тд.)

Двійкова купа (binary heap) - просто реалізована структура даних, що дозволяє швидко (за логарифмічна час) додавати елементи і витягувати елемент з максимальним пріоритетом (наприклад, максимальний за значенням).

Будемо розглядати масив як двійкове дерево. • Кожна вершина дерева відповідає елементу масива. Якщо вершина має індекс і, то її батько має індекс i/2. Вершина з індексом 1 - це корінь, а її дочірні вершини мають індекси 2і та 2і+1.

Стек — різновид лінійного списку, структура даних, яка працює за принципом «останній прийшов — перший пішов» (LIFO).

Операції зі стеком - push («заштовхнути елемент») pop («виштовхнути елемент»)

Черга — динамічна структура даних, що працює за принципом «перший прийшов — перший пішов» (англ. FIFO).

Основні операції з чергою

enqueue — "поставити в чергу".

dequeue — "отримання з черги".

Дек (двостороння черга) - структура даних типу «список», що функціонує одночасно за двома принцам організації даних: FIFO і LIFO.

Операції:

додавання елемента в початок;

додавання елемента в кінець;

видалення першого елемента;

видалення останнього елемента;

читання першого елемента;

читання останнього елемента.

Реалізація цих структур даних.

Основи застосування цих структур даних.

Клас NP-повних задач та їх приклади.

Поліноміальний час розв’язку.

Перевірка належності класу NP. NP-повнота і зведення.

Деякі NP-повні задачі.

Задача про виконуваність схеми.

Задача про кліку.