Кушниренко А. Г., Лебедев Г. В. Программирование для математиков: Учеб, пособие для вузов — М.: Наука. Гл. ред. фиэ.-ыат. лит.. 9988.- 384 с.
ISBN 5-02-014235-2 '
Книга содержит расширенный вариант начального курса программирования, который читается на механико-математическом факультете МГУ с 1980 г, Цель курса — заложить фундамент общей программистской культуры слушателей и научить их грамотно программировать практически задачи объемом несколько тысяч строк. Основу курса составляют понятие исполнителя, технология программирования «сверху вниз» и развитые структуры данных. В числе изучаемых в курсе законченных программных систем — управление ставком с ЧПУ и «луноходом», реализация простейшего компилятора арифметических формул, построение изображения полиэдра с удалением невидимых линий, ссылочная реализация списка, хеширование, двумерное хеширование по равномерной сетке, реализации виртуальной памяти, простейшей файловой системы и компонент экранного редактора текстов.
Изложение ведется в едином стиле с использованием понятия исполни< теля на учебном языке программирования с русской лексикой.
Для студентов математических факультетов университетов и факультетов прикладной математики вузов. Табл. П. Ил. 96.
Рецензенты:
ОГЛАВЛЕНИЕ
Предисловие......................... 6
Глава 1. Начала программирования...........
1. Основные понятия программирования, примеры исполнителей и простейших программ............... 9
Основные понятия программирования (9). Исполнитель «Резчик металла» (10). Исполнитель «Путник> (13). Стек (15). Исполнитель «Стековый калькулятор» (16). Исполнитель «Счетчик» (18). Задачи и упражнения (19).
2. Процесс выполнения программы. Управляющие конструкции
и утверждения...................... 19
Управляющие конструкции (20). Конструкции выбора (23). Циклы (23). Утверждение, отказ и ничего не делать (24). Примеры программ (25). Задачи и упражнения (27).
3. Основная задача программирования и технология «сверху вниз».......................... 27
Программы и их вызовы (27). Основная задача программирования (29). Технология программирования «сверху вниз» (30). Шаг декомпозиции (31). Пример разработки программы по технологии «сверху вниз»„(33). Задачи и упражнения (41).
4. Процесс разработки программ. Рекурсия, итерация, проектирование цикла с помощью инварианта . .......• . 43
Разбиение задачи на подзадачи (44). Вызовы программ и «дано»/«по-лучить» (46). Пример (49). Рекурсия (50). Конструкция Циклов (53). Итерация (53). Схема проектирования цикла с помощью инварианта (56). Задачи и упражнения (62).
5. Процесс разработки программ. Один пример....... 64
Формулировка задачи (64). Решение (66). Задачи и упражнения (76).
6. Объекты, параметры, типы. Схема вычисления инвариантной функции....................... 77
Объекты (77). Локальные объекты программ (79). Глобальные объекты исполнителей (81). Входные и выходные параметры программ (82). Программы, вырабатывающие значение (84). Типы объектов (85). Описания типов (87). Примеры программ (88). Схема вычисления значения инвариантной функции (90). Задачи и упражнения (92).
7. Способы конструирования типов, объектов и исполнителей 93
Перечисление (93). Отрезок (94). Запись (95). Структуры (96). Стек (97). Очередь (98). Дек (98). Множество (99). Нагруженное множество (100). Последовательность (100). Л2-список (101). Л1-еписок (102). Вектор (Ш).Матрица (Ю4). Динамический вектор (104). Структуры как способы конструирования исполнителей (104). Структуры как способы конструирования объектов (105). Примеры программ (106). Циклы «для каждого» (107). Задачи и упражнения (111).
8. Индуктивное вычисление функций на пространстве последовательностей ......................ПЗ
Индуктивные функции (114). Стационарные значения (116). Индуктивные расширения функций (117). Минимальное индуктивное расширение (118). Теорема существования (119). Разные пространства и доопределения (120). Практика (122). Замечания (130). Задача н упражнения (134).
41, ОГЛАВЛЕНИЕ
Глава 2. Несколько примеров программ.........136
9. Проект «Выпуклая оболочка» последовательно поступающих точек плоскости.....................136
Формулировка задачи (136). Основные идеи (137). Первый шаг декомпозиции (138). Второй шаг декомпозиции (142). Третий шаг декомпозиции (148). Задачи и упражнения (149).
10. Компиляция и интерпретация. Реализация простейшего компилятора с языка арифметических формул........150
Язык и грамматика (150). Компиляция (154). Рекурсивная реализация компилятора правильных формул (154). Компиляция и интерпретация (161). Реализация компилятора с помощью стека (161). Задачи и упражнения (166).
11. Проект «Построение изображения полиэдра».......167
Постановка задачи (168). Реализация (170). Оптимизация (183). Фильтрование граней (183). Предкомпиляция граней (187). Задачи и упражнения (187).
Глава 3. Структуры данных и их реализации......189
12. Примеры реализации одних структур данных на базе других. Непрерывные реализации на базе вектора.........190
Последовательность на базе двух очередей (190). Непрерывные реализации на базе вектора (194). Ограниченный стек (194). Ограниченная очередь на базе «циклического» вектора (196). Задачи и упражнения (200).
13. Ссылочные реализации на базе вектора..........202
Задачи и упражнения (210).
14. Три способа реализации множества на базе вектора. Последовательный поиск, бинарный поиск, хеширование .... 211
Непрерывная реализация; последовательный поиск (211). Непрерывная реализация; бинарный поиск (214). Битовая реализация (220). Хеширование (223). Задачи и упражнения (234).
15. Двумерное хеширование по равномерной сетке. Оптимизация алгоритма построения изображения полиэдра.......235
Идея двумерного хеширования (235). Реализация (238). Оценки эффективности (245). Задачи и упражнения (248).
16. Виртуальная память...................249
Кэш-память (252). Виртуальная память (254). Хеш-реализация виртуальной памяти'(261). Задачи и упражнения (264).
17. Простейшая файловая система..............265
Постановка задачи (266). Основные идеи реализации (?69). Реализация (270). Задачи и упражнения (281).
18. Иерархия структур данных при разработке программ . . . 283
Идеи реализации (287). Задачи и упражнения (298).
Глава 4. Логическое устройство и принципы работы ЭПВМ 300
19. Логическое устройство и принципы работы ЭВМ.....300
Память (301). Процессор (304). Работа процессора (305). Команды процессора (306). Задание аргументов команд (311). Примеры программ (313). Внешние устройства, магистраль, адрес (315). Подпрограммы и их вызовы (318). Прерывания (319). Задачи и упражнения (322).
20. Работа программиста на ЭВМ..............323
Начальная загрузка (324). Загрузка операционной системы (324). Программирование в кодах (325). Компиляция (325). Интерпретация (327). Соотношение компиляции и интерпретации (327). Синтаксически ориентированные редакторы (328). Инструментальные среды (329). ЭПВМ (330).
ОГЛАВЛЕНИЕ 5
Глава 5. Программирование на языке Фортран......332
21. Справочные сведения о языке Фортран. Простейшие примеры программ........................333
Пример программы (333). Размещение информации внутри строки (333). Секции (335). Управляющие конструкции (337). Предопределенные типы (339). Способы конструирования (342). Задание объектов и типов объектов (342). Параметры (343). Функции (344). Константы (345). Ввод/вывод (345). Примеры перекодировки программ на Фортран (346). Некоторые вопросы устройства Фортран—машины (352). Расположение и отождествление объектов в памяти (352). Механизм передачи параметров (356). Часто встречающиеся ошибки (356). Задачи и упражнения (358).
22. Реализация исполнителей на Фортране. Примеры реализации структур данных.....................359
Приложение. Краткое неформальное описание использованного в книге языка программирования.........374
Предметный указатель....................380
