Непейвода Н.Н., Скопин И.Н. - Основания программирования [2003, PDF, RUS]

Заголовки только первого и второго уровня
I. БАЗОВЫЕ ПОНЯТИЯ
1. Введение в систему понятий программирования
2. Синтаксис, семантика и прагматика языка программирования
3. Стили программирования, или программирование с птичьего полёта
4. Понятие жизненного цикла программного обеспечения и его модели
II. СТРУКТУРЫ ПРОГРАММИРОВАНИЯ
5. Выражения
6. Разветвление вычислений
7. Цикличные вычисления
8. Подпрограммы
9. Структуры данных
III. МЕТОДЫ ПРОГРАММИРОВАНИЯ
10. Методы программирования от состояний
11. Методы, основанные на рекурсии
12. Объектно-ориентированный подход
14. Функциональное программирование
15. Моделирование

PDF, 4 MB (4665216 bytes)
http://libgen.io/book/index.php?md5=86455917685a8881639118ff98fb3992

Предисловие i
I Базовые понятия 1
1. Введение в систему понятий программирования 3
1.1. Языки и системы программирования . . . . . . . . . . . 3
1.1.1. Сравнение программ на разных языках . . . . . . . . . 3
1.1.2. Язык, его реализация и среда программирования . . . . 6
1.2. Модель вычислений фон Неймана и традиционные языки . . 15
1.3. Базовые конструкции языка . . . . . . . . . . . . . . 37
1.3.1. Линейные программы и их компоненты . . . . . . . . 37
1.3.2. Не выполняемые вычислителем фрагменты программы 38
1.3.3. Подключение внешней информации (библиотек) . . . 39
1.3.4. Описания . . . . . . . . . . . . . . . . . . . . . 44
1.3.5. Действия . . . . . . . . . . . . . . . . . . . . . 46
1.4. Структура вычислений и структура текста программы . .48
1.4.1. Последовательное, параллельное и совместное исполнение . .48
1.4.2. Управление порядком вычислений . . . . . . . . . . . . 54
1.5. Работа со значениями . . . . . . . . . . . . . . . . . . . .59
2. Синтаксис, семантика и прагматика языка программирования 69
2.1. Синтаксис, семантика . . . . . . . . . . . . . . . . . . . 70
2.2. Прагматика . . . . . . . . . . . . . . . . . . . . . . . . 81
2.3. Абстрактное и конкретное представления программы . . . . . 86
2.3.1. Абстрактное представление . . . . . . . . . . . . . . . 86
2.3.2. Структура абстрактного синтаксиса . . . . . . . . . . . 88
2.3.3. Абстрактный вычислитель и абстрактная структура . . 93
2.3.4. Вызовы как пример синтаксических схем . . . . . . . . 99
2.4. Принципиальные трудности, связанные с семантикой . . . . . 100
3. Стили программирования, или программирование с птичьего полета 106
3.1. Стили программирования . . . . . . . . . . . . . . . . . . . . . 107
3.2. Программирование от состояний . . . . . . . . . . . . . . . . . 118
3.3. Структурное программирование — самый распространенный
стиль . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.4. Сентенциальное программирование . . . . . . . . . . . . . . . 132
3.5. Программирование от событий . . . . . . . . . . . . . . . . . . 135
3.6. Программирование от приоритетов . . . . . . . . . . . . . . . 142
3.7. Функциональное программирование . . . . . . . . . . . . . . . 147
3.8. Объектно-ориентированный подход . . . . . . . . . . . . . . . 151
3.9. Три технологических стиля программирования . . . . . . . . . 155
3.9.1. Программирование от переиспользования . . . . . . . 156
3.9.2. Программирование от образцов . . . . . . . . . . . . . 164
3.9.3. Специализирующее программирование . . . . . . . . . 167
3.10. Общие выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
4. Понятие жизненного цикла программного обеспечения и его модели 181
4.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
4.2. Модели традиционного представления о жизненном цикле . . 184
4.2.1. Общепринятая модель . . . . . . . . . . . . . . . . . . 184
4.2.2. Классическая итерационная модель . . . . . . . . . . . 186
4.2.3. Каскадная модель . . . . . . . . . . . . . . . . . . . . . 188
4.2.4. Модель фазы-функции . . . . . . . . . . . . . . . . . . 193
4.3. Итеративные модели жизненного цикла . . . . . . . . . . . . . 196
4.3.1. Базовые технологические принципы итеративного проектирования . . 199
4.3.2. Итеративная модификация модели фазы-функции . . . 202
4.3.3. Параллельное выполнение итераций . . . . . . . . . . 209
4.3.4. Моделирование итеративного наращивания возможностей системы . . 211
4.4. Требования к программному изделию и жизненный цикл . . . 214
4.4.1. Проблемы определения и анализа требований . . . . . 215
4.4.2. Трассировка требований . . . . . . . . . . . . . . . . . 218
4.4.3. Учет трассировки требований в модели жизненного
цикла . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
4.4.4. Особенности первой итерации . . . . . . . . . . . . . . 226
4.4.5. Фаза завершения . . . . . . . . . . . . . . . . . . . . . 231
4.5. Итоги и перспективы . . . . . . . . . . . . . . . . . . . . . . . 235
II Структуры программирования 244
5. Выражения 247
5.1. Операции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
5.2. Логические выражения . . . . . . . . . . . . . . . . . . . . . . 252
5.3. Приоритет операций . . . . . . . . . . . . . . . . . . . . . . . . 260
6. Разветвление вычислений 269
6.1. Разбор случаев . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
6.1.1. Цепочка условий . . . . . . . . . . . . . . . . . . . . . 269
6.1.2. Переключение . . . . . . . . . . . . . . . . . . . . . . . 273
6.1.3. Типы данных, связанные с разветвлением . . . . . . . 278
6.2. Табличное задание разветвлений и оператор выбора Дейкстры 281
6.2.1. Таблицы решений . . . . . . . . . . . . . . . . . . . . 281
6.2.2. Охраняемые команды . . . . . . . . . . . . . . . . . . . 283
6.2.3. Условные выражения . . . . . . . . . . . . . . . . . . . 285
7. Циклические вычисления 287
7.1. Мотивация циклических вычислений . . . . . . . . . . . . . . 287
7.2. Потоковая обработка . . . . . . . . . . . . . . . . . . . . . . . 292
7.2.1. Порождение элементов потока . . . . . . . . . . . . . . 293
7.2.2. Фильтрация потока . . . . . . . . . . . . . . . . . . . . 297
7.2.3. Потоки и данные . . . . . . . . . . . . . . . . . . . . . 300
7.2.4. Потоки и цикл for . . . . . . . . . . . . . . . . . . . . . 326
7.3. Логическая структура цикла . . . . . . . . . . . . . . . . . . . 329
7.3.1. Инвариант и параметры цикла . . . . . . . . . . . . . . 329
7.3.2. Цикл Дейкстры и цикл-‘паук’ . . . . . . . . . . . . . . 332
7.3.3. Совместный цикл . . . . . . . . . . . . . . . . . . . . . 333
7.3.4. Входные и выходные потоки. Сопрограммы . . . . . . 335
7.3.5. Понятие обстановки вычислений. Действия, меняющие обстановку . . 343
7.4. Абстрактно-синтаксическое представление циклов . . . . . . 347
7.4.1. Представление циклов . . . . . . . . . . . . . . . . . . 347
7.4.2. Структурные переходы . . . . . . . . . . . . . . . . . . 348
7.4.3. Исключения . . . . . . . . . . . . . . . . . . . . . . . . 358
8. Подпрограммы 362
8.1. Виды подпрограмм . . . . . . . . . . . . . . . . . . . . . . . . 364
8.2. Именование процедур . . . . . . . . . . . . . . . . . . . . . . . 371
8.3. Контексты и обстановки. Локализация имен . . . . . . . . . . 377
8.4. Вызов процедуры . . . . . . . . . . . . . . . . . . . . . . . . . 390
8.4.1. Семантика вызова процедуры . . . . . . . . . . . . . . 390
8.4.2. Статическая и динамическая цепочки . . . . . . . . . . 393
8.4.3. Понятие экземпляра процедуры . . . . . . . . . . . . . 396
8.5. Параметризация . . . . . . . . . . . . . . . . . . . . . . . . . . 400
8.5.1. Назначение параметризации . . . . . . . . . . . . . . . 400
8.5.2. Полиморфизм и вызовы с переменным числом параметров . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
8.5.3. Механизмы передачи параметров . . . . . . . . . . . . 410
8.5.4. Рекомендации по использованию параметров . . . . . 426
8.5.5. Параметры-процедуры и параметры-функции. Процедурный тип . . . . 437
8.6. Развитие языковых средств модульности в языках линии Turbo
Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
8.6.1. Поддержка модульности в стандартном языке Pascal . 447
8.6.2. Модули в TURBO-системах программирования . . . . 453
8.6.3. Пример использования модуля . . . . . . . . . . . . . . 458
8.7. Рекурсивные программы . . . . . . . . . . . . . . . . . . . . . 463
8.7.1. Сопоставление итеративной и рекурсивной схем . . . 465
8.7.2. Рекурсия через параметры . . . . . . . . . . . . . . . . 469
8.7.3. Пример для самостоятельного анализа . . . . . . . . . 472
8.8. Процедуры в разных моделях вычислений . . . . . . . . . . . 475
9. Структуры данных 482
9.1. Общие концепции структурирования данных . . . . . . . . . . 482
9.1.1. Структура программы и структуры данных . . . . . . . 482
9.1.2. Базовые структуры данных и конструкторы структур . 485
9.1.3. Операции над вновь определяемыми типами данных . 488
9.1.4. Типизация и стили . . . . . . . . . . . . . . . . . . . . 493
9.1.5. Абстрактные типы данных . . . . . . . . . . . . . . . . 494
9.2. Базовые и выводимые типы . . . . . . . . . . . . . . . . . . . . 499
9.2.1. Перечисления . . . . . . . . . . . . . . . . . . . . . . . 499
9.2.2. Булевский тип . . . . . . . . . . . . . . . . . . . . . . . 501
9.2.3. Тип литерных . . . . . . . . . . . . . . . . . . . . . . . 501
9.2.4. Тип целых . . . . . . . . . . . . . . . . . . . . . . . . . 502
9.2.5. Вещественные типы . . . . . . . . . . . . . . . . . . . 504
9.3. Структурные типы . . . . . . . . . . . . . . . . . . . . . . . . . 508
9.3.1. Наборы компонент . . . . . . . . . . . . . . . . . . . . 510
9.3.2. Записи . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
9.3.3. Объединения . . . . . . . . . . . . . . . . . . . . . . . . 519
9.3.4. Массивы . . . . . . . . . . . . . . . . . . . . . . . . . . 524
9.3.5. Множества . . . . . . . . . . . . . . . . . . . . . . . . . 534
9.4. Рекурсивные структуры данных . . . . . . . . . . . . . . . . . 541
9.4.1. Списочные структуры . . . . . . . . . . . . . . . . . . 544
9.4.2. Указательные типы . . . . . . . . . . . . . . . . . . . . 547
9.4.3. Специальные рекурсивные структуры . . . . . . . . . . 550
9.4.4. Деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . 552
III Методы программирования 555
10. Методы программирования от состояний 560
10.1. Основные структуры программирования от состояний . . . . 561
10.2. Задача подсчета длин слов текста и задание конечного автомата561
10.2.1. Постановка задачи и первичный анализ . . . . . . . . . 561
10.2.2. Построение графа состояний . . . . . . . . . . . . . . . 563
10.2.3. Табличное представление графа состояний конечного
автомата . . . . . . . . . . . . . . . . . . . . . . . . . . 567
10.2.4. Ручная трансляция диаграмм переходов . . . . . . . . 572
10.2.5. Представления, ориентированные на автоматические
преобразования диаграмм переходов . . . . . . . . . . 579
10.2.6. Обсуждение решения . . . . . . . . . . . . . . . . . . . 588
10.3. Синтаксические таблицы . . . . . . . . . . . . . . . . . . . . . 593
10.3.1. Расширение сферы применения конечных автоматов:
анализатор как система связанных конечных автоматов 593
10.3.2. Задача анализа простых выражений . . . . . . . . . . . 595
10.3.3. Синтаксические таблицы и рекурсивный спуск . . . . 601
10.3.4. Преобразования грамматики, сохраняющие язык. Вычислительная мощность синтаксических таблиц . . 604
10.3.5. Построение графа состояний . . . . . . . . . . . . . . . 607
10.4. Диаграммы состояний и переходов. Их связь с математическими моделями . . . . . . . 609
10.5. Программные представления графа состояний . . . . . . . . . 612
10.5.1. Требования к автоматической трансляции таблиц . . . 613
10.5.2. Языки разметки и автоматическая трансляция таблиц . 614
10.5.3. Автоматное преобразование структурированных текстов617
10.6. Переход от данных к конечному автомату . . . . . . . . . . . . 625
11. Методы, основанные на рекурсии 634
11.1. Механизмы рекурсии . . . . . . . . . . . . . . . . . . . . . . . 635
11.2. Закрашивание замкнутых областей . . . . . . . . . . . . . . . 641
11.3. Переборные алгоритмы и рекурсия . . . . . . . . . . . . . . . 645
11.3.1. Перебор/генерация вариантов с возвратами . . . . . . 646
11.4. Лабиринт . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661
11.4.1. Блуждание по лабиринту и закраска области . . . . . . 662
11.4.2. Абстрактное и конкретное представления данных . . . 664
11.4.3. Абстрактное представление лабиринта . . . . . . . . . 666
11.4.4. Поиск пути в лабиринте . . . . . . . . . . . . . . . . . 673
11.5. Рекурсия при обработке символьной информации . . . . . . . 684
11.6. Рекурсия в транслирующих программах . . . . . . . . . . . . . 690
11.6.1. Синтаксический распознаватель простых выражений . 690
11.6.2. Метод рекурсивного спуска . . . . . . . . . . . . . . . 692
11.6.3. Обратная польская запись выражений: понятие, алгоритмы вычисления и построения . . 699
12. Объектно-ориентированный подход 708
12.1. Объекты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 708
12.1.1. Объекты как структуры данных и права доступа . . . . 709
12.1.2. Наследование и полиморфизм . . . . . . . . . . . . . . 714
12.1.3. Множественное наследование и интерфейсы . . . . . . 718
12.2. Объектная модульность . . . . . . . . . . . . . . . . . . . . . . 722
13. Сентенциальные методы 728
13.1. Конкретизация . . . . . . . . . . . . . . . . . . . . . . . . . . . 729
13.1.1. Структура данных . . . . . . . . . . . . . . . . . . . . . 729
13.1.2. Модель вычислений и Рефал-программа . . . . . . . . 733
13.1.3. Дополнительные возможности . . . . . . . . . . . . . . 739
13.1.4. Развитие языка и его диалекты . . . . . . . . . . . . . . 744
13.2. Унификация . . . . . . . . . . . . . . . . . . . . . . . . . . . . 746
13.2.1. Общие концепции . . . . . . . . . . . . . . . . . . . . . 746
13.2.2. Поле зрения, поле памяти и PROLOG-программа . . . 751
13.2.3. Управление исполнением программы . . . . . . . . . . 755
13.2.4. Динамическое пополнение и порождение программы . 762
13.3. Языки разметки . . . . . . . . . . . . . . . . . . . . . . . . . . 765
13.3.1. TEX и L ATEX . . . . . . . . . . . . . . . . . . . . . . . . . 765
13.3.2. Языки разметки для Internet . . . . . . . . . . . . . . . 774
13.4. Применения сентенциального программирования . . . . . . . 787
13.4.1. Аналитические преобразования . . . . . . . . . . . . . 787
13.4.2. Сентенциальные методы в традиционных языках . . . 788
14. Функциональное программирование 791
14.1. Структура данных . . . . . . . . . . . . . . . . . . . . . . . . . 791
14.2. Модель вычислений . . . . . . . . . . . . . . . . . . . . . . . . 793
14.3. Объекты и LISP . . . . . . . . . . . . . . . . . . . . . . . . . . 800
15. Моделирование 805
15.1. Модели и вычисления . . . . . . . . . . . . . . . . . . . . . . . 808
15.2. Моделирование времени . . . . . . . . . . . . . . . . . . . . . 810
15.3. Информационные системы с временем . . . . . . . . . . . . . 811
15.4. Моделирование и информационные системы . . . . . . . . . . 814
15.4.1. Информационное обеспечение моделирования . . . . . 816
15.4.2. Информационные системы для моделей принятия решений . . . . 817
15.5. Системы с дискретными событиями . . . . . . . . . . . . . . . 819
15.6. UML-моделирование и RUP . . . . . . . . . . . . . . . . . . . 829
16. Подведение итогов 831
A. Математические модели 837
A.1. Несколько терминов . . . . . . . . . . . . . . . . . . . . . . . . 837
A.2. Вычислительные интерпретации . . . . . . . . . . . . . . . . . 839
A.3. Модели Янова . . . . . . . . . . . . . . . . . . . . . . . . . . . 844
A.4. Автоматы и машины Тьюринга . . . . . . . . . . . . . . . . . . 845
A.5. Алгоритмы над структурами . . . . . . . . . . . . . . . . . . . 848
A.6. Рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 849
A.7. Совместность и параллелизм . . . . . . . . . . . . . . . . . . . 860
B. Методологические результаты 863
B.1. Логические парадоксы . . . . . . . . . . . . . . . . . . . . . . 863
B.2. Теоремы Тарского и Геделя . . . . . . . . . . . . . . . . . . . . 866
B.3. Идеальные и реальные понятия по Гильберту . . . . . . . . . . 867
B.4. Парадокс изобретателя . . . . . . . . . . . . . . . . . . . . . . 868
B.5. Типы и порядки . . . . . . . . . . . . . . . . . . . . . . . . . . 869
B.6. Чистые теоремы существования . . . . . . . . . . . . . . . . . 870
B.7. Доказательства и программы . . . . . . . . . . . . . . . . . . . 872
B.8. Основные понятия неформализуемости . . . . . . . . . . . . . 874
C. Знания, данные, умения 877
C.1. Анализ понятий . . . . . . . . . . . . . . . . . . . . . . . . . . 877
C.2. Уровень насекомого . . . . . . . . . . . . . . . . . . . . . . . . 879
C.3. Стереотипное реагирование . . . . . . . . . . . . . . . . . . . 880
C.4. Тупость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 882
C.5. Комбинационное (комбинаторное) планирование . . . . . . . . 882
C.6. Глупость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 884
C.7. Стратегическое планирование и преобразование действий . . 885
C.8. Релятивизм . . . . . . . . . . . . . . . . . . . . . . . . . . . 887
C.9. Владение методом . . . . . . . . . . . . . . . . . . . . . . . . 888
C.10. Умничанье, мессианство . . . . . . . . . . . . . . . . . . . . . 889
C.11. Многоуровневое мышление . . . . . . . . . . . . . . . . . . . . 890
C.12. Мудрствование, интуитивизм . . . . . . . . . . . . . . . . . . 891
C.13. Дао . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 891
C.14. Лжепророки . . . . . . . . . . . . . . . . . . . . . . . . . . 891
C.15. Химеры и вымыслы . . . . . . . . . . . . . . . . . . . . . . . 892