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

От издательства
Об авторах
Часть I. Введение
Глава 1. Предисловие
1.1. О чем эта книга
1.2. Основополагающие принципы, определяющие содержание этой книги
1.3. Наш взгляд на данные
1.4. Что делает эту книгу особенной
1.5. Для кого предназначена эта книга
1.6. Структура книги
1.7. Организация материала книги
1.8. Наш выбор языка программирования
1.9. Обратная связь, сообщения об ошибках и комментарии
Глава 2. Благодарности
Часть II. Основы
Глава 3. Начинаем работу
3.1. Поясняющий пример: флаги
3.2. Числа
3.3. Выражения
3.4. Терминология
3.5. Строки
3.6. Изображения
3.6.1. Объединение изображений
3.6.2. Создание флага
3.7. Небольшое отступление: типы, ошибки и документация
3.7.1. Типы и контракты
3.7.2. Ошибки формата и нотации
3.7.3. Поиск других функций: документация
Глава 4. Именование значений
4.1. Панель определений
4.2. Именование значений
4.2.1. Сравнение имен и строк
4.2.2. Сравнение выражений с инструкциями
4.3. Каталог программы
4.3.1. Объяснение смысла кнопки Run
4.4. Использование имен для оптимизации создания изображений
Глава 5. От повторяющихся выражений к функциям
5.1. Учебный пример: похожие флаги
5.2. Определение функций
5.2.1. Как вычисляются функции
5.2.2. Аннотации типов
5.2.3. Документация
5.3. Практическая методика разработки функций: расчет веса на Луне
5.4. Документирование функций с примерами
5.5. Практическая методика разработки функций: стоимость авторучек
5.6. Резюме: определение функций
Глава 6. Условные и логические выражения
6.1. Учебный пример: вычисление стоимости доставки
6.2. Условные выражения: вычисления с принятием решений
6.3. Логические выражения
6.3.1. Другие логические операции
6.3.2. Объединение логических выражений
6.4. Как задать сразу несколько вопросов
6.5. Вычисление методом упрощения выражений
6.6. Совместное использование функций
6.6.1. Как вычисляются совместно используемые функции
6.6.2. Совместное использование функций и внутренний каталог
6.7. Вложенные условные выражения
6.8. Резюме: логические и условные выражения
Глава 7. Введение в табличные данные
7.1. Создание табличных данных
7.2. Извлечение значений строк и ячеек
7.3. Функции для работы со строками
7.4. Обработка строк таблицы
7.4.1. Поиск строк
7.4.2. Упорядочение строк
7.4.3. Добавление новых столбцов
7.4.4. Вычисление новых значений столбца
7.5. Примеры функций для создания таблиц
Глава 8. Обработка таблиц
8.1. Очистка таблиц данных
8.1.1. Загрузка таблиц данных
8.1.2. Обработка отсутствующих элементов
8.1.3. Нормализация данных
8.1.4. Нормализация, систематическое применение
8.1.4.1. Использование программ для обнаружения ошибок в данных
8.2. Планирование задач
8.3. Подготовка таблиц данных
8.3.1. Создание групп по категориям
8.3.2. Разделение столбцов
8.4. Управление и именование таблиц данных
8.5. Визуальные представления и графики
8.6. Резюме: управление анализом данных
Глава 9. От таблиц к спискам
9.1. Основные статистические вопросы
9.2. Извлечение столбца из таблицы
9.3. Объяснение смысла списков
9.3.1. Списки как анонимные данные
9.3.2. Создание литеральных списков
9.4. Операции со списками
9.4.1. Встроенные операции со списками чисел
9.4.2. Встроенные операции для любых списков
9.4.3. Небольшое отступление о соглашениях об именовании
9.4.4. Получение элементов по позиции
9.4.5. Преобразование списков
9.4.6. Резюме: краткий обзор операций для работы со списками
9.5. Лямбда: анонимные функции
9.6. Совместное использование списков и таблиц
Глава 10. Обработка списков
10.1. Создание списков и разделение их на части
10.2. Несколько упражнений с примерами
10.3. Структурированные задачи со скалярными ответами
10.3.1. my-len: примеры
10.3.2. my-sum: примеры
10.3.3. От примеров к исходному коду
10.4. Структурированные задачи, в которых выполняется преобразование списков
10.4.1. my-doubles: примеры и код
10.4.2. my-str-len: примеры и код
10.5. Структурированные задачи, которые выбирают элементы из списков
10.5.1. my-pos-nums: примеры и код
10.5.2. my-alternating: примеры и код
10.6. Структурированные задачи на нестрогих областях определения
10.6.1. my-max: примеры
10.6.2. my-max: от примеров к коду
10.7. Более структурированные задачи со скалярными ответами
10.7.1. my-avg: примеры
10.8. Структурированные задачи с аккумуляторами
10.8.1. my-running-sum: первая попытка
10.8.2. my-running-sum: примеры и код
10.8.3. my-alternating: примеры и код
10.9. Работа с несколькими ответами
10.9.1. uniq: постановка задачи
10.9.2. uniq: примеры
10.9.3. uniq: код
10.9.4. uniq: сокращенное вычисление
10.9.5. uniq: пример и варианты кода
10.9.6. uniq: почему создается список?
10.10. Мономорфные списки и полиморфные типы
Глава 11. Введение в структурированные данные
11.1. Объяснение типов сложных составных данных
11.1.1. Первый взгляд на структурированные данные
11.1.2. Первый взгляд на условные данные
11.2. Определение и создание структурированных и условных данных
11.2.1. Определение и создание структурированных данных
11.2.2. Аннотации для структурированных данных
11.2.3. Определение и создание условных данных
11.3. Программирование со структурированными и условными данными
11.3.1. Извлечение полей из структурированных данных
11.3.2. Различение вариантов условных данных
11.3.3. Обработка полей вариантов
Глава 12. Наборы структурированных данных
12.1. Списки как наборы данных
12.2. Множества как наборы данных
12.2.1. Выбор элементов из множеств
12.2.2. Вычисления с использованием множеств
12.3. Сочетание структурированных и объединенных в набор данных
12.4. Задача проектирования данных: представление опросов
Глава 13. Рекурсивные данные
13.1. Функции для обработки рекурсивных данных
13.2. Шаблон для обработки рекурсивных данных
Глава 14. Деревья
14.1. Задача проектирования данных – данные родословной
14.1.1. Вычисление генетических родителей по таблице родословной
14.1.2. Вычисление прародителей по таблице родословной
14.1.3. Создание типа данных для деревьев родословной
14.2. Программы для обработки деревьев родословной
14.3. Резюме: методика решения задач о деревьях
14.4. Учебные вопросы
Глава 15. Функции как данные
15.1. Немного математического анализа
15.2. Удобная сокращенная форма записи для анонимных функций
15.3. Потоки из функций
15.4. Объединение сил: потоки производных
Глава 16. Интерактивные игры как системы с обратной связью
16.1. Немного об анимации с обратной связью
16.2. Предварительные условия
16.3. Версия: самолет пересекает экран
16.3.1. Обновление состояния окружающей среды
16.3.2. Вывод представления состояния окружающей среды
16.3.3. Наблюдение за временем (и совмещение всех элементов)
16.4. Версия: непрерывное циклическое движение
16.5. Версия: снижение
16.5.1. Движение самолета
16.5.2. Визуализация сцены
16.5.3. Завершающие штрихи
16.6. Версия: ответная реакция на нажатия клавиш
16.7. Версия: посадка
16.8. Версия: закрепленный воздушный шар
16.9. Версия: следите за топливным баком
16.10. Версия: воздушный шар тоже двигается
16.11. Версия: один, два, ... девяносто девять летающих воздушных шаров
Глава 17. Примеры, тестирование и проверка программ
17.1. От примеров к тестам
17.2. Улучшенные сравнения
17.3. Когда тесты не проходят
17.4. Прогнозирование тестирования
Часть III. Алгоритмы
Глава 18. Прогнозирование роста
18.1. Маленькая (правдивая) история
18.2. Основной аналитический принцип
18.3. Модель стоимости для времени выполнения Pyret
18.4. Размер входных данных
18.5. Табличный метод для отдельных структурированных рекурсивных функций
18.6. Создание рекуррентных последовательностей
18.7. Форма записи для функций
18.8. Сравнение функций
18.9. Объединение О-больших без проблем
18.10. Решение рекуррентных последовательностей
Глава 19. Обратимся к множествам
19.1. Представление множеств с помощью списков
19.1.1. Варианты выбора представления
19.1.2. Временнáя сложность
19.1.3. Выбор одного из представлений
19.1.4. Другие операции
19.2. Как заставить множества расти на деревьях
19.2.1. Преобразование значений в упорядоченные значения
19.2.2. Использование двоичных деревьев
19.2.3. Точный баланс: обрезка деревьев
19.2.3.1. Вариант левое–левое
19.2.3.2. Вариант левое–правое
19.2.3.3. Существуют ли какие-либо другие варианты?
Глава 20. Хэллоуин-анализ
20.1. Первый пример
20.2. Новая форма анализа
20.3. Пример: очереди из списков
20.3.1. Представления в виде списка
20.3.2. Первоначальный анализ
20.3.3. Более разнообразные последовательности операций
20.3.4. Второй этап анализа
20.3.5. Сравнение амортизации с отдельными операциями
20.4. Материал для дополнительного чтения
Глава 21. Совместное использование значений и равенство
21.1. Новый взгляд на равенство
21.2. Стоимость вычисления ссылок
21.3. Формы записи равенства
21.4. В интернете никто не знает, что вы НАГ
21.5. НАГ был всегда
21.6. От ацикличности к циклам
Глава 22. Графы
22.1. Объяснение сущности графов
22.2. Представления
22.2.1. Связи по имени
22.2.2. Связи по индексам
22.2.3. Список ребер
22.2.4. Абстрагирующие представления
22.3. Измерение сложности для графов
22.4. Достижимость
22.4.1. Простая рекурсия
22.4.2. Приведение в порядок цикла
22.4.3. Проход с использованием памяти
22.4.4. Улучшенный интерфейс
22.5. Обход в глубину и в ширину
22.6. Графы со взвешенными ребрами
22.7. Наикратчайшие (или наилегчайшие) пути
22.8. Моравские остовные деревья
22.8.1. Глобальная задача
22.8.2. Жадное решение
22.8.3. Другое жадное решение
22.8.4. Третье решение
22.8.5. Проверка связности компонентов
Часть IV. От Pyret к Python
Глава 23. От Pyret к Python
23.1. Выражения, функции и типы
23.2. Возврат значений из функций
23.3. Примеры и варианты тестов
23.4. Небольшое отступление по поводу чисел
23.5. Условные выражения
23.6. Создание и обработка списков
23.6.1. Фильтры, отображения и друзья
23.7. Данные с компонентами
23.7.1. Доступ к полям внутри классов данных
23.8. Обход списков
23.8.1. Представляем циклы for
23.8.1.1. Небольшое отступление о порядке обработки элементов списка
23.8.2. Использование циклов for в функциях, создающих списки
23.8.3. Резюме: шаблон обработки списков для Python
Часть V. Программирование с сохранением состояния
Глава 24. Изменение структурированных данных
24.1. Изменение полей структурированных данных
24.2. Изменение совместно используемых данных
24.3. Объяснение функционирования памяти
24.4. Переменные и равенство
24.5. Хранение простых данных в памяти
Глава 25. Изменение переменных
25.1. Изменение переменных в памяти
25.2. Изменение переменных, связанных со списками
25.3. Создание функций, изменяющих переменные
25.3.1. Аннотация global
25.4. Тестирование функций, изменяющих глобальные переменные
25.4.1. Внутренняя структура функции тестирования
25.4.2. Общие выводы о тестировании изменений
Глава 26. Возврат к спискам и переменным
26.1. Обновление совместно используемого списка
26.1.1. Операции, изменяющие списки
26.2. Списки в памяти
26.3. Практический пример: данные для совместно используемых банковских счетов
26.4. Циклические ссылки
26.4.1. Тестирование циклических данных
26.4.2. Снова переменные: функция для создания счетов для новых клиентов
26.5. Многочисленные роли переменных
26.6. Управление всеми счетами
Глава 27. Хеш-таблицы и словари
27.1. Поиск по условиям, отличающимся от ключей
27.2. Словари с более сложными значениями
27.3. Использование структурированных данных в качестве ключей
Часть VI. Дополнительные темы
Глава 28. Алгоритмы, использующие состояние
28.1. И снова о непересекающихся множествах
28.1.1. Оптимизации
28.1.2. Анализ
28.2. Установка членства методом обратного хеширования
28.2.1. Улучшение времени доступа
28.2.2. Улучшенное хеширование
28.2.3. Фильтры Блума
28.3. Устранение повторных вычислений с помощью запоминания ответов
28.3.1. Интересная числовая последовательность
28.3.1.1. Использование состояния для запоминания предыдущих ответов
28.3.1.2. От дерева вычислений к НАГ
28.3.1.3. Сложность чисел
28.3.1.4. Абстрагирование мемоизации
28.3.2. Редакторское расстояние для исправления орфографических ошибок
28.3.3. Природа как машинистка с неловкими пальцами
28.3.4. Динамическое программирование
28.3.4.1. Числа Каталана и динамическое программирование
28.3.4.2. Расстояние Левенштейна и динамическое программирование
28.3.5. Сравнение мемоизации и динамического программирования
Часть VII. Приложения
Глава 29. Pyret для пользователей Racket и Scheme
29.1. Числа, строки и логические значения
29.2. Инфиксные выражения
29.3. Определение и применение функций
29.4. Тесты
29.5. Имена переменных
29.6. Определения данных
29.7. Условные выражения
29.8. Списки
29.9. Функции первого класса
29.10. Аннотации
29.11. Что еще?
Глава 30. Сравнение Pyret с Python
Глава 31. Сравнение этой книги с книгой «Как проектировать программы» (HtDP)
Глава 32. Примечания к текущей редакции книги
Глава 33. Словарь терминов
Предметный указатель