- •Зміст дисципліни.
- •Найменування тем, їхній зміст, обсяг у годинах лекційних занять
- •Вказівки з використанНя літературних джерел
- •Алгоритми й структури даних
- •Стеки, списки
- •Дерева пошуку Бінарні дерева
- •Двійкові дерева
- •Червоно- чорні дерева
- •Частково впорядковані дерева Статья I.При створенні чуд елементи вводилися в наступному порядку: (13, 6, 15, 5, 10, 6, 3, 13, 5, 6, 35, 8). Пояснити побудова (переформування) дерева.
- •Рекурсія
- •Перебір з поверненням
- •Машина Тьюрінга
- •Приклади Послідовний пошук
- •Структури даних. Масиви Решето Ератосфена
- •Обчислення найближчої точки
- •Структури даних. Списки Приклад циклічного списку (задача Йосипа)
- •Сортування методом вставки в список
- •Звертання порядку проходження елементів списку
- •Структури даних. Рядки Сортування масиву рядків
- •Абстрактні типи даних (атд) Інтерфейс абстрактного типу даних стека
- •Реалізація черги fifo на базі масиву
- •Реалізація черги fifo на базі зв'язного списку
- •Перетворення з інфіксної форми в постфіксну
- •Рекурсія Алгоритм Евклида
- •Рекурсивна програма для оцінки префіксних виразів
- •Розв’язання
- •Приклад 2 Завдання
- •Розв’язання
- •Приклад 3 Завдання
- •Розв’язання
- •Приклад 4 Завдання
- •Розв’язання
- •Приклад 5 Завдання
- •Розв’язання
- •Приклад 6 Завдання
- •Розв’язання
- •Приклад 7 Завдання
- •Розв’язання
- •Алгоритм роботи машини т’юринга
- •Дослідження функції на рекурсивність
- •Нормальні алгоритми Маркова
- •Алгоритм роботи програми.
- •Приклад роботи програми.
- •Варіанти курсових робіт
- •Варіанти виконання Алгоритм виконання курсової роботи:
- •Приклад1.
- •Побудова моделі.
- •Розроблення алгоритму.
- •Правильність алгоритму.
- •Реалізація алгоритму.
- •Перевірка програми.
- •Приклад2
- •Постановка задачі
- •Перший варіант розв’язку
- •Другий варіант розв’язку.
- •Приклад3
- •Опукла оболонка
- •Метод обходу Грехема
- •Метод обходу Джарвіса
- •Алгоритм апроксимації опуклої оболонки
- •Швидкі методи побудови опуклої оболонки
- •Алгоритм типу розділяй та пануй
- •Побудова опуклої оболонки простого многокутника
- •Динамічні алгоритми побудови опуклої оболонки
- •Порівняльний аналіз алгоритмів побудови опуклої оболонки
- •Висновки
Перебір з поверненням
п Дане дерево глибини N, кожна внутрішня вершина якого має K (< 10) безпосередніх нащадків (нумеруються від 1 до K). Корінь дерева має номер 0. Записати в текстовий файл із даним ім'ям всі можливі шляхи, що ведуть від кореня до листів. Перебирати шляхи, починаючи з «самого лівого» і закінчуючи «самим правим» (при цьому першими заміняти кінцеві елементи шляху).
п Дане дерево глибини N, кожна внутрішня вершина якого має K (< 10) безпосередніх нащадків (нумеруються від 1 до K). Корінь дерева має номер 0. Записати в текстовий файл із даним ім'ям всі шляхи, що ведуть від кореня до листів і задовольняючій наступній умові: ніякі сусідні елементи шляхи не нумеруються однієї й тією же цифрою. Порядок перебору шляхів такий же, як у завданні 14.
п Дане дерево глибини N (N — парне), кожна внутрішня вершина якого має 2 безпосередніх нащадка: A з вагою 1 й B з вагою –1. Корінь дерева C має вага 0. Записати в текстовий файл із даним ім'ям всі шляхи від кореня до листів, що задовольняють наступній умові: сумарна вага елементів шляхи дорівнює 0. Порядок перебору шляхів такий же, як у завданні 14.
п Дане дерево глибини N того ж типу, що й у завданні 16. Записати в текстовий файл із даним ім'ям всі шляхи від кореня до листів, що задовольняють наступній умові: сумарна вага елементів для будь-якого початкового відрізка шляху ненегативний. Порядок перебору шляхів такий же, як у завданні 14.
п Дане дерево глибини N, кожна внутрішня вершина якого має 3 безпосередніх нащадка: A з вагою 1, B з вагою 0 й C з вагою –1. Корінь дерева D має вага 0. Записати в текстовий файл із даним ім'ям всі шляхи від кореня до листів, що задовольняють наступним умовам: сумарна вага елементів для будь-якого початкового відрізка шляху непозитивний, а сумарна вага всіх елементів шляхи дорівнює 0. Порядок перебору шляхів такий же, як у завданні 14.
п Дане дерево глибини N того ж типу, що й у завданні 18. Записати в текстовий файл із даним ім'ям всі шляхи від кореня до листів, що задовольняють наступним умовам: ніякі сусідні елементи шляхи не позначаються однієї й тією же буквою, а сумарна вага всіх елементів шляхи дорівнює 0. Порядок перебору шляхів такий же, як у завданні 14.
Машина Тьюрінга
Побудувати машину, що розпізнає парність натурального числа.
Побудувати машину Нгги яка обчислює остача від ділення натурального числа на т.
Побудувати машини Тьюрінга, що обчислюють наступні функції, задані на N х N:
а) x + 2y; б) x2 + 3y.
Написати машину Тьюрінга для обчислення наступних виразів, враховуючи умови:
а) машина починає роботові з положення на першому символі першого слова на стрічці;
б) після виконання роботи вхідні слова залишаються на стрічці, а відповідь дописується за останнім вхідним словом через пусту клітинку.
Завдання:
Функція
.Функція
.Функція
.Функція
.* Функція
(якщо
,
те відповідь винна бути 0).* Функція
.* Функція
.* Функція
.Функція
.Функція
.
5. Побудувати машину Тьюрінга для функцій 5-10 попереднього пункту завдання за умови, що на стрічці повинна залишитися тільки відповідь.
6. За допомогою машин Тьюрінга, поданих у методичних вказівках, обчислити вирази:
1.1+2.
2.1*3.
3. (1+1)*2.
4. |1-2|.
5.
.
6.
.
7.0*2.
8.3+1.
9.2*3.
10. ?3-2?.
7. Побудувати в алфавіті {0,1} машину Тюрінга, яка має наступну властивість (в якості порожнього символу береться 0):
1) машина застосовна до будь-якого непустого слова в алфавіті{0,1};
2) машина застосовна до слів виду 13n (n>0) і не застосовна до жодного зі слів виду 13n+a (a=1,2);
3) машина застосовна до слів виду 1a01a (a>0), і не застосовна до слів 1a01b (a не дорівнює b, a>0, b>0).
8. Які одномісні функції обчислюються всіма машинами Тюрінга ( алфавіті {0,1}), програми яких містять лише по одній команді?
9. Довести , що для всякої обчислюваної функції існує машина Тюрінга , що правильно обчислює цю функцію .
10. Довести примітивну рекурсивність функції.
1)
;
2)
.
3)
.
11. З'ясувати , чи застосовна машина Тюрінга Т , що задається програмою П , до послідовності слів Р. Якщо застосовна , то знайти результат застосування машини Т до послідовності слів Р.
1)
Стан |
0 |
1 |
1 |
0R2 |
1R1 |
2 |
0R3 |
1L1 |
3 |
0C0 |
1R2 |
а) P=110011
б) P=1110111
в) P=1001011
2)
Стан |
0 |
1 |
1 |
1R2 |
0R3 |
2 |
1L3 |
1C2 |
3 |
0C0 |
1R1 |
а) P=111101
б) P=111011
в) P=111111
3)
Стан |
0 |
1 |
1 |
1R1 |
0R2 |
2 |
1R1 |
1L3 |
3 |
1L1 |
1C0 |
а) P=1011
б) P=11001
в) P=10101
12. По заданій машині Тюрінга Т та початковій конфігурації К знайти заключну конфігурацію (стрічка нескінченна вправо):
1)
Стан |
0 |
1 |
1 |
1С0 |
0R2 |
2 |
0R1 |
1L2 |
а) K=11111101
б) K=111111
2)
Стан |
0 |
1 |
1 |
0C0 |
1R2 |
2 |
1L0 |
0R3 |
3 |
1L1 |
0R1 |
а) K=1111111
б) K=111101
в) K=1011111
NP-повнота.
Довести NP-повноту відповідним методом.
1. * Метод звуження проблеми.
Найдовший шлях.
Умова:
задано граф
і додатне ціле число
.
Питання:
чи міститься в
простий шлях, який складається не менше
ніж з
ребер?
Упакування множин.
Умова:
задано сімейство
кінцевих множин і додатне ціле число
.
Питання: чи вірно, що в міститься множин, що не перетинаються?
Розбиття на гамільтонові підграфи.
Умова: задано граф і додатне ціле число .
Питання:
чи можна множину вершин графа розбити
на
підмножин, що не перетинаються,
,
, ...,
так щоб для всіх
(
) кожний підграф, індукований на
відповідній множині, складає гамільтонів
цикл у графі
?
Найбільший загальний підграф.
Умова:
задано графи
,
і додатне ціле число
.
Питання:
чи існують такі підмножини
і
,
що
,
а підграфи
,
ізоморфні?
Мінімум суми квадратів.
Умова:
задано кінцеву множину
і функцію розміру
для шкірного
і додатні цілі числа
і
.
Питання:
чи можна всі елементи заданої множини
розбити на
множин, що не перетинаються
так, щоб
?
2. * Метод локальної заміни.
Множина вершин, що розрізають контури.
Умова:
задано орієнтований граф
і додатне ціле число
,
.
Питання:
чи існує така підмножина
,
що
і будь-який орієнтований цикл у
містить принаймні одне ребро, що належить
?
Точне покриття чотирьохелементними множинами.
Умова:
задано кінцеву множину
,
,
ціле число
і сімейство
чотирьох елементних підмножин множини
.
Питання:
чи існує підсімейство
,
таке, що кожний елемент з
належить тільки одному елементу з
?
Домінуюча множина.
Умова: задано граф і додатне ціле число .
Питання:
чи існує така підмножина
,
що
і кожна вершина
з’єднана ребром принаймні з однією
вершиною з
?
Дерево Штейнера.
Умова:
задано граф
і підмножина
і додатне ціле число
.
Питання:
чи існує піддерево в
,
яку містить всі вершини з
і має не більше
ребер?
Нееквівалентність регулярних виразів, що не містять символу „зірка”.
Умова:
задано два регулярних вирази
та
,
що не містять символи „зірка”, у
скінченному алфавіті
.
Такий вираз визначається наступним
чином: а) будь-який символ
алфавіту
це регулярний вираз, що не містить
символу „зірка”; б) якщо
та
– два вирази, що не містять символи
„зірка”, те і слова
і
також регулярні вирази, що не містять
символу „зірка”.
Питання:
чи вірно, що
та
представляють собою різні мови в алфавіті
?(Якщо
та
представляють відповідно алфавіти
та
,
то
представляє алфавіт
,
а
–
).
3. * Метод побудови компонент.
Розбиття множини.
Умова:
задано сімейство
підмножин скінченної множини
.
Питання:
чи існує розбиття множини
на дві підмножини
та
,
таке що жодна множина з сімейства
не міститься ні в
ні в
?
Розбиття на шляхи довжини 2.
Умова:
задано граф
,
де
для деякого цілого додатного
.
Питання:
чи існує розбиття
на
множин, що не перетинаються, по трьох
вершині в кожній, таке, що для всіх
принаймні два з трьох ребра утворених
цими вершинами належати
?
Нумерація графа по Грунді.
Умова:
задано орієнтований граф
.
Питання:
чи існує така нумерація
(де кожній вершині може бути присвоєно
тільки один номер), що для всіх
існує найменше невід’ємне число, що не
належить множині
?
Задача про розфарбування графа в 3 кольори.
Умова: задано граф .
Питання:
чи можна розфарбувати граф
в 3 кольори? Або чи існує функція
,
така, що
,
якщо
?
