Убедительно о программировании

А. Шень Программирование: теоремы и задачи М.: МЦНМО, 2004. 296 с.

Профессор Александр Шень — математик, профессиональный программист, пишущий нетривиальные программы, и при этом весьма интересный педагог. Предлагаемая вниманию читателей книга написана им по материалам занятий с учениками математических классов московской школы №57 и студентами младших курсов МГУ, Независимого московского университета и университета г. Уппсала, Швеция. Не спешите откладывать ее в сторону под тем предлогом, что она рассчитана на серьезно подготовленных читателей, ведь временами весьма полезно думать о себе с позиции роста самосознания. Не только со школьниками и студентами ведет беседу А. Шень в своей книге «Программирование: теоремы и задачи», вышедшей вторым изданием.

Он отстаивает важные позиции в программировании. Вот как он излагает некоторые из них в начале книги. Она «написана в убеждении, что программирование имеет свой предмет, не сводящийся ни к конкретным языкам и системам, ни к методам построения быстрых алгоритмов». Далее А. Шень, обозначая цель работы, утверждает: «Кто-то однажды сказал, что можно убедить в правильности алгоритма, но не в правильности программы. Одна из целей книги — попытаться продемонстрировать, что это не так». Характеризуя жанр книги, автор полагает ее интересной для «программирования в малом» и оставляет в стороне обязательную часть программистского образования, связанную с модификацией больших программ. И если читатель данной книги, по мысли А. Шеня, «почувствует прелесть хорошо написанной программы, в которой «ни убавить ни прибавить» и сомнения в правильности которой кажутся нелепыми, то автор будет считать свою цель достигнутой».

Уточняя круг читателей книги, А. Шень полагает ее «не столько учебником для школьников, сколько справочником и задачником для преподавателя, готовящегося к занятиям». Весьма ценно замечание А. Шеня об авторских правах: «Право формулировать задачу и объяснять ее решение является неотчуждаемым естественным правом всякого, кто на это способен. В соответствии с этим текст (на русском языке) является свободно распространяемым. Адреса автора: shen@mccme.ru, shen@landau.ac.ru».

Теперь рассмотрим содержание книги внимательнее. В связи с повышенным интересом в мире к вопросам стандартизации образования книга А. Шеня представляет собой хороший пример семестрового курса введения в программирование для тех специальностей, которые предполагают творческое к нему отношение. В объеме семестрового курса, чему соответствуют 16 глав книги, автор рассматривает следующие задачи, которые уже имеют достаточный уровень формального представления.

Начинает он с главы, посвященной выполнению работы с переменными, выражениями, присваиваниями, когда рассматриваются задачи без массивов, с массивами и индуктивными функциями. Следующими задачами, предложенными автором для изучения, являются различные способы порождения комбинаторных объектов, среди которых размещения с повторениями, перестановки, подмножества, разбиения и ряд других подобных.

Далее внимание читателя останавливается на примерах обхода дерева и перебора с возвратами, в частности на программировании задач расположения на шахматной доске не бьющих друг друга ферзей и ряде других, относимых к обходу деревьев.

Важному классу проблем, возникающих при написании программ сортировки тех или иных объектов и использовании при этом разных алгоритмов, посвящена одна глава. В ней рассмотрены задачи на применение сортировок, количественных оценок операций при их выполнении и родственные сортировкам задачи.

Ряд глав книги включает задачи на обработку текстов, среди них — программирование работы с составными символами, комментариями и при вводе чисел, а также при сопоставлении с образцом.

Конечно, автор рассматривает, как программировать данные различных типов — стеки, очереди, множества, описывает различную организацию самих программ (с рекурсией и без нее), например, при обработке деревьев, порождении комбинаторных объектов и переборе, а кроме того, при использовании таблицы значений (динамическое программирование), стеков отложенных заданий или сложных случаев рекурсии.

Несколько глав книги посвящено программированию задач, обычно относимых к весьма популярным научно-практическим проблемам. Это программирование задач для различных алгоритмов на графах, например, поиска на них кратчайших путей, связных компонентов, а также глубины и ширины графов. Сюда же следует включить анализ игр и оптимальное кодирование информации.

Разумеется, при программировании часто приходится иметь дело с представлением множеств. Задачам, использующим для этого хеширование и представление множеств с помощью деревьев, в том числе сбалансированных, А. Шень также уделил внимание в книге.