Введение в программирование и структуры данных
Покупка
Тематика:
Программирование и алгоритмизация
Издательство:
ДМК Пресс
Перевод:
Снастин А. В.
Год издания: 2022
Кол-во страниц: 440
Дополнительно
Вид издания:
Практическое пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-93700-137-5
Артикул: 817217.01.99
В этой книге представлены полезные методики программирования, имеющие практическую ценность. Опираясь на свой многолетний опыт, авторы показывают, как написать надежный код, который смогут читать другие разработчики. Основной принцип обучения — составление плана решения: от определения структур данных по условиям поставленной задачи через примеры и тесты к написанию программного кода. Обсуждаются типичные ошибки программистов. Многочисленные примеры и упражнения позволяют читателям самостоятельно закрепить изученный материал на практике.
Издание будет полезно студентам вузов, где преподается информатика, а также всем, кто хочет изучить современное программирование.
- Полная коллекция по информатике и вычислительной технике
- Аналитика данных
- ДМК Пресс. Информационные системы и технологии
- ДМК Пресс. ИТ-технологии для обучающихся
- Интермедиатор. Информационные системы и технологии (сводная)
- Интермедиатор. ИТ-технологии для обучающихся (сводная)
- Программирование и алгоритмизация
- Программирование на Python
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 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 9785937001375 (рус.) © Перевод, оформление, издание, ДМК Пресс, 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
Содержание 11 23.8.2. Использование циклов for в функциях, создающих списки ..................339 23.8.3. Резюме: шаблон обработки списков для Python .....................................340 Часть V. ПРОГРАММИРОВАНИЕ С СОХРАНЕНИЕМ СОСТОЯНИЯ .........................................................................................................341 Глава 24. Изменение структурированных данных ...................................342 24.1. Изменение полей структурированных данных ..............................................343 24.2. Изменение совместно используемых данных ................................................344 24.3. Объяснение функционирования памяти ........................................................346 24.4. Переменные и равенство ..................................................................................347 24.5. Хранение простых данных в памяти ...............................................................348 Глава 25. Изменение переменных .................................................................350 25.1. Изменение переменных в памяти ...................................................................350 25.2. Изменение переменных, связанных со списками ..........................................354 25.3. Создание функций, изменяющих переменные ..............................................355 25.3.1. Аннотация global .......................................................................................356 25.4. Тестирование функций, изменяющих глобальные переменные ..................357 25.4.1. Внутренняя структура функции тестирования ........................................361 25.4.2. Общие выводы о тестировании изменений ............................................361 Глава 26. Возврат к спискам и переменным...............................................363 26.1. Обновление совместно используемого списка ...............................................363 26.1.1. Операции, изменяющие списки ...............................................................364 26.2. Списки в памяти ...............................................................................................365 26.3. Практический пример: данные для совместно используемых банковских счетов .....................................................................................................367 26.4. Циклические ссылки .........................................................................................371 26.4.1. Тестирование циклических данных .........................................................373 26.4.2. Снова переменные: функция для создания счетов для новых клиентов.................................................................................................................373 26.5. Многочисленные роли переменных ................................................................374 26.6. Управление всеми счетами ..............................................................................375 Глава 27. Хеш-таблицы и словари ..................................................................377 27.1. Поиск по условиям, отличающимся от ключей ...............................................378 27.2. Словари с более сложными значениями .........................................................379 27.3. Использование структурированных данных в качестве ключей ...................380 Часть VI. ДОПОЛНИТЕЛЬНЫЕ ТЕМЫ .......................................................382 Глава 28. Алгоритмы, использующие состояние .......................................383 28.1. И снова о непересекающихся множествах ......................................................383 28.1.1. Оптимизации .............................................................................................384 28.1.2. Анализ .........................................................................................................385 28.2. Установка членства методом обратного хеширования ..................................386 28.2.1. Улучшение времени доступа .....................................................................387 28.2.2. Улучшенное хеширование .........................................................................389 28.2.3. Фильтры Блума...........................................................................................389
Содержание 28.3. Устранение повторных вычислений с помощью запоминания ответов ......391 28.3.1. Интересная числовая последовательность ..............................................391 28.3.1.1. Использование состояния для запоминания предыдущих ответов ...............................................................................................................393 28.3.1.2. От дерева вычислений к НАГ .............................................................394 28.3.1.3. Сложность чисел .................................................................................395 28.3.1.4. Абстрагирование мемоизации ..........................................................395 28.3.2. Редакторское расстояние для исправления орфографических ошибок ...................................................................................................................397 28.3.3. Природа как машинистка с неловкими пальцами ..................................402 28.3.4. Динамическое программирование ..........................................................403 28.3.4.1. Числа Каталана и динамическое программирование ......................404 28.3.4.2. Расстояние Левенштейна и динамическое программирование .....405 28.3.5. Сравнение мемоизации и динамического программирования .............408 Часть VII. ПРИЛОЖЕНИЯ .................................................................................411 Глава 29. Pyret для пользователей Racket и Scheme ..............................412 29.1. Числа, строки и логические значения .............................................................412 29.2. Инфиксные выражения ....................................................................................413 29.3. Определение и применение функций .............................................................413 29.4. Тесты ..................................................................................................................414 29.5. Имена переменных ...........................................................................................415 29.6. Определения данных ........................................................................................415 29.7. Условные выражения .........................................................................................417 29.8. Списки ................................................................................................................419 29.9. Функции первого класса ...................................................................................420 29.10. Аннотации .......................................................................................................420 29.11. Что еще? ...........................................................................................................420 Глава 30. Сравнение Pyret с Python ...............................................................421 Глава 31. Сравнение этой книги с книгой «Как проектировать программы» (HtDP) .............................................................................................424 Глава 32. Примечания к текущей редакции книги ...................................427 Глава 33. Словарь терминов .............................................................................428 Предметный указатель .......................................................................................431
От издательства Отзывы и пожелания Мы всегда рады отзывам наших читателей. Расскажите нам, что вы ду маете об этой книге – что понравилось или, может быть, не понравилось. Отзывы важны для нас, чтобы выпускать книги, которые будут для вас максимально полезны. Вы можете написать отзыв на нашем сайте www.dmkpress.com, зайдя на страницу книги и оставив комментарий в разделе «Отзывы и рецензии». Также можно послать письмо главному редактору по адресу dmkpress@gmail. com; при этом укажите название книги в теме письма. Если вы являетесь экспертом в какойлибо области и заинтересованы в написании новой книги, заполните форму на нашем сайте по адресу http:// dmkpress.com/authors/publish_book/ или напишите в издательство по адресу dmkpress@gmail.com. Список опечаток Хотя мы приняли все возможные меры для того, чтобы обеспечить высокое качество наших текстов, ошибки все равно случаются. Если вы найдете ошибку в одной из наших книг, мы будем очень благодарны, если вы сообщите о ней главному редактору по адресу dmkpress@gmail.com. Сделав это, вы избавите других читателей от недопонимания и поможете нам улучшить последующие издания этой книги. Нарушение авторских прав Пиратство в интернете попрежнему остается насущной проблемой. Издательство «ДМК Пресс» очень серьезно относится к вопросам защиты авторских прав и лицензирования. Если вы столкнетесь в интернете с незаконной публикацией какойлибо из наших книг, пожалуйста, пришлите нам ссылку на интернетресурс, чтобы мы могли применить санкции. Ссылку на подозрительные материалы можно прислать по адресу электронной почты dmkpress@gmail.com. Мы высоко ценим любую помощь по защите наших авторов, благодаря которой мы можем предоставлять вам качественные материалы.
Об авторах Кати Фислер (Kathi Fisler) научный сотрудник-исследователь в области информационных технологий в университете Брауна (Про- виденс, Род-Айленд, США) Заместитель директора программы бакалавриата по информационным технологиям (ИТ). Содиректор программы Bootstrap. Кати интересуют различные аспекты того, как люди изучают и используют формальные системы. В настоящее время она занимается компьютерным образованием, где рассматриваются модели и представления для объяснения поведения программы (воображаемых машин) и способы использования противоположностей между конкретными примерами для обучения концепциям ИТ. Кати разрабатывает курс (и учебник) по обучению ИТ, ориентированному на данные (наука о данных + структуры данных). Кати также является одним из преподавателей, занимающихся разработкой и оценкой усилий нашей кафедры по интеграции социально ответственного применения ИТ на протяжении всех четырех лет нашей учебной программы по ИТ. Ранее Кати участвовала в разработке схематической логики для проектирования оборудования (конец 1990х гг.), модульной верификацией функционально ориентированных программ (начало 2000х гг.) и анализом политики управления доступом и конфиденциальности (середина–конец 2000х гг.). В этих проектах упор делался на формальные системы, а не на человеческое мышление. Шрирам Кришнамурти (Shriram Krishnamurthi) профессор информатики в университете Брауна (Провиденс, Род-Айленд, США) Основные области исследования (сам Шрирам называет их «скорее исследовательскими взглядами/ представлениями»): абстракции необходимы для прогресса в информационных технологиях; но абстракции могут быть трудными для понимания и изучения; тем не менее абстракции еще и прекрасны; как мы можем помочь людям эффективно изучать абстракции?
Об авторах 15 Главная цель состоит в том, чтобы добиться прогресса в максимально возможном количестве аспектов этих представлений. Сначала Шрирам обучался языкам программирования, но в дальнейшем изучал различные аспекты разработки программного обеспечения, формальные методы, взаимодействие человек–компьютер, безопасность и сети. На протяжении многих лет участвовал в нескольких проектах разработки инновационных и полезных программных систем: инструменты JavaScript, Flowlog, Racket (ранее DrScheme), WeScheme, Margrave, Flapjax, FrTime, Continue, FASTLINK, (Per)Mission и др. В настоящее время в основном работает с языком Pyret. С 2016 г. Шрирам посвятил значительную часть своего времени и энергии самой сложной проблеме – компьютерным исследованиям в области образования, поскольку она требует серьезной работы как с технической точки зрения, так и с учетом человеческого фактора: если вы допустите оплошность, то можете нанести реальный ущерб не только отдельным людям, но и всей отрасли и обществу. Шрирам занимается информационными технологиями с 1995 г. Возможно, он знаком читателям по таким книгам (написанным в соавторстве), как HtDP, PLAI, PAPL или (в настоящее время) DCIC. Участник социально ориентированной программы Bootstrap, которая используется во всем мире для внедрения информационных технологий в математику, физику, социальные науки и другие дисциплины. Шрирам являлся заместителем директора программы Brown’s Executive Master in Cybersecurity, где отвечал за курс по человеческому фактору. Новая версия программы объединена с информационными технологиями. Шрирам является лауреатом премии SIGPLAN для молодых исследователей Робина Милнера (Robin Milner Young Researcher Award), премии SIGSOFT для авторитетных преподавателей, премии SIGPLAN в области программного обеспечения (совместно), а также Wriston Fellowship университета Брауна. Бенджамин С. Лернер (Benjamin S. Lerner) адъюнкт-профессор (доцент-преподаватель) ИТ Khoury Colledge в Северо-Восточном университете (Northeastern University, Бостон, Массачусетс, США) Области научных интересов Бенджамина: Pyret: язык, разработанный для начального обучения программированию, с акцентом на тестирование, ясность и иногда с ужасными каламбурами из пиратского («пиретского») лексикона; семантика вебпрограммирования: современные вебпрограммы сочетают в себе богатые структуры данных, хитроумное выполнение на основе событий, данные, получаемые от третьих сторон, и мощные, но мелкомасштабные API. Понимание и анализ этих про
Об авторах грамм требуют сначала создания тестируемой и исполняемой семантики для каждого из данных компонентов, а затем использования соответствующей семантики для проведения анализа программы; обеспечение совместимости расширений веббраузера (проект Conflicts of Interest: Interactions among Browser Extensions): рост популярности Firefox можно в значительной степени объяснить его широко разрекламированными расширениями, которые предлагают универсальность, удобство и относительно низкие кривые обучения как для любителей, так и для опытных программистов. Но вместе с такой возможностью гибкой настройки возникают проблемы: многие расширения не работают должным образом при одновременной установке. Этот проект направлен на предоставление улучшенной модели программирования для расширений, которые могут обнаруживать и, возможно, исправлять подобные конфликты до их возникновения. Джо Гиббс Политц (Joe Gibbs Politz) адъюнкт-профессор (доцент-преподаватель) ИТ Калифорнийского университета Сан-Диего (UC San Diego), США Преподаватель многочисленных курсов по информационным технологиям (ИТ), разработанных с использованием повторно используемых материалов, включая видео, заметки и первоначальный исходный код для контрольных заданий: Advanced Compiler Design (UCSD CSE 231); Software Engineering (UCSD CSE 110); Advanced Data Structures (UCSD CSE 100); Basic Data Structures and ObjectOriented Design (UCSD CSE 12); Data Structures and Algorithms (Swarthmore CS 35); Programming Languages (Brown University CS173; совместно с Шрирамом Кришнамурти) и многих других.
Часть I ВВЕДЕНИЕ
Глава 1 Предисловие 1.1. О чем эта книга Эта книга представляет собой введение в информатику. Она научит вас программировать такими способами, которые имеют практическую ценность и важность. Но этот процесс обучения будет к тому же выходить за рамки программирования в более широкую область информатики, богатой, глубокой, увлекательной и прекрасной многогранной дисциплины. Вы узнаете много полезных вещей, которые сможете сразу же применить на практике, но мы также продемонстрируем вам коечто из того, что скрывается за ними. Прежде всего мы хотим предоставить вам способы мышления для решения задач с помощью вычислений. Некоторые из этих способов являются техническими методиками, такими как обработка данных и примеры для разработки решений задач. Другие представляют собой научные методы, такие как способы, позволяющие убедиться в том, что программы надежны и делают именно то, для чего они предназначены. Наконец, некоторые из таких способов имеют социальную составляющую, они заставляют задуматься о влиянии программ на людей. 1.2. ОснОвОпОлагающие принципы, Определяющие сОдержание этОй книги Наша точка зрения основана на многолетнем опыте работы в качестве разработчиков программного обеспечения, исследователей и преподавателей. Эти виды деятельности позволили нам выработать следующие твердые убеждения: программное обеспечение пишется не только для того, чтобы его выполнять. Программы следует писать так, чтобы их могли читать и сопровождать другие люди. Часто этим «другим» человеком являетесь вы сами, через шесть месяцев забывшие, что было сделано и почему именно так;