ПРОГРАММИРОВАНИЕ: ТЕОРЕМЫ И ЗАДАЧИ
Содержание:
НЕСКОЛЬКО ЗАМЕЧАНИЙ ВМЕСТО ПРЕДИСЛОВИЯ
Глава 1. Переменные, выражения, присваивания.
1.3. Индуктивные функции (по А.Г.Кушниренко).
Глава 2. Порождение комбинаторных объектов.
2.1. Размещения с повторениями.
2.5. Коды Грея и аналогичные задачи.
Глава 3. Обход дерева. Перебор с возвратами.
3.1. Ферзи, не бьющие друг друга: обход дерева позиций
3.2. Обход дерева в других задачах.
4.2. Алгоритмы порядка n log n.
4.4. Нижние оценки для числа сравнений при сортировке.
4.5. Родственные сортировке задачи.
Глава 5. Конечные автоматы в задачах обработки текстов
5.1. Составные символы, комментарии и т.п.
7.1. Примеры рекурсивных программ.
7.2. Рекурсивная обработка деревьев
7.3. Порождение комбинаторных объектов, перебор
7.4. Другие применения рекурсии
Глава 8. Как обойтись без рекурсии.
8.1. Таблица значений (динамическое программирование)
8.3. Более сложные случаи рекурсии.
Глава 9. Разные алгоритмы на графах
9.2. Связные компоненты, поиск в глубину и ширину
Глава 10. Сопоставление с образцом.
10.2. Повторения в образце - источник проблем.
10.3. Вспомогательные утверждения
10.4. Алгоритм Кнута - Морриса - Пратта
10.7. Более сложные образцы и автоматы
Глава 11. Представление множеств. Хеширование.
11.1. Хеширование с открытой адресацией
Глава 12. Множества и деревья.
12.1. Представление множеств с помощью деревьев.
12.2. Сбалансированные деревья.
Глава 13. Контекстно-свободные грамматики.
13.1. Контекстно-свободные грамматики. Общий алгоритм разбора.
13.2. Метод рекурсивного спуска.
13.3. Алгоритм разбора для LL(1)-грамматик.
Глава 14. Синтаксический разбор слева направо (LR)
14.4. LR(1)-грамматики, LALR(1)-грамматики
14.5. Общие замечания о разных методах разбора.
(Предупреждение автора)
В этой книге ничего не говорится об особенностях BIOSа, DOSа, OSа, GEMа и Windows, представляющих основную сложность при настоящем программировании.
В ней нет ни слова об объектно-ориентированном программировании, открывшем новую эпоху в построении дружественных и эффективных программных систем.
Из нее Вы не узнаете о графических возможностях компьютера, без которых немыслимо современное программирование, о богатстве и разнообразии мира видеоадаптеров.
Не рассказано в ней и о написании резидентных программ, тонкости взаимодействия которых должен знать каждый.
Искусственный интеллект, открывший новые рынки сбыта для программного обеспечения, обойден презрительным молчанием.
Экспертные системы, которые в скором будущем займут место на рабочем столе каждого, даже не упоминаются.
Логическое программирование, постепенно вытесняющее устаревший операторный стиль программирования, не затронуто.
Драматический поворот от баз данных к базам знаний, вызвавший в жизни новую профессию -- инженер знаний -- остался незамеченным автором.
Проблемы отладки и сопровождения программ, занимающие, по общему мнению профессионалов, 90% в программировании, игнорируются.
В книге используются лишь самые элементарные возможностипаскаля. Обширные возможности, предоставляемые современными интегрированными программными средами, остаются невостребованными. (Не говоря уже о том, что паскаль уже вообще устарел, вытесненный языком Си.)
Игрушечные головоломки, которым посвящена книга, никому не нужны. Если же перед Вами встанет действительно важная задача, неужели Вы не справитесь с ней сами, без непрошеных учителей и советчиков?
Короче говоря, покупать эту книгу глупо - особенно теперь, когда выходит столько переводных руководств, написанных в цивилизованных странах настоящими профессионалами.
Книга написана по материалам занятий программированием со школьниками математических классов школы N 57. Книга написана в убеждении, что программирование имеет свой предмет, не сводящийся ни к конкретным языкам и системам, ни к методам построения быстрых алгоритмов. Кто-то однажды сказал, что можно убедить в правильности алгоритма, но не в правильности программы. Одна из целей книги - попытаться продемонстрировать, что это не так.
В принципе, возможность практического исполнения программ не является непременным условием изучения программирования. Однако она является сильнейшим стимулом - без такого стимула вряд ли у кого хватит интереса и терпения.
Выбранный жанр книги по необходимости ограничивает ее "программированием в малом", оставляя в стороне необходимую часть программистского образования - работу по модификации больших прог-
рамм. Автор продолжает мечтать о наборе учебных программных систем эталонного качества, доступных для модификации школьниками.
Кажется, Хоар сказал, что эстетическая прелесть программы - это не архитектурное излишество, а то, что отличает в программировании успех от неудачи. Если, решая задачи из этой книги, читатель почувствует прелесть хорошо написанной программы, в которой "ни убавить, ни прибавить", и сомнения в правильности которой кажутся нелепыми, то автор будет считать свою цель достигнутой.
Характер глав различен: в одних предлагается набор мало связанных друг с другом задач с решениями, в других по существу излагается один-единственный алгоритм. Темы глав во многом пересекаются, и мы предпочли кое-какие повторения формальным ссылкам.
Уровень трудности задач и глав весьма различен. Мы старались включить как простые задачи, которые могут быть полезны для начинающих, так и трудные задачи, которые могут посадить в лужу и сильного школьника. (Хоть и редко, но это бывает полезно.)
В качестве языка для записи программ был выбран паскаль Паскаль достачно прост и естествен, имеет неплохие реализации (например, Turbo Pascal 3.0 и 5.0 фирмы Borland) и позволяет записать решения всех рассматриваемых задач. Возможно, Модула-2 или Оберон были бы более изящным выбором, но пока что они труднее доступны.
Неудачный опыт писания "популярных" учебников по программированию учит: никакого сюсюканья! писать надо так, чтобы потом самим было не стыдно прочесть.
Практически все задачи и алгоритмы, разумеется, не являются новыми. (В некоторых редких случаях приведены ссылки на конкретную книгу или конкретного человека. См. также список книг для дальнейшего чтения.) Вместе с тем мы надеемся, что в некоторых случаях алгоритмы (и особенно доказательства) изложены более коротко и отчетливо.
Это не только и не столько учебник для школьника, сколько справочник и задачник для преподавателя, готовящегося к занятию.
Об "авторских правах": право формулировать задачу и объяснять её решение является неотчуждаемым естественным правом всякого, кто на это способен. В соответствии с этим текст (в ASCII и TeX-версиях) является свободно распространяемыми. С ним можно делать всё, что угодно, и если Вы внесли в него ошибки, не указав, что они принадлежат Вам, или использовали текст в коммерческих целях, не поделившись прибылью - Бог Вам судья.
Благодарности. Я рад случаю поблагодарить всех, с кем имел честь сотрудничать, преподавая программирование, особенно тех, кто был "по другую сторону баррикады".