Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
TA_last_u3.doc
Скачиваний:
2
Добавлен:
01.04.2025
Размер:
3 Мб
Скачать
☆

Перебір з поверненням

  1. п Дане дерево глибини N, кожна внутрішня вершина якого має K (< 10) безпосередніх нащадків (нумеруються від 1 до K). Корінь дерева має номер 0. Записати в текстовий файл із даним ім'ям всі можливі шляхи, що ведуть від кореня до листів. Перебирати шляхи, починаючи з «самого лівого» і закінчуючи «самим правим» (при цьому першими заміняти кінцеві елементи шляху).

  2. п Дане дерево глибини N, кожна внутрішня вершина якого має K (< 10) безпосередніх нащадків (нумеруються від 1 до K). Корінь дерева має номер 0. Записати в текстовий файл із даним ім'ям всі шляхи, що ведуть від кореня до листів і задовольняючій наступній умові: ніякі сусідні елементи шляхи не нумеруються однієї й тією же цифрою. Порядок перебору шляхів такий же, як у завданні 14.

  3. п Дане дерево глибини N (N — парне), кожна внутрішня вершина якого має 2 безпосередніх нащадка: A з вагою 1 й B з вагою –1. Корінь дерева C має вага 0. Записати в текстовий файл із даним ім'ям всі шляхи від кореня до листів, що задовольняють наступній умові: сумарна вага елементів шляхи дорівнює 0. Порядок перебору шляхів такий же, як у завданні 14.

  4. п Дане дерево глибини N того ж типу, що й у завданні 16. Записати в текстовий файл із даним ім'ям всі шляхи від кореня до листів, що задовольняють наступній умові: сумарна вага елементів для будь-якого початкового відрізка шляху ненегативний. Порядок перебору шляхів такий же, як у завданні 14.

  5. п Дане дерево глибини N, кожна внутрішня вершина якого має 3 безпосередніх нащадка: A з вагою 1, B з вагою 0 й C з вагою –1. Корінь дерева D має вага 0. Записати в текстовий файл із даним ім'ям всі шляхи від кореня до листів, що задовольняють наступним умовам: сумарна вага елементів для будь-якого початкового відрізка шляху непозитивний, а сумарна вага всіх елементів шляхи дорівнює 0. Порядок перебору шляхів такий же, як у завданні 14.

  6. п Дане дерево глибини N того ж типу, що й у завданні 18. Записати в текстовий файл із даним ім'ям всі шляхи від кореня до листів, що задовольняють наступним умовам: ніякі сусідні елементи шляхи не позначаються однієї й тією же буквою, а сумарна вага всіх елементів шляхи дорівнює 0. Порядок перебору шляхів такий же, як у завданні 14.

Машина Тьюрінга

  1. Побудувати машину, що розпізнає парність натурального числа.

  2. Побудувати машину Нгги яка обчислює остача від ділення натурального числа на т.

  3. Побудувати машини Тьюрінга, що обчислюють наступні функції, задані на N х N:

а) x + 2y; б) x2 + 3y.

  1. Написати машину Тьюрінга для обчислення наступних виразів, враховуючи умови:

а) машина починає роботові з положення на першому символі першого слова на стрічці;

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

Завдання:

  1. Функція .

  2. Функція .

  3. Функція .

  4. Функція .

  5. * Функція (якщо , те відповідь винна бути 0).

  6. * Функція .

  7. * Функція .

  8. * Функція .

  9. Функція .

  10. Функція .

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. * Метод звуження проблеми.

  1. Найдовший шлях.

Умова: задано граф і додатне ціле число .

Питання: чи міститься в простий шлях, який складається не менше ніж з ребер?

  1. Упакування множин.

Умова: задано сімейство кінцевих множин і додатне ціле число .

Питання: чи вірно, що в міститься множин, що не перетинаються?

  1. Розбиття на гамільтонові підграфи.

Умова: задано граф і додатне ціле число .

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

  1. Найбільший загальний підграф.

Умова: задано графи , і додатне ціле число .

Питання: чи існують такі підмножини і , що , а підграфи , ізоморфні?

  1. Мінімум суми квадратів.

Умова: задано кінцеву множину і функцію розміру для шкірного і додатні цілі числа і .

Питання: чи можна всі елементи заданої множини розбити на множин, що не перетинаються так, щоб ?

2. * Метод локальної заміни.

  1. Множина вершин, що розрізають контури.

Умова: задано орієнтований граф і додатне ціле число , .

Питання: чи існує така підмножина , що і будь-який орієнтований цикл у містить принаймні одне ребро, що належить ?

  1. Точне покриття чотирьохелементними множинами.

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

Питання: чи існує підсімейство , таке, що кожний елемент з належить тільки одному елементу з ?

  1. Домінуюча множина.

Умова: задано граф і додатне ціле число .

Питання: чи існує така підмножина , що і кожна вершина з’єднана ребром принаймні з однією вершиною з ?

  1. Дерево Штейнера.

Умова: задано граф і підмножина і додатне ціле число .

Питання: чи існує піддерево в , яку містить всі вершини з і має не більше ребер?

  1. Нееквівалентність регулярних виразів, що не містять символу „зірка”.

Умова: задано два регулярних вирази та , що не містять символи „зірка”, у скінченному алфавіті . Такий вираз визначається наступним чином: а) будь-який символ алфавіту це регулярний вираз, що не містить символу „зірка”; б) якщо та – два вирази, що не містять символи „зірка”, те і слова і також регулярні вирази, що не містять символу „зірка”.

Питання: чи вірно, що та представляють собою різні мови в алфавіті ?(Якщо та представляють відповідно алфавіти та , то представляє алфавіт , а – ).

3. * Метод побудови компонент.

  1. Розбиття множини.

Умова: задано сімейство підмножин скінченної множини .

Питання: чи існує розбиття множини на дві підмножини та , таке що жодна множина з сімейства не міститься ні в ні в ?

  1. Розбиття на шляхи довжини 2.

Умова: задано граф , де для деякого цілого додатного .

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

  1. Нумерація графа по Грунді.

Умова: задано орієнтований граф .

Питання: чи існує така нумерація (де кожній вершині може бути присвоєно тільки один номер), що для всіх існує найменше невід’ємне число, що не належить множині ?

  1. Задача про розфарбування графа в 3 кольори.

Умова: задано граф .

Питання: чи можна розфарбувати граф в 3 кольори? Або чи існує функція , така, що , якщо ?

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]