Дискретная математика. Громов Ю.Ю - 70 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

70
Приведём интуитивное (наивное) определение алгоритма. Сово-
купность правил, обладающих свойствами массовости (инвариантности
относительно входной информации), детерменированности (однознач-
ности применения этих правил на каждом шаге), результативности (по-
лучения после применения этих правил информации, являющейся ре-
зультатом) и элементарности (отсутствии необходимости дальнейшего
уточнения правил), называется алгоритмом.
Рассмотренное понятие машины Тьюринга является строгим уточне-
нием этого наивного определения алгоритма и позволяет решить вопрос
алгоритмической (машинной) разрешимости той или иной проблемы.
Тезис Тьюринга. Для любого алгоритма, понимаемого в интуитив-
ном смысле, можно построить машину Тьюринга, функционирование
которой эквивалентно этому алгоритму. ■
В соответствии с данным тезисом некоторая проблема является ал-
горитмически разрешимой, если существует алгоритм (соответствующая
машина Тьюринга) для её решения, и алгоритмически неразрешимой −
в противном случае.
Заметим, что каждая отдельная машина Тьюринга может быть пред-
ставлена программой произвольного вида для цифровой вычислительной
машины с потенциально бесконечной памятью.
Задачи и упражнения
1. На ленте записана непрерывная последовательность символов
‘+’ и УГ в своём начальном положении
видит один из этих символов.
Разработать машину Тьюринга, которая заменяет, начиная с левого кон-
ца, каждый второй символ ‘+’ на символ ‘−’.
2. В начальном положении УГ видит самую правую цифру неотри-
цательного целого числа, записанного на ленте в троичной системе счис-
ления. Разработать машину Тьюринга, которая увеличивает заданное
число на 1 и возвращает УГ в исходное положение.
3. На ленте записано натуральное число в четверичной системе
счисления и УГ в своём начальном положении
видит самую правую циф-
ру этого числа. Разработать машину Тьюринга, которая уменьшает за-
данное число на 1, не оставляя образующихся при этом незначащих ну-
лей, и возвращает УГ в исходное положение.
13. ЭЙЛЕРОВЫ И ГАМИЛЬТОНОВЫ ГРАФЫ
Эйлеровым циклом в связном неориентированном графе G называет-
ся цикл, в котором каждое ребро этого графа содержится ровно один раз.
Граф G называется эйлеровым графом, если в нём существует эйлеров
цикл. Граф G называется полуэйлеровым графом, если в нём существует

Страницы