Что такое инвариант в программировании
Перейти к содержимому

Что такое инвариант в программировании

  • автор:

Инвариант (программирование)

Инвариа́нтом в программировании называется логическое выражение, истинное после каждого прохода тела цикла (после выполнения фиксированного оператора) и перед началом выполнения цикла, зависящее от переменных, изменяющихся в теле цикла. [1]

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

  1. Доказывается, что выражение инварианта истинно перед началом цикла.
  2. Доказывается, что выражение инварианта сохраняет свою истинность после выполнения тела цикла; таким образом, по индукции, доказывается, что по завершении цикла инвариант будет выполняться.
  3. Доказывается, что при истинности инварианта после завершения цикла переменные примут именно те значения, которые требуется получить (это элементарно определяется из выражения инварианта и известных конечных значениях переменных, на которых основывается условие завершения цикла).
  4. Доказывается (возможно — без применения инварианта), что цикл завершится, то есть условие завершения рано или поздно будет выполнено.
  5. Истинность утверждений, доказанных на предыдущих этапах, однозначно свидетельствует о том, что цикл выполнится за конечное время и даст желаемый результат.

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

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

Примечания

  1. Построение цикла с помощью инварианта
  • Формальные методы

Wikimedia Foundation . 2010 .

  • Инвариант (математика)
  • Инвариант (физика)

Полезное

Смотреть что такое «Инвариант (программирование)» в других словарях:

  • Инвариант — или инвариантность термин, обозначающий нечто неизменяемое. Конкретное значение термина зависит от той области, где он используется: Инвариант (математика) Инвариант узла в топологии Инвариант (физика) Инвариант (программирование) Инвариант … Википедия
  • ПРОГРАММИРОВАНИЕ ТЕОРЕТИЧЕСКОЕ — математическая дисциплина, изучающая математич. абстракции программ, трактуемых как объекты, выраженные на формальном языке, обладающие определенной информационной и логич. структурой и подлежащие исполнению на автоматич. устройствах. П. т.… … Математическая энциклопедия
  • Конструктор (программирование) — У этого термина существуют и другие значения, см. Конструктор. В объектно ориентированном программировании конструктор класса (от англ. constructor, иногда сокращают ctor) специальный блок инструкций, вызываемый при создании объекта.… … Википедия
  • ДРАКОН — Эта статья предлагается к удалению. Пояснение причин и соответствующее обсуждение вы можете найти на странице Википедия:К удалению/28 сентября 2012. Пока процесс обсуждения не завершён, статью мож … Википедия
  • ДРАКОН (алгоритмический язык) — У этого термина существуют и другие значения, см. Дракон (значения). Пример блок схемы алгоритма на языке ДРАКОН дракон схемы ДРАКОН (Дружелюбный Русский Алгоритмический язык, Который Обеспечивает Наглядность) визуальный… … Википедия
  • Конструктор класса — В объектно ориентированном программировании конструктор класса (от англ. constructor, иногда сокращают ctor) специальный блок инструкций, вызываемый при создании объекта, причём или при его объявлении (располагаясь в стеке или в статической… … Википедия
  • Конструктор объекта — В объектно ориентированном программировании конструктор класса (от англ. constructor, иногда сокращают ctor) специальный блок инструкций, вызываемый при создании объекта, причём или при его объявлении (располагаясь в стеке или в статической… … Википедия
  • Ковариантность и контравариантность — Ковариантность и контравариантность математическое и физическое понятие, которое описывает то, как величины изменяются при преобразовании системы координат. Координаты геометрического вектора измеряются в какой нибудь конкретной системе… … Википедия
  • КУЛЬТУРА — (лат. cultura возделывание, воспитание, почитание) универсум искусственных объектов (идеальных и материальных предметов; объективированных действий и отношений), созданный человечеством в процессе освоения природы и обладающий структурными,… … Философская энциклопедия
  • Шаблон — О шаблонах в Википедии смотрите страницу Википедия:Шаблоны. Шаблон в технике пластина (лекало, трафарет и т. п.) с вырезами, по контуру которых изготовляются чертежи или изделия либо инструмент для измерения размеров. Шаблон в… … Википедия
  • Обратная связь: Техподдержка, Реклама на сайте
  • �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,
WordPress, MODx.

  • Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
  • Искать во всех словарях
  • Искать в переводах
  • Искать в ИнтернетеИскать в этой же категории

Отличие терминов Инварианта и Свойства?

Чем отличается понятия инварианта и свойства (неизменного)?

( Корректно ли составлен вопрос?

В чем смысл различия инварианта и спецификации, предъявляемой к классу, который воплощает некую абстракцию из предметной области?
)

Привожу ниже примеры и, возможно, ошибочные суждения:

1) Допустим есть граф, который можно визуально отобразить разными способами (список связей, матрица вершин, перечисление цепочек). Инвариантом графа является ( или корректнее — являЮтся? ) количество вершин и ребер.

  • Инвариантом класса уровня наследования 1 является неприватный интерфейс базового класса.
  • Инвариантом класса уровня наследования 2 является неприватный интерфейс конкретного класса-родителя из уровня наследования 1.

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

4) «Куча имеет свойство упорядоченности элементов по невозрастанию» (эквивалентно) «Класс, реализующий абстрактную структуру данных куча, обеспечивает инвариант упорядоченности элементов по невозрастанию»

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

  • Вопрос задан более трёх лет назад
  • 1384 просмотра

