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

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

  • автор:

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

Инвариа́нтом в программировании называется логическое выражение, истинное после каждого прохода тела цикла (после выполнения фиксированного оператора) и перед началом выполнения цикла, зависящее от переменных, изменяющихся в теле цикла. [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) «Куча имеет свойство упорядоченности элементов по невозрастанию» (эквивалентно) «Класс, реализующий абстрактную структуру данных куча, обеспечивает инвариант упорядоченности элементов по невозрастанию»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 ответа 4

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

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

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

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

List<> : 0 ≤ _size ≤ _items.Length

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

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, с, програмирование, книги по с, разработка программ, государственное управление, методы управления, управление организацией, структуры управления, управление проектами, управление рисками, теории управления, скачать управление, процесс управления, исследование управления, программа управления, схемы управления, информационное управление, управление образования, стратегическое управление, исследование систем управления, социальное управление, функции управления, технология управления, модели управления, блок управления, организационное управление, менеджмент управления, психология управления, управление ресурсами, управление производством, принципы управления, корпоративное управление, управление работами, дистанционное управление, эффективность управления, управление компьютером, пульты управления, проблемы управления, области управления, основы управления, управление конфликтами, обеспечение управления, управление деятельностью, анализ управления, автоматизированное управление, стили управления, организационные структуры управления, автоматическое управление, современное управление, подходы управления, управление службами, стратегии управления, социология управления, управление развитием, объект управления, информационные технологии управления, автоматизированные системы управления, совершенствование управления, управление средствами, управление потоками, оперативное управление, механизм управления, управление удаленным, примеры управления, управление через, понятие управление, особенности управления, задачи управления, сфера управления, управление культуры, право управления, управление собственностью, управление книги, концепция управления, управление трудом, панель управления, опыт управления, информационные системы управления, формы управления, роль управления, политика управления, контроль управления, организация, управление организацией, организация труда, организация производства, теория организации, организация система, организация учета, структура организации, формы организации, анализ организации, принципы организации, организация процессов, развитие организации, пример организации , среда организации, организация контроля, метод организации, внутренняя организация, стратегии организации, понятие организация, уровни организации, основы организации, функции организации, современная организация, организация проекта, развитие, перспективы развития, этапы развития, программа развития, тенденции развития, развитие систем, стратегия развития, проблемы развития, концепция развития, развитие личности, дети развитие, современное развитие, развитие ребенка, план развития, теория развития, психология развития, особенности развития, развитие техники, развитие человека, развитие образования, устойчивое развитие, развитие памяти, фактор развития, развитие способностей, управление развитием, развитие связи, развитие технологии, развитие мышления, направления развития, пути развития, модели развития, русское развитие, развитие жизни, основные этапы развития, развитие страны, возникновение развитие, стратегическое развитие, развитие информационного развития, скачать развитие, развитие персонала, методы развития, творческое развитие, развитие языка, развитие школьника, проектирование, проектирование систем, проектирование программа, нормы проектирования, проектирование информационных, проектирование данных, проектирование информационной системы, проектирование базы, организационное проектирование, основы проектирования, автоматизированное проектирование, проектирование скачать, организация проектирования, методы проектирования, управление проектирование, технологическое проектирование, проектирование процессов, этапы проектирования, системы автоматизированного проектирования

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

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