ЗМІСТ
Вступ 7
Розділ 1. Види програмування 12
1.1. Машинні та високорівневі мови програмування 12
1.2. Парадигми програмування 13
1.3. Системне програмування 13
1.4. Структурне та процедурне програмування 13
1.5. Модульне та об’єктно-орієнтоване програмування 14
1.6. Функційне програмування 14
1.7. Питання для самоперевірки 15
1.8. Тестові завдання 15
1.9. Ключ до тестових завдань 15
Розділ 2. Елементи обчислювальних машин 16
2.1. Архітектура комп’ютерів 16
2.2. Архітектурні принципи Джона фон Неймана 18
2.3. Системи числення 19
2.3.1. Позиційні системи числення 20
2.3.2. Одиниці виміру інформації 21
2.3.3. Двійкова система числення 21
2.3.4. Вісімкова система числення 23
2.3.5. Шістнадцяткова система числення 24
2.3.6. Переведення числа з двійкової системи числення у вісімкову і навпаки 25
2.3.7. Взаємозв’язок між двійковою системою числення і шістнадцятковою 27
2.3.8. Взаємозв’язок між вісімковою системою числення і шістнадцятковою 28
2.4. Поняття алгоритму та способи його подання 29
2.5. Властивості та класи алгоритмів 36
2.6. Питання для самоперевірки 44
2.7. Тестові завдання 45
2.8. Ключ до тестових завдань 45
2.9. Індивідуальні завдання виконання лабораторних робіт 46
Розділ 3. Основи програмування 47
3.1. Історія розвитку мови С 47
3.2. Структура програми 47
3.3. Типи даних 55
3.4. Змінні 57
3.5. Константи 59
3.6. Питання для самоперевірки 61
3.7. Тестові завдання 61
3.8. Ключ до тестових завдань 61
3.9. Індивідуальні завдання виконання лабораторних робіт 61
Розділ 4. Оператори та операції 67
4.1. Оператор присвоєння 67
4.2. Арифметичні операції 68
4.3. Перетворення типів 69
4.3.1. Неявне перетворення типів даних для бінарних операцій 69
4.3.2. Неявне перетворення типів даних для операції присвоєння 69
4.3.3. Явне перетворення типів 70
4.4. Операції відношень та логічні операції 72
4.5. Математичні функції 75
4.6. Стандартний ввід даних з клавiатури та вивiд на екран 78
4.6.1. Форматний вивiд даних 79
4.6.2. Форматний ввiд даних 81
4.6.3. Неформатний ввiд/вивiд та його фукції 84
4.7. Питання для самоперевірки 85
4.8. Тестові завдання 85
4.9. Ключ до тестових завдань 85
4.10. Індивідуальні завдання виконання лабораторних робіт 85
Розділ 5. Розгалуження 94
5.1. Поняття розгалуження 94
5.2. Оператор безумовного переходу 94
5.3. Умовний оператор 94
5.4. Оператор вибору варіантів 99
5.5. Питання для самоперевірки 100
5.6. Тестові завдання 100
5.7. Ключ до тестових завдань 100
5.8. Індивідуальні завдання виконання лабораторних робіт 100
Розділ 6. Цикли 101
6.1. Поняття ітерації та циклу. 101
6.2. Цикл з параметром 101
6.3. Цикл з передумовою 105
6.4. Цикл з післяумовою 107
6.5. Оператори переривання циклів 109
6.6. Питання для самоперевірки 111
6.7. Тестові завдання 111
6.8. Ключ до тестових завдань 111
6.9. Індивідуальні завдання виконання лабораторних робіт 111
Розділ 7. Вказівники та посилання 112
7.1. Основні поняття 112
7.2. Операції з вказівниками 114
7.3. Вказівники на вказівники 116
7.4. Питання для самоперевірки 116
7.5. Тестові завдання 116
7.6. Ключ до тестових завдань 116
7.7. Індивідуальні завдання виконання лабораторних робіт 116
Розділ 8. Підпрограми 2
8.1. Поняття підпрограми 2
8.2. Параметри та їх види 3
8.3. Статичні змінні 7
8.4. Передавання параметрів функцій 8
8.4.1. Параметри-значення 8
8.4.2. Параметри-вказівники 9
8.4.3. Параметри-посилання 9
8.4.4. Параметри зі значеннями за замовчуванням 11
8.4.5. Імена функцій як параметри 12
8.5. Вбудовані функції 12
8.6. Функції зі змінною кількістю параметрів 13
8.7. Питання для самоперевірки 15
8.8. Тестові завдання 16
8.9. Ключ до тестових завдань 16
8.10. Індивідуальні завдання виконання лабораторних робіт 16
Розділ 9. Рекурсія 2
9.1. Поняття рекурсії 2
9.2. Рекурентні співвідношення 2
9.3. Питання для самоперевірки 7
9.4. Тестові завдання 7
9.5. Ключ до тестових завдань 8
9.6. Індивідуальні завдання виконання лабораторних робіт 8
Розділ 10. Модульне програмування 9
10.1. Основні поняття 9
10.2. Включення файлів 9
10.3. Проблема повторного включення 11
10.4. Умовна компіляція 12
10.5. Зовнішні змінні 12
10.6. Питання для самоперевірки 15
10.7. Тестові завдання 15
10.8. Ключ до тестових завдань 15
10.9. Індивідуальні завдання виконання лабораторних робіт 15
Розділ 11. Масиви 2
11.1. Поняття масива 2
11.2. Одновимірні масиви 5
11.2.1. Оголошення одновимірних масивів 5
11.2.2. Операції над вказівниками на масиви 7
11.2.3. Введення-виведення одновимірних масивів 7
11.3. Багатовимірні масиви 8
11.3.1. Двовимірні масиви 8
11.3.2. Тривимірні масиви 11
11.4. Опрацювання масивів у функціях 12
11.4.1. Передавання параметрів у функцію 12
11.4.2. Повернення масива як результату функції 16
11.5. Питання для самоперевірки 18
11.6. Тестові завдання 18
11.7. Ключ до тестових завдань 18
11.8. Індивідуальні завдання виконання лабораторних робіт 18
Розділ 12. Динамічна пам’ять 2
12.1. Загальні поняття 2
12.2. Функції для роботи з динамічною пам’яттю 2
12.3. Динамічні одновимірні масиви 3
12.3.1. Оголошення динамічного одновимірного масива 3
12.3.1.1. Використання функції malloc() 3
12.3.1.2. Використання функції calloc() 4
12.3.1.3. Використання функції new() 5
12.4. Динамічні двовимірні масиви 6
12.4.1. Динамічний двовимірний масив як одновимірний 6
12.4.2. Динамічний двовимірний масив як двовимірний 8
12.5. Опрацювання динамічних масивів у функціях 9
12.6. Питання для самоперевірки 12
12.7. Тестові завдання 12
12.8. Ключ до тестових завдань 12
12.9. Індивідуальні завдання виконання лабораторних робіт 12
Розділ 13. Символьні рядки
13.1. Символьний тип
13.1.1. Коди символів
13.1.2. Опрацювання символів
13.1.3. Введення та виведення символів
13.2. Рядки символів
13.2.1. Оголошення рядків
13.2.2. Введення-виведення рядків
13.2.3. Опрацювання символьних рядків
13.3. Опрацювання символьних рядків у функціях
13.4. Питання для самоперевірки
Розділ 14. Переліки
14.1. Оголошення переліків
14.2. Питання для самоперевірки
Розділ 15. Комбіновані типи
15.1. Структури
15.1.1. Визначення структурного типу
15.1.2. Оголошення структур
15.1.3. Розподіл пам’яті для структур
15.1.4. Операції над структурою
15.2. Опрацювання структур у функціях
15.3. Бітові поля
15.4. Питання для самоперевірки
Розділ 16. Об’єднання
16.1. Вступ
16.2. Визначення об’єднуваного типу
16.3. Оголошення об’єднань
16.4. Розподіл пам’яті для об’єднань
16.5. Ініціалізація об’єднання
16.6. Питання для самоперевірки
Розділ 17. Файлові структури даних
17.1. Загальні поняття
17.2. Потоки та файли
17.3. Додаткові можливості опрацювання файлів
17.4. Текстові файли
17.5. Бінарні файли
17.6. Питання для самоперевірки
Розділ 18. Динамічні структури даних та алгоритми їх опрацювання 4
18.1. Поняття структури даних. Рівні подання структур даних 4
18.2. Структурні та лінійні типи даних 6
18.2.1. Масив 6
18.2.2. Множина 10
18.2.3. Запис (прямий декартовий добуток) 10
18.2.4. Таблиця 12
18.3. Списки 13
18.3.1. Зв’язний список 13
18.3.2. Лінійний однозв’язний список 13
18.3.2.1. Створення елемента списку 14
18.3.2.2. Операції включення й виключення елементів списку 15
18.3.2.3. Реалізація списку в послідовній пам’яті 15
18.3.2.4. Додавання вузла 16
18.3.2.4.1. Додавання вузла в початок списку 16
18.3.2.4.2. Додавання вузла після заданого 16
18.3.2.4.3. Додавання вузла перед заданим 16
18.3.2.4.4. Додавання вузла в кінець списку 17
18.3.2.4.5. Прохід по списку 17
18.3.2.4.6. Пошук вузла в списку 17
18.3.2.5. Алфавітно-частотний словник 18
18.3.2.6. Видалення вузла 19
18.3.3. Циклічний лінійний список 19
18.3.4. Двозв’язний лінійний список 20
18.3.4.1. Операції з двусвязного списком 20
18.3.4.1.1. Додавання вузла в початок списку 20
18.3.4.1.2. Додавання вузла в кінець списку 21
18.3.4.1.3. Додавання вузла після заданого 21
18.3.4.1.4. Пошук вузла в списку 22
18.3.4.1.5. Видалення вузла 22
18.3.5. Багатозв’язний список 23
18.4. Стеки 24
18.4.1. Реалізація стека за допомогою масиву 25
18.4.2. Реалізація стека за допомогою списку 27
18.4.2.1. Додавання елемента на вершину стека 27
18.4.2.2. Отримання верхнього елементу з вершини стека 27
18.4.3. Системний стек в програмах 29
18.5. Черги 29
18.5.1. Реалізація черзі за допомогою масиву 30
18.5.2. Реалізація черзі за допомогою списку 31
18.5.2.1. Додавання елемента в кінець черги 32
18.5.2.2. Приклад відображення на список 32
18.6. Деки 33
18.7. Зв’язний розподіл пам’яті 36
18.7.1. Структура даних типу вказівник 37
18.7.2. Статичні й динамічні змінні 37
18.8. Дерева 38
18.8.1. Основні поняття 38
18.8.2. Двійкові дерева 39
18.8.2.1. Реалізація двійкових дерев в мові С 39
18.8.2.1.1. Опис вершини 39
18.8.2.1.2. Дерева мінімальної висоти 40
18.8.2.1.3. Обхід дерева 40
18.8.2.2. Пошук за допомогою дерева 41
18.8.2.2.1. Побудова дерева пошуку 42
18.8.2.2.2. Пошук по дереву 43
18.8.2.2.3. Сортування за допомогою дерева пошуку 43
18.8.2.2.4. Пошук однакових елементів 43
18.8.2.2.5. Робота з бінарними деревами пошуку 43
18.8.2.3. Розбір арифметичного виразу 47
18.8.2.3.1. Дерево для арифметичного виразу 47
18.8.2.3.2. Форми запису арифметичного виразу 47
18.8.2.3.3. Алгоритм побудови дерева 48
18.8.2.3.4. Обчислення виразу по дереву 49
18.8.2.3.5. Розбір вираження з дужками 50
18.8.2.3.6. Багатозначні числа і змінні 51
18.8.2.3.7. Спрощення виразу за допомогою дерева 52
18.8.3. дерево ігор 53
18.9. Графи 54
18.9.1. Основні понятія 54
18.9.2. Опис графів 54
18.9.3. Задача Прима-Краскала 55
18.9.3.1. Формулювання завдання 55
18.9.3.2. Жадібні алгоритми 55
18.9.3.3. Рішення 55
18.9.4. Найкоротший шлях 56
18.9.4.1. Формулювання завдання 56
18.9.4.2. Алгоритм Дейкстри 56
18.9.4.2.1. Ініціалізація 57
18.9.4.2.2. Основний цикл 57
18.9.4.2.3. Виведення результату 57
18.9.4.2.4. Приклад 57
18.9.4.3. Алгоритм Флойда-Уоршелла 58
18.9.5. Оптимальне розміщення 58
18.9.5.1. Завдання на мінімум суми 58
18.9.5.2. Мінімаксна завдання розміщення 59
18.9.6. Завдання комівояжера 60
18.9.6.1. Формулювання завдання 60
18.9.6.2. Метод грубої сили 60
18.9.6.3. Метод гілок і меж 61
18.9.6.4. Алгоритм Літтла 61
18.9.6.5. Метод випадкових перестановок 63
18.9.7. Задача про паросполучення 63
18.9.7.1. Формулювання завдання 63
18.9.7.2. Досяжність вершин в графі 63
18.9.7.2.1. Ініціалізація 64
18.9.7.2.2. Загальний крок 64
18.9.7.3. Метод ланцюгів, що чергуються 64
18.10. Питання для самоперевірки 65
18.11. Тестові завдання 66
18.12. Ключ до тестових завдань 72
18.13. Індивідуальні завдання виконання лабораторних робіт 72
Розділ 19. Алгоритми пошуку
19.1. Загальна класифікація алгоритмів пошуку 2
19.2. Лінійний пошук 2
19.3. Двійковий (бінарний) пошук елемента в масиві 2
19.4. Пошук методом Фібоначчі 3
19.5. М-блоковий пошук 4
19.6. Пошук з використанням хеш-функції 5
19.7. Інтерполяційний пошук 6
19.8. Бінарний пошук із визначенням найближчих вузлів 6
19.9. Пошук у таблиці 7
19.10. Прямий пошук рядка 8
19.11. Алгоритм Ахо-Корасик 8
19.12. Алгоритм Моріса-Прата 9
19.13. Алгоритм Кнута, Моріса і Пратта 9
19.14. Алгоритм Рабіна-Карпа 10
19.15. Алгоритм Боуера і Мура 11
19.16. Алгоритм Хорспула 12
19.17. Порівняння методів пошуку 13
19.18. Питання для самоперевірки 13
19.19. Тестові завдання 13
19.20. Ключ до тестових завдань 14
19.21. Індивідуальні завдання виконання лабораторних робіт 14
Розділ 20. Алгоритми сортування
20.1. Методи внутрішнього сортування 3
20.1.1. Сортування вставкою (включенням) 3
20.1.1.1. Опис алгоритму сортування методом включення 3
20.1.1.2. Аналіз алгоритму сортування методом включення 5
20.1.1.2.1. Аналіз псевдокода алгоритму 5
20.1.1.2.2. Машина з довільним доступом до пам’яті 6
20.1.1.2.3. Аналіз алгоритму сортування методом включення 6
20.1.1.2.4. Порядок зростання 8
20.1.1.2.5. Асимптотичні позначення 8
20.1.1.2.6. 2.6. Порівняння функцій 11
20.1.2. Сортування шляхом підрахунку 11
20.1.3. Сортування включенням зі спадним приростом (метод Шелла) 12
20.1.4. Сортування обміном (метод бульбашки) 13
20.1.5. Сортування прямим вибором 15
20.1.6. Швидке сортування (метод Хоара) 16
20.1.6.1. Опис алгоритму сортування методом Хоара 16
20.1.6.2. Аналіз алгоритму сортування методом Хоара 17
20.1.6.3. Ефективність швидкого сортування 19
20.1.6.4. Випадкова версія швидкого сортування 20
20.1.6.5. Порядкові статистики 22
20.1.6.6. Вибір за лінійний час 23
20.1.7. Сортування за допомогою дерева 25
20.1.8. Сортування за лінійний час 26
20.1.8.1. Нижня оцінка алгоритмів сортування 26
20.1.8.2. Сортування підрахунком 27
20.1.8.3. Сортування за розрядами 28
20.1.9. Піраміди 30
20.1.9.1. Означення, призначення та властивості піраміди 30
20.1.9.2. Підтримка властивості піраміди 31
20.1.9.3. Створення піраміди 32
20.1.9.4. Пірамідальне сортування 34
20.1.9.5. Побудова піраміди методом Флойда 35
20.1.9.6. Аналіз алгоритму пірамідального сортування 36
20.1.9.7. Черги з пріоритетами 37
20.1.10. Сортування методом злиттям 39
20.1.11. Аналіз алгоритму сортування методом злиття 41
20.1.11.1. Метод декомпозиції 41
20.1.11.2. Підрахунок інверсій 45
20.1.11.3. Добуток матриць 48
20.1.12. Методи порозрядного сортування 49
20.1.12.1. Порозрядне сортування для списків 49
20.1.12.2. Порозрядне сортування для масивів 51
20.1.12.3. Ефективність порозрядного сортування 52
20.2. 9.2. Методи зовнішнього сортування 52
20.2.1. 9.2.1. Пряме злиття 53
20.2.2. Природне злиття 53
20.2.3. Збалансоване багатошляхове злиття 54
20.2.4. Багатофазне сортування 56
20.3. Питання для самоперевірки 56
20.4. Тестові завдання 57
20.5. Ключ до тестових завдань 58
20.6. Індивідуальні завдання виконання лабораторних робіт 58
Список використаних джерел 117
(Для ознайомлення з повним текстом статті необхідно залогінитись)