7.4. Теория алгоритмов

Пример. Пусть на ленте записаны два натуральных числа в унарном коде (унарный код  это представление числа в виде соответствующей последовательности единиц. Например, 4=1111=1⁴). Числа разделены символом «+». Требуется реализовать операцию сложения таким образом, чтобы после ее реализации на ленте были сохранены исходные данные и записан результат выполнения операции. Управляющее устройство после завершения работы должно находиться на первом символе текущей записи на ленте.

Начальное состояние МТ, например, для чисел 2 и 4 должно иметь вид:

А заключительное:

В основе алгоритма будет лежать следующая идея, записав символ «=», после исходных данных, за ним следует скопировать все единицы из первого и второго числа, после чего вернуть управляющее устройство в первую позицию записи на ленте. Опишем МТ в виде системы команд:

Множества A и Q определены так:

8. Построить машину Тьюринга, реализующую заданную функцию. Описание машины должно быть представлено в виде системы команд, графа переходов или таблицы. Считать, что исходные данные записаны на ленте, на ней же они должны быть сохранены после выполнения всех действий. Результаты записываются на ленте после исходных данных и отделяются от них символом «=»:

а) Пусть на ленте записана последовательность нулей и единиц. Реализовать машину, которая будет подсчитывать число единиц в исходной последовательности и записывать результат счета;

б) Реализовать функцию, которая в выражении в бинарной форме записи будет подсчитывать количество комбинаций вида 010. Например, 1101101010101=11;

в) Реализовать функцию, которая в выражении в бинарной форме записи будет подсчитывать количество комбинаций вида 101. Например, 01101110001011010=111;

г) Реализовать функцию, которая в выражении в бинарной форме записи будет производить замену комбинации 01 на 1, а 10 на 0. Считать, что такие комбинации в исходном выражении являются взаимно непересекающимися или отделены друг от друга символами. Например, 01111001110001=111011001;

д) ;

е) ;

ж)

з)

и)

к) Реализовать функцию, которая в выражении в унитарной форме записи будет каждую третью единицу заменять на ноль. Например, 1111111 = 1101101;

л) . Символ «[ ]» означает выделение целой части от результата деления. Считать, что x > y;

м) ;

н) ;

о) . Считать, что x > y;

п) .

7.5. Элементы теории нечетких множеств

1. Пусть задано множество студентов С={Иванов, Петров, Сидоров, Федоров}. Определить на нем следующие нечеткие множества: S – трудолюбивых студентов, P – ленивых студентов и U – студентов, успешно сдавших сессию. Найти результаты следующих операций над множествами:

2. Пусть задано два множества E={a,d,f,r} и Y={10,20,15,55}, на которых определены нечеткие множества E и T, соответственно определить отношение между E и T, если эти множества заданы следующим образом:

E = , T = .

3. Пусть задано множество студентов С={Иванов, Петров, Сидоров} и множество курсовых проектов K={k₁,k₂,k₃,k₄}. Определить на множестве студентов нечеткое множество S – сильных студентов, а на K – множество P – сложных курсовых проектов. Определить нечеткое отношение, которое будет соответствовать утверждению: «Если студент сильный, то он будет защищать сложный курсовой проект».

4. Пусть задано множество курсовых проектов K={k₁,k₂,k₃,k₄}, на котором определено нечеткое множество P – непростых курсовых проектов и задано множество D={d₁,d₂,d₃,d₄,d₅} – дипломных проектов, на котором определено нечеткое множество H  хороших дипломных проектов. Определить нечеткое отношение, которое будет соответствовать утверждению: «Если курсовой проект непростой, то из него можно сделать хороший дипломный проект».

5. Пусть заданы два нечетких отношения U и B:

;

.

Определить их свертку .

6. Используя результаты примеров 3 и 4 построить свертку нечетких отношений, которая будет соответствовать утверждению: «Если студент сильный, то у него получится хороший дипломный проект».