Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Артикул: 817217.01.99
В этой книге представлены полезные методики программирования, имеющие практическую ценность. Опираясь на свой многолетний опыт, авторы показывают, как написать надежный код, который смогут читать другие разработчики. Основной принцип обучения — составление плана решения: от определения структур данных по условиям поставленной задачи через примеры и тесты к написанию программного кода. Обсуждаются типичные ошибки программистов. Многочисленные примеры и упражнения позволяют читателям самостоятельно закрепить изученный материал на практике. Издание будет полезно студентам вузов, где преподается информатика, а также всем, кто хочет изучить современное программирование.
7
28
133
244
341
382
383
Введение в программирование и структуры данных : практическое руководство / К. Фисле, Ш. Кришнамурти, С. Б. Лернер, Дж. Г.Политц ; пер. с англ. А. В. Снастина. - Москва : ДМК Пресс, 2022. - 440 с. - ISBN 978-5-93700-137-5. - Текст : электронный. - URL: https://znanium.com/catalog/product/2109495 (дата обращения: 18.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Кати Фислер, Шрирам Кришнамурти,  
Бенджамин С. Лернер, Джо Гиббс Политц
Введение в программирование  
и структуры данных


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


6    Содержание
Глава 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


8    Содержание
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


10    Содержание
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