ПРОГРАММИРОВАНИЕ: ТЕОРЕМЫ И ЗАДАЧИ


            НЕСКОЛЬКО ЗАМЕЧАНИЙ ВМЕСТО ПРЕДИСЛОВИЯ

Книга   написана  по  материалам  занятий  программированием  со
школьниками математических классов школы N 57.

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

Кто-то однажды сказал, что можно убедить в правильности алгорит-
ма, но не в правильности программы. Одна из целей книги -  попы-
таться продемонстрировать, что это не так.

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

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

Кажется, Хоар сказал, что эстетическая прелесть программы -  это
не архитектурное излишество, а то, что отличает в программирова-
нии успех от неудачи. Если, решая задачи из этой книги, читатель
почувствует  прелесть хорошо написанной программы, в которой "ни
убавить, ни прибавить", и сомнения в правильности которой кажут-
ся нелепыми, то автор будет считать свою цель достигнутой.

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

Уровень трудности задач и глав  весьма  различен.  Мы  старались
включить  как простые задачи, которые могут быть полезны для на-
чинающих, так и трудные задачи, которые могут посадить в лужу  и
сильного школьника. (Хоть и редко, но это бывает полезно.)

В качестве языка для записи программ был выбран паскаль  Паскаль
достачно прост и естествен, имеет неплохие реализации (например,
Turbo Pascal 3.0 и 5.0 фирмы Borland) и позволяет записать реше-
ния  всех  рассматриваемых  задач. Возможно, Модула-2 или Оберон
были бы более изящным выбором, но пока что они труднее доступны.

Неудачный опыт писания "популярных" учебников по  программирова-
нию учит: никакого сюсюканья! писать надо так, чтобы потом самим
было не стыдно прочесть.

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

Это не только и не столько учебник для школьника, сколько  спра-
вочник и задачник для преподавателя, готовящегося к занятию.

Об "авторских правах": право формулировать задачу и объяснять её
решение является неотчуждаемым естественным правом всякого,  кто
на это способен. В соответствии с этим текст (в ASCII и TeX-вер-
сиях)  является  свободно  распространяемыми. С ним можно делать
всё, что угодно, и если Вы внесли в него ошибки, не указав,  что
они  принадлежат  Вам, или использовали текст в коммерческих це-
лях, не поделившись прибылью - Бог Вам судья.

Благодарности. Я рад случаю поблагодарить всех, с кем имел честь
сотрудничать, преподавая программирование, особенно тех, кто был
"по другую сторону баррикады".