Программирование: теоремы и задачи

Фрагменты предисловия

Книга написана по материалам занятий программированием со школьниками математических классов школы N57 г.Москвы и студентами младших курсов (Московский государственный университет, Независимый Московский университет).

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

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

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

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

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

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

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

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

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

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

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

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

Сказанное относится к русскому тексту; все права на переводы переданы издательству Birkhauser.

При подготовке текста использовалась (свободно распространяемая) версия LaTeXа, включающая стилевые файлы, составленные С.М.Львовским, а также самодельные Metafont-шрифты, срисованные с образцов типа «таймс».

Благодарности. Я рад случаю поблагодарить всех, с кем имел честь сотрудничать, преподавая программирование, особенно тех, кто был «по другую сторону баррикады», а также всех приславших мне замечания и исправления (специальная благодарность — Ю.В.Матиясевичу).

Благодарю также Американское математическое общество (фонд помощи бывшему СССР), Международный научный фонд, университет г.Бордо и фонд «Культурная инициатива» за полученные во время подготовки этой книги деньги.


Не покупайте эту книгу!

Обращение автора к потенциальным покупателям
В этой книге ничего не говорится об особенностях BIOSа, DOSа, OSа, GEMа и Windows, представляющих основную сложность при настоящем программировании.

В ней нет ни слова об объектно-ориентированном программировании, открывшем новую эпоху в построении дружественных и эффективных программных систем.

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

Не рассказано в ней и о написании резидентных программ, тонкости взаимодействия которых должен знать каждый.

Искусственный интеллект, открывший новые рынки сбыта для программного обеспечения, обойден презрительным молчанием.

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

Логическое программирование, постепенно вытесняющее устаревший операторный стиль программирования, не затронуто.

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

Проблемы отладки и сопровождения программ, занимающие, по общему мнению профессионалов, 90% в программировании, игнорируются.

В книге используются лишь самые элементарные возможности паскаля. Обширные возможности, предоставляемые современными интегрированными программными средами, остаются невостребованными. (Не говоря уже о том, что паскаль вообще устарел, вытесненный С/C++)

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

Короче говоря, покупать эту книгу глупо — особенно теперь, когда выходит столько переводных руководств, написанных в цивилизованных странах настоящими профессионалами.


Оглавление

1. Переменные, выражения, присваивания
1.1.  Задачи без массивов
1.2.  Массивы
1.3.  Индуктивные функции (по А.Г.Кушниренко)
2. Порождение комбинаторных объектов
2.1.  Размещения с повторениями
2.2.  Перестановки
2.3.  Подмножества
2.4.  Разбиения
2.5.  Коды Грея и аналогичные задачи
2.6.  Несколько замечаний
2.7.  Подсчет количеств
3. Обход дерева. Перебор с возвратами
3.1.  Ферзи, не бьющие друг друга: обход дерева позиций
3.2.  Обход дерева в других задачах
4. Сортировка
4.1.  Квадратичные алгоритмы
4.2.  Алгоритмы порядка n*log(n)
4.3.  Применения сортировки
4.4.  Нижние оценки для числа сравнений при сортировке
4.5.  Родственные сортировке задачи
5. Конечные автоматы и обработка текстов
5.1.  Составные символы, комментарии и т.п.
5.2.  Ввод чисел
6. Типы данных
6.1.  Стеки
6.2.  Очереди
6.3.  Множества
6.4.  Разные задачи
7. Рекурсия
7.1.  Примеры рекурсивных программ
7.2.  Рекурсивная обработка деревьев
7.3.  Порождение комбинаторных объектов, перебор
7.4.  Другие применения рекурсии
8. Как обойтись без рекурсии
8.1.  Таблица значений (динамическое программирование)
8.2.  Стек отложенных заданий
8.3.  Более сложные случаи рекурсии
9. Разные алгоритмы на графах
9.1.  Кратчайшие пути
9.2.  Связные компоненты, поиск в глубину и ширину
10. Сопоставление с образцом
10.1.  Простейший пример
10.2.  Повторения в образце — источник проблем
10.3.  Вспомогательные утверждения
10.4.  Алгоритм Кнута-Морриса-Пратта
10.5.  Алгоритм Бойера-Мура
10.6.  Алгоритм Рабина
10.7.  Более сложные образцы и автоматы
11. Представление множеств. Хеширование
11.1.  Хеширование с открытой адресацией
11.2.  Хеширование со списками
12. Представление множеств. Деревья. Сбалансированные деревья
12.1.  Представление множеств с помощью деревьев
12.2.  Сбалансированные деревья
13. Контекстно-свободные грамматики
13.1.  Общий алгоритм разбора
13.2.  Метод рекурсивного спуска
13.3.  Алгоритм разбора для LL(1)-грамматик
14. Синтаксический разбор слева направо (LR)
14.1.  LR-процессы
14.2.  LR(0)-грамматики
14.3.  SLR(1)-грамматики
14.4.  LR(1)-грамматики, LALR(1)-грамматики
14.5.  Общие замечания о разных методах разбора

© 2015 Sofarider Inc. All rights reserved. WordPress theme by Dameer DJ.