Данный номер составлен из фрагментов книги

Столяр С.Е., Владыкин А.А.

Информатика: Представление данных и алгоритмы. — СПб.: Невский Диалект. М.: БИНОМ. Лаборатория знаний,

2007.— 382 с.: ил.

Оглавление книги

Разделы, вошедшие в номер, выделены

Предисловие

A. Введение в алгоритмику

A1. Алгоритмы: терминология, свойства, запись

A2. Оценка эффективности алгоритма

A3. Конструирование алгоритмов

A4. От алгоритма к структуре данных

A5. От структуры данных к алгоритму

A6. Алгоритмы обмена

B. Компьютерная арифметика

B1. Системы счисления

B2. Системы счисления и операции

B3. Двоичная арифметика

B4. Логические операции

B5. Целочисленная и вещественная арифметика

B6. Механизм маскирования и возведение в степень

B7. Перевод чисел в различные нумерации

C. Структуры данных и операции

C1. Порядки

C2. Информационно-поисковый язык: пример

C3. Словари

C4. Классификации

C5. Деревья

C6. Деревья поиска

D. Массивы

D1. Размещение массивов и доступ к элементам

D2. Последовательный просмотр вектора

D3. Дихотомия и другие эффективные алгоритмы

D4. Циклические перестановки

D5. Простые обменные сортировки вектора

D6. Сортировки обменом «на расстоянии»

D7. k-й максимум. Сортировки вставками

D8. Сортировки слиянием

D9. Распределяющая сортировка. Устойчивость

D10. Обработка двумерных массивов

E. Динамические структуры

E1. Динамическое программирование

E2. Примеры задач

E3. Стек и стековые операции

E4. Стековая арифметика

E5. Использование нескольких стеков

E6. Рекурсия: сплошные недостатки?

E7. Рекурсия: реабилитация

E8. Хеширование

F. Коды и сжатие данных

F1. Общие сведения

F2. Исключение избыточных элементов данных

F3. n-разрядное кодирование. Код Морзе

F4. Коды переменной длины

F5. Код Хаффмена

Указания и решения

Список литературы

Указатель алгоритмов

Алфавитный указатель

Предисловие к номеру газеты

Вы это читаете. Значит, неожиданное предложение С.Л. Островского реализовалось.

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

Смею заверить, второй вариант пока что неактуален. Что до первого, то версия “забытого” учебника не подтверждается приводимыми выходными данными: издательский тираж выпущен всего-то пару лет назад. Но, возможно, — на что ранее намекнул Сергей Львович (“Информатика”, № 3/2009), — нас просто “не заметили”. Коли так, ничего удивительного: тиражная политика издательств осторожна, чужие денежки счет любят. Разошелся ли в итоге трехтысячный тираж полностью, мне трудно судить. Во всяком случае, в моем родном городе на магазинных полках означенной книги не видно.

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

Прошу не судить строго авторов за возможные полиграфические ляпы. Скорее всего они возникли как последствия технически нетривиального перегона материалов книги в новый (газетный) вид. Но некоторые ошибки могут быть унаследованы из книги. Поэтому стоит заглянуть на web-страницу http://rain.ifmo.ru/cat/view.php/books/seva-2007/errata, где вы найдете их перечень. Кстати, рекомендую коллегам воспользоваться размещенными на том же сайте визуализаторами алгоритмов, частично относящимися к тематике книги.

Ваши отзывы и замечания приму с интересом и благодарностью. Не исключено, что нынешняя публикация подтолкнет нашего издателя к выпуску дополнительного тиража или нового издания. Пишите в раздел http://rain.ifmo.ru/cat/view.php/feedback на том же сайте, где сообщения предварительно просматриваются и для всеобщего обозрения не появятся.

С.Е. Столяр

Предисловие к книге

Ральфу

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

П.Г. Вудхауз¹

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

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

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

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

Несколько позднее, в первой половине 90-х гг., ситуация с машинным временем стабилизировалась, нас перестали гонять из класса в класс. В итоге мы оказались соседями с “конкурирующей” физико-технической школой. Однажды во время перерыва мы с коллегами из той школы С.В. Богдановым и А.В. Юриным делились наболевшим, обсуждая состояние дел в школьной информатике. Сошлись в том, что алгоритмическую часть курса, приоритетную по нашему мнению, надо существенно расширять вопреки официальным документам того времени².

Мы договорились документально сравнить собственные учебные программы. Через неделю, увидев многостраничные таблицы моего тематического плана, коллеги-соседи переглянулись, куда-то спрятали собственный одностраничный трактат и взялись за содержание моего. Еще спустя неделю они предложили добавить в мой план несколько полезных тем, далее дописать к “готовому оглавлению” содержательный текст и в завершение издать учебник.

