Завдання до проведення самостійних та індивідуальних занять з дисципліни Теорія алгоритмів для спеціальності Інтелектуальні системи прийняття рішень, НУДПСУ

ДЕРЖАВНА ПОДАТКОВА АДМІНІСТРАЦІЯ УКРАЇНИ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ДЕРЖАВНОЇ ПОДАТКОВОЇ СЛУЖБИ УКРАЇНИ

Кафедра систем і методів прийняття рішень 

ЗАВДАННЯ

до проведення самостійних та індивідуальних занять здисципліни

«ТЕОРІЯ АЛГОРИТМІВ»

для підготовки бакалаврів

за напрямом 0804 «Комп'ютерні науки»

спеціальності 6.080400 «Інтелектуальні системи прийняття рішень»

денної форми навчання

статус дисципліни: нормативна

Ірпінь – 2012

Завдання складені на основі робочої навчальної програми курсу «Теорія алгоритмів», затвердженої у 2008 році.

Розглянуто і схвалено на засіданні кафедри

інтелектуальних систем прийняття рішень,

протокол № ____ від «___»___________200_ р.

Зав. кафедрою __________________ С.П.Ріппа

ПОЯСНЕННЯ ДО РОБОТИ

1. Номери задач, включених до кожного варіанту роботи, визначаються за таблицею варіантів, наведеною нижче.

2. Номер варіанту визначається за списком в журналі.

3. Робота оформлюється на подвійному аркуші паперу із зошиту. Перша сторінка – титульна, на якій подається призвище, ім’я і ім’я по батьку, а також номер варіанту, на наступних сторінках – задачі.

4. Умови задач переписати повністю без скорочень.

5. Розв’язок задачі супроводжувати короткими, але вичерпними поясненнями щодо походження формул та рівнянь, позначень величин, математичних перетворень. Якщо це необхідно, навести креслення.

6. Сумарна кількість балів за розрахункову роботу – 10. Задачі з розділу 1 оцінюються по 1 балу (отже, всього – 2 бали), з розділів 2–5 – по 2 бали (всього – 8 балів).

1. МНОЖИНИ

1. Перерахуйте елементи множини {x | х – цілі числа, причому x² < 100}.

2. Перерахуйте підмножини множини А = {a,b,c,d}.

3. Встановіть істинність або хибність твердження Æ Í Æ.

4. Встановіть істинність або хибність твердження Æ Ì Æ.

5. Встановіть істинність або хибність твердження Æ Î Æ.

6. Встановіть істинність або хибність твердження Æ Í А.

7. Встановіть істинність або хибність твердження Æ Î А.

8. Встановіть істинність або хибність твердження {2} Î {1,2,3,4,5}.

9. Встановіть істинність або хибність твердження A È Æ = A.

10. Встановіть істинність або хибність твердження A \ Æ = A.

11. Для приведених нижче множин використайте діаграми Ейлера – Вена для двох множин і заштрихуйте ті її частини, які зображують задану множину А \ А Ç В.

12. Для приведених нижче множин використайте діаграми Ейлера – Вена для двох множин і заштрихуйте ті її частини, які зобажують задану множину А \ В.

13. Для приведених нижче множин використайте діаграми Ейлера – Вена для двох множин і заштрихуйте ті її частини, які зобажують задану множину (А È В) \ А Ç В.

14. Доведіть, що A Ì B « A È B = B « A Ç B = A « A \ B = Æ « Ā Ç B = U.

15. Доведіть, що A Ç (B \ A) = Æ, A \ (B È C) = (A \ B) \ C.

16. Доведіть, що A Ç B = A \ (A \ B).

17. Доведіть, що A È B = A È (B \ A).

18. Поясніть, чому {1,2} Ï {{1,2,3},{2,3},1,2}.

19. Нехай А = {1,2,3,4,5,6,7}, В = {4,5,6,7,8,9,10}, С = {2,4,6,8,10}, U = {1,2,3,4,5,6,7,8,9,10}. Визначити множину А È С.

20. Нехай А = {1,2,3,4,5,6,7}, В = {4,5,6,7,8,9,10}, С = {2,4,6,8,10}, U = {1,2,3,4,5,6,7,8,9,10}. Визначити множину А Ç В.

21. Нехай А = {1,2,3,4,5,6,7}, В = {4,5,6,7,8,9,10}, С = {2,4,6,8,10}, U = {1,2,3,4,5,6,7,8,9,10}. Визначити множину А Ç (В È С).

22. Нехай А = {1,2,3,4,5,6,7}, В = {4,5,6,7,8,9,10}, С = {2,4,6,8,10}, U = {1,2,3,4,5,6,7,8,9,10}. Визначити множину (А Ç В) È С).

23. Нехай А = {1,2,3,4,5,6,7}, В = {4,5,6,7,8,9,10}, С = {2,4,6,8,10}, U = {1,2,3,4,5,6,7,8,9,10}. Визначити множину А \ В.

