Введение в программирование и структуры данных

Кати Фислер, Шрирам Кришнамурти,  
Бенджамин С. Лернер, Джо Гиббс Политц

Введение в программирование  
и структуры данных

Kathi Fisler,  
Shriram Krishnamurthi,  
Benjamin S. Lerner,  
Joe Gibbs Politz

A Data-Centric 
Introduction  
to Computing

Кати Фислер,  
Шрирам Кришнамурти,  
Бенджамин С. Лернер,  
Джо Гиббс Политц

Введение  
в программирование  
и структуры данных

Москва, 2022

УДК 004.6
ББК 32.972
Ф63

Фислер К., Кришнамурти Ш., Лернер Б. С., Политц Дж. Г.
Ф63  Введение в программирование и структуры данных / пер. с англ. А. В. Снастина. – М.: ДМК Пресс, 2022. – 440 с.: ил. 

ISBN 978-5-93700-137-5

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

УДК 004.6
ББК 32.972

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

 
©  Kathi Fisler, Shriram Krishnamurthi, 
Benjamin S. Lerner, Joe Gibbs Politz, 2022
ISBN 978­5­93700­137­5 (рус.)  
©  Перевод, оформление, издание,  
ДМК Пресс, 2022

Содержание

От издательства ......................................................................................................13

Об авторах ................................................................................................................14

Часть I. ВВЕДЕНИЕ ...............................................................................................17

Глава 1. Предисловие ............................................................................................18
1.1. О чем эта книга .....................................................................................................18
1.2. Основополагающие принципы, определяющие содержание этой книги ........18
1.3. Наш взгляд на данные ..........................................................................................19
1.4. Что делает эту книгу особенной ...........................................................................20
1.5. Для кого предназначена эта книга ......................................................................21
1.6. Структура книги ....................................................................................................21
1.7. Организация материала книги.............................................................................22
1.8. Наш выбор языка программирования ................................................................24
1.9. Обратная связь, сообщения об ошибках и комментарии ..................................25

Глава 2. Благодарности .........................................................................................26

Часть II. ОСНОВЫ ..................................................................................................28

Глава 3. Начинаем работу ....................................................................................29
3.1. Поясняющий пример: флаги ................................................................................29
3.2. Числа ......................................................................................................................30
3.3. Выражения .............................................................................................................32
3.4. Терминология ........................................................................................................33
3.5. Строки ....................................................................................................................33
3.6. Изображения .........................................................................................................34
3.6.1. Объединение изображений ...........................................................................35
3.6.2. Создание флага ..............................................................................................36
3.7. Небольшое отступление: типы, ошибки и документация ..................................37
3.7.1. Типы и контракты ..........................................................................................37
3.7.2. Ошибки формата и нотации..........................................................................39
3.7.3. Поиск других функций: документация ........................................................40

Глава 4. Именование значений ..........................................................................42
4.1. Панель определений .............................................................................................42
4.2. Именование значений ..........................................................................................42
4.2.1. Сравнение имен и строк ................................................................................43
4.2.2. Сравнение выражений с инструкциями ......................................................44
4.3. Каталог программы ..........................................................................................45
4.3.1. Объяснение смысла кнопки Run ...................................................................46
4.4. Использование имен для оптимизации создания изображений ......................48

 Содержание

Глава 5. От повторяющихся выражений к функциям ................................50
5.1. Учебный пример: похожие флаги ........................................................................50
5.2. Определение функций ..........................................................................................51
5.2.1. Как вычисляются функции ............................................................................52
5.2.2. Аннотации типов ...........................................................................................53
5.2.3. Документация ................................................................................................55
5.3. Практическая методика разработки функций: расчет веса на Луне .................56
5.4. Документирование функций с примерами ........................................................57
5.5. Практическая методика разработки функций: стоимость авторучек ..............58
5.6. Резюме: определение функций ............................................................................61

Глава 6. Условные и логические выражения ................................................63
6.1. Учебный пример: вычисление стоимости доставки ..........................................63
6.2. Условные выражения: вычисления с принятием решений ...............................64
6.3. Логические выражения .........................................................................................65
6.3.1. Другие логические операции ........................................................................66
6.3.2. Объединение логических выражений ..........................................................68
6.4. Как задать сразу несколько вопросов ..................................................................68
6.5. Вычисление методом упрощения выражений ....................................................72
6.6. Совместное использование функций ..................................................................73
6.6.1. Как вычисляются совместно используемые функции ................................74
6.6.2. Совместное использование функций и внутренний каталог .....................75
6.7. Вложенные условные выражения ........................................................................76
6.8. Резюме: логические и условные выражения ......................................................80

