1.2. Задания на разработку

Алгоритмы выбираются из следующих списков.

Алгоритмы покрытия:

A1 - граничный перебор по вогнутому множеству;

A2 - построение одного кратчайшего покрытия;

A3 - построение одного минимального покрытия;

A4 - по методу "минимальный столбец - максимальная строка";

*А5 - построение циклического остатка;

*A6 - разложение по столбцу;

*A7 - по методу ветвей и границ.

Алгоритмы на графах:

B1 - нахождение кратчайшего пути;

B2 - алгоритм Дейкстры нахождения кратчайшего пути;

B3 - нахождение длиннейшего пути;

B4 - построение минимального остова;

B5 - построение системы независимых циклов;

B6 - нахождение компонент связности;

*B7 - кратчайшая раскраска;

*B8 - определение максимального потока в сети;

*B9 - определение минимального потока в сети.

Алгоритмы сортировки:

C1 - сортировка бинарными включениями;

C2 - шейкер-сортировка;

C3 - сортировка Шелла;

*C4 - пирамидальная сортировка;

*C5 - быстрая сортировка.

Примечания:

1. Алгоритмы А6 и А7 строятся, считая, что циклический остаток уже есть.

2. Простые алгоритмы описаны в [4], более сложные - в [5,6].

Задания по построению машины Тьюринга выбираются из следующего списка.

МТ1. Сравнение двух отмеченных символом "*" чисел a и b в после- довательности. В качестве результата справа от этой последовательности должен стоять знак отношения: ">", "<" либо "="; числа при этом должны быть сохранены.

МТ2. Сложение двух отмеченных символом "*" чисел a и b в последовательности. Справа от неё должна находиться сумма.

МТ3. Определение остатка от деления числа a на 3.

МТ4. Определение середины последовательности чисел. Если количество чисел чётное, то поставить один символ "*" в середине последовательности вместо пустой ячейки; если же количество чисел нечётное, то "окаймить" символом "*" центральное число.

МТ5. Пересылка отмеченного символом "*" числа на место первого слева, остальные числа сдвигаются.

МТ6. Пересылка отмеченного символом "*" числа на место за последним справа, остальные сдвигаются.

МТ7. Копирование системы чисел (x₁, x₂ ..., x_n). Должно получиться: (x₁, x₂, .., x_n, x₁, x₂, ...,x_n).

МТ8. Обмен двух отмеченных символом "*" чисел a и b в последовательности.

МТ9. Разметка чисел в последовательности с шагом 3. Это значит, что необходимо вместо пустого символа поставить символ "*" после каждого третьего числа.

*МТ10. Разметка чисел в последовательности с шагом k, заданным на ленте на месте самого левого числа. Необходимо символ "*" поставить вместо пустого символа после каждого k-го числа.

*МТ11. Определение середины последовательности чисел и обмен рядом стоящих у середины чисел местами. Принять, что количество чисел - чётное. Отметить середину последовательности символом *.

*МТ12. Сравнение двух трехразрядных чисел (3 десятичных разряда в каждом). Начальная конфигурация на ленте:

11 v 11...1*11...1*11...1 v 11...1*11...1*11...100....

а b

здесь a и b - числа, которые необходимо сравнить; v - указатель на числа; * - разделитель между разрядами для трехразрядных чисел. В результате справа от последовательности чисел должны стоять знаки отношения: ">", "<" либо "=".

*МТ13. Вычислить выражение: 2(a+b)-c.

*МТ14. Вычислить выражение: 2a+b-3c.

*МТ15. Вычислить выражение: a-3b-2c.

Примечания:

1.Числа a, b, c, ... расположены на ленте в порядке перечисления.

2. Начальное расположение головки задаётся руководителем курсо-вой работы (по умолчанию - стандартное).