1.3. Рекомендации к выполнению курсовой работы

Рекомендации к разд. 1. В подразд. 1.1 рассматриваются 2 пункта: "Постановка задачи" и "Математическое описание задачи и методов её ре-шения". Подразд. 1.2 содержит 3 пункта: "Словесное описание алгоритма", "Структуры данных" и "Техническое описание схемы алгоритма". Содер-жание п. 1.2.1 ясно из названия. В п. 1.2.2 описывается выбор структур данных (т.е. представление в памяти ЭВМ исходных, промежуточных и конечных данных) и его обоснование. Отметим, что выбор подходящих структур данных осуществляется параллельно с составлением схемы ал-горитма (СА). В п. 1.2.3 приводятся основная СА и СА предопределённых процессов и функций, а также их описания с указанием передаваемых параметров и их значений. СА составляют достаточно подробными для того, чтобы по ним можно было понять работу алгоритма; в то же время СА не должна дублировать программу. В подразд. 1.3 необходимо пошагово описать работу алгоритма, используя контрольный(е) пример(ы) (задаются таблицы из [4] для алгоритмов покрытия и на графах, а также количество чисел - для алгоритмов сортировки). В п. 1.4 необходимо провести анализ эффективности заданного алгоритма и продумать возможность повысить её за счёт разделения задачи на подзадачи и балансировки данных, использования рекурсии либо итераций, а также метода динамического программирования.

Примечание. Для алгоритмов сортировки необходимо подсчитать количество пересылок элементов массива и их сравнений для трёх примеров массивов, состоящих из заданного числа элементов:

а) отсортированный;

б) отсортированный в обратном порядке;

в) отсортированный случайным образом.

Сравнить полученные оценки с формулами (прил. Г) для оценки количества сравнений и пересылок, а также с соответствующими оценками для алгоритмов одного класса (например, бинарные включения с простыми и наоборот).

Рекомендации к разд. 2. В подразд. 2.1 должны быть представлены следующие пункты: "Постановка задачи", "Идея решения задачи", "Словесное описание алгоритма решения", "Используемые символы на ленте" (в результате анализа словесного описания алгоритма определяется множество используемых символов, требуемых для реализации алгоритма заданной операции; иногда для решения задачи бывает проще использовать дополнительные символы, но желательно использовать как можно меньшее их количество). В подразд. 2.2 должны быть представлены два пункта, "Схема алгоритма" и "Функциональная схема". В первом пункте необходимо привести схему алгоритма, построенную в соответствии с его словесным описанием, и описать работу машины Тьюринга (МТ). Во втором пункте необходимо проанализировать СА с целью определения состояний и переходов МТ, реализующей этот алгоритм; построить программу работы машины (её функциональную схему - ФС), которая выполняет заданную операцию над указанными числами в некоторой последовательности (желательно решить задачу, используя как можно меньше внутренних состояний машины Тьюринга, т.е. меньше строк в ФС); нарисовать граф состояний МТ (для заданного фрагмента СА). В подразд. 2.3 необходимо рассмотреть пример (выбирается самостоятельно), показывающий работу машины для конкретной начальной конфигурации на ленте, расписав по тактам последующие конфигурации (в случае цикла допустимо ограничиться начальным и конечным тактами); пример должен охватывать все ветви алгоритма. Далее этот пример анализируется с целью выявления аварийных ситуаций. В заключение определяется длительность (в тактах) процесса выполнения заданной операции.