- •Поняття алгоритму. Властивості алгоритмів. Виконавці алгоритмів. Математичні основи аналізу алгоритмів (о нотація).
- •Базові структури алгоритмів. Основні властивості базових структур алгоритмів.
- •Алгоритми сортування, їх характеристики та оцінка.
- •Алгоритм сортування методом прямого обміну.
- •Алгоритм сортування методом вставки.
- •Алгоритм сортування методом Шелла.
- •Алгоритм сортування методом Хоара.
- •Алгоритм сортування пірамідальним методом.
- •Основні структури даних.
- •Алгоритми шифрування інформації. Загальна характеристика, класифікація.
- •Алгоритм шифрування rsa.
- •Компілятори інтерпретатори, основні поняття.
- •Списки, черги основні поняття. Приклади реалізації.
- •Зворотня польська нотація. Основні поняття , використання.
- •Графи , алгоритм Дейкстри
Поняття алгоритму. Властивості алгоритмів. Виконавці алгоритмів. Математичні основи аналізу алгоритмів (о нотація).
Алгоритм – це послідовність математичних, логічних чи інших операцій, що характеризуються детермінованістю, масовістю, спрямованістю і призводить до рішення задачі певного класу за численне число кроків.
Властивості алгоритмів:
Скінченність – виконання алгоритму має закінчуватись за численне число кроків.
Результативність – виконання алгоритму призводить до результату.
Формальність – виконавець відповідно до алгоритму повинен отримати результат, не вникаючи в його суть.
Визначеність – будь-який алгоритм повинен бути описаний так, щоб при його виконанні у його виконавця не виникало двозначних вказівок(різні виконавці – один результат).
Масовість – за допомогою алгоритму розв’язується цілий ряд задач.
Зрозумілість – в алгоритмі повинні бути операції знайомі виконавцю.
Завдання сортування полягає в перестановці елементів послідовності таким чином, щоб виконалась умова а(і)<а(і+1).
О-нотація – вимірюється в од. часу. Згідно з о-нотацією всі алгоритми діляться на: квадратичні і субквадратичні, логарифмічні і лінійні(к=1).
----------------------------------------------------
Базові структури алгоритмів. Основні властивості базових структур алгоритмів.
Базові структури алгоритмів (керуючі структури) – це способи керування процесом обробки даних.
Існує три базові структури алгоритмічної конструкції:
лінійні алгоритми (слідування)
умова (розгалуження)
цикли (повторення)
Лінійна структура передбачає, що тіло алгоритму являє собою послідовність команд, виконуваних одна за одною.
Умова (розгалуження) – це керуюча структура, що передбачає можливість вибору з кількох варіантів, для кожного з яких, залежно від умови виконується різна послідовність команд.
Цикл – це керуюча структура, що дозволяє багаторазово повторювати задану послідовність команд.
Цикл з передумовою
Цикл з післяумовою
Цикл з параметром
Способи опису алгоритмів:
Словесний
Формульний
Графічний
Алгоритмічною мовою
----------------------------------------------------
Алгоритми сортування, їх характеристики та оцінка.
Алгоритм сортування — це алгоритм, що розв'язує задачу сортування, тобто здійснює впорядкування лінійного списку (масиву) елементів.
Завдання сортування полягає в перестановці елементів послідовності таким чином, щоб виконалась умова а(і)<а(і+1).
Для оцінки критеріїв алгоритмів існують такі критерії:
Час виконання, який характеризується швидкодією.
Пам'ять, при цьому не враховується пам'ять, що займають вхідні дані і програмна реалізація.
Стійкість – стійке сортування не змінює вільне розташування рівних елементів. Вигідне, якщо декілька полів сортування.
Природність поведінки алгоритму сортування. Якщо враховує, що послідовність відсортована або частково відсортована.
О-нотація – вимірюється в од. часу. Згідно з о-нотацією всі алгоритми діляться на: квадратичні і субквадратичні, логарифмічні і лінійні(к=1).