65. Сравнение программ.

Цель: Большинство задач можно решить несколькоми способами. Эти способы могут различаться по сложности, требуемым ресурсам и многим другим парамметрам. Поэтому перед программистом стоит задача в выборе одного способа или алгоритма решения поставленной задачи. Из этого вытекает проблема сравнения эквивлоентности программ: вызывают ли программы вычисления, приводящие к одним и тем же результатам.

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

Пример1:

if B2 then begin while B1 do S1 end

else begin while B1 do S2 end

Пример2:

while B1 do begin if B2 then S1

else S2 end

Для программ (1) и (2) можно доказать эквиволентность результатов вычислений, но сравнивать вычисления этих двух программ либо сравнивать по каким-либо другим параметрам - затруднительно.

Поэтапное составление программ: Суть метода в составлении программы мелкими шагами, принимая на каждом этапе как можно меньше решений. Рассмотрим на примере программы, находящей n простых чисел.

(0)

begin "написать n простых чисел" end,

но ее надо разбить на набор более простых команд.

(1)

begin

"заполнить таблицу P простыми числами"

"вывести элементы таблицы P"

end

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

(2)

begin "присвоить p и j начальные значения"

while "таблица p не заполнена" do

begin "присвоить j значение следующего простого числа"; добавить j к p;

end

end

"вывести элементы таблицы p"

end

Далее происходит разбиние поиска следующего простого числа на более мелкие задачи и т.д.

66. Структурная организация данных.

Отправной момент абстракции заключается в фиксировании сходства некоторых объектов, ситуаций или процессов реального мира и решении выделить сходные свойства, временно оставляя в стороне различия.

В процессе абстрагирования выделяются следующие четыре этапа:

• Абстракция: решение сосредоточиться на свойствах, являющихся общими для многих объектов и ситуаций реального мира, отвлекаясь от существующих между ними различий.

• Представление: выбор некоторого множества символов для изображения абстрактных понятий; представление можно использовать в качестве средства общения.

• Манипуляция: правила преобразования символического представления как средство предсказания результата аналогичных манипуляций в реальном мире.

• Аксиоматизация: строгая формулировка тех свойств, кото-рые были выделены из реального мира и которые являются общими при манипуляциях как в реальном мире, так и над символами, пред-ставляющими реальный мир.

Чиста и цифры

Для изображения чисел используются символы, называемые цифрами (двоичное представление числа).

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

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

Абстракция и программирование для вычислительной машины

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

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

Этап аксиоматизации обычно не считается в программировании самостоятельной фазой и часто подразумевается неявно

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

Важнейшей особенностью этого метода программирования является то, что фактическое кодирование программы производится лишь тогда, когда (почти) нет сомнений, что во всех остальных отношениях программа разработана правильно. Так как кодирование и отладка программы обыкновенно самый дорогостоящий этап ее разработки, внесение изменений в программу на этом этапе крайне нежелательно.

Абстракция в языках программирования высокого уровня

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

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

Большим достоинством является и то, что при использовании языка высокого уровня значительно уменьшается объем элементарных ошибок программирования.

При разработке языков высокого уровня нужно стремиться к тому, чтобы большинство ошибок программирования стало либо логически невозможным, либо могло быть обнаружено компилятором.

Язык программирования высокого уровня позволяет программисту описать типы значений переменных, которые он намеревается использовать, и таким образом специфицировать смысл допустимых операций над значениями этого типа. Теперь компилятору сравнительно нетрудно проверить согласованность конструкций программы, не допуская появления ошибок в рабочей программе.

Система обозначений

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

Понятие типа

Отличительными особенностями понятия типа являются следующие:

(1) Тип определяет класс значений, которые могут принимать переменная или выражение.

(2) Каждое значение принадлежит одному и только одному типу.

(3) Тип значения константы, переменной или выражения можно вывести либо из контекста, либо из вида самого операнда, не обращаясь к значениям, вычисляемым во время работы программы.

(4) Каждой операции соответствует некоторый фиксированный тип ее операндов и некоторый фиксированный (обычно такой же) тип результата. В случае когда к различным в отношении типа операндам применяется один и тот же символ (например, + для сложения как целых, так и действительных величин), можно считать, что этот символ многозначен и что он обозначает несколько различных операций.

(5) Для каждого типа свойства значений и элементарных операций над значениями задаются с помощью аксиом.

(6) При работе с языком высокого уровня знание типа позволяет обнаруживать в программе бессмысленные конструкции и решать вопрос о методе представления данных и преобразования их в вычислительной машине.

(7) Интересующие нас типы — это прямые произведения, размеченные объединения, множества, функции, последовательности и рекурсивные структуры.

Определение типов данных

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

Количество различных значений некоторого типа называется его мощностью.