Книга: А.Г. Кушниренко, Т.В. Лебедев - Программирование для математиков
Описание
Характеристики книги
Список файлов
А.Г. КУШНИРЕНКО
Т.В.ЛЕБЕДЕВ
ПРОГРАММИРОВАНИЕ
ДЛЯ МАТЕМАТИКОВ
Допущено Министерством'
высшего и среднего специального образования СССР
в качестве учебного пособия
для студентов высших учебных заведений
по специальностям
<Математика> и <Прикладная математика*
МОСКВА <НАУКА>
ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
1988
Кушниренко А.Г., Лебедев Г.В. Программирование для мате-
матиков: Учеб. пособие для вузов - М.: Наука. Гл. ред. физ.-мат, лит.,
1988- 384 с. . '
ISBN 5-02-014235-2 I '
Книга содержит расширенный вариант начального курса программирова-
ния, который читается на механико-математическом факультете МГУ с 1980 г.
Цель курса - заложить фундамент общей программистской культуры слуша-
телей и научить их грамотно программировать практически задачи объемом
несколько тысяч строк. Основу курса составляют понятие исполнителя, техно-
логия программирования <сверху вниз> и развитые структуры данных. В числе
изучаемых в курсе законченных программных систем - управление станком
с ЧПУ и <луноходом>, реализация простейшего компилятора арифметических
формул, построение изображения полиэдра с удалением невидимых линий,
ссылочная реализация списка, хеширование, двумерное хеширование по
равномерной сетке, реализации виртуальной памяти, простейшей файловой
системы и компонент экранного редактора текстов.
Изложение ведется в едином стиле с использованием понятия исполни-
теля на учебном языке программирования с русской лексикой.
Для студентов математических факультетов университетов в факультетов
прикладной математики вузов.
Табл. II. Ил. 96.
Рецензенты:
кафедра прикладной математики МИЭМ,
доктор физико-математических наук /1, Л. Семенов.
1702070000-158
053 (02)-88
ISBN 5-02-014235-2
КБ-14-63- 88
c Издательство <Наука>
Главная редакция
физико-математической
литературы, 1988
ОГЛАВЛЕНИЕ
Предисловие
Глава 1. Начала программирования
1. Основные понятия программирования, примеры исполните-
лей и простейших программ ...............
Основные понятия программирования (9). Исполнитель <Резчик ме-
талла> (10). Исполнитель <Путник> (13). Стек (15). Исполнитель <Сте-
ковый калькулятор> (16). Исполнитель <Счетчик> (18). Задачи и
упражнения (19).
2. Процесс выполнения программы. Управляющие конструкции
и утверждения......................
Управляющие конструкции (20). Конструкции выбора (23). Циклы (23).
Утверждение, отказ и ничего не делать (24). Примеры программ (25).
Задачи и упражнения (27).
3. Основная задача программирования и технология <сверху
вниз> ..........................
Программы и их вызовы (27). Основная задача программирования (29).
Технология программирования <сверху вниз> (30). Шаг декомпози-
ции (31). Пример разработки программы по технологии <сверху
вниз> (33). Задачи и упражнения (41).
4. Процесс разработки программ. Рекурсия, итерация, проекти-
рование цикла с помощью инварианта ......... .
Разбиение задачи на подзадачи (44), Вызовы программ и <дано>/<по-
лучить> (46). Пример (49). Рекурсия (50). Конструкция циклов (53). Ите-
рация (53). Схема проектирования цикла с помощью инварианта (56).
Задачи и упражнения (62).
5. Процесс разработки программ. Один пример . . . . . . .
Формулировка задачи (64). Решение (66). Задачи и упражнения (76).
6. Объекты, параметры, типы. Схема вычисления инвариант-
ной функции .......................
Объекты (77). Локальные объекты программ (79). Глобальные объекты
исполнителей (81). Входные и выходные параметры программ (82).
Программы, вырабатывающие значение (84). Типы объектов (85). Опи-
сания типов (87). Примеры программ (88). Схема вычисления значе-
ния инвариантной функции (90). Задачи и упражнения (92).
7. Способы конструирования типов, объектов и исполнителей
Перечисление (93). Отрезок (94). Запись (93). Структуры (96).
Стек (97). Очередь (98). Дек (98). Множество (99). Нагруженное мно-
жество (100). Последовательность (100). Л2-список (101). Л1-список (102).
Вектор (103). Матрица (104). Динамический вектор (104). Структуры как
способы конструирования исполнителей (104). Структуры как способы
конструирования объектов (105). Примеры программ (106). Циклы <для
каждого> (107). Задачи и упражнения (111).
8. Индуктивное вычисление функций на пространстве последо-
вательностей ......................
Индуктивные функции (114), Стационарные значения (116). Индуктив-
ные расширения функций (117). Минимальное индуктивное расшире-
ние (118). Теорема существования (119). Разные пространства и доопре-
деления (120). Практика (122). Замечания (130). Задача и упражне-
ния (134).
189
190
202
211
f ОГЛАВЛЕНИЕ
Глава 2. Несколько примеров программ
9. Проект <Выпуклая оболочка> последовательно поступающих
точек плоскости ..................... 136
Формулировка задачи (136). Основные идеи (137). Первый шаг деком-
позиции (138). Второй шаг декомпозиции (142). Третий шаг декомпози-
ции (148). Задачи и упражнения (149).
10. Компиляция и интерпретация. Реализация простейшего ком-
пилятора с языка арифметических формул ........ 150'
Язык и грамматика (150). Компиляция (154). Рекурсивная реализация
компилятора правильных формул (154), Компиляция и интерпрета-
ция (161). Реализация компилятора с помощью стека (161). Задачи и
упражнения (166).
11. Проект <Построение изображения полиэдра>
Постановка задачи (168). Реализация (170). Оптимизация (183). Фильтро-
вание граней (183). Предкомпиляция граней (187). Задача и упражне-
ния (187).
Глава 3. Структуры данных и их реализации . . . ..
12. Примеры реализации одних структур данных на базе других.
Непрерывные реализации на базе вектора .........
Последовательность на, базе двухочередей (190). Непрерывные реали-
зации на базе вектора (194). Ограниченный стек (194). Ограниченная
очередь на базе <циклического> вектора (196). Задачи и упражнения (200).
13. Ссылочные реализации на базе вектора ..........
Задачи и упражнения (210).
14. Три способа реализации множества на базе вектора. После-
довательный поиск, бинарный поиск, хеширование
Непрерывная реализация; последовательный поиск (211). Непрерывная
реализация; бинарный поиск (214). Битовая реализация (220). Хеширо-
вание (223). Задачи и упражнения (234).
15. Двумерное хеширование по равномерной сетке. Оптимизация
алгоритма построения изображения полиэдра ....... 235
Идея двумерного хеширования (235). Реализация (238). Оценки эффек-
тивности (245). Задачи и упражнения (248).
16. Виртуальная память .........>>..... 249
Кэш-память (252). Виртуальная память (254). Хеш-реализация виртуаль-
ной памяти (261). Задачи и упражнения (264).
17. Простейшая файловая система .............. 265
Постановка задачи (266). Основные идеи реализации (269). Реализа-
Файл скачан с сайта StudIzba.com
При копировании или цитировании материалов на других сайтах обязательно используйте ссылку на источник
Начать зарабатывать