Предисловие к русскому изданию............. 7
Предисловие......................10
ЧАСТЬ I. ОСНОВНЫЕ СВОЙСТВА И ИХ ОТНОШЕНИЯ.....13
Глава 1. Введение..................13
Идеализированный программный цикл 9 Координаты. 9 Измеримые свойства алгоритмов 9 Пример . Алгоритм Евклида
Глава 2. Длина программы..............20
Проверка уравнения длины* Обоснование уравнения длины для больших выборок 9 Независимое обоснование для длинных программ 9 Обоснование для частей программ
Глава 3. Объем программы............... 30
Потенциальный объем V*
Г л а в а 4. Соотношения между операторами и операндами 32
Глава 5. Уровень программы............. 35
Вывод уравнения уровня программы 9 Обоснование уравнения уровня программы
Глава 6. Квантификация интеллектуального содержания 41 Глава 7. Совершенство программы..........47
Классы несовершенств е Дополняющие друг друга операции (несовершенство I) • Неоднозначные операнды (несовершенство II) в Синонимичные операнды (несовершенство 111) 9 Общие подвыражения (несовершенство IV) 9 Ненужное присваивание (несовершенство V) о Выражения, не представленные в виде произведения множителей (несовершенство VI) 9 Значение несовершенств
Глава 8. Работа в программировании.........55
Вывод уравнения работы 9 Различения в единицу времени 9 Экспериментальное обоснование соотношения времени программирования • Экспери мент по времени программирования (серия 1) 9 Эксперимент по времени программирования (серия 2) 9 Аппроксимация уравнения времени, если известна только длина 9 Обоснование аппроксимации для программирования в машинном коде
Г л а в а 9. Уровень языка................70
, Обоснование соотношения для языка 9 Влияние размера блока |3 на уровень языка А е Изменения уровняет языка к языку • Значение уровня языка
5
ЧАСТЬ 1Г. ПРИЛОЖЕНИЯ ТЕОРИИ ПРОГРАММ ........ 79
Глава 10. Определение длины и времени программирования по начальным условиям........79
Определение % по т|| и Л • Определение словаря и длины программы по г\* и Я, • Определение работы и времени программирования по г\, и К
Глава 11. Гипотеза ошибок..............87
Вывод уравнения ошибок • Обоснование уравнения ошибок с помощью данных Белла и Салливе-на • Обоснование уравнения ошибок с помощью данных Акиямы
Глава 12. Модульность.................95
Приравнивание длины • Минимизация потенциального объема модулей • Модули как программы без ошибок • Размер модулей из объектов
Глава 13. Количественный анализ английской прозы . . . 102
Выделение операторов и операндов в английской прозе • Определение количества избыточности • Выбор научной прозы
Глава 14. Приложения к аппаратному обеспечению . . .117 Эмпирическое соотношение • Программная гипотеза схем
Глава 15. Приложения к определению размера операционной системы..................121
Вывод уравнения размера системы • Сравнение гипотезы размеров с известными данными
Литература.........................125
ПРЕДИСЛОВИЕ К РУССКОМУ ИЗДАНИЮ
Предлагаемая советскому читателю книга М. X. Холстеда «Начала науки о программах» впервые обобщает материалы исследований, посвященных в основном сбору фактического материала и в гораздо меньшей степени — подытоживанию и сравнению результатов. Все более или менее близкие по тематике работы, опубликованные у нас в стране и за рубежом, лишь отчасти касались развитого автором направления в изучении программ.
Метрическая теория программ М. X. Холстеда исходит из статистического выражения алгоритма на конкретном языке программирования, поскольку лишь программы в машинном коде представляют собой «динамическое» исключение — они могут быть непосредственно выполнены. Все же остальные выражения, или реализации, алгоритмов должны исследоваться в первую очередь по их текстуальным представлениям. Исходя из простых и естественных комбинаторных соображений, а также учитывая структурные особенности исследуемых языков программирования и текстов написанных на них программ, М. X. Холстед получает пригодные для практического использования соотношения между основными метрическими характеристиками.
Первая часть книги посвящена изложению собственно метрической теории программ. Здесь приводятся основные определения и находятся соотношения между программными параметрами. Автор выводит формулы для длины программы (гл. 2) и ее объема (гл. 3), получает важные для дальнейшего изложения соотношения между операторами и операндами, составляющими словарь программы (гл. 4). В гл. 5 даются практические рекомендации по вычислению
