Введение в программирование и структуры данных
Покупка
Тематика:
Программирование и алгоритмизация
Издательство:
ДМК Пресс
Перевод:
Снастин А. В.
Год издания: 2022
Кол-во страниц: 440
Дополнительно
Вид издания:
Практическое пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-93700-137-5
Артикул: 817217.01.99
В этой книге представлены полезные методики программирования, имеющие практическую ценность. Опираясь на свой многолетний опыт, авторы показывают, как написать надежный код, который смогут читать другие разработчики. Основной принцип обучения — составление плана решения: от определения структур данных по условиям поставленной задачи через примеры и тесты к написанию программного кода. Обсуждаются типичные ошибки программистов. Многочисленные примеры и упражнения позволяют читателям самостоятельно закрепить изученный материал на практике.
Издание будет полезно студентам вузов, где преподается информатика, а также всем, кто хочет изучить современное программирование.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 09.03.01: Информатика и вычислительная техника
- 09.03.02: Информационные системы и технологии
- 09.03.03: Прикладная информатика
- 09.03.04: Программная инженерия
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Кати Фислер, Шрирам Кришнамурти, Бенджамин С. Лернер, Джо Гиббс Политц Введение в программирование и структуры данных
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