Лекция 4. Работа в программировании. Уровни языков программирования. Метрика числа ошибок в программе.

Работа в программировании

Если мы ограничим понятие работы в программировании умственной деятельностью, затрачиваемой на превращение заранее разработанного алгоритма в реализацию на языке, которым исполнитель свободно владеет, то метрические характеристики и понятия, введенные выше, дадут нам возможность проникнуть в суть процесса программирования и образуют исходную систему для его количественной оценки. Простое соотношение между этими метрическими характеристиками и работой, выполняемой программистом, может быть получено с помощью шести шагов, описанных ниже в общих чертах.

Вывод уравнения работы

1. Как и ранее, допустим, что любая реализация какого­­-либо алгоритма заключается в N­-кратном выборе из словаря, состоящего из h элементов.

2. Предположим далее, что каждый выбор из словаря h неслучаен. Исследования методов сортировки показали, что, за исключением хеширования, самым быстрым способом поиска в упорядоченном списке является двоичный поиск, при котором список многократно делится пополам до тех пор, пока не будет найден нужный элемент. Полученное в результате число сравнений равно двоичному логарифму числа элементов в списке. Следовательно, эффективный процесс, эквивалентный двоичному поиску , требует log₂h сравнений для нахождения элемента.

3. На основании шагов 1 и 2 можно заключить, что программа порождается выполнением N ´ log₂h мысленных сравнений.

4. Поскольку объем программы V определяется как

V = N log₂h, (4.1)

из шага 3 следует, что он равен числу мысленных сравнений, затрачиваемых на порождение программы.

5. Каждое мысленное сравнение содержит ряд элементарных мысленных различений, число которых является мерой сложности задачи. Из предыдущих результатов вытекает, что именно уровень программы L является величиной, обратной ее сложности.

6. Так как объем V равен числу мысленных сравнений, а величина, обратная уровню программы, т.е. 1/L, есть среднее число элементарных мысленных различений, входящих в каждое мысленное сравнение, общее число элементарных мысленных различений Е, требуемых для порождения программы, должно задаваться выражением

Е = (4.2)

Можно выявить более глубокий смысл уравнения работы, если вспомнить уравнение (3.1)

L =

и подставить его в уравнение (4.2)

E = (4.3)

Уравнение (4.3) показывает, что мысленная работа по реализации любого алгоритма с данным потенциальным объемом в каждом языке пропорциональна квадрату объема программы. Как будет детально показано далее, из уравнения (4.3) следует, что, так как «квадрат суммы больше суммы двух квадратов», правильное разбиение на модули может уменьшить работу по программированию реализаций, разбитых на отдельные части. Теперь перейдем от подсчета элементарных мысленных различений к измерению времени.