24. Дайте геометричну інтерпретацію відношення {{(x,у) Î D² | y = x}.

25. Дайте геометричну інтерпретацію відношення {{(x,у) Î D² | y = x²}.

26. Дайте геометричну інтерпретацію відношення {{(x,у) Î D² | y < x}.

27. Дайте геометричну інтерпретацію відношення {{(x,у) Î D² | y > x}.

28. Дайте геометричну інтерпретацію відношення {{(x,у) Î D² | 0 ≤ x ≤ 1}.

29. Дайте геометричну інтерпретацію відношення {{(x,у) Î D² | 0 ≤ y ≤ 1}.

30. Дайте геометричну інтерпретацію відношення {{(x,у) Î D² | 0 ≤ x ≤ 1 і 0 ≤ y ≤ 1}.

2. ПОРІВНЯННЯ СКЛАДНОСТІ МАСОВИХ ПРОБЛЕМ

1. Порівняйте асимптотичні складності функцій

3. ФОРМИ ПОДАННЯ АЛГОРИТМІВ

1. Складіть словесний припис, що задає алгоритм розв’язку наступної задачі: розв’язати нерівність.

Побудуйте блок-схему для даної задачі, а також складіть запис даної задачі алгоритмічною мовою.

2. Складіть словесний припис, що задає алгоритм розв’язку наступної задачі: розв’язати нерівність.

Побудуйте блок-схему для даної задачі, а також складіть запис даної задачі алгоритмічною мовою.

3. Складіть словесний припис, що задає алгоритм розв’язку наступної задачі: розв’язати нерівність.

Побудуйте блок-схему для даної задачі, а також складіть запис даної задачі алгоритмічною мовою.

4. Складіть словесний припис, що задає алгоритм розв’язку наступної задачі: розв’язати нерівність.

Побудуйте блок-схему для даної задачі, а також складіть запис даної задачі алгоритмічною мовою.

5. Складіть словесний припис, що задає алгоритм розв’язку наступної задачі: розв’язати нерівність.

Побудуйте блок-схему для даної задачі, а також складіть запис даної задачі алгоритмічною мовою.

6. Складіть словесний припис, що задає алгоритм розв’язку наступної задачі: розв’язати нерівність.

Побудуйте блок-схему для даної задачі, а також складіть запис даної задачі алгоритмічною мовою.

7. Складіть словесний припис, що задає алгоритм розв’язку наступної задачі: обчислити значення наступної функції

Побудуйте блок-схему для даної задачі, а також складіть запис даної задачі алгоритмічною мовою.

8. Обчислити значення функції.

Складіть словесний припис, що задає алгоритм розв’язку наступної задачі, побудуйте блок-схему для даної задачі, а також складіть запис даної задачі алгоритмічною мовою.

9. Обчислити значення функції.

Складіть словесний припис, що задає алгоритм розв’язку наступної задачі, побудуйте блок-схему для даної задачі, а також складіть запис даної задачі алгоритмічною мовою.

10. Обчислити значення функції.

Складіть словесний припис, що задає алгоритм розв’язку наступної задачі, побудуйте блок-схему для даної задачі, а також складіть запис даної задачі алгоритмічною мовою.

11. Обчислити значення функції.

Складіть словесний припис, що задає алгоритм розв’язку наступної задачі, побудуйте блок-схему для даної задачі, а також складіть запис даної задачі алгоритмічною мовою.

12. Обчислити значення функції.

Складіть словесний припис, що задає алгоритм розв’язку наступної задачі, побудуйте блок-схему для даної задачі, а також складіть запис даної задачі алгоритмічною мовою.

13. Обчислити значення функції.

Складіть словесний припис, що задає алгоритм розв’язку наступної задачі, побудуйте блок-схему для даної задачі, а також складіть запис даної задачі алгоритмічною мовою.

14. Обчислити значення функції.

Складіть словесний припис, що задає алгоритм розв’язку наступної задачі, побудуйте блок-схему для даної задачі, а також складіть запис даної задачі алгоритмічною мовою.

15. Обчислити значення функції.

Складіть словесний припис, що задає алгоритм розв’язку наступної задачі, побудуйте блок-схему для даної задачі, а також складіть запис даної задачі алгоритмічною мовою.

4. МАШИНА ТЬЮРИНГА

1. Дано два натуральних числа х₁ і х₂, які зображуються за допомогою наборів символів «|». Числа розділені порожньою кліткою S₀. В стандартному стані q_l оглядається самий правий символ вхідної послідовності. Розробити машину Тьюринга, яка на стрічці залишить суму чисел х₁ і х₂. Крім самої програми-таблиці, опишіть словами, що виконується машиною в кожному стані.

2. Яким результатом роботи машини Тьюринга буде, якщо вона працює за програмою

Перевірте це на стрічці

3. Яким результатом роботи машини Тьюринга буде, якщо вона працює за програмою

Перевірте це на стрічці

4. На стрічці машини Тьюринга міститься послідовність символів «+». Напишіть програму для машини Тьюринга, яка кожен другий символ «+» замінить на «-». Заміна починається з лівого символу вхідної послідовності і автомат в стані q_l оглядає один із символів зазначеної послідовності. Крім самої програми-таблиці, описати словами, що виконується машиною в кожному стані.

5. Машина Тьюринга працює за програмою, яка задана наступною таблицею

Яку задачу розв’язує ця машина? Перевірте це на прикладі.

6. На стрічці машини Тьюринга міститься послідовність символів «+». Напишіть програму для машини Тьюринга, яка кожен символ «+» замінить на «-». Заміна починається з лівого кінця послідовності. Автомат в стані q_l оглядає один із символів зазначеної послідовності. Крім самої програми-таблиці, описати словами, що виконується машиною в кожному стані.

7. Яким результатом роботи машини Тьюринга буде, якщо вона працює за програмою

Яку задачу розв’язує ця машина? Перевірте це на прикладі.

8. На стрічці машини Тьюринга задано набір чисел х₁,…,х_n, які зображуються за допомогою наборів символів «|» і сприймається в стандартному положенні. Числа розділені порожньою кліткою S₀. Напишіть програму для машини Тьюринга, яка в заключному стані дасть набір чисел х₁,…,х_n,3.

9. На стрічці машини Тьюринга задано набір чисел х₁,…,х_n, які зображуються за допомогою наборів символів «|» і сприймається в стандартному положенні. Числа розділені порожньою кліткою S₀. Напишіть програму для машини Тьюринга, яка в заключному стані дасть набір чисел х₁,…,х_n,4.

10. На стрічці машини Тьюринга задано набір чисел х₁,…,х_n, які зображуються за допомогою наборів символів «|» і сприймається в стандартному положенні. Числа розділені порожньою кліткою S₀. Напишіть програму для машини Тьюринга, яка в заключному стані дасть набір чисел 2,х₁,…,х_n.

11. На стрічці машини Тьюринга задано набір чисел х₁,…,х_n, які зображуються за допомогою наборів символів «|» і сприймається в стандартному положенні. Напишіть програму для машини Тьюринга, яка в заключному стані дасть набір чисел 3,х₁,…,х_n.

12. На стрічці машини Тьюринга задано набір чисел х₁,…,х_n, які зображуються за допомогою наборів символів «|» і сприймається в стандартному положенні. Напишіть програму для машини Тьюринга, яка в заключному стані дасть набір чисел 4,х₁,…,х_n.

13. Яким результатом роботи машини Тьюринга буде, якщо вона працює за програмою

Яку задачу розв’язує ця машина? Перевірте це на прикладі.

14. Яким результатом роботи машини Тьюринга буде, якщо вона працює за програмою

Яку задачу розв’язує ця машина? Перевірте це на прикладі.

15. Машина Тьюринга працює за програмою, яка задана наступною таблицею

Яку задачу розв’язує ця машина? Перевірте це на прикладі.

5. АСИМПТОТИЧНІ СПІВВІДНОШЕННЯ

1. Перевірити, що n²/2 – 3n = Ө(n²).

2. Перевірити, що n²/3 – 3n + 100 = Ө(n²).

3. Перевірити, що 5n³ – 3n = Ө(n³).

4. Перевірити, що n³/7 – n²/3 + 5n +1000 = Ө(n³).

5. Перевірити, що n⁴/8 – n³/5 + 5n +1500 = Ө(n⁴).

6. Перевірити, що 8n⁴ – n³/5 + n²/2 – 5n + 999 = Ө(n⁴).

7. Перевірити, що n/2 – 3 = Ө(n).

8. Перевірити, що 100n + 9999 = Ө(n).

9. Для f(n) = n⁴/8 – n³/5 + 5n +1500 і g(n) = 8n⁴ – n³/5 + n²/2 – 5n + 999 знайдіть таку константу с > 0 і таке n₀, що 0 ≤ сf(n) ≤ g(n) для всіх n ≥ n₀.

10. Для f(n) = 5n³ – 300n і g(n) = n³/7 – n²/3 + 5n – 1000 знайдіть таку константу с > 0 і таке n₀, 0 ≤ g(n) ≤ сf(n) для всіх n ≥ n₀.

11. Для f(n) = 5n² – 300n +17 і g(n) = n²/7 – 1000 знайдіть таку константу с > 0 і таке n₀, 0 ≤ сg(n) ≤ f(n) для всіх n ≥ n₀.

12. Для f(n) = 5n³ – 3n і g(n) = n³/7 – n²/3 + 5n +1000 знайдіть таку константу с > 0 і таке n₀, що 0 ≤ f(n) ≤ сg(n) для всіх n ≥ n₀.

13. Для f(n) = n⁴/8 – n³/5 + 5n +1500 і g(n) = 8n⁴ – n³/5 + n²/2 – 5n + 999 знайдіть таку константу с > 0 і таке n₀, що 0 ≤ сf(n) ≤ g(n) для всіх n ≥ n₀.

14. Для f(n) = 5n³ – 300n і g(n) = n³/7 – n²/3 + 5n – 1000 знайдіть таку константу с > 0 і таке n₀, 0 ≤ g(n) ≤ сf(n) для всіх n ≥ n₀.

15. Для f(n) = 5n² – 300n +17 і g(n) = n²/7 – 1000 знайдіть таку константу с > 0 і таке n₀, 0 ≤ сg(n) ≤ f(n) для всіх n ≥ n₀.

З повагою ІЦ “KURSOVIKS”!