Комментировать
Решения вопроса 1
Developer, ex-admin
Из википедии:

Инвариант в объектно-ориентированном программировании — выражение, определяющее непротиворечивое внутреннее состояние объекта.

Но это относится не только к ООП, а в принципе.
Из ваших примеров, по моему, только 4 про инвариант.

Исходя из определения из вики, инвариант — логическое выражение (а не свойство), которое всегда должно выполняться для объекта. Если оно не выполняется, то объект (класс, структура и т.п.) находится в несогласованном состоянии и его дальнейшее использование опасно.
Обычно инварианты нарушаются внутри методов класса, при выходе из метода инвариант должен снова восстанавливаться, иначе метод отработал не правильно.
Простой пример: для Си строки инвариант — не нулевой указатель на начало и символ 0 в конце строки.
Например у вас есть функция AddString, которая добавляет к существующей строке другую строку. Для простоты предположим, что не нужно перевыделять память. В процессе выполнения AddString инвариант нарушается — 0 символ заменяется добавляемыми символами второй строки. Но после добавления нулевой символ должен быть восстановлен в конце, после чего инвариант снова будет истинным.

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

Что такое инвариант в программировании

Честно несколько раз прочитал определение у Страуструпа, но смысл сего понятия от меня ускользает.

Пожалуйста объясните, чем являтся инвариант класса с точки зрения практического кода.

Что это — функция? Как она используется? И т.п.

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

Что такое инвариант в ООП?

Что имеется ввиду под этим термином? Как выглядят инварианты в коде?

Я нашёл описание термина «инвариант цикла»:

Инвариант цикла – это соотношение, которое истинно перед циклом, истинно в процессе выполнения цикла и истинно при выходе из цикла. Все это описано у Дейкстры в книге «Дисциплина программирования», и детально разжевано у Гриса в книге «Наука программирования».

А хотелось бы понять, что понимают под инвариантом

  1. в программировании по контракту и
  2. чистом ООП (я так понял, это имеет отношение к инкапсуляции)

Отслеживать
81.3k 9 9 золотых знаков 78 78 серебряных знаков 136 136 бронзовых знаков
задан 21 июл 2018 в 21:06
28.7k 22 22 золотых знака 61 61 серебряный знак 141 141 бронзовый знак

4 ответа 4

Сортировка: Сброс на вариант по умолчанию

Инвариант в математике — это выражение которое сохраняет свое значение. В программировании инвариантом также называют предикат который всегда истинный.

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

В коде инварианты чаще всего никак не выражены, но иногда ставятся защитные проверки которые их проверяют.

List<> : 0 ≤ _size ≤ _items.Length

List<>.Enumerator : list.version = const = version; есть защитная проверка

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *