==== Метод штрафных функций ====
* Можно также почитать [[mlwikimachinelearning:Метод штрафных функций]].
* Относится к методам снятия ограничений.
* '''Задача.''' J(u) → min при огр. g<sub>i</sub> ≤ 0 либо = 0 начиная с g<sub>m+1</sub>-ой.
==== Метод барьерных функций ====
* Можно почитать [[mlwikimachinelearning:Метод штрафных функций#Метод барьерных функций]].
* По сути то же, что и метод штрафных функций, только штраф другого вида.
== Оптимальное управление ==
# Частично берётся из лекций {{Скачать|Орлов - лекции по оптимальному управлению 2005.pdf}}. Но содержит несколько мистические вопросы — например, 3 последних, для которых связных материалов найти не удалось вообще. Дифференциальные игры можно, конечно, почитать по книге Айзекса 1967-го года, но там про это вся книга (480 страниц), но нам-то кратко надо. ''Специалисты по оптимальному управлению — welcome! Дополните секцию! (и уберите пометки (404) = (не найдено) из заголовков)'' ==== Постановка задач оптимального управления, их классификация==== * '''Опр.''' задача ОУ (дифур, доп.множества, нач.усл., функционал), множество достижимости.# * Задачи: быстродействия, с фикс. временем, с закреплёнными концами, с подвижными концами, с неавтономной системой. ==== Принцип максимума Понтрягина. Краевая задача принципа максимума==== * '''Опр.''' сопряжённая система, гамильтониан.# * '''Л.''' скалярное произведение решений прямой и сопряжённой систем константно.* '''Т.''' (ПМП) <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) Управляемость и наблюдаемость в линейных системах, их взаимосвязь (взаимодвойственность). Теоремы Калмана, Красовского==== * '''Опр.''' Система полностью управляема, если она может быть переведена из любого начального состояния в начало координат под действием управления u(t) за конечное время.# * '''Т.''' (Калмана) Состояние непрерывной системы (x' = Ax + bu) управляемо, если и только если<br />rang N<sub>y</sub>=[b | Ab | A²b | … | A<sup>n-1</sup>b] = n. ==== (404) Метод динамической регуляризации в задаче наблюдения.====# ==== (404) Дифференциальные игры.====
== Дискретная оптимизация ==
== Теория функциональных систем ==
Берётся снова из {{Скачать|Яблонский - Введение в дискретную математику.djvu}}. ==== Проблема полноты. Теорема о полноте систем функций двузначной логики ''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- — переменная либо формула. * Полнота системы {''f<sub>k</sub>''}: все функции из ''P''<sub>2</sub> можно выразить формулами над {''f<sub>k</sub>''}. * Замкнутый класс- — все формулы над функциями из класса принадлежат тому же классу. * Замкнутые классы: ''T<sub>0</sub>'' (f(0,0...00…0)=0), ''T<sub>1</sub>'' (f(1,1...11…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-значной — нифига.* '''Т.''' (Янова) для всякого 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 — простое число. ==== Автоматы. Регулярные события и их представление в автоматах.====# ==== Эксперименты с автоматами==== * Берётся из {{Скачать|Алексеев - лекции по дискретной математике 2002.pdf}}.# * '''Опр.''' автомат с выходом, отличимые состояния, эксперимент.* '''Л.''' (о существовании отличимых экспериментом данной длины состояний)* '''Т.''' (Мура) (о максимальной длине эксперимента, +пример)* '''Т.''' (про отличимые состояния разных автоматов)* '''Т.''' (о макс. длине эксп. отличающего состояния двух автоматов, +пример) ==== Алгоритмическая неразрешимость проблемы полноты для автоматов.====# ==== Вычислимые функции. Эквивалентность класса рекурсивных функций и класса функций, вычислимых на машинах Тьюринга.====# ==== Алгоритмическая неразрешимость проблемы эквивалентности слов в ассоциативных исчислениях==== * Берётся из {{Скачать|Мальцев - Алгоритмы и рекурсивные функции.djvu}}, стр. 254.* '''Опр.''' полугруппа, система порождающих, определяющие соотношения, умножение классов.* '''Опр.''' ассоциативного исчисления (набор замен); эквивалентные слова.* '''Т.''' (Пост, Марков) {{exists}} ассоциативное исчисление с алгоритмически неразрешимой проблемой эквивалентности слов.
== Комбинаторный анализ и теория графов ==
* Можно почитать [[rupedia:Код Боуза — Чоудхури — Хоквингема]], [[rupedia:Циклический код]] (а в CD-ROM’ах используется [[rupedia:Код Рида — Соломона]]).
* Коды БЧХ — «обобщение» Хэмминга на случай двух ошибок. Требование решения системы уравнений относительно i и j (позиций ошибок) как раз и приводит к полям…
* Коды '''Опр.''' циклический код, порождающий полином, проверочная матрица.* '''Т.''' коды БЧХ — циклические коды, задаваемые порождающим полиномом.* '''Т.''' о границе БЧХ.
== Управляющие системы ==
Вопрос тут один, ёмкий, аки нецензурное послание: ''. ==== Понятие управляющей системы. Основные модельные классы управляющих систем: дизъюнктивные нормальные формы, формулы, контактные схемы, схемы из функциональных элементов, автоматы, машины Тьюринга, операторные алгоритмы. Основные проблемы теории управляющих систем''. ==== Берётся он из {{Скачать|Ложкин С.А. - Лекции по основам кибернетики 2004.djvu}}.
* Управляющая система — типа задаёт поведение некоторой системы.
== Дизъюнктивные нормальные формы ==
# Берётся из лекций Ложкина по ОК: {{Скачать|Ложкин С.А. - Лекции по основам кибернетики 2004.djvu}}. ==== Проблема минимизации булевых функций. Дизъюнктивные нормальные формы (ДНФ). Постановка задачи в геометрической форме.==== # ==== Локальные алгоритмы построения ДНФ. Построение ДНФ ''∑Т'' (сумма тупиковых) с помощью локального алгоритма==== * '''Опр.''' тупиковая ДНФ, ДНФ ΣT и {{cap}}T, ядровая точка, ядровая грань, ядро; пучок, регулярные и нерегулярные точки, регулярные грани; окрестность порядка r, ДНФ Квайна; локальный алгоритм.* '''Л.''' (о составе ДНФ {{cap}}T)* '''Т.''' (Журавлева) (о составе ДНФ ΣT), идея о покрытии регулярных точек гранями из меньшего пучка. # ==== Невозможность построения ДНФ ''∑М'' (сумма минимальных) в классе локальных алгоритмов==== * '''Опр.''' ДНФ ΣM, цепная функция.* '''Т.''' (Журавлева) (неприменимость локального алгоритма для построения ДНФ ΣM цепной функции).
== Синтез и сложность управляющих систем ==
# Берётся всё из тех же лекций Ложкина: {{Скачать|Ложкин С.А. - Лекции по основам кибернетики 2004.djvu}}. ==== Асимптотически оптимальный метод синтеза схем из функциональных элементов==== * '''Опр.''' дискретно-универсальное множество функций.* '''Т.''' (Лупанова) о верхней оценке функции Шеннона в классе СФЭ.* '''Сл.''' (асимптотика функции Шеннона). # ==== Асимптотически оптимальный метод синтеза контактных схем==== * '''Опр.''' m-регулярное множество.* '''Т.''' (Лупанова) то же, но в классе КС.* Идея метода Лупанова: разложение функции по подфункциям и полосам, построение суперпозиции КС на основе m-регулярного множества. # ==== Инвариантные классы и их свойства==== * Берётся из {{Скачать|Сапоженко - Некоторые вопросы сложности алгоритмов.djvu}}.* '''Опр.''' инв.класс, характеристика ИК, сложная функция, правильный алгоритм.* Пример ИК с характеристикой 0.5.* '''Т.''' (Яблонского) о существовании ИК с заданной характеристикой.* '''Т.''' (Яблонского) о работе правильного алгоритма, строящего сложную последовательность функций. # ==== Синтез схем для функций из некоторых инвариантных классов==== * Из Сапоженко и Ложкина.# * '''Т.''' (Лупанова) о верхней оценке функции Шеннона для ИК с заданной характеристикой.* '''Т.''' о нижней мощностной оценке функции Шеннона для ИК с характеристикой, большей 1. ==== Нижние оценки сложности реализации булевых функций параллельно-последовательными контактными схемами==== * Соотношение между π-схемами и формулами с поднятыми отрицаниями.# * '''Опр.''' каркас.* Оценка числа формул данной сложности на основе количества каркасов и способов подстановки переменных.* '''Л.''' о верхней оценке количества π-схем данной сложности через число формул.* '''Л.''' об обращении степенного неравенства.* Принцип получения нижних оценок функции Шеннона.* '''Т.''' о нижней оценке функции Шеннона. ==== Нижние оценки сложности реализации булевых функций формулами в произвольном базисе==== * '''Опр.''' приведенный вес, каркас.* '''Л.''' о соотношении между рангом формулы, ее сложностью и приведенным весом.* Оценка числа формул данной сложности на основе количества каркасов и способов подстановки переменных.
== Эквивалентные преобразования управляющих систем ==
# Опять-таки берётся из лекций Ложкина {{Скачать|Ложкин С.А. - Лекции по основам кибернетики 2004.djvu}}, кроме примера Линдона, который можно взять из методички Алексеева {{Скачать|Алексеев и др. - Задачи по курсу Основы кибернетики.djvu}}. ==== Эквивалентные преобразования формул двузначной логики ''Р''<sub>2</sub>==== * '''Опр.''' тождество, выводимость, эквивалентное преобразование.* Тождества: ассоциативности, коммутативности, отождествления переменных, де Моргана, дистрибутивности, поглощения, подстановки констант.* '''Т.''' Основная и расширенная системы тождеств эквивалентны.* '''Т.''' основной система тождеств полна (поднятие отрицаний → раскрытие скобок → приведение подобных, переход к совершенной ДНФ). # ==== Эквивалентные преобразования контактных схем==== * '''Опр.''' тождества основные, вспомогательные, обобщенные, каноническая КС, каноническая цепь, цикломатическое число графа (компонент связности + рёбер — вершин), контактной схемы.# * '''Т.''' основная система тождеств полна (принцип индукции → расширение контактов → применение тождества «звезда» → добавление фиктивных цепей → удаление вершины → удаление висячих и параллельных цепей → удаление транзитной проводимости).* '''Л.''' (об изменении цикломатического числа при эквивалентных преобразованиях).* '''Т.''' (о неполноте любой конечной системы тождеств). ==== (404) Эквивалентные преобразования операторных алгоритмов.====# ''Специалисты, welcome — дополните секцию и уберите пометку (404) из заголовка!'' ==== Пример Линдона==== * '''Опр.''' функция Линдона (которая с 1 5 6).* Основные тождества и их вывод, преобразование к каноническому виду и его единственность.* '''Т.''' Полнота системы тождеств.* Свойство C<sup>n</sup> и его инвариантность относительно применения тождеств.* Невыводимость тождеств.* '''Т.''' {{notexists}} КПСТ.
== Надежность и контроль функционирования управляющих систем ==
# ==== Построение надежных контактных схем из ненадежных контактов==== * Из методички по ОК: {{Скачать|Алексеев и др. - Задачи по курсу Основы кибернетики.djvu}}.# * Логико-комбинаторный подход к понятию неисправности. Понятие самокоррекции.* Способы построения самокорректирующихся КС.* Представление об асимптотически наилучшем методе синтеза самокорректирующихся КС. ==== Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты==== * Из лекций Ложкина: {{Скачать|Ложкин С.А. - Лекции по основам кибернетики 2004.djvu}}.* Модель источника неисправности и ненадежной схемы (N состояний, реализуемых при неисправностях).* '''Опр.''' отделимая по столбцам матрица; таблица контроля, цель контроля; диагностика схемы, проверка исправности схемы; тесты: минимальный, тупиковый, диагностический, проверяющий; функция теста.* '''Л.''' (о формуле для функции теста)* '''Л.''' (о длине диагностического теста)
== Математическая экономика ==
* И попёрли развивать какую-то левую теорию, мажоризация, слабая мажоризация, мажоризация как частичное упорядочение<span style="color:#a0a0a0">'', такая мажоризация, сякая мажоризация, групповая мажоризация, любительская мажоризация, извращённая мажоризация''</span>…
== Основная литература == # Яблонский С. В. Введение в дискретную математику. М.: Высш. школа, 2001.# Кудрявцев В.В, Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.: Наука, 1985.# Мальцев А. И. Алгоритмы и вычислимые функции. М.: Наука, 1986.# Оре О. Теория графов. М.: Наука, 1980.# Кибернетический сборник. 1960—1990. Вып. 1—9; вып. 1—28 (новая серия). М.: Мир.# Дискретная математика и математические вопросы кибернетики. Т. 1. / Под общ. ред. С. В. Яблонского и О. Б. Лупанова. М.: Наука, 1974.# Нигматуллин Р. Г. Сложность булевых функций. М.: Наука, 1991.# Проблемы кибернетики. 1959—1984. Вып. 1—41. М.: Наука.# Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. М.: Наука, 1990.# Труды Математического института им. В. А. Стеклова. Т. 51. М.: Изд-во АН СССР, 1958.# Математические вопросы кибернетики. 1988—2001. Вып. 1—10. М.: Наука.# Гермейер Ю. Б. Введение в теорию исследования операций. М.: Наука, 1969.# Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. М.: Наука, 1986.# Васильев Ф. П. Методы оптимизации. М.: Факториал, 2002.# Карманов В. Г. Математическое программирование. М.: Наука, 2000.# Понтрягин Л. Избранные научные труды. Т. 2. М.: Наука, 1988.# Тихомиров В. М., Фомин С. В., Алексеев В. М. Оптимальное управление. М.: Наука, 1979.# Краснощеков П. С., Петров А. А. Принципы построения моделей. М.: Фазис, 2002.# Подиновский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1981.# Морозов В. В. Основы теории игр. М.: Изд-во МГУ, 2002.# Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. М.: Наука, 198 .# Никайдо Х. Выпуклые структуры и математическая экономика. М.: Мир, 1972.# Ашманов С. А. Введение в математическую экономику. М.: Наука, 1984.# Экланд И. Элементы математической экономики. М.: Мир, 1983.# Обен Ж.-П. Нелинейный анализ и его экономические приложения. М.: Мир, 1988.# Маршалл А., Олкин И. Неравенства, теория мажоризации и ее приложения. М.: Мир, 1983.# Мельников А. В. Стохастический анализ и расчет производных ценных бумаг. М.: ТВП, 1997. == Дополнительная литература Литература ==
# МакВильмс Ф* {{Скачать|Лекции по методам оптимизации 2003. Джpdf}}* {{Скачать|Орлов - лекции по оптимальному управлению 2005., Слоэн Нpdf}}* {{Скачать|Шананин А. ДжА. Теория кодов, исправляющих ошибки. М.: Связь, 1979- Лекции по математическим моделям в экономике 1999.pdf}}# Лупанов О* {{Скачать|Ложкин С. БА. Асимптотические оценки сложности управляющих систем- Лекции по основам кибернетики 2004. М.: Издdjvu}}* {{Скачать|Алексеев -во МГУ, 1984лекции по дискретной математике 2002.pdf}}# Сэведж Дж* {{Скачать|Алексеев и др. Э- Задачи по курсу Основы кибернетики. Сложность вычислений. М.: Факториал, 1998djvu}}* {{Скачать|Сапоженко - Некоторые вопросы сложности алгоритмов.djvu}}# Марков * {{Скачать|А. А. Введение в теорию кодирования. М.: НаукаВасин, 1982В.# Орлов В. А. Простое доказательство алгоритмической неразрешимости некоторых задач о полноте автоматных базисов. //Кибернетика. 1973. № 4Морозов - Теория игр и модели математической экономики. С. 109—113djvu}}* {{Скачать|Васин, Морозов - Дополнительные главы теории операций - Глава 5 - Теория принятия решений.djvu}}# Редькин Н. П. Надежность и диагностика схем. М.: Изд* {{Скачать|Яблонский -во МГУВведение в дискретную математику.djvu}}* {{Скачать|Пападимитриу, 1992Стайглиц - Комбинаторная оптимизация.djvu}}# Соловьев Н* {{Скачать|Оре - Теория графов. А. Тесты (теорияdjvu}}* {{Скачать|Макмиллан, построениеСлоэн - Теория кодов, применения)исправляющих ошибки. Новосибирск: Наука, 1978djvu}}* {{Скачать|Алексеев - лекции по сложности комбинаторных алгоритмов.pdf}}# Поляк Б* {{Скачать|Мальцев - Алгоритмы и рекурсивные функции. Т. Введение в оптимизацию. М.: Наукаdjvu}}* {{Скачать|Маршалл, 1984Олкин - Неравенства - теория мажоризации и ее приложения.djvu}}
[[Категория:Кандаминимум]]
