- •Зміст дисципліни.
- •Найменування тем, їхній зміст, обсяг у годинах лекційних занять
- •Вказівки з використанНя літературних джерел
- •Алгоритми й структури даних
- •Стеки, списки
- •Дерева пошуку Бінарні дерева
- •Двійкові дерева
- •Червоно- чорні дерева
- •Частково впорядковані дерева Статья I.При створенні чуд елементи вводилися в наступному порядку: (13, 6, 15, 5, 10, 6, 3, 13, 5, 6, 35, 8). Пояснити побудова (переформування) дерева.
- •Рекурсія
- •Перебір з поверненням
- •Машина Тьюрінга
- •Приклади Послідовний пошук
- •Структури даних. Масиви Решето Ератосфена
- •Обчислення найближчої точки
- •Структури даних. Списки Приклад циклічного списку (задача Йосипа)
- •Сортування методом вставки в список
- •Звертання порядку проходження елементів списку
- •Структури даних. Рядки Сортування масиву рядків
- •Абстрактні типи даних (атд) Інтерфейс абстрактного типу даних стека
- •Реалізація черги fifo на базі масиву
- •Реалізація черги fifo на базі зв'язного списку
- •Перетворення з інфіксної форми в постфіксну
- •Рекурсія Алгоритм Евклида
- •Рекурсивна програма для оцінки префіксних виразів
- •Розв’язання
- •Приклад 2 Завдання
- •Розв’язання
- •Приклад 3 Завдання
- •Розв’язання
- •Приклад 4 Завдання
- •Розв’язання
- •Приклад 5 Завдання
- •Розв’язання
- •Приклад 6 Завдання
- •Розв’язання
- •Приклад 7 Завдання
- •Розв’язання
- •Алгоритм роботи машини т’юринга
- •Дослідження функції на рекурсивність
- •Нормальні алгоритми Маркова
- •Алгоритм роботи програми.
- •Приклад роботи програми.
- •Варіанти курсових робіт
- •Варіанти виконання Алгоритм виконання курсової роботи:
- •Приклад1.
- •Побудова моделі.
- •Розроблення алгоритму.
- •Правильність алгоритму.
- •Реалізація алгоритму.
- •Перевірка програми.
- •Приклад2
- •Постановка задачі
- •Перший варіант розв’язку
- •Другий варіант розв’язку.
- •Приклад3
- •Опукла оболонка
- •Метод обходу Грехема
- •Метод обходу Джарвіса
- •Алгоритм апроксимації опуклої оболонки
- •Швидкі методи побудови опуклої оболонки
- •Алгоритм типу розділяй та пануй
- •Побудова опуклої оболонки простого многокутника
- •Динамічні алгоритми побудови опуклої оболонки
- •Порівняльний аналіз алгоритмів побудови опуклої оболонки
- •Висновки
Приклад 7 Завдання
Машина,
яка обчислює функцію
Розв’язання
Початок: |
|
|||||||||
Кінцевий стан: |
|
|
|
I |
1 |
|
1L2 |
2 |
0L3 |
1L2 |
3 |
|
1L4 |
4 |
0R93 |
1R5 |
5 |
|
0R6 |
6 |
0R6 |
1R7 |
7 |
0R8 |
1R7 |
8 |
0L9 |
1L8 |
9 |
0L10 |
1L8 |
10 |
0L10 |
1L11 |
11 |
0R28 |
1R12 |
12 |
|
0R13 |
13 |
0R13 |
1R14 |
14 |
0R15 |
1R14 |
15 |
1L16 |
1R14 |
16 |
0L17 |
|
17 |
0L17 |
1L18 |
18 |
0R23 |
1R19 |
19 |
|
0R20 |
20 |
0R20 |
1R21 |
21 |
1L22 |
1R21 |
22 |
0C17 |
1L22 |
23 |
|
1R24 |
24 |
1R24 |
1L25 |
25 |
|
0R26 |
26 |
0L27 |
1R26 |
27 |
|
1C8 |
28 |
|
1R29 |
29 |
0R29 |
1R30 |
30 |
0R31 |
1R30 |
31 |
0L32 |
1R30 |
32 |
0L32 |
1C33 |
33 |
|
1L34 |
34 |
0L35 |
1L34 |
35 |
|
1L36 |
36 |
0R77 |
1R37 |
37 |
|
0R38 |
38 |
0R38 |
1R39 |
39 |
0L40 |
1R39 |
40 |
0L41 |
1L40 |
41 |
0L42 |
1L40 |
42 |
0L42 |
1L43 |
43 |
0R60 |
1R44 |
44 |
|
0R45 |
45 |
0R45 |
1R46 |
46 |
0R47 |
1R46 |
47 |
1L48 |
1R46 |
48 |
1L49 |
|
49 |
1L49 |
1L50 |
50 |
OR55 |
1L51 |
51 |
|
1L52 |
52 |
0R52 |
1L53 |
53 |
1L54 |
1L53 |
54 |
0C49 |
1L54 |
55 |
|
1L56 |
56 |
1R56 |
1L57 |
57 |
|
0R58 |
58 |
1L59 |
1R58 |
59 |
|
1C40 |
60 |
|
1R61 |
61 |
0R61 |
1R62 |
62 |
0R63 |
1R62 |
63 |
0R64 |
1R62 |
64 |
0R64 |
1C65 |
65 |
0L66 |
1L65 |
66 |
0R71 |
1R67 |
67 |
1R68 |
|
68 |
0L69 |
1R68 |
69 |
|
0L70 |
70 |
|
0L65 |
71 |
0L72 |
1R71 |
72 |
|
0L73 |
73 |
1L74 |
1L73 |
74 |
0R71 |
1R75 |
75 |
0L80 |
1R75 |
76 |
|
1C81 |
77 |
0R78 |
1R77 |
78 |
0L79 |
1R78 |
79 |
0L76 |
0L79 |
80 |
|
0L76 |
81 |
0L82 |
1L81 |
82 |
0R85 |
1R83 |
83 |
0R83 |
1R84 |
84 |
0L33 |
1R84 |
85 |
0R85 |
1R86 |
86 |
0L87 |
1R86 |
87 |
|
0L88 |
88 |
1L89 |
1L88 |
89 |
0R90 |
1R91 |
90 |
0L88 |
1R90 |
91 |
0L92 |
1R91 |
92 |
|
1C0 |
93 |
0R94 |
1R93 |
94 |
0R94 |
1R95 |
95 |
0L96 |
1R95 |
96 |
1C92 |
0L96 |
1-7 – видалення з однієї "I".
8-32 – послідовне коментуємо управо по стрічці, видаляючи при цьому палички з .
33-80 – виконуємо перемножування всіх (детально воно описане в машині, що будує ).
81-86 – йде перевірка, є ще що перемножити чи ні.
87-92 – множення закінчене, тепер треба змістити результат .
93-96
– реалізація випадку
окремо.
Приклад 8
Завдання
Для функції rest(x,y)x побудувати машину Т’юринга, дослідити її на рекурсивність та побудувати нормальний алгоритм Маркова.
Розв’язання
Машина Тьюринга
Правила машини Т’юринга.
Правила описуються наступним чином. Є три стовпчика: перший - номер стану, другий – дії машини, якщо у поточній клітинці 0, третій - дій машини, якщо у клітинці 1. Дії записуються наступним чином. Спершу йде той символ, який буде записуватись в поточну клітинку. Потім - символ, який визначає напрямок руху каретки. І останній - стан, в який машина переходить. Так, наприклад, 0<68 означає, що у клітинку записується 0, каретка рухається вліво на одну клітинку і машина переходить у стан 68. Літера S означає кінець роботи машини.
№ |
|
I |
0 |
0L68 |
|
1 |
0L2 |
1L1 |
2 |
0R60 |
1L2 |
3 |
0R10 |
0R4 |
4 |
0R5 |
1R4 |
5 |
0R6 |
1R5 |
6 |
1L7 |
1R6 |
7 |
0L8 |
1L7 |
8 |
0L9 |
1L8 |
9 |
1R3 |
1L9 |
10 |
|
1R11 |
11 |
|
0L12 |
12 |
0L13 |
1L12 |
13 |
0L13 |
1L14 |
14 |
0R15 |
1L14 |
15 |
|
1R16 |
16 |
|
1R35 |
17 |
0R18 |
1R17 |
18 |
0R18 |
1R19 |
19 |
1R20 |
1R19 |
20 |
0L24 |
0L21 |
21 |
0L22 |
1L21 |
22 |
0L22 |
1L23 |
23 |
1R16 |
1L23 |
24 |
0L25 |
1L24 |
25 |
0L25 |
1L26 |
26 |
1R27 |
1L26 |
27 |
0R28 |
1R27 |
28 |
0R28 |
1R29 |
29 |
0L34 |
0L30 |
30 |
0L31 |
lLЗО |
31 |
0L31 |
0R32 |
32 |
0R32 |
1R33 |
33 |
1R29 |
1R33 |
34 |
0R10 |
1L36 |
35 |
0R37 |
1L36 |
36 |
|
0R17 |
37 |
0R37 |
1R38 |
38 |
1R53 |
1R38 |
39 |
0R40 |
1L39 |
40 |
0R41 |
0R40 |
41 |
|
0L42 |
42 |
0L42 |
1R43 |
43 |
0R44 |
|
44 |
1R45 |
|
45 |
0R45 |
1R46 |
46 |
0L49 |
1L47 |
47 |
|
0L48 |
48 |
0L48 |
1R44 |
49 |
|
0L50 |
50 |
0L50 |
1R51 |
51 |
1R52 |
|
52 |
0L89 |
|
53 |
0L54 |
1L39 |
54 |
0L55 |
1L54 |
55 |
ОL55 |
1L56 |
56 |
ОR58 |
1R57 |
57 |
|
0L55 |
58 |
|
1R59 |
59 |
0R59 |
0R40 |
60 |
|
1R61 |
61 |
0R62 |
1LЗ |
62 |
0L63 |
0R62 |
63 |
0L63 |
1R64 |
64 |
0S0 |
|
65 |
1R66 |
|
66 |
0R67 |
|
67 |
1R52 |
|
68 |
|
1L69 |
69 |
0R70 |
1R71 |
70 |
0S0 |
1R70 |
71 |
0L72 |
lL71 |
72 |
0R73 |
1L72 |
73 |
0R80 |
0R74 |
74 |
0R75 |
1R74 |
75 |
0R76 |
1R75 |
76 |
1L77 |
1R76 |
77 |
0L78 |
1L77 |
78 |
0L79 |
1L78 |
79 |
1R73 |
1L79 |
80 |
0R87 |
0R81 |
81 |
0R82 |
1R81 |
82 |
0R83 |
1R82 |
83 |
1L84 |
1R83 |
84 |
0L85 |
1L84 |
85 |
0L86 |
1L85 |
86 |
1R80 |
1L86 |
87 |
0R88 |
1R87 |
88 |
0L1 |
1R88 |
89 |
0R90 |
1R89 |
90 |
1R91 |
|
91 |
1L92 |
|
92 |
|
1L93 |
93 |
0L94 |
|
94 |
0R95 |
1L94 |
95 |
|
1R96 |
96 |
0S0 |
0L97 |
97 |
0L98 |
1L97 |
98 |
0R99 |
1L98 |
99 |
|
1R100 |
100 |
0R135 |
1R101 |
101 |
0R117 |
0R102 |
102 |
0R103 |
1R102 |
103 |
0R103 |
1R104 |
104 |
0R105 |
1R104 |
105 |
0R106 |
1R105 |
106 |
0R106 |
1R107 |
107 |
0L112 |
0R108 |
108 |
0R109 |
1R108 |
109 |
lL110 |
1R109 |
110 |
0L111 |
lL110 |
111 |
1R107 |
lL111 |
112 |
0L113 |
1L112 |
113 |
0L115 |
1L114 |
114 |
0L115 |
1L114 |
115 |
0L116 |
1L115 |
116 |
1R101 |
1L116 |
117 |
0R118 |
1R117 |
118 |
0R119 |
1R118 |
119 |
1R120 |
1R119 |
120 |
0L121 |
1R120 |
121 |
|
0L122 |
122 |
0L123 |
1L122 |
123 |
0L125 |
1L124 |
124 |
1R96 |
1L124 |
125 |
0L126 |
0L125 |
126 |
0R127 |
0L126 |
127 |
1R128 |
|
128 |
0R128 |
1R129 |
129 |
0L132 |
1L130 |
130 |
|
0L131 |
131 |
0L131 |
1R127 |
132 |
|
0L133 |
133 |
0L133 |
1R134 |
134 |
0S0 |
|
135 |
0R136 |
0R135 |
136 |
0R137 |
0R136 |
137 |
0L138 |
0R137 |
138 |
0L138 |
1R134 |
