40гг первые цифровые компьютеры программирование путем коммутации проводов

Вид материала

Содержание

Р=>{r}s{q}) = ({r}s{q}) = ({р&r}s{q})
Примеры использования правила вывода для оператора присваивания
Определение абстрактного типа данных
Объектно-ориентированное программирование

Подобный материал:

1 2 3 4 5 6 7 8 9 ... 12

{P} S {true}

{false} S {Q}

Правила замены

Для доказательства правил достаточно рассмотреть два случая:

P=true:

(Р=>{R}S{Q}) = ({R}S{Q}) = ({Р&R}S{Q})

P=false:

(Р =>{R}S{Q}) = true = ({false} S {Q}) =

=({P&R}S{Q})

В

ыражения

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

- если первый операнд в выражении (A and В) ложен, то и значение всего выражения ложно независимо от значения второго операнда.
- если первый операнд в выражении (A оr В) истинен, то и значение всего выражения истинно независимо от значения второго операнда.

Следовательно, вычислять значение второго операнда в этих случаях не надо.

Операторы действия

Операторы действия — это средства языка, позволяющие изменять в процессе выполнения программы состояние вычислений.
Самый простой оператор действия — оператор присваивания:

Х:=Е;

где X — переменная или другой допустимый объект данных, а Е — выражение соответствующего типа.

Правило вывода для оператора присваивания

Здесь утверждается, что если Р истинно для подстановки Е вместо X перед выполнением присваивания, то Р должно быть истинно после присваивания переменной X ее нового значения Е.

римеры использования правила вывода для оператора присваивания

Операторы управления

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

Оператор последовательного выполнения

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

Достаточно иметь правило для N=2

Условные операторы

Условные операторы позволяют выбирать для выполнения те или иные части программы в зависимости от некоторых условий.
Пусть В — логическое выражение (т.е. выражение, тип значения которого есть boolean), S1 , S2 — последовательности операторов (в крайнем случае один оператор). Тогда оператор

if В then

Si

else

S2

end if;

означает следующее: вычисляется В; если его значение истинно (true), то выполняется S , в противном случае — S2.

Правило вывода для условного оператора

Построим правило вывода для условного оператора. Если требуется установить истинность спецификации

{P} if В then S1 else S2 end if; {Q}

то необходимо доказать два утверждения:

