0
правок
Изменения
Нет описания правки
==== Метод штрафных функций ====
* Можно также почитать [[mlwikimachinelearning:Метод штрафных функций]].
* Относится к методам снятия ограничений.
* '''Задача.''' J(u) → min при огр. g<sub>i</sub> ≤ 0 либо = 0 начиная с g<sub>m+1</sub>-ой.
==== Метод барьерных функций ====
* Можно почитать [[mlwikimachinelearning:Метод штрафных функций#Метод барьерных функций]].
* По сути то же, что и метод штрафных функций, только штраф другого вида.
== Оптимальное управление ==
==== Постановка задач оптимального управления, их классификация ====
* '''Опр.''' задача ОУ (дифур, доп.множества, нач.усл., функционал), множество достижимости.
* Задачи: быстродействия, с фикс. временем, с закреплёнными концами, с подвижными концами, с неавтономной системой.
==== Принцип максимума Понтрягина. Краевая задача принципа максимума ====
* '''Опр.''' сопряжённая система, гамильтониан.* '''Л.''' скалярное произведение решений прямой и сопряжённой систем константно.* '''Т.''' (ПМП) <m>\forall (u(t), x(t)) \exists \psi(t): \psi' =H_x'</m>, H(x, u,ψ) достигает максимума, а максимум постоянен на всём отрезке времени.* '''Т.''' (тоже ПМП, в другом виде) для оптимальной пары, если начальное и конечное множества выпуклы, существует ψ такое, что верно условие максимума: (u(t),ψ(t))=c(U,ψ(t)) и 2 трансверсальности: (x(t<sub>0</sub>),ψ(t<sub>0</sub>))=c(M<sub>0</sub>,ψ(t<sub>0</sub>)) и (x(t<sub>1</sub>),-ψ(t<sub>1</sub>))= c(M<sub>1</sub>,-ψ(t<sub>1</sub>)). ==== (404) Линейная задача быстродействия, ее свойства (существование решения, число переключений) ==== ==== (404) Принцип максимума и вариационное исчисление ==== * Видимо, про те самые вариации Макшейна?
==== Принцип максимума (404) Управляемость и вариационное исчисление наблюдаемость в линейных системах, их взаимосвязь (взаимодвойственность). Теоремы Калмана, Красовского ====
==== {{notexists}} :( 404) Метод динамической регуляризации в задаче наблюдения ====
==== {{notexists}} :( 404) Дифференциальные игры ====
== Дискретная оптимизация ==
==== Проблема полноты. Теорема о полноте систем функций двузначной логики ''P''<sub>2</sub> ====
* Формула над системой {''f<sub>k</sub>''}: 1) ''f<sub>i</sub>''- формула 2) ''f<sub>i</sub>''(''A<sub>1</sub>'',…,''A<sub>n</sub>'') — — формула, где A — A — переменная либо формула.
* Полнота системы {''f<sub>k</sub>''}: все функции из ''P''<sub>2</sub> можно выразить формулами над {''f<sub>k</sub>''}.
* Замкнутый класс — класс — все формулы над функциями из класса принадлежат тому же классу.
* Замкнутые классы: ''T<sub>0</sub>'' (f(0,0…0)=0), ''T<sub>1</sub>'' (f(1,1…1)=1), ''S'' (f(!x<sub>1</sub>,!x<sub>2</sub>,…!x<sub>n</sub>) = !f(!x<sub>1</sub>,!x<sub>2</sub>,…!x<sub>n</sub>)), ''M'' (1й набор по всем переменным ≥ 2го, тогда f(1го)≥f(2го)), ''L'' (формула над +, &, 1, 0, оно же полином Жегалкина)
* Теорема о полноте: если система не входит полностью ни в одно из ''T<sub>0</sub>'', ''T<sub>1</sub>'', ''S'', ''M'', ''L'' — — то она полна. Доказывается через получение констант 0 и 1 из не входящих в ''T<sub>0</sub>'', ''T<sub>1</sub>'' и ''S'', из них и функции, не принадлежащей ''L''- отрицания, и из них, отрицания и функции, не принадлежащей ''M'' — — дизъюнкции.
==== Алгоритм распознавания полноты систем функций ''k''-значной логики ''P<sub>k</sub>'' ====
* '''Т.''' существует алгоритм анализа системы на полноту. («в лоб»)<br /> '''Док-во:''' строим мн-ва функций от 2х переменных, подставляя в функции из нашей системы либо функции от 2х переменных с предыдущего шага, либо просто переменную x<sub>1</sub> или x<sub>2</sub>. Так как функций k-значной логики у нас конечное количество, то рано или поздно множество окажется замкнутым. Если оно совпадает со всеми функциями 2х переменных — переменных — то система полна, иначе нет.* Предыдущий результат с практической т.з. бесполезен, ибо задолбаешься так проверять =) Поэтому мы сначала введем понятие функции, сохраняющей множество (см. опять же предыдущий вопрос, только тут не 0 и 1, а произвольные множества — множества — причем замкнутость класса, сохраняющего множество, есть всегда, независимо от того, какое это множество), а потом! Мы докажем…
* '''Т.''' (о функциональной полноте, Кузнецова) про то, что и в k-значной логике можно построить аналоги 5 классов из бинарной (см. теорему о полноте на 1 вопрос выше), то есть если система полностью не вложена ни в 1 из них- то она полна.
* И все равно нам это не поможет, потому что такие классы задолбаешься строить (вроде бы для 3 и 4-значной логики сделали, для остальных — остальных — нишмагли). Поэтому придумали теорему Слупецкого…
==== Теорема Слупецкого ====
* …которая в обобщенном виде гласит, что если система содержит все функции 1й переменной, принимающие не более k-1 значений (в необобщенном виде — виде — просто все функции 1й переменной), то для полноты н. и д., чтобы она содержала еще существенную (то есть зависящую от 2+ переменных) функцию, принимающую k значений. Подробнее про док-во — во — в Яблонском, там несколько длинных (по доказательству) лемм.
* Это уже хорошо, но всех функций 1й переменной, принимающих не более k-1 значений, все равно очень много. Поэтому проще искать «базисы» для таких функций, примеры см. в Яблонском, с.64-65.
* В бинарной логике каждый замкнутый класс имеет конечный базис; всего их счётное число; всякую функцию можно записать полиномом.
* А в k-значной — значной — нифига.
* '''Т.''' (Янова) для всякого k≥3 в P<sub>k</sub> {{exists}} замкнутый класс, не имеющий базиса.
* '''Т.''' (Мучника) для всякого k≥3 в P<sub>k</sub> {{exists}} замкнутый класс, имеющий счётный базис.
* '''Т.''' для всякого k≥3 в P<sub>k</sub> {{exists}} континуум различных замкнутых классов.
* '''Т.''' система полиномов в P<sub>k</sub> полна ⇔ k — k — простое число.
==== Автоматы. Регулярные события и их представление в автоматах ====
* Можно почитать [[rupedia:Код Боуза — Чоудхури — Хоквингема]], [[rupedia:Циклический код]] (а в CD-ROM’ах используется [[rupedia:Код Рида — Соломона]]).
* Коды БЧХ — БЧХ — «обобщение» Хэмминга на случай двух ошибок. Требование решения системы уравнений относительно i и j (позиций ошибок) как раз и приводит к полям…
* '''Опр.''' циклический код, порождающий полином, проверочная матрица.
* '''Т.''' коды БЧХ — БЧХ — циклические коды, задаваемые порождающим полиномом.
* '''Т.''' о границе БЧХ.
==== Эквивалентные преобразования контактных схем ====
* '''Опр.''' тождества основные, вспомогательные, обобщенные, каноническая КС, каноническая цепь, цикломатическое число графа (компонент связности + рёбер — рёбер — вершин), контактной схемы.
* '''Т.''' основная система тождеств полна (принцип индукции → расширение контактов → применение тождества «звезда» → добавление фиктивных цепей → удаление вершины → удаление висячих и параллельных цепей → удаление транзитной проводимости).
* '''Л.''' (об изменении цикломатического числа при эквивалентных преобразованиях).
* '''Т.''' (о неполноте любой конечной системы тождеств).
==== {{notexists}} :( 404) Эквивалентные преобразования операторных алгоритмов ==== ''Специалисты, welcome — дополните секцию и уберите пометку (404) из заголовка!''
==== Пример Линдона ====