Идея не казалась пустой, ведь учебников информатики, которые бы нас устраивали, в то время действительно не было. Однако техническая реализация представлялась столь трудоемкой, что тогда я за нее не взялся. И правильно сделал: сейчас-то знаю, что круг охваченных в тогдашнем плане тем был заметно yже нынешнего. Позднее тот же АВЮ иногда привлекал меня к внутриредакционному рецензированию рукописей, которые поступали в издаваемый им журнал “Пролог”. Читая эти работы и обнаруживая в них множество ляпов, я лишний раз убеждался, как рискован авторский труд.

Относительно той учебной программы должен сознаться: качеством ее проработки обязан был Т.Г. Осиповой. Именно ТГО впервые объяснила мне, что в школе принято более тщательное тематическое планирование, чем казалось поначалу мне самому, да и обоим нашим коллегам, равно не отягощенным специальным педагогическим образованием. Сейчас мне приятно отметить, что около десяти лет я имел возможность совместно с ТГО вести общие классы и, само собой, беззастенчиво перекладывать на нее значительную часть работы, в том числе написание подобных планов. Кажется, наше сотрудничество вполне устраивало и окружающих: иногда потенциальные кандидаты на итоговый “неуд” сбегали из моей группы, находя приют в параллельной группе с молчаливого согласия администрации.

Еще в начале 1990-х гг. В.Г. Парфенов стал проводить в физико-математических школах нашего города осеннюю агитационную кампанию в целях отбора потенциальных абитуриентов для кафедры компьютерных технологий ИТМО. Заметив успехи наших учеников, в 1996 г. он пригласил меня читать отобранным кандидатам предварительный, установочный курс алгоритмики³. Спустя год я продолжил начатую работу уже со студентами, еще через год курс был легализован как двухгодичный.

В 1998 г. по предложению ВГП мы организовали так называемую “Интернет-школу программирования”, призванную вести посредством электронной почты обучение школьников в рамках нашей программы. “Педагогический коллектив” состоял из трех человек. Я писал тексты высылаемых “Уроков”, М.А. Казаков готовил задачи и обеспечивал необходимую техническую поддержку, включая автоматизированную проверку присылаемых решений, организационно-методическую помощь в ведении переписки осуществляла ТГО. Меня ВГП именовал, для пущей солидности проекта, не иначе как “директором” интернет-школы. В таком составе и при такой организации проект существовал 2 учебных года. График рассылки, а значит, и подготовки очередных уроков был довольно жесткий, я едва успевал. К счастью, выручили коллеги, написавшие несколько уроков (не нашедших отражения в настоящей книге).

Второй раз предложение писать учебник инициировал ВГП, озабоченный не только довузовской подготовкой абитуриентов, но и выстраиванием стройной системы “выращивания олимпиадных бойцов”. Согласно далеко идущим планам речь шла об учебнике сквозного содержания для старшеклассников и студентов. Авторами он “назначил” меня и Р.А. Елизарова, занятого в то время подготовкой студенческой команды к соревнованиям АСМ. Поначалу мы с энтузиазмом взялись за дело, пару месяцев согласовывали содержание и оглавление будущей, очень толстой книги, но потом основные занятия отвлекли РАЕ. Я еще некоторое время размышлял над содержанием книги, примерял к оглавлению готовые тексты из занятий интернет-школы, “сдабривая” их исходниками от МАКа, но текущие дела затянули в свой водоворот, и на том книжная затея закончилась. Однако пользу для своего курса я все-таки извлек, добавив в него несколько новых тем, отмеченных вниманием РАЕ.

В 2000 г. вариант с электронной перепиской в рамках нашей интернет-школы уступил место более современной технологии с использованием сайта, и мы с МАКом с головой ушли в этот WWW-проект. Для сайтовой версии курса я подготовил развернутое оглавление, учтя опыт обсуждений предыдущего проекта. Главы курса нумеровались буквами латиницы, диапазона которой едва хватило, разделы внутри глав сохранили название “урок”. Я занялся обновлением прежних текстов и подготовкой новых, нанятые ВГП студенты перегоняли их в HTML-формат, бессовестно плодя разнообразные баги.

Обнаружив в собственном оглавлении отсутствие важной главы, с просьбой написать ее я обратился к И.В. Романовскому. Встречное предложение уважаемого профессора подготовить совместный текст было неожиданным: я с трудом представлял, как работали прежде Ильф с Петровым или братья Стругацкие. Однако процесс оказался как результативным, так и поучительным: благодаря соавтору я приобрел интерес к языку PostScript, а впоследствии ИВР повернул меня лицом к ТЕХу.