Если В истинно, то выполняется S1. Так как Р
справедливо перед выполнением if, делаем вывод, что в
этом случае Р & В справедливо перед выполнением S1. Если Q справедливо после выполнения if, то должно быть
справедливо и {Р & В} S1{Q}. Итак, мы должны доказать {Р & В} S1 {Q} .
2. Если В ложно, то выполняется S2. Так как Р
справедливо перед выполнением if, делаем вывод, что в
этом случае Р & not В справедливо перед выполнением S2. Если Q справедливо после выполнения if, то должно быть справедливо и {Р & not В} S2 {Q} Итак, мы должны доказать {Р & not B> S2 {Q} .

Если мы доказали истинность {P&B}S1{Q} и {Р & not В} S2 {Q}, то можно утверждать, что если Р справедливо перед выполнением if, то Q будет справедливо по окончании его выполнения независимо от того, какой оператор (S1 или S2) был выбран для выполнения.

Операторы цикла

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

while В do

S end do;

называется оператором цикла while do, логическое выражение В — условием цикла, а последовательность операторов S — телом цикла.
Цикл while do означает повторное выполнение S, пока В истинно:

сначала вычисляется В; если его значение ложно (false), то выполнение цикла заканчивается, в противном случае выполняется S;
после чего снова вычисляется значение В и т.д.
Таким образом, если В ложно с самого начала, то S не будет выполняться ни разу.

Правило вывода для оператора while do

Пусть существует такой предикат Р, что

{Р & В} S {Р}

Пусть этот предикат истинен перед выполнением цикла. Тогда если в тот же момент истинно и В, то перед выполнением S будет истинным и Р & В. Но тогда после выполнения S опять будет истинным Р. Если при этом В снова истинно, то получаем еще раз истинным Р & В перед новым выполнением S и т.д. Иными словами, Р остается истинным после каждой итерации, поэтому он называется инвариантом цикла.
Предикат Р остается истинным и при завершении цикла, когда становится ложным В.

Оператор цикла for

Пусть S(X) — последовательность операторов, при выполнении которых используется значение переменной X (и оно не изменяется). Часто необходимо выполнить S(X) для всех возможных значений X, например для всех элементов заданного массива. Для этого используется оператор цикла for:

for X: тип do

S(X) end do;

Множество значений указанного типа должно быть конечно. В качестве типа переменной X может быть указан анонимный подтип, например

for X: integer range 1..10 do

S(X) end do;

Допустимы также сокращения вида

for X: 1.. 10 do

S(X) end do;

Считается, что для этого оператора переменная X локальна, т.е. она создается в начале его выполнения и уничтожается в конце (ее не надо описывать где-либо в другом месте программы).
Поэтому приведенный оператор полностью эквивалентен следующей последовательности:
S(v1) S(v2) ... S(vn)
где v1,v2,…,vn - множество значений указанного типа.
Во многих случаях важен порядок перечисления этих значений. Обычно полагается, что v’тип'SUCC(vi-1) для i=2,3,...,n (т.е. тип должен быть целым или перечислимым) и V1=тип' FIRST, Vn=тип' LAST.

Получение правила вывода

Правило вывода для цикла for

Пример доказательства программ с последовательным выполнением операторов

Рассмотрим программу

X:=X+2;

X:=X*2;

Докажем ее правильность

Для этого нужно доказать, что после выполнения программы X = (X+2)*2;

На начальное значение X не накладывается ограничений.

Значит

Предусловие программы P = {X=a};

Постусловие программы Q = {X=(a+2)*2}

Программа S = (X:=X+2;X:=X*2)

Обозначим

S1 = (X :=X+2)

S2 = (X :=X*2)

и воспользуемся правилом вывода для оператора последовательного выполнения

2

2 семестр

Объектно-ориентированное программирование

Основные вопросы

Основные понятия объектно-ориентированного программирования
Объектно-ориентированное программирование на C++
Дополнительные средства создания классов в С++

Множественное наследование
Шаблоны классов

Поколения языков

Первое поколение - языки с минимальными возможностями типизации

Предоставляют лишь средства для описания переменных простых типов и массивов; никаких новых типов вводить нельзя.
Фортран, Алгол-60.

Второе поколение – языки, предоставляющие программисту основные конструкторы типов: массивы, записи, объединения

ПЛ/1, Алгол-68, Паскаль, С
Тип рассматривается как множество значений, получаемых из базисных множеств с помощью конструкторов.
Все операции над типами данных предопределенные — определяемые языком, а не программистом.
Новые типы могут получать имена, но с ними нельзя связывать новых, специально вводимых операций.

Третье поколение – языки, предоставляющие программисту средства определения абстрактных типов данных

С++, C#, Java
Типы понимаются как множества с операциями.

Понятие абстракции

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

Определение абстрактного типа данных

Абстрактный тип данных — это способ определения некоторого понятия в виде класса объектов с некоторыми свойствами и операциями.
Так как свойства обычно выражаются в терминах операций, то абстрактный тип данных часто отождествляют с соответствующим множеством операций.
Например:

определение понятия стека в терминах операций " втолкнуть элемент в стек", " создать новый стек", "выдать верхний элемент" и т.д.

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

Объектно-ориентированное программирование

Идея абстрактных типов данных является основой объектно-ориентированного программирования (ООП).

Основные принципы ООП были разработаны еще в языках Simula-67 и Smaltalk, но в то время не получили распространения из-за сложности освоения и низкой эффективности реализации.
В С++ концепции ООП реализованы эффективно и непротиворечиво, что явилось основой успешного распространения как языка, так и концепции ООП.

ООП – не просто набор новых средств, добавленных в язык

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

ООП – новая парадигма программирования

Понятие парадигмы ООП

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

Выбор степени абстракции

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

Абстрактные типы данных и ООП

Переменные абстрактного типа данных называются «объектами» или «экземплярами» данного типа данных (применительно к С++ «экземплярами класса»).
Объекты взаимодействуют между собой посылая и получая сообщения.
Сообщение – это запрос на выполнения некоторого действия, содержащий необходимые параметры.
Механизм сообщений реализуется с помощью вызова операций, включенных в абстрактный тип данных.

Основные свойства ООП

Инкапсуляция
Наследование
Полиморфизм

Инкапсуляция

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

Наследование

Наследование – это возможность создания иерархии типов данных, когда потомки наследуют все свойства своих предков, могут их изменять и добавлять новые.
Имеющиеся свойства повторно не описываются, что сокращает объем программы.
Выделение общих черт различных типов данных в один тип данных - предок является мощным механизмом абстракции.
Иерархия типов данных представляется в виде древовидной структуры в которой более общие типы располагаются ближе к корню, а более специализированные – на ветвях и листьях.

Пример иерархии типов данных

Полиморфизм

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

Пример полиморфизма

Объявим переменную X типа «Аналитик».

Объект X является как экземпляром класса «Аналитик» так и экземпляром

классов «Сотрудник ФСБ», «Военнослужащий», «Гражданин»

Преимущества и недостатки ООП

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

ООП в С++

Абстрактные типы данных в С++ создаются с помощи синтаксической конструкции называемой «классом».
Классы позволяют программисту на С++ воспользоваться всеми свойствами ООП (инкапсуляция, наследование и полиморфизм)

Инкапсуляция в С++

Спецификация класса в С++

class имя_класса{

модификатор_доступа:

[атрибуты]

[методы]

модификатор_доступа:

[атрибуты]

[методы]

…

};

Модификаторы доступа

private
public
protected

Пример использования класса для реализации понятия даты

class date{

private:

int month, day, year;

public:

void set(int, int, int);

void get(int*, int*, int*);

void next();

void print();

};

Простое наследование в C++

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

class имя:

[private|protected|public] базовый_класс

{

тело класса

};

По умолчанию для классов используется ключ доступа private
Простым называется наследование, при котором производный класс имеет одного родителя.

Доступ к элементам базового класса

Ключ доступа	Спецификатор в базовом классе	Доступ в производном классе
private	private protected public	нет
private	private protected public	private private
protected	private protected public	нет protected protected
protected	private protected public
public	private protected public	нет protected public

Пример простого наследования

class date{

private:

int month, day, year;

public:

void set(int, int, int);

void get(int*, int*, int*);

void next();

void print();

};

…

date d;

d.day = 15; // Ошибка!

d.set(2006,1,1);

d.print();

Blog

40гг первые цифровые компьютеры программирование путем коммутации проводов

Содержание