ðòïçòáííéòï÷áîéå
ÔÅÏÒÅÍÙ É ÚÁÄÁÞÉ
Издание шестое, дополненное
Москва
Издательство МЦНМО
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
Последние комментарии
11 часов 13 минут назад
12 часов 8 минут назад
12 часов 11 минут назад
23 часов 2 минут назад
23 часов 4 минут назад
1 день 11 часов назад