Программирование: теоремы и задачи [Александр Ханиевич Шень] (pdf) читать постранично

А. ШЕНЬ

ðòïçòáííéòï÷áîéå
ÔÅÏÒÅÍÙ É ÚÁÄÁÞÉ
Издание шестое, дополненное

Москва

Издательство МЦНМО

2017

УДК 519.671
ББК 22.18
Ш47

Ш47

Шень А.

Программирование: теоремы и задачи. | 6-е изд., дополненное. | М.: МЦНМО, 2017. | 320 с.: ил.
ISBN 978-5-4439-0685-0
Книга содержит задачи по программированию различной трудности.
Большинство задач приводятся с решениями. Цель книги | научить основным методам построения корректных и быстрых алгоритмов.
Для учителей информатики, старшеклассников, студентов младших курсов высших учебных заведений. Пособие может быть использовано на кружковых и факультативных занятиях в общеобразовательных учреждениях, в
школах с углублённым изучением математики и информатики, а также в
иных целях, не противоречащих законодательству РФ.
Предыдущее издание книги вышло в 2014 г.

ББК 22.18

ISBN 978-5-4439-0685-0

c
○

А. Шень, 1995, 2017

Несколько замечаний вместо предисловия
Книга написана по материалам занятий программированием со
школьниками математических классов школы Ђ 57 г. Москвы
и студентами младших курсов (Московский государственный
университет, Независимый московский университет, университет
г. Uppsala, Швеция ).
Книга написана в убеждении, что программирование имеет свой предмет,
не сводящийся ни к конкретным языкам и системам, ни к методам
построения быстрых алгоритмов.
Кто-то однажды сказал, что можно убедить в правильности алгоритма,
но не в правильности программы. Одна из целей книги | попытаться
продемонстрировать, что это не так.
В принципе, возможность практического исполнения программ не
является непременным условием изучения программирования. Однако она
является сильнейшим стимулом | без такого стимула вряд ли у кого
хватит интереса и терпения.
Выбранный жанр книги по необходимости ограничивает её
«программированием в малом», оставляя в стороне необходимую часть
программистского образования | работу по модификации больших
программ. Автор продолжает мечтать о наборе учебных программных
систем эталонного качества, доступных для модификации школьниками.
Кажется, Хоар сказал, что эстетическая прелесть программы | это не
архитектурное излишество, а то, что отличает в программировании
успех от неудачи. Если, решая задачи из этой книги, читатель
почувствует прелесть хорошо написанной программы, в которой «ни
убавить, ни прибавить», и сомнения в правильности которой кажутся
нелепыми, то автор будет считать свою цель достигнутой.
Характер глав различен: в одних предлагается набор мало связанных друг
с другом задач с решениями, в других по существу излагается
один-единственный алгоритм. Темы глав во многом пересекаются, и мы
предпочли кое-какие повторения формальным ссылкам.
Уровень трудности задач и глав весьма различен. Мы старались
включить как простые задачи, которые могут быть полезны для
начинающих, так и трудные задачи, которые могут посадить в лужу
сильного школьника. (Хоть и редко, но это бывает полезно.)

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

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

(и особенно доказательства ) изложены более коротко и отчётливо.

Это не только и не столько учебник для школьника, сколько справочник
и задачник для преподавателя, готовящегося к занятию.
Об «авторских правах»: право формулировать задачу и объяснять её
решение является неотчуждаемым естественным правом всякого, кто на
это способен. В соответствии с этим текст является свободно
распространяемым. Адреса автора: shen@mccme.ru, sasha.shen@gmail.com,
alexander.shen@lirmm.fr. Сказанное относится к русскому тексту; все
права на переводы переданы издательству Springer.
При подготовке текста использовалась (свободно распространяемая )
версия LATEXа, включающая стилевые файлы, составленные
С. М. Львовским (см. ftp://ftp.mccme.ru/pub/tex/).
Я рад случаю поблагодарить всех, с кем имел честь сотрудничать, преподавая программирование, особенно тех, кто был «по другую сторону баррикады», а также всех приславших мне замечания и исправления

(специаль-

ная благодарность | Ю. В. Матиясевичу ). Автор благодарит В. Шувалова
за хлопоты по вёрстке, а также издательство МЦНМО. Благодарю также Институт проблем передачи информации РАН, Американское матема-

(фонд помощи бывшему СССР ), фонд Сороса, универ(Швеция ),
CNRS (Франция ), Ecole Normale (Лион, Франция ), LIF (Марсель, Франция ),
LIRMM