Легко догадаться, что упомянутая должность “директора” была явно виртуальной. Чтобы как-то соответствовать ей, во время летнего ремонта я стащил в родной школе одноименную табличку и водрузил ее на полку рядом с рабочим столом. Спустя время проект интернет-школы разросся, одновременно сменив WWW-дислокацию, к нему стали присоединять(ся) другие учебные курсы, и возник целый управленческий аппарат с неясными функциями. Постепенно я потерял интерес к проекту, так и оставив пол-алфавита латиницы незадействованным. Но та табличка сохранилась и стоит на прежнем месте как напоминание о моей неудачной административной карьере!

Очередным проектом, рожденным ВГП при поддержке журнала “Компьютерные инструменты в образовании”, стала подготовка серии учебных брошюр, дублирующих главы моего сайтового курса. Вновь ревизии пришлось подвергнуть его тексты, по-прежнему казавшиеся мне весьма сырыми. Так или иначе, но в 2002 г. одна за другой были изданы 7 книжек (в том числе 2 — совместно с ИВР [40]), которые позднее легли в основу этой книги. Помню, как удивило и позабавило неожиданное оформление тех книжек: художник поселил в них целое семейство ежей, с невиданной плодовитостью размножавшихся по всем страницам. Теперь стараюсь согласовывать с издателем подобные вопросы.

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

Итак, примерно в 2003 г. я наконец созрел, чтобы взяться за сведение готовых фрагментов книги в одно целое, останавливала только перспектива вновь вычитывать и связывать надоевшие автору собственные тексты. По счастью, в начале следующего года А.А. Владыкин, активно занимавшийся тем временем созданием нашего сайта⁵ в поддержку учебного курса в ИТМО, согласился взять на себя и эту работу. Его задачей стал перевод в ТеХовский формат тех самых книжек и пополнение набора упражнений. Однако он этим не ограничился, а попутно устранил множество недочетов и нестыковок в моих текстах, заново, по-своему, переписал все имевшиеся исходники, добавил ряд новых примеров, полностью подготовил раздел “Указания и решения” и, наконец, написал разделы Е1, Е2, Е8. Кто, кроме соавтора, способен на такой титанический труд!

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

Стоит сказать несколько слов о списке литературы, вызвавшем нарекания нашего редактора О.М. Рощиненко. Предложение ОМР состояло в разбиении этого списка на три тематически однородных. Я же отстаивал единство перечня, не видя четких критериев для разграничения. Кроме того, любимые школьными методистами “межпредметные связи” иногда вполне актуальны, зачем их специально разрывать? Кто “победил” в нашем споре, смотрите сами.

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

Впрочем, есть и обратная сторона медали: ручная верстка всегда грозит появлением новых опечаток. Поскольку наши с ААВ огрехи редактор и корректор благополучно устранили, то все претензии пытливого читателя, особенно к программному коду, авторы решительно отказываются принимать на свой счет. Все же не сочтите за труд сообщать о них через сайтовую страницу книги http: / /rain. ifmo.ru/cat/view.php/books/seva-2007, содействуя тем самым пополнению публикуемого там перечня.

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

Хочу также отметить вклад многих своих школьников и студентов: их замечания и вопросы неоднократно провоцировали расширение курса.

Множество замечаний и прерываний, когда я просиживал за компьютером, набирая эти тексты, исходили от Ольги и Темы. Оба по разным причинам не считали эту работу столь важной, чтобы забывать о времени обеда. И если жена руководствовалась, пожалуй, моими интересами, то кот, подозреваю, больше заботился о своих. В любом случае, благодарю их за актуальные прерывания. И, разумеется, Ральфа: он не мешал никогда и водил меня на прогулку.

С.Столяр

Июль 2006 г.,
Санкт-Петербург

Вовсе не легко отыскать книгу, которая научила нас столь же многому, как книга, написанная нами самими.

Ф.Ницше⁶

---

1 См. [53, c. 6].

2 Удивительно, но и сейчас мало что изменилось: достаточно познакомиться с содержанием тестов ЕГЭ, чтобы понять, каким разделам информатики отдается предпочтение.

3 Такой курс я читаю до сих пор, время от времени слегка его пополняя. См. http://rain.ifmo.ru/cat/view.php/entrants/.

4 Если кому-то интересно, то нынешнее его содержание доступно на странице http://www.school.ioffe.ru/lessons/subjects/programming/ школьного сайта.

5 http://rain.ifmo.ru/cat.

6 См. [65, с. 749].