Инвариант (программирование)
Инвариа́нтом в программировании называется логическое выражение, истинное после каждого прохода тела цикла (после выполнения фиксированного оператора) и перед началом выполнения цикла, зависящее от переменных, изменяющихся в теле цикла. [1]
Инварианты используются в теории верификации программ для доказательства правильности выполнения цикла. Порядок доказательства работоспособности цикла с помощью инварианта сводится к следующему:
- Доказывается, что выражение инварианта истинно перед началом цикла.
- Доказывается, что выражение инварианта сохраняет свою истинность после выполнения тела цикла; таким образом, по индукции, доказывается, что по завершении цикла инвариант будет выполняться.
- Доказывается, что при истинности инварианта после завершения цикла переменные примут именно те значения, которые требуется получить (это элементарно определяется из выражения инварианта и известных конечных значениях переменных, на которых основывается условие завершения цикла).
- Доказывается (возможно — без применения инварианта), что цикл завершится, то есть условие завершения рано или поздно будет выполнено.
- Истинность утверждений, доказанных на предыдущих этапах, однозначно свидетельствует о том, что цикл выполнится за конечное время и даст желаемый результат.
Также инварианты используют при проектировании и оптимизации циклических алгоритмов. Например, чтобы убедиться, что оптимизированный цикл остался корректным, достаточно доказать, что инвариант цикла не нарушен и условие завершения цикла достижимо.
Понятие инварианта также используется в объектно-ориентированном программировании для обозначения непротиворечивого состояния объекта. Подразумевается, что вызов любого метода оставляет объект в состоянии инварианта.
Примечания
- ↑Построение цикла с помощью инварианта
- Формальные методы
Wikimedia Foundation . 2010 .
- Инвариант (математика)
- Инвариант (физика)
Полезное
Смотреть что такое «Инвариант (программирование)» в других словарях:
- Инвариант — или инвариантность термин, обозначающий нечто неизменяемое. Конкретное значение термина зависит от той области, где он используется: Инвариант (математика) Инвариант узла в топологии Инвариант (физика) Инвариант (программирование) Инвариант … Википедия
- ПРОГРАММИРОВАНИЕ ТЕОРЕТИЧЕСКОЕ — математическая дисциплина, изучающая математич. абстракции программ, трактуемых как объекты, выраженные на формальном языке, обладающие определенной информационной и логич. структурой и подлежащие исполнению на автоматич. устройствах. П. т.… … Математическая энциклопедия
- Конструктор (программирование) — У этого термина существуют и другие значения, см. Конструктор. В объектно ориентированном программировании конструктор класса (от англ. constructor, иногда сокращают ctor) специальный блок инструкций, вызываемый при создании объекта.… … Википедия
- ДРАКОН — Эта статья предлагается к удалению. Пояснение причин и соответствующее обсуждение вы можете найти на странице Википедия:К удалению/28 сентября 2012. Пока процесс обсуждения не завершён, статью мож … Википедия
- ДРАКОН (алгоритмический язык) — У этого термина существуют и другие значения, см. Дракон (значения). Пример блок схемы алгоритма на языке ДРАКОН дракон схемы ДРАКОН (Дружелюбный Русский Алгоритмический язык, Который Обеспечивает Наглядность) визуальный… … Википедия
- Конструктор класса — В объектно ориентированном программировании конструктор класса (от англ. constructor, иногда сокращают ctor) специальный блок инструкций, вызываемый при создании объекта, причём или при его объявлении (располагаясь в стеке или в статической… … Википедия
- Конструктор объекта — В объектно ориентированном программировании конструктор класса (от англ. constructor, иногда сокращают ctor) специальный блок инструкций, вызываемый при создании объекта, причём или при его объявлении (располагаясь в стеке или в статической… … Википедия
- Ковариантность и контравариантность — Ковариантность и контравариантность математическое и физическое понятие, которое описывает то, как величины изменяются при преобразовании системы координат. Координаты геометрического вектора измеряются в какой нибудь конкретной системе… … Википедия
- КУЛЬТУРА — (лат. cultura возделывание, воспитание, почитание) универсум искусственных объектов (идеальных и материальных предметов; объективированных действий и отношений), созданный человечеством в процессе освоения природы и обладающий структурными,… … Философская энциклопедия
- Шаблон — О шаблонах в Википедии смотрите страницу Википедия:Шаблоны. Шаблон в технике пластина (лекало, трафарет и т. п.) с вырезами, по контуру которых изготовляются чертежи или изделия либо инструмент для измерения размеров. Шаблон в… … Википедия
- Обратная связь: Техподдержка, Реклама на сайте
- �� Путешествия
Экспорт словарей на сайты, сделанные на PHP,
WordPress, MODx.
- Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
- Искать во всех словарях
- Искать в переводах
- Искать в ИнтернетеИскать в этой же категории
12.2.7.1 Инварианты.
Значение членов или объектов, доступных с помощью членов класса, называется состоянием объекта (или просто значением объекта). Главное при построении класса — это: привести объект в полностью определенное состояние (инициализация), сохранять полностью определенное состояние обЪекта в процессе выполнения над ним различных операций, и в конце работы уничтожить объект без всяких последствий. Свойство, которое делает состояние объекта полностью определенным, называется инвариантом.
Поэтому назначение инициализации — задать конкретные значения, при которых выполняется инвариант объекта. Для каждой операции класса предполагается, что инвариант должен иметь место перед выполнением операции и должен сохраниться после операции. В конце работы деструктор нарушает инвариант, уничтожая объект. Например, конструктор String::String( const char *) гарантирует, что p указывает на массив из, по крайней мере, sz элементов, причем sz имеет осмысленное значение и v[sz-1]==0. Любая строковая операция не должна нарушать это утверждение.
При проектировании класса требуется большое искусство, чтобы сделать реализацию класса достаточно простой и допускающей наличие полезных инвариантов, которые несложно задать. Легко требовать, чтобы класс имел инвариант, труднее предложить полезный инвариант, который понятен и не накладывает жестких ограничений на действия разработчика класса или на эффективность реализации. Здесь «инвариант» понимается как программный фрагмент, выполнив который, можно проверить состояние объекта. Вполне возможно дать более строгое и даже математическое определение инварианта, и в некоторых ситуациях оно может оказаться более подходящим. Здесь же под инвариантом понимается практическая, а значит, обычно экономная, но неполная проверка состояния объекта.
Понятие инварианта появилось в работах Флойда, Наура и Хора, посвященных пред- и пост-условиям, оно встречается во всех важных статьях по абстрактным типам данных и верификации программ за последние 20 лет. Оно же является основным предметом отладки в C++.
Обычно, в течение работы функции-члена инвариант не сохраняется. Поэтому функции, которые могут вызываться в те моменты, когда инвариант не действует, не должны входить в общий интерфейс класса. Такие функции должны быть частными или защищенными.
Как можно выразить инвариант в программе на С++? Простое решение — определить функцию, проверяющую инвариант, и вставить вызовы этой функции в общие операции. Например:
class String < int sz; int* p; public: class Range <>; class Invariant <>; void check(); String(const char* q); ~String(); char& operator[](int i); int size() < return sz; > //. >; void String::check() < if (p==0 || szthrow Invariant; > char& String::operator[](int i) < check(); // проверка на входе if (ithrow Range; // действует check(); // проверка на выходе return v[i]; >
Этот вариант прекрасно работает и не осложняет жизнь программиста. Но для такого простого класса как String проверка инварианта будет занимать большую часть времени счета. Поэтому программисты обычно выполняют проверку инварианта только при отладке:
inline void String::check() < if (!NDEBUG) if (p==0 || szthrow Invariant; >
Мы выбрали имя NDEBUG, поскольку это макроопределение, которое используется для аналогичных целей в стандартном макроопределении С assert(). Традиционно NDEBUG устанавливается с целью указать, что отладки нет. Указав, что check() является подстановкой, мы гарантировали, что никакая программа не будет создана, пока константа NDEBUG не будет установлена в значение, обозначающее отладку. С помощью шаблона типа Assert() можно задать менее регулярные утверждения, например:
templateclass T, class X> inline void Assert(T expr,X x) < if (!NDEBUG) if (!expr) throw x; >
вызовет особую ситуацию x, если expr ложно, и мы не отключили проверку с помощью NDEBUG. Использовать Assert() можно так:
class Bad_f_arg < >; void f(String& s, int i) < Assert(0
Шаблон типа Assert() подражает макрокоманде assert() языка С. Если i не находится в требуемом диапазоне, возникает особая ситуация Bad_f_arg.
С помощью отдельной константы или константы из класса проверить подобные утверждения или инварианты - пустяковое дело. Если же необходимо проверить инварианты с помощью объекта, можно определить производный класс, в котором проверяются операциями из класса, где нет проверки, см. упр.8 в $$13.11.
Для классов с более сложными операциями расходы на проверки могут быть значительны, поэтому проверки можно оставить только для "поимки" трудно обнаруживаемых ошибок. Обычно полезно оставлять по крайней мере несколько проверок даже в очень хорошо отлаженной программе. При всех условиях сам факт определения инвариантов и использования их при отладке дает неоценимую помощь для получения правильной программы и, что более важно, делает понятия, представленные классами, более регулярными и строго определенными. Дело в том, что когда вы создаете инварианты, то рассматриваете класс с другой точки зрения и вносите определенную избыточность в программу. То и другое увеличивает вероятность обнаружения ошибок, противоречий и недосмотров. Мы указали в $$11.3.3.5, что две самые общие формы преобразования иерархии классов состоят в разбиении класса на два и в выделении общей части двух классов в базовый класс. В обоих случаях хорошо продуманный инвариант может подсказать возможность такого преобразования. Если, сравнивая инвариант с программами операций, можно обнаружить, что большинство проверок инварианта излишни, то значит класс созрел для разбиения. В этом случае подмножество операций имеет доступ только к подмножеству состояний объекта. Обратно, классы созрели для слияния, если у них сходные инварианты, даже при некотором различии в их реализации.
Оформление и дизайн книги OtDiatlovaOU.
Вся книга, архив.
Программирование, блок схема, программа, информатика, алгоритм, управление, система управления, разделяй властвуй, языки программирования, линейное программирование, сложность, книги программирование, организация, развитие, проектирование, самосовершенствование, развитие систем, программирование скачать, программирование c, задачи программирование, динамическое программирование, ориентированное программирование, методы программирования, объектно программирование, примеры программирования, задача линейного программирования, основы программирования, объектно ориентированное программирование, программирование учебник, технология программирования, программирование си, программирование скачать книги, исходники, исходники на c, c, с, програмирование, книги по с, разработка программ, государственное управление, методы управления, управление организацией, структуры управления, управление проектами, управление рисками, теории управления, скачать управление, процесс управления, исследование управления, программа управления, схемы управления, информационное управление, управление образования, стратегическое управление, исследование систем управления, социальное управление, функции управления, технология управления, модели управления, блок управления, организационное управление, менеджмент управления, психология управления, управление ресурсами, управление производством, принципы управления, корпоративное управление, управление работами, дистанционное управление, эффективность управления, управление компьютером, пульты управления, проблемы управления, области управления, основы управления, управление конфликтами, обеспечение управления, управление деятельностью, анализ управления, автоматизированное управление, стили управления, организационные структуры управления, автоматическое управление, современное управление, подходы управления, управление службами, стратегии управления, социология управления, управление развитием, объект управления, информационные технологии управления, автоматизированные системы управления, совершенствование управления, управление средствами, управление потоками, оперативное управление, механизм управления, управление удаленным, примеры управления, управление через, понятие управление, особенности управления, задачи управления, сфера управления, управление культуры, право управления, управление собственностью, управление книги, концепция управления, управление трудом, панель управления, опыт управления, информационные системы управления, формы управления, роль управления, политика управления, контроль управления, организация, управление организацией, организация труда, организация производства, теория организации, организация система, организация учета, структура организации, формы организации, анализ организации, принципы организации, организация процессов, развитие организации, пример организации , среда организации, организация контроля, метод организации, внутренняя организация, стратегии организации, понятие организация, уровни организации, основы организации, функции организации, современная организация, организация проекта, развитие, перспективы развития, этапы развития, программа развития, тенденции развития, развитие систем, стратегия развития, проблемы развития, концепция развития, развитие личности, дети развитие, современное развитие, развитие ребенка, план развития, теория развития, психология развития, особенности развития, развитие техники, развитие человека, развитие образования, устойчивое развитие, развитие памяти, фактор развития, развитие способностей, управление развитием, развитие связи, развитие технологии, развитие мышления, направления развития, пути развития, модели развития, русское развитие, развитие жизни, основные этапы развития, развитие страны, возникновение развитие, стратегическое развитие, развитие информационного развития, скачать развитие, развитие персонала, методы развития, творческое развитие, развитие языка, развитие школьника, проектирование, проектирование систем, проектирование программа, нормы проектирования, проектирование информационных, проектирование данных, проектирование информационной системы, проектирование базы, организационное проектирование, основы проектирования, автоматизированное проектирование, проектирование скачать, организация проектирования, методы проектирования, управление проектирование, технологическое проектирование, проектирование процессов, этапы проектирования, системы автоматизированного проектирования
Что такое инвариант в программировании
Честно несколько раз прочитал определение у Страуструпа, но смысл сего понятия от меня ускользает.
Пожалуйста объясните, чем являтся инвариант класса с точки зрения практического кода.
Что это — функция? Как она используется? И т.п.
Re: Что такое Инвариант?
| От: | korzhik | |
| Дата: | 11.05.05 12:27 | |
| Оценка: | 6 (1) | |
Здравствуйте, Ignoramus, Вы писали:
I>Честно несколько раз прочитал определение у Страуструпа, но смысл сего понятия от меня ускользает.
I>Пожалуйста объясните, чем являтся инвариант класса с точки зрения практического кода.
I>Что это — функция? Как она используется? И т.п.
здесь помоему понятно написано
Re: Что такое Инвариант?
| От: | Mr.Chipset | http://merlinko.com |
| Дата: | 11.05.05 12:54 | |
| Оценка: | 1 (1) | |
Здравствуйте, Ignoramus, Вы писали:
I>Честно несколько раз прочитал определение у Страуструпа, но смысл сего понятия от меня ускользает.
I>Пожалуйста объясните, чем являтся инвариант класса с точки зрения практического кода.
Инвариант — это некоторое логическое условие, значение которого (истина или ложь) должно сохраняться.
Приложительно к ЯП — это набор условий для класса которым должен следовать любой класс в момент вызова. Проще говоря — много инвариантов для методов класса.
Ты юзаешь инварианты классов в повседневном программировании. К примеру, есть класс vector — дин. массив. Логически понятно что номер текущего элемента не должен быть больше общего количества элементов и не должен быть меньше нуля. Ты это описываешь в описании класса:
Ок, теперь девелопер знает что это должно быть истинным для любого обьекта класса, что он и задает в инварианте класса:
class vectorInv < public: bool check(vector bI) < if(bI.cur_elem > bI.count || bI.cur_elem < 0) return false; > >;И где-нибудь ты намереваешься проверить — нормален ли класс:
ASSERT(check(someObj));Если условие не выполнено — всё, кранты — ошибка ибо нормальный код должен соответствовать контракту.
Это очень упрощенно и имхо, ещё ведь есть всякие TDD (cppUnit, Boost::Test) и т.д.
I>Что это — функция? Как она используется? И т.п.
"Всё что не убивает нас, делает нас сильнее. "
Re[2]: Что такое Инвариант?
| От: | Кодт | |
| Дата: | 11.05.05 19:19 | |
| Оценка: | 2 (2) | |
Здравствуйте, Mr.Chipset, Вы писали:
MC>Отсюда:
MC>
Инвариант — это некоторое логическое условие, значение которого (истина или ложь) должно сохраняться.
MC>Приложительно к ЯП — это набор условий для класса которым должен следовать любой класс в момент вызова. Проще говоря — много инвариантов для методов класса.
Это ты не смешиваешь ли инвариант с предусловием?
Инвариант класса — это утверждение, которое (должно быть) истинно применительно к любому объекту данного класса в любой момент времени (за исключением переходных процессов в методах объекта).
Some x,y,z; assert( SomeInvariant(x) && SomeInvariant(y) && SomeInvariant(z) ); x.do_something(); assert( SomeInvariant(x) && SomeInvariant(y) && SomeInvariant(z) ); do_something_with(y); assert( SomeInvariant(x) && SomeInvariant(y) && SomeInvariant(z) ); interact(x,z); assert( SomeInvariant(x) && SomeInvariant(y) && SomeInvariant(z) );Например, инвариантом std::vector являются:
— 0 — все элементы в диапазоне [0;size()-1] являются живыми (сконструированными и не разрушенными) объектами
Предусловие — это утверждение, которое является требованием для начала работы (при вызове метода, при входе в блок и т.п.)
Some::method(args) < assert( SomePrecondition(args && this->state && global::state) ); . >Например, предусловие std::vector::operator[](int index) — индекс должен лежать в диапазоне [0;size()-1]
Постусловие — это утверждение, истинное по окончании работы (возврат из метода, выход из блока и т.п.)
Some x; result = x.method(args); assert( PostCondition(result) );Постусловие для std::vector::operator[] — результат является ссылкой на тот самый элемент (если индекс валидный).
Для std::vector::at() — либо результат это ссылка на существующий элемент, либо бросок исключения при невалидном индексе.
Естественно, что одним из постусловий является сохранение инварианта.
Перекуём баги на фичи!
Re: Что такое Инвариант?
| От: | _doctor | http://agilesoftwaredevelopment.com |
| Дата: | 11.05.05 19:42 | |
| Оценка: | 1 (1) | |
Здравствуйте, Ignoramus, Вы писали:
I>Честно несколько раз прочитал определение у Страуструпа, но смысл сего понятия от меня ускользает.
I>Пожалуйста объясните, чем являтся инвариант класса с точки зрения практического кода.
I>Что это — функция? Как она используется? И т.п.
Как говорит нам gramota.ru, инвариант — это "элемент системы, остающийся неизменным при всех ее модификациях".
Если человеческим языком, то:
У большинства классов присутствует множество членов-данных, которые периодически изменяются. В результате ошибок в программе можно наизменять такого, что объект будет представлять собой полную бессмыслицу. Функия-инвариант проверяет целостность объекта, имеет ли он смысл. Например, для объекта моделирующего человека, инвариант может проверить существование не более, чем двух рук и не более, чем трёх ног
Используется для ловли ошибок. Например в конце каждой сложной/неоднозначной функции можно вызвать инвариант, просто чтобы быть хоть немного уверенным, что объект не разрушен к чертям.
Частенько весь инвариант помещается в #ifdef _DEBUG, чтобы не включаться в финальные версии.
Chief Software Engineer,
Scrum Master, Symbian
Re: Что такое Инвариант?
| От: | Chez |
| Дата: | 12.05.05 07:12 |
| Оценка: |
Здравствуйте, Ignoramus, Вы писали:
I>Честно несколько раз прочитал определение у Страуструпа, но смысл сего понятия от меня ускользает.
I>Пожалуйста объясните, чем являтся инвариант класса с точки зрения практического кода.
I>Что это — функция? Как она используется? И т.п.
MFC's CObject::AssertValid м ему подобные.
Posted via:RSDN@Home;version:1.1.3;muzikstamp:silent
Инварианты — Python: Абстракция с помощью данных
Абстракция позволяет нам не думать о деталях реализации и сосредоточиться на ее использовании. Также при необходимости реализацию абстракции можно всегда переписать и не бояться сломать использующий ее код. Но есть еще одна важная причина, по которой нужно использовать абстракцию — соблюдение инвариантов.
В этом уроке мы познакомимся с инвариантами, нормализацией и понятием data hiding.
Инварианты
Инвариант в программировании — логическое выражение, которое определяет непротиворечивость состояния — набора данных.
Разберемся на примере. Когда мы описали конструктор и селекторы для рациональных чисел, то неявно подразумевали выполнение следующих инвариантов:
num = make_rational(numer, denom) numer == get_numer(num) # True denom == get_denom(num) # True Когда мы передаем в конструктор рационального числа числитель и знаменатель, то ожидаем, что получим те же числа, если применим селекторы к этому рациональному числу. Так определяется корректность работы данной абстракции. Этот код практически является тестами.
Инварианты существуют относительно любой операции. И иногда они довольно хитрые. Например, рациональные числа можно сравнивать между собой, но не прямым способом. Одни и те же дроби можно представлять разными способами: 1/2 и 2/4. Код, который не учитывает этого факта, работает некорректно:
num1 = make_rational(2, 4) num2 = make_rational(8, 16) num1 == num2 # False Нормализация
Задача приведения дроби к нормальной форме называется нормализацией. Реализовать ее можно разными способами. Самый очевидный — выполнять нормализацию во время создания дроби, внутри функции make_rational . Другой — выполнять нормализацию уже при обращении через функции get_numer и get_denom .
Последний способ обладает недостатком — вычисление нормальной формы происходит на каждый вызов. Избежать этого можно с помощью техники мемоизация.
Учитывая новые вводные, становится понятно, что инвариант, который связывает конструктор и селекторы, нуждается в модификации. Функции get_numer и get_denom должны вернуть не переданные значения, а значения после нормализации:
num = make_rational(10, 20) get_numer(num) # 1 get_denom(num) # 2 Если дробь уже нормализована, то это будут те же самые значения.
Абстракция не только прячет от нас реализацию, но и отвечает за соблюдение инвариантов. Если работать в обход абстракции, то внутренние преобразования не будут учтены:
# Обход конструктора # Эти данные не нормализованы, # потому что не использовался конструктор num = "numer": 10, "denom": 20> # Возвращается не то, что должно # (ожидается нормализованный возврат) get_numer(num) # 10 get_denom(num) # 20 # Прямая модификация num = make_rational(10, 20) # Тут не может быть нормализации, # так как прямое изменениe num['numer'] = 40 get_numer(num) # 40 get_denom(num) # 20 Если работать с данными напрямую, минуя абстракцию, можно сломать инварианты, которые обеспечивались дополнительной логикой в конструкторе или селекторах. Поэтому важно пользоваться кодом так, как было задумано авторами.
Сокрытие данных
Можно сделать так, чтобы обойти абстракцию было нельзя. Такой подход называют сокрытием данных — data hiding.
Чтобы обеспечить сокрытие, в языках используется специальный синтаксис. Однако защиту данных можно организовать и без специальных средств, только за счет функций высшего порядка. Такой способ основан на создании абстракций с помощью анонимных функций, замыканий и передачи сообщений. Если вы хотите узнать об этом больше, то пройдите курс Python: Составные данные.
В реальности подобные механизмы легко обходятся с помощью Reflection API. Это можно сделать даже без них — за счет ссылочных данных. Также есть немало языков, например, JavaScript, в которых все нормально с абстракциями, но нет механизмов для защиты данных. При этом ничего страшного не произошло.
На практике при использовании абстракций никто не пытается специально их нарушать. Возможно, значение принудительной защиты данных сильно преувеличено.
Открыть доступ
Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно
- 130 курсов, 2000+ часов теории
- 1000 практических заданий в браузере
- 360 000 студентов
Наши выпускники работают в компаниях: