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


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

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

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

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

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

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

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

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

Стремясь  сделать  книгу  самодостаточной,  мы предваряем задачи
краткими  теоретическими сведениями (как в задачнике Б.П.Демидо-
вича).

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

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

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

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

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

---------------------------------------------------------------

Первое знакомство

+       Игра в Робота
+/-     Игрушечный функциональный язык
+/-     Схемы из функциональных элементов

Основы программирования

+       Переменные
+       Массивы
+       Индуктивные функции
+       Некоторые средства паскаля
+       Порождение комбинаторных объектов
+       Обход дерева. Перебор с возвратами
+       Сортировка
+       Рекурсия
+       Типы данных и их реализация
+       Устранение рекурсии. Динамическое программирование.
                Стеки, польская запись
+       Представление множеств: хеширование
+       Представление множеств: сбалансированные деревья
+/-     Графы. Кратчайшие пути. Минимальное остовное дерево.
               Поиск в глубину и ширину? Число связных компонент
               Форд - Фалкерсон и паросочетания
-/+     Конечные автоматы как средство спецификации и реализации
+       Алгоритмы сравнения с образцом
+/-     Контекстно-свободные языки. LL(1)-разбор
-/+     LR(1)-разбор
-/+     Геометрические алгоритмы
        Вероятностные алгоритмы

Отдельные сюжеты, которые стоит дописать
        порождение всех расстановок скобок, числа Каталана
        мат ферзем (или ладьей?) и неподвижным королем
        подпись в spelling checker
        определение стратегии в игре (дерево с min-max)
        предвычисление древесного порядка
        сток в графе за O(n) и поиск наибольшего