Этюды для программистов

Уэзерелл Чарлз

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

Для всех, кто преподает и изучает программирование.

А вы ноктюрн сыграть могли бы?

или Предисловие редактора перевода

Своим внешним видом новый суперкомпьютер CRAY-1 мало похож на привычную всем нам вычислительную машину. Это круглый диван с высокой спинкой и мягкими кожаными сиденьями. До предела набитый электроникой, самый дорогой в мире «диванчик» вправе претендовать на включение в «Книгу рекордов Гиннеса». Но, конечно, дело не в форме, а в содержании. Машина выполняет сотни миллионов операций в секунду, и разговор о миллиардах операций уже не воспринимается как лишенная здравого смысла фантазия.

А как изменилось программирование! Никого теперь не удивить программой из одной-двух тысяч команд, когда счет идет на мегабайты. Операционные системы, разного рода АСУ — поистине монументальные произведения, настоящие симфонии из мириад нулей и единиц. И в такой симфонии не должно прозвучать ни одной фальшивой ноты, а ведь пишут ее порой сотни людей — программирование становится массовой профессией.

Как же в этих новых условиях учить и как учиться программировать? Существуют, конечно, задачники по программированию, в которых в достатке найдется примеров-миниатюр. Но, написав программу для вычисления квадратного корня, можно ли браться за разработку компилятора? Уготовано ли блестящее музыкальное будущее тому, кто преодолел только гаммы и сольфеджио?

В 1978 г. издательство «Мир» выпустило два учебных пособия по программированию (Ламуатье Ж.-П. Упражнения по программированию на Фортране IV; Дрейфус М., Ганглоф К. Практика программирования на Фортране), совершенно не похожих на прежние задачники. В них демонстрируется работа над небольшими программами с подробным обсуждением всех этапов работы. Книги оказались чрезвычайно полезными для начального обучения и в ряде вузов были немедленно использованы в учебном процессе. Но как далек еще путь от камерной пьесы к симфонии!

Книга Ч. Уэзерелла призвана заполнить еще одну «экологическую нишу» в учебной литературе по программированию. В книге в живой и увлекательной форме ставится 27 вполне реальных (или близких к реальным) задач-этюдов. Напомним, как определяется этюд в энциклопедическом словаре: «Этюд — музыкальная пьеса, основанная на определенном приеме исполнения и предназначенная для развития технического мастерства исполнителя. Создаются и высокохудожественные виртуозные сочинения этого жанра, предназначенные для концертного исполнения (фортепианные этюды Ф. Листа, Ф. Шопена, Р. Шумана и др.)». Действительно, почти каждый представленный здесь этюд несет в себе свою «изюминку»: структуры данных или управляющие структуры, обработку текстов или рекурсию… И почти каждый из них может служить заданием для курсовой работы. Есть, однако, столь «высокохудожественные» этюды (компилятор для алгебраического языка или интерпретатор-макропроцессор), что не всякий преподаватель осмелится предложить их даже в качестве дипломной работы.

Предисловие

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

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

В наши дни начинающему программисту уже не нужно семь лет

[1]

вытряхивать отходы от пробивки перфокарт, скапливающиеся в перфорирующих устройствах — необходимые технические знания ему проще получить, посещая лекции и изучая литературу. Теперь нет никакой надобности, заглядывая через плечо опытного программиста, изо дня в день наблюдать за его работой. А вот на то, чтобы набить руку на выполнении реальных программистских задач, усвоить и закрепить основные методы и принципы работы, просто для практики, наконец, действительно нужно время. Ясно, что, прочитав несколько книг по столярному делу, нельзя сразу взять и произвести на свет что-нибудь изящное в стиле Чиппендейла

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

Разнообразие предлагаемых композиций весьма велико. Некоторые этюды требуют прежде всего интеллектуальных усилий (гл. 9), у других основная трудность заключена в реализации (гл. 12); есть совсем короткие этюды (гл. 16) и, напротив, очень длинные (гл. 6); в некоторых используются широкоизвестные методы реализации (гл. 5), в других же (гл. 2) методы реализации можно непрерывно совершенствовать. Главы 25–28 образуют связный цикл, который можно включить в курсы по языкам программирования и системам. Для выполнения этих этюдов нужно подобрать группы студентов, обладающих необходимыми знаниями по системному программированию (как правило, раньше студенты и не подозревали, что работа в группе программистов — совсем не то же самое, что работа в одиночку). Главы 5, 6, 13, 17, 19 и 25 могут дать хороший материал для курса по моделированию на ЭВМ, а гл. 6, 11, 14, 19, 20 связаны с задачами искусственного интеллекта. Разумеется, широко представлены также традиционные задачи по информатике.