Next:3.2
Выбор представления данных
Up:3
Общие рекомендации по выполнению заданий
Previous:3
Общие рекомендации по выполнению заданий
Разработка алгоритма представляет собой задачу на построение. Поэтому, как обычно в таких случаях (можно, например, вспомнить о методе решения геометрических задач на построение), необходим этап анализа задачи. Он позволяет установить, что является входом и выходом будущего алгоритма, выделить основные необходимые отношения между входными и выходными объектами и их компонентами, выделить подцели, которых нужно достичь для решения задачи, и как следствие этого, выработать подход к построению алгоритма. Результатом этого этапа должна быть спецификация алгоритма, т.е. формулировка в самом общем виде того, что (в рамках выбранного подхода) должен делать алгоритм, чтобы переработать входные данные в выходные.
Особенностью индивидуальных заданий является то, что они формулируются как задачи для выполнения вычислений на дискретных конечных математических структурах. Эти задания связаны со сложными структурами данных, с организацией поиска или порождения тех элементов конечного (но, как правило, чрезвычайно большого) множества, которые удовлетворяют определенным ограничениям, и требуют при своем решении анализа алгоритма и его сложности.
В формулировках задач, как правило, отсутствуют какие-либо ограничения на размер входных данных, подлежащих обработке. Ясно, что ресурсы вычислительной системы не беспредельны как в смысле объема памяти, имеющейся для хранения программы и ее данных, так и в смысле времени счета по программе. Поэтому спецификацию алгоритма нельзя признать полной, если не описан явно (через систему ограничений) класс тех входных данных, которые, безусловно, должны обрабатываться разрабатываемым алгоритмом. Например, если обрабатываются тексты, то точным описанием класса входных данных является кроме точного описания структуры текста еще и максимальная допустимая длина входного текста, если обрабатываются матрицы, то такое описание должно включать пару чисел: максимально допустимое число строк и максимально допустимое число столбцов в матрице и т.п. Предполагается, что при выборе ограничений студент стремится не сужать, а максимально расширять класс входных данных (и, таким образом, разработать как можно более универсальную программу) в рамках тех вычислительных ресурсов, которые отводятся студенту для выполнения задания на ЭВМ.
Предполагается, что решением индивидуального задания будет программа, поддерживающая диалог с пользователем в процессе своего исполнения и представляющая результаты своей работы на экране монитора в удобной и наглядной форме. Например, для "геометрической" задачи следует изображать на экране в цвете и в динамике те объекты (точки, прямые и т.п.) и те процессы, которые связаны с шагами выполнения программы.
Поэтому спецификация решения индивидуального задания не сводится к описанию отношения между входным и выходным файлами, а представляет собой описание разрабатываемого алгоритма, но как можно более абстрактное.
При написании такой (исполнимой) спецификации прежде всего нужно иметь в виду, что данное описание предназначено не для машины, а для человека. Другими словами, речь идет не о программе, а о некотором тексте (т.е. о словесном описании), по которому можно получить представление об общей структуре разрабатываемого алгоритма, о смысле его отдельных шагов и их логической взаимосвязи. Сохранение достаточно высокого уровня описания алгоритма также облегчает его обоснование. Поэтому шаги алгоритма должны описываться в терминах тех объектов и отношений между ними, о которых идет речь в формулировке задачи. Например, для "геометрической" задачи шаги алгоритма следует описывать как действия над точками, прямыми и т.п., как проверки свойств типа принадлежности трех точек одной прямой и т.п. Но не должно быть работы с кодами этих объектов, например с матрицей координат точек некоторого множества.
Это, конечно, не исключает использования математической и иной удобной символики. Кроме того, структура алгоритма станет более ясной, если шаги записывать в виде, напоминающем конструкции языков программирования, такие, как, например, операторы цикла и условные операторы.
Next:.3.2
Выбор представления данных
Up:3
Общие рекомендации по выполнению заданий
Previous:3
Общие рекомендации по выполнению заданий