125 Кібербезпека / Магістр (вступні питання)

Шаблон функції задає спосіб побудови окремих функцій. Синтаксис шаблону функції:

template <список параметрів шаблону функції>

тип_функціі ім'я_функції (список формальних параметрів)(...)

Всі параметри зі списку параметрів шаблону функції повинні бути так званими типовими параметрами, тобто параметрами, які задають типи формальних параметрів функції та/або значення, які повертається функцією.

Опис шаблону класу виглядає як традиційний опис класу, за винятком заголовка templateclass T, що вказує на те, що це опис є шаблоном класу з параметром типу Т, що позначає тип класів, які створюватимуться на основі цього шаблону. Ідентифікатор Т визначає тип даних-елементів, що зберігаються в стеку, і може використовуватися в заголовку класу і у функціях-

елементах.

Окрім визначення узагальнених функцій, можна також визначити узагальнений клас. Для цього створюється клас, у якому визначаються всі використовувані ним алгоритми. При цьому реальний тип оброблюваних у ньому даних задається як параметр при побудові об'єктів цього класу.

Узагальнені класи особливо є корисними тоді, коли в них використовується логіка, яку можна узагальнити. Наприклад, алгоритми, які підтримують функціонування черги цілочисельних значень, також надаються і для підтримки символьних значень. Механізм, який забезпечує підтримку зв'язного списку поштових адрес, також годиться для підтримки зв'язного списку, призначеного для зберігання даних про запчастини до автомобілів. Після свого створення узагальнений клас виконує визначену програмістом операцію (наприклад,

підтримку черги або зв'язного списку) для будь-якого типу даних. Компілятор автоматично згенерує коректний тип об'єкта на основі типу, який задається під час його створення. Загальний формат оголошення узагальненого класу має такий вигляд: template class ім'я_класу { // Тіло класу }; У цьому записі елемент tType є "заповнювачем" для імені типу, який задається під час реалізації класу. У разі потреби можна визначити декілька узагальнених типів даних, використовуючи перелік елементів, розділених між собою комами.

Створивши узагальнений клас, можна створити його конкретний примірник,

використовуючи такий загальний формат: ім'я_класу <тип> ім'я_об'єкту; У

цьому записі елемент тип означає ім'я типу даних, які оброблятимуться примірником узагальненого класу. Функції-члени узагальненого класу автоматично є узагальненими. Тому програмісту не потрібно використовувати ключове слово template для безпосереднього визначення їх такими.

74. Алгоритми сортування та пошуку

Алгоритм сортування — це алгоритм, що розв'язує задачу сортування,

тобто здійснює впорядкування лінійного списку (масиву) елементів.

Характеристики алгоритмів Для алгоритму сортування (як і для будь-якого іншого сучасного

алгоритму) основними характеристиками є: час необхідний на впорядкування n-елементного масиву і додаткова пам'ять необхідна для впорядкування. Крім цих двох характеристик, сортування буває стабільним чи нестабільним, з

використанням додаткової інформації про елементи, чи без використання.

Для значної кількості алгоритмів середній і найгірший час впорядкування n-елементного масиву є \;O(n^2), це пов'язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між індексами елементів не перевищує деякого заданого числа). Такі алгоритми зазвичай є стабільними,

хоча і не ефективними для великих масивів.

Інший клас алгоритмів здійснює впорядкування за час O(n\log\;n). В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного.

Теорема про найкращий час сортування Якщо алгоритм сортування в своїй роботі спирається тільки на операції

порівняння двох об'єктів (≤) і не враховує жодної додаткової інформації про елементи, то він не може впорядкувати масив елементів швидше ніж за

O(n\log\;n) в найгіршому випадку

Список алгоритмів різної часової складності:

За час \;O(n^2)

Сортування вибором — простий алгоритм сортування лінійного масиву,

на основі вставок. Має ефективність n2, що робить його неефективним при сортування великих масивів, і в цілому, менш ефективним за подібний алгоритм сортування включенням. Сортування вибором вирізняється більшою простотою, ніж сортування включенням, і в деяких випадках, вищою продуктивністю.

Алгоритм працює таким чином: 1.Знаходить у списку найменше значення

2.Міняє його місцями із першим значеннями у списку

3.Повторює два попередніх кроки, доки список не завершиться

(починаючи з другої позиції)

Фактично, таким чином ми поділили список на дві частини: перша (ліва)

— повністю відсортована, а друга (права) — ні.

Сортування включенням — простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми,

як швидке сортування, пірамідальне сортування та сортування злиттям. Однак,

має цілу низку переваг:

простота у реалізації

ефективний (зазвичай) на маленьких масивах

ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна O(n + d), де d — кількість інверсій

на практиці ефективніший за більшість інших квадратичних алгоритмів (O(n2)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n2/4, і в найкращому випадку є лінійною

є стабільним алгоритмом

Наприклад, більшість людей при сортуванні колоди гральних карт,

використовують метод, схожий на алгоритм сортування включенням.

сортування обміном За час O(n\log\;n)

Пірамідальне сортування (англ. Heapsort, «Сортування купою») —

алгоритм сортування, працює в найгіршому, в середньому і в найкращому випадку (тобто гарантовано) за Θ(n log n) операцій при сортуванні n елементів.

Кількість застосовуваної службової пам'яті не залежить від розміру масиву

(тобто, O (1)).

Сортування пірамідою використовує бінарне сортувальне дерево.

Сортувальне дерево — це таке дерево, у якого виконані умови:

Кожен лист має глибину або {\displaystyle d} d, або {\displaystyle d-1} {\displaystyle d-1}, де {\displaystyle d} d — максимальна глибина дерева;

Значення в будь-якій вершині не менші (інший варіант — не більші) за значення їх нащадків.

Зручна структура даних для сортувального дерева — такий масив Array,

що Array[1] — елемент в корені, а нащадки елемента Array[i] є Array[2i] і

Array[2i+1].

Алгоритм сортування складатиметься з двох основних кроків:

1. Вибудовуємо елементи масиву у вигляді сортувального дерева:

{\displaystyle {\text{Array}}[i]\geq {\text{Array}}[2i]} {\displaystyle {\text{Array}}[i]\geq {\text{Array}}[2i]}

{\displaystyle {\text{Array}}[i]\geq {\text{Array}}[2i+1]} {\displaystyle {\text{Array}}[i]\geq {\text{Array}}[2i+1]}

при {\displaystyle 1\leq i<n/2} {\displaystyle 1\leq i<n/2}

Цей крок вимагає {\displaystyle O(n)} O(n) операцій.

Будемо видаляти елементи з кореня по одному за раз і перебудовувати дерево. Тобто на першому кроці обмінюємо Array[1] і Array[n], перетворюємо

Array[1], Array[2], … , Array[n-1] в сортувальне дерево. Потім переставляємо

Array[1] і Array[n-1], перетворюємо Array[1], Array[2], … , Array[n-2] в

сортувальне дерево. Процес продовжується до тих пір, поки в сортувальному дереві не залишиться один елемент. Тоді Array[1], Array[2], … , Array[n] —

впорядкована послідовність.

Швидке сортування (англ. Quick Sort) — алгоритм сортування, добре відомий, як алгоритм розроблений Тоні Гоаром (C. A. R. Hoare), який не потребує додаткової пам'яті і виконує у середньому {\displaystyle \;O(n\log \;n)} {\displaystyle \;O(n\log \;n)} операцій. Однак, у найгіршому випадку робить

{\displaystyle O(n^{2})} O(n^{2}) порівнянь. Оскільки алгоритм використовує дуже прості цикли і операції, він працює швидше інших алгоритмів, що мають таку ж асимптотичну оцінку складності. Наприклад, зазвичай більш ніж удвічі швидший порівняно з сортуванням злиттям.

Ідея алгоритму полягає в переставлянні елементів масиву таким чином,

щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин відбувається рекурсивно. Алгоритм швидкого сортування може бути реалізований як у масиві, так і в двозв'язному списку.

Швидке сортування є алгоритмом на основі порівнянь, і не є стабільним.

Сортування злиттям (англ. merge sort) — алгоритм сортування, в основі якого лежить принцип «Розділяй та володарюй».

В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів,

перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової.

Під час сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу. Потім з основної черги беруться наступні дві відсортовані підпослідовності і так доти, доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих

підпослідовностей. Сортування триватиме доти, доки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності.

За час \;O(n) з використанням додаткової інформації про елементи Сортування підрахунком (англ. Counting sort) — алгоритм впорядкування,

що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві так і від кількості різних елементів.

Ідея алгоритму полягає в наступному: спочатку підрахувати скільки разів кожен елемент (ключ) зустрічається в вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за

один прохід поставити всі елементи на свої місця.
Сортування за розрядами
Клас Алгоритм сортування
Структура даних Масив
Найгірша швидкодія {\displaystyle O(kN)} {\displaystyle O(kN)}
Просторова складність у найгіршому випадку {\displaystyle	O(k+N)}
{\displaystyle O(k+N)}

Сортування за розрядами (англ. Radix sort) — швидкий стабільний алгоритм впорядкування даних. Застосовується для впорядкування елементів,

що є ланцюжками над будь-яким скінченним алфавітом (напр. рядки, або цілі числа). Як допоміжний використовує будь-який інший стабільний алгоритм сортування.

Алгоритм застосовувався для впорядкування перфокарт.сортування комірками. Ідея полягає в тому, щоб спочатку впорядкувати всі елементи за молодшим розрядом, потім стабільно впорядкувати за другим розрядом, потім за третім і так далі аж до найстаршого. Оскільки, припускається, що кожен розряд приймає значення з невеликого діапазону, то кожен цикл впорядкування можна виконувати швидко і з малими затратами пам'яті.

За час O(n\log^2\;n)

Сортува́ння Ше́лла — це алгоритм сортування, що є узагальненням сортування включенням.

Алгоритм базується на двох тезах:

Сортування включенням ефективне для майже впорядкованих масивів.

Сортування включенням неефективне, тому що переміщує елемент тільки на одну позицію за раз.

Тому сортування Шелла виконує декілька впорядкувань включенням,

кожен раз порівнюючи і переставляючи елементи, що розташовані на різній відстані один від одного.

Сортування Шелла не є стабільним.

Ідея алгоритму На початку обираються m-елементів: {\displaystyle d_{1},d_{2},\dots ,d_{m}} {\displaystyle d_{1},d_{2},\dots ,d_{m}}, причому,

{\displaystyle d_{1}>d_{2}>\dots >d_{m}=1} {\displaystyle d_{1}>d_{2}>\dots >d_{m}=1}.

Потім виконується m впорядкувань методом включення, спочатку для елементів, що стоять через {\displaystyle \;d_{1}} {\displaystyle \;d_{1}}, потім для елементів через {\displaystyle \;d_{2}} {\displaystyle \;d_{2}} і т. д. до

{\displaystyle \;d_{m}=1} {\displaystyle \;d_{m}=1}.

Ефективність досягається тим, що кожне наступне впорядкування вимагає меншої кількості перестановок, оскільки деякі елементи вже стали на свої місця.

75. Методи розробки алгоритмів: “розділяй і володарюй”, динамічне програмування, "жадібні" алгоритми, пошук з поверненням

«Розділя́й та володарю́й » — важлива парадигма розробки алгоритмів, що полягає в рекурсивному розбитті розв'язуваної задачі на дві або більше підзадачі того ж типу, але меншого розміру, і комбінуванні їх розв'язків для отримання відповіді до вихідного завдання. Розбиття виконуються доти, поки всі підзавдання не стануть елементарними.

Динамічним програмуванням (в найбільш загальній формі) називають процес покрокового розв‘язку задачі, коли на кожному кроці вибирається один розв‘язок з множини допустимих на цьому кроці, причому такий, який оптимізує задану цільову функцію або функцію критерію. В основі теорії динамічного програмування лежить принцип оптимальності Белмана.

Жа́дібний алгори́тм — простий і прямолінійний евристичний алгоритм, який приймає найкраще рішення, виходячи з наявних на поточному етапі даних, не турбуючись про можливі наслідки, сподіваючись врешті-решт отримати оптимальне рішення. Легкий в реалізації і часто дуже ефективний за часом виконання. Багато задач не можуть бути розв'язані з його допомогою.

Пошук з вертанням (англ. backtracking), також пошук з поверненням — загальний алгоритм для знаходження всіх (або деяких) розв'язків деякої обчислювальної задачі, який поступово будує кандидатів на розв'язок, і відкидає кожного неповного кандидата c («вертається») як тільки визначає, що c не може бути доповненим до вірного розв'язку.

Класичний приклад використання пошуку з вертанням — це задача про вісім ферзів, в який потрібно знайти розташування восьми ферзів на стандартній шахівниці таким чином, щоб жоднен ферзь не атакував іншого. В звичайному підході пошуку з вертанням, неповні кандидати це розташування k ферзів в перших k рядах дошки, всі в різних рядах і стовпцях. Будь-який неповний розв'язок, що містить два ферзі, які атакують один одного має бути відкинутий, бо він не може бути доведеним до повного правильного розв'язку.

76. Композиція та агрегація класів в ООП

Агрегація – означає, що один клас містить в собі агрегати (складових частин, підсистем)

інших класів. Так автомобіль складається з кузова, двигуна, трансмісії і т.п., а до складу приймально-

передавального пристрою входять передавач, приймач і антенно-фідерний пристрій. У UML агрегації позначаються у вигляді лінії з зафарбованим ромбом на кінці. Агрегація має кратність. Так автомобіль зазвичай містить один двигун, який у свою чергу може належати тільки одному автомобілю.

Автомобіль може звичайно містити від двох до п'яти дверей. У свою чергу кожні двері можуть належати лише одному автомобілю.

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

Композиція є ще одним ставленням, родинною агрегації. Але якщо в агрегації агрегати належать класу чи об'єкту, то в композиції існує більш слабкий зв'язок. Так, студенти з вузом перебувають у відношенні композиції, тоді як факультети, які входять до складу вузу (тобто є його невід'ємною частиною або агрегатами), пов'язані з нею відношенням агрегації. На UML композиція позначається за допомогою незакрашених ромбів. Як і у випадку агрегації, ставлення композиції має кратність. Агрегація та композиція є підкласами класу відносин асоціації. Асоціація позначається у вигляді лінії без стрілок і ромбів і може приймати вигляд як агрегації, так і композиції. На ранніх етапах об'єктно-орієнтованого аналізу і проектування часто задаються відносини асоціацій, а свою конкретизацію у вигляді агрегацій і композицій вони отримують на більш пізніх етапах.

77. Масиви в мовах програмування. Оголошення, доступ до елементів, властивості

масивів. Двовимірні та N-вимірні масиви.

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

Характеристика масиву Розмірність — кількість індексів елемента (одновимірний, двовимірний, ..., багатовимірний)

·Розмір — загальна кількість елементів у масиві.

·За типом поділяється на числовий та символьний.

·В кожній мові є свої правила опису масив (у мові Бейсик — командою DIM <список

масивів>++).

В програмуванні масив (англ. array) — сукупність елементів одного типу даних,

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

Між покажчиками і масивами існує тісний зв'язок. Наприклад, коли оголошується масив у вигляді масиву INT *25+, то цим визначається не тільки виділення пам'яті для двадцяти п'яти елементів масиву, але і для покажчика з ім'ям масиву, значення якого дорівнює адресою першого по рахунку (нульового) елемента масиву, т.е , сам масив залишається безіменним, а доступ до елементів масиву здійснюється через покажчик з ім'ям масиву. З погляду синтаксису мови покажчик Аррей є константою, значення якої можна використовувати у виразах, але змінити це значення не можна.

Оскільки ім'я масиву є покажчиком допустимо, наприклад, таке присвоєння: int array[25];

int *ptr; ptr=array;

Тут покажчик PTR встановлюється на адресу першого елемента масcіва.

Для доступу до елементів масиву існує два різні способи.

Перший спосіб пов'язаний з використанням звичайних індексних виразів у квадратних дужках, наприклад, array*16+=3 или array[i+2+=7. При такому способі доступу записуються два вирази,

причому другий вираз полягає у квадратні дужки. Одне з цих виразів повинно бути дороговказом, а

друге - виразом цілого типу. Послідовність запису цих виразів може бути будь-який, але в квадратних дужках записується вираз наступне друге. Масив будуть еквівалентними і позначають елемент масиву з номером шістнадцять. Покажчик використовуваний в індексному вираженні не обов'язково повинен бути константою, що вказує на якій-небудь масив, це може бути і змінна.

Другий спосіб доступу до елементів масиву пов'язаний з використанням адресних виразів і операції разадресаціі у формі *(array+16)=3 или *(array+i+2)=7. При такому способі доступу адресний

вираз рівне адресою шістнадцятого елемента масиву теж може бути записано різними способами

*(array+16) или *(16+array).

При реалізації на комп'ютері перший спосіб приводиться до другого, тобто індексне вираз перетвориться до адресного. Для наведених прикладів масив *16+ і 16 *масив+ перетворюються в * (масив + 16).

Для доступу до початкової елементу масиву (тобто до елементу з нульовим індексом)

можна використовувати просто значення покажчика масиву або PTR. Будь-яке з присвоювань

*array = 2; array[0] = 2;

*(array+0) = 2; *ptr = 2; ptr[0] = 2; *(ptr+0) = 2;

присвоює початковому елементу масиву значення 2, але найшвидше виконаються присвоювання * масив = 2 і * PTR = 2, оскільки в них не потрібно виконувати операції додавання.

Масив може бути одновимірним (вектором), та багатовимірним (наприклад, двовимірною таблицею), тобто таким, де індексом є не одне число, а кортеж (сукупність) з декількох чисел,

кількість яких збігається з розмірністю масиву.

У переважній більшості мов програмування масив є стандартною вбудованою структурою

даних.

Масиви бувають одновимірними (у вигляді послідовності чисел), двовимірними (у вигляді таблиць чисел розміром m x n) і багатовимірними (3-,4-вимірні і т.д. 3-вімірні - це об'ємний простір з комірками, а 4-вимірні і більше - це фантастично-абстрактні поняття).

Масив називається одновимірним, якщо для задання місцеположення елемента в масиві необхідно вказати значення лише одного індексу.

Масив називається двовимірним, якщо для задання місцеположення елемента в масиві необхідно вказати значення двох індексів.

Запам'ятайте, що у двовимірних масивах перший індекс завжди вказує на номер рядка, а

другий - на номер стовпчика в цьому рядку!

Розмірність масивів у Pascal необмежена, вона визначається лише об'ємом пам'яті вашого комп'ютера.

Резонним буде запитання: а як же розташовуються масиви в пам'яті комп'ютера? Пояснення для одновимірних масивів дуже просте – всі вони розташовані в пам'яті підряд. Двовимірні масиви розташовуються дещо інакше - спочатку елементи першого рядка, потім другого і т. д. Розташування масивів більшої розмірності пояснюється аналогічно.

78. Динамічне виділення пам’яті в мовах програмування. Робота з динамічними

об’єктами.