Этюды для программистов

Конечно, результатом работы над этюдом должна быть понятная и четкая программа, стиль и комментарии которой соответствовали бы задаче и выбранному языку. Но этого мало. Еще необходим набор тестов, достаточный для демонстрации работы программы и ее реакции на экстремальные ситуации и неправильное обращение. Наряду с самой программой требуется краткое словесное описание методов решения. Особый упор в нем следует сделать на положенные в основу решения алгоритмы и структуры данных. Наряду с описанием программы программист должен с достаточной степенью правдоподобности хотя бы неформально проиллюстрировать ее правильность (при недостатке времени можно ограничиться рассмотрением ключевых мест). Наконец, должен быть произведен подсчет затраченных ресурсов, как людских, так и машинных; особое внимание следует обратить на обоснование затрат. Также следует указать, чему программист научился на примере этой задачи (на этот вопрос легко ответить, если сформулировать его в виде: «Что я в следующий раз сделаю иначе?»). Такой объем документации может показаться избыточным. Заметим, однако, что умению вовремя поставить точку тоже очень полезно научиться. Решение небольшой задачи не следует перегружать документацией. Один знакомый автору преподаватель определяет оценку на 40% тем, что студент убедил его в правильности программы, на 50% легкостью, с которой его удалось убедить, и только на 10% отличным программированием. Очень хорошая оценка — это 80% и более. А поскольку часть документации — результаты машинных прогонов, такая отметка означает, что программа произвела благоприятное впечатление и на преподавателя, и на ЭВМ.

Советы преподавателю

Первоначально книга предназначалась для студентов — слушателей вводного курса по информатике. Лекционная часть этого курса охватывает широкий спектр вопросов, включая языки и технику программирования, архитектуру ЭВМ, структуры данных, алгоритмы и некоторые сведения из теории. Лектор может использовать некоторые задачи в качестве примеров (скажем, задачу о раскрашивании карты — для обучения Паскалю), но в целом задачи предназначены для самостоятельного решения. Предполагается только, что общее время, отводимое на решение задач, будет не меньше, чем продолжительность всего курса. На структуру самого курса не налагается практически никаких ограничений. С другой стороны, имеются четыре задачи специально для курсов по компиляторам. Эти задачи прямо ориентированы на поддержку обучения методам реализации языков программирования. В нескольких задачах представлены некоторые основные аспекты программирования игр. Другие могут служить материалом для практических занятий по программированию коммерческих задач и задач имитационного моделирования. Заинтересованный преподаватель сможет найти здесь задачи из любой области, кроме численного анализа.

Литература

Science Citation Index. Institute for Scientific Information, Philadelphia, PA. Yearly.

Если вы хотите узнать побольше по какому-либо из затронутых в нашей книге направлений, можно воспользоваться цитированной литературой, затем — библиографией из этих работ и т. д. Но как найти работы, которые вышли в свет уже после перечисленных в книге? Если у вас есть некий источник по какой-либо теме, то в Science Citation Index можно найти работы, ссылающиеся на имеющуюся у вас. В каждом из ежегодных выпусков разъясняется, как им пользоваться, да и библиотекарь вам в этом поможет.

Конвей, Грис (Conway R., Gries D.). An Introduction to Programming, 2nd ed. Winthrop, Cambridge, MA, 1975.

Строго говоря, это — введение в программирование (а заодно и хорошее руководство по PL/I). Но, кроме того, это прекрасный учебник по надежности и методам доказательства правильности программ. Перед тем как приступить к вашему первому этюду, имеет смысл повторить материал по построению программ, приведенный в этой книге.

Вирт (Wirth N.). Algorithms + Data Structures = Programs, Prentice-Hall, Englewood Cliffs, NJ, 1976.

Дейкстра (Dijkstra E. W.). A Discipline of Programming, Prentice-Hall, Englewood Cliffs, NJ, 1976. [Имеется перевод: Дейкстра Э. Дисциплина программирования.— М.: Мир, 1978.]

Работы Дейкстры и Вирта перекликаются друг с другом, хотя и написаны независимо. Примерный курс мог бы выглядеть так: прочитайте Конвея и Гриса; попробуйте несколько несложных задач; прочитайте Вирта; попробуйте несколько более трудных задач; прочитайте Дейкстру и снова решите уже пройденные задачи. Вирт, по существу, приводит примеры программ и методы их построения для некоторых задач среднего размера. Дейкстра обсуждает в целом только критические циклы, а также структуры данных, но приводит больше формальных доказательств. В книге Дейкстры также содержатся размышления о программировании как творческой деятельности, и эти мысли, может быть, самая ценная часть книги (но для того, чтобы их оценить, требуется некоторый опыт).