LINUX.ORG.RU
ФорумTalks

Вопрос по крайне жесточайшему олимпиадному программированию.

 


0

2

Что такое инвариант, если простыми словами? На русский могу перевести как нечто, что не изменяется. Например «инвариант цикла» - логическое выражение, которое трушно на каждой итерации цикла (например i < 16). Если инвариант сдох (i >= 16), то цикл разрушается. Цикл как-бы стоит на инварианте как на фундаменте, нет фундамента - сущность «цикл» взрывается на куски (прекращается динамический процесс исполнения цикла).

А что такое инвариант узла дерева, например? В узлах дерева обычно лежит ключ, значение, указатели на сыновей и т.п. Что там инвариант?

P.S. Жутко бесят эти непонятные слова из мира бессмысленного и беспощадного программирования.

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

xnick ()

Для дерева это некий показатель характерный для всего дерева, а не отдельных его узлов

plohish ()
Ответ на: комментарий от xnick

Я так понял, в высшем абстрактном матанном computer science цикл - это динамический процесс, стоящий на инварианте. Инвариант разрушился - цикл взорвался в клочья. Нет необходимости вводить понятие «условие выхода», ибо у цикла нет выхода — цикл сам либо существует, либо не существует. Т.е. он может существовать, потом инвариант сломался и цикл не существует (вышел). Как физически это реализовано — науку не интересует - выстрелом из пистолета в процессор или неким «выходом из цикла».

hlamotron ()

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

ilovewindows ★★★★★ ()

Что там инвариант?

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

f1u77y ★★★ ()

антивариант это то, что выглядит старым и за что дают много денег

unt1tled ★★★★ ()

А что такое инвариант узла дерева, например?

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

Жутко бесят эти непонятные слова из мира бессмысленного и беспощадного программирования.

Будь инвариантным к непонятным словам.
1 способ: учи математику.
2 способ: не учи математику, иди в писатели, у них все слова понятные :)

quickquest ★★★★★ ()
Последнее исправление: quickquest (всего исправлений: 1)

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

cadaber ★★ ()

А что такое инвариант узла дерева, например? В узлах дерева обычно лежит ключ, значение, указатели на сыновей и т.п. Что там инвариант?

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

ival ★★ ()
Ответ на: комментарий от ival

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

Для красно-чёрных это выполнить невозможно. Что делать теперь?

utf8nowhere ★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.