Глава 7. Введение в табличные данные .........................................................82
7.1. Создание табличных данных ................................................................................84
7.2. Извлечение значений строк и ячеек ....................................................................86
7.3. Функции для работы со строками ........................................................................88
7.4. Обработка строк таблицы .....................................................................................89
7.4.1. Поиск строк .....................................................................................................90
7.4.2. Упорядочение строк .......................................................................................91
7.4.3. Добавление новых столбцов ..........................................................................93
7.4.4. Вычисление новых значений столбца ..........................................................95
7.5. Примеры функций для создания таблиц .............................................................96

Глава 8. Обработка таблиц ..................................................................................98
8.1. Очистка таблиц данных ........................................................................................99
8.1.1. Загрузка таблиц данных ................................................................................99
8.1.2. Обработка отсутствующих элементов ........................................................100
8.1.3. Нормализация данных ................................................................................102
8.1.4. Нормализация, систематическое применение..........................................106
8.1.4.1. Использование программ для обнаружения ошибок в данных ........107
8.2. Планирование задач ...........................................................................................108
8.3. Подготовка таблиц данных ................................................................................111
8.3.1. Создание групп по категориям ...................................................................112
8.3.2. Разделение столбцов ...................................................................................112
8.4. Управление и именование таблиц данных .......................................................114
8.5. Визуальные представления и графики ..............................................................115
8.6. Резюме: управление анализом данных .............................................................117

   7

Глава 9. От таблиц к спискам ............................................................................119
9.1. Основные статистические вопросы ...................................................................119
9.2. Извлечение столбца из таблицы ........................................................................120
9.3. Объяснение смысла списков ..............................................................................121
9.3.1. Списки как анонимные данные ..................................................................121
9.3.2. Создание литеральных списков ..................................................................122
9.4. Операции со списками .......................................................................................123
9.4.1. Встроенные операции со списками чисел .................................................123
9.4.2. Встроенные операции для любых списков  ...............................................123
9.4.3. Небольшое отступление о соглашениях об именовании ..........................124
9.4.4. Получение элементов по позиции .............................................................125
9.4.5. Преобразование списков .............................................................................126
9.4.6. Резюме: краткий обзор операций для работы со списками .....................127
9.5. Лямбда: анонимные функции ............................................................................129
9.6. Совместное использование списков и таблиц ..................................................130

Глава 10. Обработка списков ............................................................................133
10.1. Создание списков и разделение их на части ..................................................133
10.2. Несколько упражнений с примерами ..............................................................136
10.3. Структурированные задачи со скалярными ответами ...................................136
10.3.1. my-len: примеры ..........................................................................................136
10.3.2. my-sum: примеры ..........................................................................................138
10.3.3. От примеров к исходному коду.................................................................139
10.4. Структурированные задачи, в которых выполняется преобразование  
списков .......................................................................................................................141
10.4.1. my-doubles: примеры и код .........................................................................142
10.4.2. my-str-len: примеры и код .........................................................................144
10.5. Структурированные задачи, которые выбирают элементы из списков .......145
10.5.1. my-pos-nums: примеры и код  .......................................................................145
10.5.2. my-alternating: примеры и код ...................................................................147
10.6. Структурированные задачи на нестрогих областях определения .................150
10.6.1. my-max: примеры ..........................................................................................150
10.6.2. my-max: от примеров к коду .........................................................................152
10.7. Более структурированные задачи со скалярными ответами .........................154
10.7.1. my-avg: примеры ..........................................................................................154
10.8. Структурированные задачи с аккумуляторами ..............................................156
10.8.1. my-running-sum: первая попытка .................................................................156
10.8.2. my-running-sum: примеры и код ...................................................................156
10.8.3. my-alternating: примеры и код ...................................................................158
10.9. Работа с несколькими ответами ......................................................................159
10.9.1. uniq: постановка задачи .............................................................................159
10.9.2. uniq: примеры .............................................................................................159
10.9.3. uniq: код .......................................................................................................160
10.9.4. uniq: сокращенное вычисление .................................................................162
10.9.5. uniq: пример и варианты кода ...................................................................163
10.9.6. uniq: почему создается список? .................................................................164
10.10. Мономорфные списки и полиморфные типы ...............................................164

