ОПОРНИЙ КОНСПЕКТ ЛЕКЦІЙ
ОПОРНИЙ КОНСПЕКТ ЛЕКЦІЙ
з дисципліни
«ТЕОРІЯ АЛГОРИТМІВ»
(Аналіз алгоритмів та алгоритмічні стратегії)
для студентів освітньо-кваліфікаційного рівня «бакалавр»
напряму підготовки: 6.050101 «Комп’ютерні науки»
Тернопіль – 2014
Міністерство освіти і науки України
Тернопільський національний економічний університет
Факультет комп’ютерних інформаційних технологій
з дисципліни
«ТЕОРІЯ АЛГОРИТМІВ»
(Аналіз алгоритмів та алгоритмічні стратегії)
для студентів освітньо-кваліфікаційного рівня «бакалавр»
напряму підготовки: 6.050101 «Комп’ютерні науки»
Тернопіль – 2014
Опорний конспект лекцій з дисципліни «Теорія алгоритмів» для студентів освітньо-кваліфікаційного рівня «бакалавр» напряму підготовки: 6.050101 «Комп’ютерні науки» / Укладачі: Коваль В.С., Добровольська Н.С. – Тернопіль, 2014, – 64 с.
Опорний конспект лекцій складається з теоретичних частин, що рекомендовані програмою на основі галузевого стандарту вищої освіти України з напряму підготовки 6.050101 «Комп’ютерні науки».
Укладачі: Коваль Василь Сергійович, к.т.н., доцент
Добровольська Нінель Станіславівна, викладач
Рецензенти: Карпінський М.П.., д.т.н., професор кафедри комп’ютерної інженерії, Тернопільський національний технічний університет імені І.Пулюя
Якименко І.З., к.т.н., доцент кафедри комп’ютерної інженерії, Тернопільський національний економічний університет
Затверджено на засіданні кафедри інформаційно-обчислювальних систем та управління, протокол №10 від 11.03.2014
Розглянуто та схвалено науково-методичною радою факультету комп’ютерних інформаційних технологій, протокол №2 від 18.03.2014 р.
ЗМІСТ
ВСТУП.. 5
I. МАТЕМАТИЧНІ ОСНОВИ АНАЛІЗУ АЛГОРИТМІВ.. 6
1.1 Історія розвитку математичної логіки. 6
1.2 Основи математичної логіки. 7
1.3 Операції над висловленнями. 8
1.4 Таблиці істинності 13
1.5 Алгоритм побудови формули за таблицею істинності 15
II. БЛОК-СХЕМИ АЛГОРИТМІВ.. 16
2.1 Поняття алгоритму. 16
2.2 Ефективність алгоритмів. 17
2.3 Основні символи та правила побудови схем алгоритмів. 20
2.4 Лінійний алгоритм.. 24
2.5 Алгоритм із розгалуженням.. 28
2.6 Циклічні алгоритми. 32
III. ОСНОВИ ТЕОРІЇ ОБЧИСЛЮВАЛЬНОСТІ. 38
3.1 Принцип дедукції 38
3.2 Числення предикатів. 41
3.3 Машини Тьюрінга. Обчислюваність за Тьюрінгом.. 43
3.4 Нормальні алгоритми Маркова. Обчислюваність за Марковим.. 45
3.5 Система Поста. Обчислюваність за Постом.. 47
IV. АЛГОРИТМІЧНІ СТРАТЕГІЇ. 49
4.1 Поняття та види стратегій. 49
4.2 Методи розробки алгоритмів. 54
V. КЛАСИ СКЛАДНОСТІ P I NP. 59
5.1 Поняття складності алгоритмів. 59
5.2 Правила аналізу складності алгоритмів. 62
ЛІТЕРАТУРА.. 64