Предисловие

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

Данная книга предназначена для начального обучения студентов вузов программированию на языке Паскаль и базируется на опыте преподавания основного курса по программированию для студентов механико-математического факультета Новосибирского государственного университета (ММФ НГУ) [40, 41, 47, 48, 62, 67], который читается автором, начиная с 1975 г. Предварительное издание курса было осуществлено в 1999-2001 гг. виде трех учебных пособий НГУ [44-45]. Есть положительный опыт их использования в вузах, а также в школах с углубленным изучением математики и программирования.

Задачи начального обучения, составляющие основу данной книги, используются в НГУ во вводной части курса по программированию, нацеленной на овладение студентами навыками точного формулирования алгоритмов на языке высокого уровня и развитие у студентов алгоритмического мышления посредством упражнений в пошаговой разработке программ. Основные приемы и методы программирования изучаются по ходу рассмотрения языка Паскаль и с использованием системы Турбо Паскаль. При этом обучение общим методам ведется на многочисленных примерах и индивидуальных задачах разной степени сложности (гл. 1-7) и подкрепляется практикумом на ЭВМ, в процессе которого каждый студент должен решить пять индивидуальных заданий (гл. 8).

В основу курса положен принцип концентрического изложения материала. Предполагается, что с первых занятий студенты начинают упражняться в составлении программ, которые могут реально выполняться на доступных ЭВМ, и постепенно овладевают навыками разработки на языке Паскаль линейных, ветвящихся и итеративных алгоритмов, алгоритмов обработки структурированных данных и алгоритмов с процедурами и указателями. Также постепенно одновременно с расширением класса задач студенты углубляют свои знания о языке Паскаль.

К концу вводной части курса студенты овладевают основными конструкциями языка, образующими то естественно выделяемое его ядро для ``начального обучения'', которое условно можно назвать языком мини-Паскаль. В этом ядре нет ряда весьма важных возможностей языка Турбо Паскаль, таких как, например, поддержка объектно-ориентированного программирования, сужены средства языка Паскаль по структурированию данных и действий -- например, нет конструкторов типа множеств и файлов. Поэтому, хотя мини-Паскаль и содержит все необходимые сведения о языке Паскаль для построения программ начального обучения, он является лишь базой для изучения программирования на языке Паскаль. Отметим, что в мини-Паскале идентификаторы могут содержать наряду с латинскими буквами и буквы русского алфавита, хотя в большинстве существующих реализаций языка Паскаль (в том числе и в Турбо Паскале) использование русских букв разрешается только в комментариях и строках.

Следует отметить, что использование в качестве основы вводной части курса подмножества ``живого'' языка программирования на ММФ НГУ является традиционным. Первым использовалось подмножество языка Алгол-60, получившее название языка Минал [40]. Затем, когда в НГУ появились терминальные классы с диалоговым языком, являющимся вариантом языка Фортран, Минал был заменен языком мини-Фортран [67]. Что же касается языка мини-Паскаль, то он стал использоваться с момента появления в НГУ первой реализации языка Паскаль, тогда еще на машинах серии ЕС [62].

Книга содержит почти 4000 задач и состоит из восьми глав.

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

Главу завершает список заданий. Каждая из формулировок заданий представляет собой фактически схему для построения конкретных вариантов задания -- индивидуальных задач на программирование для всех студентов учебной группы. Эти варианты получаются в результате выбора подходящих частей текста, составляющего формулировку задания по значению параметра . Строки факультативных частей текста формулировок заданий напечатаны со смещением вправо и с указанием условий на , при которых соответствующие части должны включаться в формулировку конкретного варианта задания. При записи условий на используется следующее сокращение: вместо выражения mod <число> пишется просто <число>, так что большинство условий для формирования вариантов задания являются простыми логическими выражениями над и т.д. Например, 7-й вариант задания 1.2.3 следует читать так: ``Описать синтаксическую диаграмму, которая задает бесконечное множество всех таких идентификаторов , что начинается с последовательности букв нечетной длины, за которой следует цифра 7, а затем следует последовательность, не содержащая согласных букв, но содержащая четную цифру''.

Восьмая глава содержит индивидуальные задания различной сложности, ориентированные на приобретение навыка практического решения на ЭВМ задач, требующих разработки алгоритма, обработки сложных структур данных и разработки дружественного интерфейса. Каждое индивидуальное задание -- это самостоятельная, как правило, комбинаторная или логическая задача с краткой и четкой формулировкой, не содержащей описания алгоритма. Тематические задачи разбиты на пять разделов: графы и системы дорог; грамматики, языки и автоматы; формулы и программы; геометрия; игры. Большая часть главы -- это подробные рекомендации по выполнению разных видов работ, которые должен освоить студент, чтобы научиться создавать эффективные, наглядные и надежные программы решения нетривиальных задач на ЭВМ.

Нужно сказать, что хотя книга рассчитана на студентов младших курсов вузов, она может быть использовано в школе и для самостоятельного овладения начальными навыками конструирования алгоритмов на языке Паскаль. При составлении сборника автор стремился сделать изложение доступным для читателей, не обладающих специальными знаниями ни по математике, ни по программированию. Поэтому все необходимые для решения задач сведения по языку Паскаль включены в сборник, а условия большинства заданий и упражнений доступны для учащихся старших классов.

Тем, кто будет использовать сборник для самостоятельного изучения программирования и/или желает углубить свои знания по программированию, можно рекомендовать книги [1-79].

Фундаментальным вопросам конструирования корректных и эффективных программ с нетривиальными структурами данных и действий посвящен целый ряд монографий [1, 6 - 8, 11 - 16, 19 - 25, 29 - 34, 39, 42 - 46, 48, 51 - 59, 61, 53, 68, 69]. В книгах [1, 3, 5, 10, 12, 18, 28, 38, 47 - 49, 60, 64, 71, 72, 74, 78] содержится большое число упражнений и задач по программированию, снабженных рекомендациями по широкому кругу вопросов, касающихся стиля написания программ, рациональных методов их разработки и оптимизации, стратегии отладки и тестирования. Существует целый ряд книг [26, 35, 36, 50, 65, 70, 73, 75 - 77], предназначенных для начинающих пользователей, желающих работать с интегрированной пользовательской оболочкой (языком, редактором, компилятором, отладчиком) Турбо Паскаль, и содержащих большое количество простых и легко воспроизводимых примеров, а также полезных рекомендаций по программированию в среде Турбо Паскаль и описание языка Паскаль. Помимо книг по Турбо Паскалю можно указать немало книг [1, 2, 26, 41, 44, 79], также содержащих описание языка Паскаль, в том числе и книги [15, 16] известного швейцарского специалиста Н. Вирта -- автора языка Паскаль. Тем не менее они не могут служить учебником языка Паскаль -- для этого существует более подходящая книга [37].

Автор рад случаю поблагодарить всех, с кем имел честь сотрудничать при организации и проведении в НГУ курсов по программированию и практике на ЭВМ и при работе над данной книгой, в первую очередь профессора В.К. Сабельфельда и доцента М.Б. Трахтенброта. Особая благодарность академику А.П. Ершову и профессору Н. Вирту, во многом определившим взгляды автора на программирование и вопросы его преподавания.

Хочется закончить предисловие следующими словами Уинстона Черчилля: ``This is not the end. It is not even the beginning of the end. It is just the end of the beginning¹''. Счастливого Вам пути в большой мир информатики и программирования. Вы выбрали правильный курс.

Май 2001 г.

Проф. В. Н. Касьянов