Глава 11. Введение в структурированные данные ..................................166
11.1. Объяснение типов сложных составных данных .............................................166

 Содержание

11.1.1. Первый взгляд на структурированные данные .......................................166
11.1.2. Первый взгляд на условные данные .........................................................167
11.2. Определение и создание структурированных и условных данных ...............168
11.2.1. Определение и создание структурированных данных ...........................168
11.2.2. Аннотации для структурированных данных ...........................................169
11.2.3. Определение и создание условных данных .............................................170
11.3. Программирование со структурированными и условными данными ..........171
11.3.1. Извлечение полей из структурированных данных .................................171
11.3.2. Различение вариантов условных данных ................................................172
11.3.3. Обработка полей вариантов ......................................................................173

Глава 12. Наборы структурированных данных .........................................175
12.1. Списки как наборы данных ..............................................................................176
12.2. Множества как наборы данных ........................................................................178
12.2.1. Выбор элементов из множеств .................................................................179
12.2.2. Вычисления с использованием множеств ................................................180
12.3. Сочетание структурированных и объединенных в набор данных ................181
12.4. Задача проектирования данных: представление опросов .............................182

Глава 13. Рекурсивные данные .......................................................................185
13.1. Функции для обработки рекурсивных данных ...............................................187
13.2. Шаблон для обработки рекурсивных данных .................................................192

Глава 14. Деревья .................................................................................................195
14.1. Задача проектирования данных – данные родословной ...............................195
14.1.1. Вычисление генетических родителей по таблице родословной ............196
14.1.2. Вычисление прародителей по таблице родословной ..............................198
14.1.3. Создание типа данных для деревьев родословной .................................199
14.2. Программы для обработки деревьев родословной .........................................201
14.3. Резюме: методика решения задач о деревьях ................................................203
14.4. Учебные вопросы ..............................................................................................203

Глава 15. Функции как данные ........................................................................205
15.1. Немного математического анализа .................................................................205
15.2. Удобная сокращенная форма записи для анонимных функций ...................208
15.3. Потоки из функций ...........................................................................................208
15.4. Объединение сил: потоки производных .........................................................214

Глава 16. Интерактивные игры как системы с обратной связью ........216
16.1. Немного об анимации с обратной связью ......................................................217
16.2. Предварительные условия ................................................................................218
16.3. Версия: самолет пересекает экран ...................................................................218
16.3.1. Обновление состояния окружающей среды ............................................219
16.3.2. Вывод представления состояния окружающей среды ............................220
16.3.3. Наблюдение за временем (и совмещение всех элементов) ....................221
16.4. Версия: непрерывное циклическое движение ................................................222
16.5. Версия: снижение ..............................................................................................223
16.5.1. Движение самолета ....................................................................................224
16.5.2. Визуализация сцены ..................................................................................225
16.5.3. Завершающие штрихи ...............................................................................226

Содержание  9

16.6. Версия: ответная реакция на нажатия клавиш ...............................................226
16.7. Версия: посадка .................................................................................................228
16.8. Версия: закрепленный воздушный шар ..........................................................230
16.9. Версия: следите за топливным баком .............................................................232
16.10. Версия: воздушный шар тоже двигается .......................................................234
16.11. Версия: один, два, ... девяносто девять летающих воздушных шаров ........235

Глава 17. Примеры, тестирование и проверка программ ......................236
17.1. От примеров к тестам .......................................................................................236
17.2. Улучшенные сравнения.....................................................................................238
17.3. Когда тесты не проходят ...................................................................................241
17.4. Прогнозирование тестирования ......................................................................242

Часть III. АЛГОРИТМЫ ......................................................................................244

