- •Задачи для программирования по темам
- •Направление ″бизнес-информатика″, специальность ″математические методы в экономике″
- •1 . Обходы графа . Вычисление числа компонент связности графа.
- •2. Алгоритмы поиска путей в графе.
- •3. Алгоритмы нахождения минимального остова в графе
- •4. Хроматическое число графа. Алгоритм правильной раскраски вершин графа методом перебора с возвратами.
- •5. Транспортные сети. Теорема форда-фалкерсона о максимальном потоке в транспортной сети
- •6А. Варианты задач для групп по направлению ″бизнес-информатика″ тема ″транспортные сети″
- •6Б. Варианты задач для групп по специальности ″математические методы в экономике″
- •7.Задачи по теме ″рекурсивные функции″.
- •1. Доказать, что следующие функции примитивно рекурсивны:
- •8. Задачи по теме ″машины тьюринга″
- •2. (Гаврилов г. П., Сапоженко а.А. Задачник. С. 220-221, идея из № 1.2.) Построить машину в алфавите , , которая:
- •3. (Гаврилов г. П., Сапоженко а.А. Задачник. С. 221, № 1.3.) По заданной машине Тьюринга и начальной конфигурации найти заключительную конфигурацию:
- •4. (Лавров и.А., Максимова л.Л. С. 138, № 1.) Какую функцию вычисляет машина Тьюринга со следующей программой п:
- •5. (Лавров и.А., Максимова л.Л. С. 139, № 5.) Построить следующие машины Тьюринга в алфавите , , начальную конфигурацию в заключительную конфигурацию :
8. Задачи по теме ″машины тьюринга″
1. (Гаврилов Г. П., Сапоженко А.А. Задачник. С. 220, № 1.1.) Установить, применима ли машинаТьюринга , заданная программой , к слову . Если применима, найти рельтат применения. Предполагается, что − начальное, − заключительное состояния машины, а начальная конфигурация.
|
|
||||||||||||||||
0 |
|
0 |
|
|
0 |
||||||||||||
1 |
|
1 |
|
1 |
|
||||||||||||
a) б) в) |
|
a) б) в) |
|
a) б) в) |
|||||||||||||
|
|
||||||||||||||||
|
|
2. (Гаврилов г. П., Сапоженко а.А. Задачник. С. 220-221, идея из № 1.2.) Построить машину в алфавите , , которая:
a) применима к любой непустой ленте (т.е. останавливается лишь в том случае, если хотя бы в одной из ячеек записан символ ; зона действия − бесконечная слева и справа от начальной обозреваемой ячейки) ;
б) применима к словам вида и не применима к словам вида ;
в) применима только к словам вида ();
г) применима к словам вида () и не применима к словам вида , если .
3. (Гаврилов г. П., Сапоженко а.А. Задачник. С. 221, № 1.3.) По заданной машине Тьюринга и начальной конфигурации найти заключительную конфигурацию:
|
|||||||||
0 |
|
0 |
|||||||
1 |
|
1 |
|||||||
а) б) |
|
а) б) в) |
4. (Лавров и.А., Максимова л.Л. С. 138, № 1.) Какую функцию вычисляет машина Тьюринга со следующей программой п:
0 |
||
1 |
5. (Лавров и.А., Максимова л.Л. С. 139, № 5.) Построить следующие машины Тьюринга в алфавите , , начальную конфигурацию в заключительную конфигурацию :
1) |
А. |
Перенос нуля: |
|
2) |
П. |
Правый сдвиг: |
|
3) |
Л. |
Левый сдвиг: |
|
4) |
Т. |
Транспозиция: |
|
5) |
У. |
Удвоение: |
|
6) |
Циклический сдвиг: |
||
7) |
Копирование: |
6. (Лавров И.А., Максимова Л.Л. С. 139, № 3, 4, 6, 8.) Построить следующие машины Тьюринга в алфавите , , вычисляющие следующие функции:
(а) |
|
|
(е) |
|
(б) |
|
(ж) |
||
(в) |
|
(з) |
||
(г) |
|
(и) |
||
(д) |
|
(к) |
7. (Лавров И.А., Максимова Л.Л. С. 139, № 8.) Построить следующие машины Тьюринга в алфавите , , правильно вычисляющие следующие функции:
1) ; 2) .
Замечание. Машина останавливается лишь тогда, когда результат − неотрицательное целое число, в противном случае работает бесконечно.
8. (Гаврилов Г. П., Сапоженко А.А. Задачник. С. 223, № 1.9, 1-3. Композиция машин.) Построить композицию машин Тьюринга и по паре состояний (, ) и найти результат применения композиции к слову .
|
||||||
0 |
|
0 |
||||
1 |
|
1 |
||||
а) ; б) ; |
9. (Гаврилов Г. П., Сапоженко А.А. Задачник. С. 223, № 1.11, 1-2. Разветвление машины.) Найти результат применения машины , (, ), , (, ), ) к слову .
|
|
|
|
||||||||
0 |
|
|
0 |
|
|
0 |
|||||
1 |
|
|
1 |
|
|
1 |
− |
а) ; б) ;
|
|
||||||||||
0 |
|
0 |
|
0 |
|||||||
1 |
|
1 |
|
1 |
а) (); б) (, , );