Глава 18. Прогнозирование роста ..................................................................245
18.1. Маленькая (правдивая) история ......................................................................245
18.2. Основной аналитический принцип .................................................................249
18.3. Модель стоимости для времени выполнения Pyret ........................................250
18.4. Размер входных данных ...................................................................................251
18.5. Табличный метод для отдельных структурированных рекурсивных  
функций .....................................................................................................................252
18.6. Создание рекуррентных последовательностей ..............................................254
18.7. Форма записи для функций ..............................................................................256
18.8. Сравнение функций ..........................................................................................256
18.9. Объединение О­больших без проблем ............................................................258
18.10. Решение рекуррентных последовательностей .............................................259

Глава 19. Обратимся к множествам ...............................................................263
19.1. Представление множеств с помощью списков ...............................................264
19.1.1. Варианты выбора представления .............................................................264
19.1.2. Временнáя сложность ................................................................................265
19.1.3. Выбор одного из представлений ..............................................................266
19.1.4. Другие операции ........................................................................................268
19.2. Как заставить множества расти на деревьях ...................................................269
19.2.1. Преобразование значений в упорядоченные значения .........................270
19.2.2. Использование двоичных деревьев ..........................................................272
19.2.3. Точный баланс: обрезка деревьев .............................................................276
19.2.3.1. Вариант левое–левое ..........................................................................279
19.2.3.2. Вариант левое–правое ........................................................................280
19.2.3.3. Существуют ли какие­либо другие варианты? .................................281

Глава 20. Хэллоуин-анализ ...............................................................................283
20.1. Первый пример .................................................................................................283
20.2. Новая форма анализа ........................................................................................283
20.3. Пример: очереди из списков ............................................................................284
20.3.1. Представления в виде списка ...................................................................284
20.3.2. Первоначальный анализ ...........................................................................285
20.3.3. Более разнообразные последовательности операций ............................285
20.3.4. Второй этап анализа ..................................................................................287

 Содержание

20.3.5. Сравнение амортизации с отдельными операциями .............................287
20.4. Материал для дополнительного чтения ..........................................................287

Глава 21. Совместное использование значений и равенство...............288
21.1. Новый взгляд на равенство ..............................................................................288
21.2. Стоимость вычисления ссылок ........................................................................292
21.3. Формы записи равенства ..................................................................................294
21.4. В интернете никто не знает, что вы НАГ .........................................................294
21.5. НАГ был всегда ..................................................................................................296
21.6. От ацикличности к циклам ..............................................................................297

Глава 22. Графы .....................................................................................................299
22.1. Объяснение сущности графов ..........................................................................299
22.2. Представления ...................................................................................................303
22.2.1. Связи по имени ..........................................................................................303
22.2.2. Связи по индексам .....................................................................................305
22.2.3. Список ребер ..............................................................................................307
22.2.4. Абстрагирующие представления ..............................................................308
22.3. Измерение сложности для графов ...................................................................308
22.4. Достижимость ....................................................................................................309
22.4.1. Простая рекурсия .......................................................................................309
22.4.2. Приведение в порядок цикла ....................................................................310
22.4.3. Проход с использованием памяти ............................................................311
22.4.4. Улучшенный интерфейс ............................................................................312
22.5. Обход в глубину и в ширину .............................................................................313
22.6. Графы со взвешенными ребрами .....................................................................314
22.7. Наикратчайшие (или наилегчайшие) пути .....................................................315
22.8. Моравские остовные деревья ...........................................................................317
22.8.1. Глобальная задача ......................................................................................318
22.8.2. Жадное решение ........................................................................................318
22.8.3. Другое жадное решение ............................................................................319
22.8.4. Третье решение ..........................................................................................320
22.8.5. Проверка связности компонентов ............................................................321

Часть IV. ОТ PYRET К PYTHON .....................................................................326

Глава 23. От Pyret к Python ...............................................................................327
23.1. Выражения, функции и типы ...........................................................................327
23.2. Возврат значений из функций .........................................................................329
23.3. Примеры и варианты тестов ............................................................................330
23.4. Небольшое отступление по поводу чисел .......................................................331
23.5. Условные выражения ........................................................................................333
23.6. Создание и обработка списков .........................................................................333
23.6.1. Фильтры, отображения и друзья ...............................................................334
23.7. Данные с компонентами ...................................................................................335
23.7.1. Доступ к полям внутри классов данных ...................................................336
23.8. Обход списков ...................................................................................................336
23.8.1. Представляем циклы for ...........................................................................336
23.8.1.1. Небольшое отступление о порядке обработки элементов списка ....338