Кандаминимум 010109 - ответы основной специальности — различия между версиями

Материал из YourcmcWiki
Перейти к: навигация, поиск
(Модель олигополистической конкуренции Курно. Теорема Нэша)
 
(не показаны 52 промежуточные версии 2 участников)
Строка 3: Строка 3:
 
По большей части берётся из лекций по МетОптам: {{Скачать|Лекции по методам оптимизации 2003.pdf}}. Другие источники описаны отдельно.
 
По большей части берётся из лекций по МетОптам: {{Скачать|Лекции по методам оптимизации 2003.pdf}}. Другие источники описаны отдельно.
  
=== Теоремы о достижении нижней грани функции (функционала) на множестве (в ''Е<sup>N</sup>'', в метрических пространствах, в гильбертовых пространствах) ===
+
==== Теоремы о достижении нижней грани функции (функционала) на множестве (в ''Е<sup>N</sup>'', в метрических пространствах, в гильбертовых пространствах) ====
  
 
Они же Теоремы Вейерштрасса.
 
Они же Теоремы Вейерштрасса.
Строка 10: Строка 10:
 
* Слабый вариант. Гильбертово пространство, компакт слабый, п/н слабо. Слабые п.т. мин. последовательности в Argmin.
 
* Слабый вариант. Гильбертово пространство, компакт слабый, п/н слабо. Слабые п.т. мин. последовательности в Argmin.
  
=== Выпуклые множества, выпуклые функции, сильно выпуклые функции, их свойства ===
+
==== Выпуклые множества, выпуклые функции, сильно выпуклые функции, их свойства ====
  
 
* '''Опр.''' множество выпуклое; функция выпуклая, строго выпуклая, сильно выпуклая с k > 0.
 
* '''Опр.''' множество выпуклое; функция выпуклая, строго выпуклая, сильно выпуклая с k > 0.
Строка 18: Строка 18:
 
* '''Т.''' (критерий сильной вып. для диф-мых функций).
 
* '''Т.''' (критерий сильной вып. для диф-мых функций).
  
=== Критерии оптимальности в гладких выпуклых задачах минимизации ===
+
==== Критерии оптимальности в гладких выпуклых задачах минимизации ====
  
* '''Т.''' <m>J(u) \in C^1(U)</m>, U выпукло &rArr; <m>(J'(u_*), u-u_*) >= 0</m> (1), <m>J'(u_* \in int U) = 0</m>. Если (1) и J(u) выпукла — значит u argmin (то есть &lArr;).
+
* '''Т.''' <m>J(u) \in C^1(U)</m>, U выпукло &rArr; <m>(J'(u_*), u-u_*) >= 0</m> (1), <m>J'(u_* \in int U) = 0</m>. Если (1) и J(u) выпукла — значит u argmin (то есть &lArr;).
 
* Ещё там есть пара примеров.
 
* Ещё там есть пара примеров.
  
=== Правило множителей Лагранжа ===
+
==== Правило множителей Лагранжа ====
  
 
* [[rupedia:Метод множителей Лагранжа]] относится к методам снятия ограничений.
 
* [[rupedia:Метод множителей Лагранжа]] относится к методам снятия ограничений.
 
* '''Задача.''' J(u) &rarr; min при огр. g<sub>i</sub> &le; 0.
 
* '''Задача.''' J(u) &rarr; min при огр. g<sub>i</sub> &le; 0.
* А мы будем минимизировать L(u,λ) = λ<sub>0</sub>J(u) + сумма λ<sub>i</sub>g<sub>i</sub>, λ<sub>i</sub> — множители Лагранжа.
+
* А мы будем минимизировать L(u,λ) = λ<sub>0</sub>J(u) + сумма λ<sub>i</sub>g<sub>i</sub>, λ<sub>i</sub> множители Лагранжа.
  
=== Теорема Куна-Таккера, двойственная задача, ее свойства ===
+
==== Теорема Куна-Таккера, двойственная задача, ее свойства ====
  
* '''Т.''' (Куна-Таккера) (обоснование метода Лагранжа) — всё существует, λ<sub>i</sub> неотрицательно, λ<sub>i</sub>g<sub>i</sub>=0 (усл.доп.нежёсткости). Для достаточности ещё λ<sub>i</sub> &ne; 0.
+
* '''Т.''' (Куна-Таккера) (обоснование метода Лагранжа) всё существует, λ<sub>i</sub> неотрицательно, λ<sub>i</sub>g<sub>i</sub>=0 (усл.доп.нежёсткости). Для достаточности ещё λ<sub>i</sub> &ne; 0.
 
* '''Опр.''' Двойственная задача: <m>(\psi(\lambda) = inf_{u \in U_0} L(u, \lambda)) \to sup_{\lambda \in \Lambda_0}</m>
 
* '''Опр.''' Двойственная задача: <m>(\psi(\lambda) = inf_{u \in U_0} L(u, \lambda)) \to sup_{\lambda \in \Lambda_0}</m>
 
* '''Т.''' (свойства дв.задачи). <m>\psi \le \psi^* \le \phi_* = J_* \le \phi(u)</m>. '''=''' только если L имеет седловую точку.
 
* '''Т.''' (свойства дв.задачи). <m>\psi \le \psi^* \le \phi_* = J_* \le \phi(u)</m>. '''=''' только если L имеет седловую точку.
  
=== Метод проекции градиента (в ''Е<sup>N</sup>'', в гильбертовом пространстве) ===
+
==== Метод проекции градиента (в ''Е<sup>N</sup>'', в гильбертовом пространстве) ====
  
* Условный минимум — минимизируем J(u) на множестве U. В лоб — метод град. спуска проецируем на U = pr<sub>U</sub>(u<sub>k</sub>-a<sub>k</sub>J'(u<sub>k</sub>)).
+
* Условный минимум — минимизируем J(u) на множестве U. В лоб — метод град. спуска проецируем на U = pr<sub>U</sub>(u<sub>k</sub>-a<sub>k</sub>J'(u<sub>k</sub>)).
* '''Т.''' (скорость сходимости) <m>\le |u_0 — u_*|_H q^k(\alpha), q(\alpha) = \sqrt{1-2k\alpha+\alpha² L²}</m>
+
* '''Т.''' (скорость сходимости) <m>\le |u_0 — u_*|_H q^k(\alpha), q(\alpha) = \sqrt{1-2k\alpha+\alpha² L²}</m>
  
=== Метод Ньютона ===
+
==== Метод Ньютона ====
  
* Идея — градиентный (или скорейший) спуск по квадратичной аппроксимации функции J(u) в окрестности u<sub>k</sub>.
+
* Идея — градиентный (или скорейший) спуск по квадратичной аппроксимации функции J(u) в окрестности u<sub>k</sub>.
 
* '''Т.''' (скорость сходимости) <m>\le \frac{2k}{L}q^{2^k}(1-q^{2^k})^{-1}</m>
 
* '''Т.''' (скорость сходимости) <m>\le \frac{2k}{L}q^{2^k}(1-q^{2^k})^{-1}</m>
  
=== Метод покоординатного спуска ===
+
==== Метод покоординатного спуска ====
  
 
* Сдвигаемся на a<sub>k</sub> в одну из сторон по одной координате по очереди, пока удаётся. Потом переходим к следующей. Потом дробим a.
 
* Сдвигаемся на a<sub>k</sub> в одну из сторон по одной координате по очереди, пока удаётся. Потом переходим к следующей. Потом дробим a.
 
* '''Т.''' (обоснование сходимости)
 
* '''Т.''' (обоснование сходимости)
  
=== Метод штрафных функций ===
+
==== Метод штрафных функций ====
  
* Можно также почитать [[mlwiki:Метод штрафных функций]].
+
* Можно также почитать [[machinelearning:Метод штрафных функций]].
 
* Относится к методам снятия ограничений.
 
* Относится к методам снятия ограничений.
 
* '''Задача.''' J(u) &rarr; min при огр. g<sub>i</sub> &le; 0 либо = 0 начиная с g<sub>m+1</sub>-ой.
 
* '''Задача.''' J(u) &rarr; min при огр. g<sub>i</sub> &le; 0 либо = 0 начиная с g<sub>m+1</sub>-ой.
* От задачи переходим к последовательности задач <m>J(u)+A_k P(u) \to min</m>. P(u) — штраф, <m>A_k \to +\inf</m>.
+
* От задачи переходим к последовательности задач <m>J(u)+A_k P(u) \to min</m>. P(u) штраф, <m>A_k \to +\inf</m>.
 
* '''Т.''' (обоснование) индив. штрафы должны давать огран. множество &rArr; всё сходится.
 
* '''Т.''' (обоснование) индив. штрафы должны давать огран. множество &rArr; всё сходится.
  
=== Метод барьерных функций ===
+
==== Метод барьерных функций ====
  
* Можно почитать [[mlwiki:Метод штрафных функций#Метод барьерных функций]].
+
* Можно почитать [[machinelearning:Метод штрафных функций#Метод барьерных функций]].
 
* По сути то же, что и метод штрафных функций, только штраф другого вида.
 
* По сути то же, что и метод штрафных функций, только штраф другого вида.
  
=== Метод динамического программирования ===
+
==== Метод динамического программирования ====
  
 
* Нет в МетОптах.
 
* Нет в МетОптах.
 
* Можно почитать книжку {{Скачать|Пападимитриу, Стайглиц - Комбинаторная оптимизация.djvu}}, страницы 461—464.
 
* Можно почитать книжку {{Скачать|Пападимитриу, Стайглиц - Комбинаторная оптимизация.djvu}}, страницы 461—464.
 
* Или просто [[rupedia:Динамическое программирование|Википедию]].
 
* Или просто [[rupedia:Динамическое программирование|Википедию]].
* Идея — поиск пути по минному полю с конца к началу, ибо любой конец оптимальной траектории оптимален (принцип оптимальности Беллмана).
+
* Идея — поиск пути по минному полю с конца к началу, ибо любой конец оптимальной траектории оптимален (принцип оптимальности Беллмана).
 
* Вообще-то ещё есть непрерывный аналог, идея та же, реализация на дифф.исчислении и ощутимо мохнатее.
 
* Вообще-то ещё есть непрерывный аналог, идея та же, реализация на дифф.исчислении и ощутимо мохнатее.
  
=== Устойчивость задач оптимизации. Метод стабилизации (регуляризация по Тихонову) ===
+
==== Устойчивость задач оптимизации. Метод стабилизации (регуляризация по Тихонову) ====
  
 
* '''Опр.''' корректно пост.задача: 1) существует, 2) единственно, 3) из сходимости значений следует сходимость аргументов.
 
* '''Опр.''' корректно пост.задача: 1) существует, 2) единственно, 3) из сходимости значений следует сходимость аргументов.
* Суть метода — в отсутствие (3) добавить к J(u) <m>+ \alpha |u|²</m> и минимизировать полученный ''функционал Тихонова''.
+
* Суть метода — в отсутствие (3) добавить к J(u) <m>+ \alpha |u|²</m> и минимизировать полученный ''функционал Тихонова''.
 
* '''Т.''' (обоснование метода).
 
* '''Т.''' (обоснование метода).
  
=== Линейное программирование. Симплекс-метод. Двойственные задачи линейного программирования ===
+
==== Линейное программирование. Симплекс-метод. Двойственные задачи линейного программирования ====
  
 
* '''Опр.''' ЗЛП, каноническая ЗЛП (u &ge; 0), угловая точка, невырожденная угловая точка, невырожденная задача.
 
* '''Опр.''' ЗЛП, каноническая ЗЛП (u &ge; 0), угловая точка, невырожденная угловая точка, невырожденная задача.
 
* '''Т.''' (критерий угловой точки) (про линейную комбинацию r столбцов матрицы A)
 
* '''Т.''' (критерий угловой точки) (про линейную комбинацию r столбцов матрицы A)
* Симплекс-метод — идея перебора угловых точек в направлении минимизации функции.
+
* Симплекс-метод — идея перебора угловых точек в направлении минимизации функции.
  
 
== Исследование операций, теория игр ==
 
== Исследование операций, теория игр ==
  
Источники — две книжки по тиграм ('''т'''еории '''игр''') Васина и Морозова:
+
Источники — две книжки по тиграм ('''т'''еории '''игр''') Васина и Морозова:
 
# {{Скачать|А.А.Васин, В.В.Морозов - Теория игр и модели математической экономики.djvu}}
 
# {{Скачать|А.А.Васин, В.В.Морозов - Теория игр и модели математической экономики.djvu}}
 
# {{Скачать|Васин, Морозов - Дополнительные главы теории операций - Глава 5 - Теория принятия решений.djvu}} (только 5-я глава).
 
# {{Скачать|Васин, Морозов - Дополнительные главы теории операций - Глава 5 - Теория принятия решений.djvu}} (только 5-я глава).
  
=== Антагонистические игры. Матричные игры, теорема о минимаксе ===
+
==== Антагонистические игры. Матричные игры, теорема о минимаксе ====
  
 
* '''Опр.''' седловая точка F(x, y); антаг. игра <tt><X,Y,F(x,y)></tt>; игра имеет решение; значение игры; матричная игра; нижнее и верхнее значения игры (sup inf и inf sup); максиминная, минимаксная стратегии.
 
* '''Опр.''' седловая точка F(x, y); антаг. игра <tt><X,Y,F(x,y)></tt>; игра имеет решение; значение игры; матричная игра; нижнее и верхнее значения игры (sup inf и inf sup); максиминная, минимаксная стратегии.
Строка 96: Строка 96:
 
* '''Т.''' (о минимаксе) 1) есть с.т. &hArr; max inf = min sup. 2) с.т. = стратегии максиминная и минимаксная.
 
* '''Т.''' (о минимаксе) 1) есть с.т. &hArr; max inf = min sup. 2) с.т. = стратегии максиминная и минимаксная.
  
=== Выпукло-вогнутые антагонистические игры. Теорема существования седловой точки ===
+
==== Выпукло-вогнутые антагонистические игры. Теорема существования седловой точки ====
  
 
* '''Опр.''' игра с вогнутой, выпуклой функцией выигрыша.
 
* '''Опр.''' игра с вогнутой, выпуклой функцией выигрыша.
Строка 102: Строка 102:
 
* '''Т.''' (существование решения) <m>x^0 \in X, \psi^0 = \sum_1^{m+1} q_j^0 I_y_j</m>
 
* '''Т.''' (существование решения) <m>x^0 \in X, \psi^0 = \sum_1^{m+1} q_j^0 I_y_j</m>
  
=== Бескоалиционные игры ''n'' лиц. Равновесие по Нэшу ===
+
==== Бескоалиционные игры ''n'' лиц. Равновесие по Нэшу ====
  
 
* '''Опр.''' игра n лиц.
 
* '''Опр.''' игра n лиц.
Строка 108: Строка 108:
 
* '''Т.''' (существования равновесия)
 
* '''Т.''' (существования равновесия)
  
=== Принцип гарантированного результата. Минимаксные задачи ===
+
==== Принцип гарантированного результата. Минимаксные задачи ====
  
 
* Из книжки 2.
 
* Из книжки 2.
Строка 115: Строка 115:
 
* '''Т.''' F1 &le; F2 &le; F3 &le; F4. Противник знает x &rarr; не знает &rarr; мы знаем y.
 
* '''Т.''' F1 &le; F2 &le; F3 &le; F4. Противник знает x &rarr; не знает &rarr; мы знаем y.
  
=== Многокритериальная оптимизация. Оптимальность по Парето. Лексикографический подход ===
+
==== Многокритериальная оптимизация. Оптимальность по Парето. Лексикографический подход ====
  
 
* Из книжки 2.
 
* Из книжки 2.
* Многокритериальная оптимизация — как выбрать стратегию, если критериев качества несколько?
+
* Многокритериальная оптимизация — как выбрать стратегию, если критериев качества несколько?
 
* Опт. по Парето = «не улучшишь хотя бы один критерий».
 
* Опт. по Парето = «не улучшишь хотя бы один критерий».
 
* Опт. по Слейтеру = «не улучшишь все критерии разом».
 
* Опт. по Слейтеру = «не улучшишь все критерии разом».
* Лексикографический подход — упорядочиваем их по важности и ORDER BY.
+
* Лексикографический подход — упорядочиваем их по важности и ORDER BY.
  
=== Кооперативные игры (''с''-ядро, вектор Шепли) ===
+
==== Кооперативные игры (''с''-ядро, вектор Шепли) ====
  
 
* Игроки делят выручку.
 
* Игроки делят выручку.
 
* '''Опр.''' коалиции, хар.функция, супераддитивная, игра, игра с постоянной суммой, вектор дележа, эквив. игры (масштаб-сдвиг), 0-1 редуц. форма игры.
 
* '''Опр.''' коалиции, хар.функция, супераддитивная, игра, игра с постоянной суммой, вектор дележа, эквив. игры (масштаб-сдвиг), 0-1 редуц. форма игры.
* Индивидуальная разумность — выручку в коалиции не меньше, чем индивидуальная игрока.
+
* Индивидуальная разумность — выручку в коалиции не меньше, чем индивидуальная игрока.
* Групповая разумность — выручка любой подкоалиации не меньше, чем её индивидуальная.
+
* Групповая разумность — выручка любой подкоалиации не меньше, чем её индивидуальная.
* '''Ядро''' (c-ядро) — дележи, удовлетворяющие групповой разумности.
+
* '''Ядро''' (c-ядро) дележи, удовлетворяющие групповой разумности.
* '''Вектор Шепли''' — состоит из компонент, равных мат.ожиданиям вкладов конкретных игроков.
+
* '''Вектор Шепли''' состоит из компонент, равных мат.ожиданиям вкладов конкретных игроков.
  
=== Задача распределения ресурсов (модель Гросса, принцип уравнивания Гермейера) ===
+
==== Задача распределения ресурсов (модель Гросса, принцип уравнивания Гермейера) ====
  
 
* Из книжки 2.
 
* Из книжки 2.
* Задача 1: максимизируем минимум эффекта по всем пунктам.
+
* Задача 1: максимизируем минимум эффекта по всем пунктам.
* '''Т.''' (пр. ур. Гермейера) оптимальное решение существует и единственно — идея: вначале распределяем ресурсы по наиболее слабым пунктам так, чтобы эффекта им досталось поровну.
+
* '''Т.''' (пр. ур. Гермейера) оптимальное решение существует и единственно — идея: вначале распределяем ресурсы по наиболее слабым пунктам так, чтобы эффекта им досталось поровну.
 
* Задача 2: максимизируем сумму эффекта по всем пунктам.
 
* Задача 2: максимизируем сумму эффекта по всем пунктам.
 
* '''Т.''' (критерий Гросса) аналог уравнивания для производных.
 
* '''Т.''' (критерий Гросса) аналог уравнивания для производных.
  
=== Иерархические игры ===
+
==== Иерархические игры ====
  
 
* '''Опр.''' иерархической игры (есть обмен информацией о стратегиях).
 
* '''Опр.''' иерархической игры (есть обмен информацией о стратегиях).
* Г<sub>1</sub>: x &rarr; y(x) — Y знает стратегию X.
+
* Г<sub>1</sub>: x &rarr; y(x) Y знает стратегию X.
 
* Г<sub>2</sub>: f(y) &rarr; y(f(y)) &rarr; x=f(y).
 
* Г<sub>2</sub>: f(y) &rarr; y(f(y)) &rarr; x=f(y).
 
* Г<sub>3</sub>: f<sub>1</sub>(g(x)) &rarr; g(x) &rarr; x=f(g(x)).
 
* Г<sub>3</sub>: f<sub>1</sub>(g(x)) &rarr; g(x) &rarr; x=f(g(x)).
 
* '''Т.''' (Гермейера). В Г<sub>2</sub> гарантированный результат игрока X = максимум из 1) гарантированного результата X при наилучшем ответе Y на стратегию наказания, применяемую к нему X и 2) лучшего результата X в случае, если он позволит Y получить больше, чем в первом случае.
 
* '''Т.''' (Гермейера). В Г<sub>2</sub> гарантированный результат игрока X = максимум из 1) гарантированного результата X при наилучшем ответе Y на стратегию наказания, применяемую к нему X и 2) лучшего результата X в случае, если он позволит Y получить больше, чем в первом случае.
  
=== Потоки в сетях (теорема Форда-Фалкерсона, задача и алгоритмы поиска кратчайшего пути в графе, задача составления расписаний, транспортная задача) ===
+
==== Потоки в сетях (теорема Форда-Фалкерсона, задача и алгоритмы поиска кратчайшего пути в графе, задача составления расписаний, транспортная задача) ====
  
 
* В книжках нет.
 
* В книжках нет.
 
* Можно почитать [[rupedia:Теорема Форда — Фалкерсона]], [[rupedia:Транспортная задача]], [[rupedia:Алгоритм Дейкстры]].
 
* Можно почитать [[rupedia:Теорема Форда — Фалкерсона]], [[rupedia:Транспортная задача]], [[rupedia:Алгоритм Дейкстры]].
 
* '''Опр.''' транспортная сеть, поток, сечение графа, величина сечения.
 
* '''Опр.''' транспортная сеть, поток, сечение графа, величина сечения.
* '''Т.''' (Ф-Ф, очевидная — «пропускная способность определяется слабым звеном») максимальный поток между истоком и стоком равен величине минимального сечения.
+
* '''Т.''' (Ф-Ф, очевидная — «пропускная способность определяется слабым звеном») максимальный поток между истоком и стоком равен величине минимального сечения.
 
* Решение транспортной задачи [[rupedia:Транспортная задача#Решение с помощью теории графов|аналогично]] Ф-Ф.
 
* Решение транспортной задачи [[rupedia:Транспортная задача#Решение с помощью теории графов|аналогично]] Ф-Ф.
* Поиск кратчайшего пути — динамическое программирование, [[rupedia:Алгоритм Дейкстры|алгоритм Дейкстры (жадный)]].
+
* Поиск кратчайшего пути — динамическое программирование, [[rupedia:Алгоритм Дейкстры|алгоритм Дейкстры (жадный)]].
  
 
== Оптимальное управление ==
 
== Оптимальное управление ==
  
# Постановка задач оптимального управления, их классификация.
+
Частично берётся из лекций {{Скачать|Орлов - лекции по оптимальному управлению 2005.pdf}}. Но содержит несколько мистические вопросы — например, 3 последних, для которых связных материалов найти не удалось вообще. Дифференциальные игры можно, конечно, почитать по книге Айзекса 1967-го года, но там про это вся книга (480 страниц), но нам-то кратко надо.
# Принцип максимума Понтрягина. Краевая задача принципа максимума.
+
 
# Линейная задача быстродействия, ее свойства (существование решения, число переключений).
+
''Специалисты по оптимальному управлению — welcome! Дополните секцию! (и уберите пометки (404) = (не найдено) из заголовков)''
# Принцип максимума и вариационное исчисление.
+
 
# Управляемость и наблюдаемость в линейных системах, их взаимосвязь (взаимодвойственность). Теоремы Калмана, Красовского.
+
==== Постановка задач оптимального управления, их классификация ====
# Метод динамической регуляризации в задаче наблюдения.
+
 
# Дифференциальные игры.
+
* '''Опр.''' задача ОУ (дифур, доп.множества, нач.усл., функционал), множество достижимости.
 +
* Задачи: быстродействия, с фикс. временем, с закреплёнными концами, с подвижными концами, с неавтономной системой.
 +
 
 +
==== Принцип максимума Понтрягина. Краевая задача принципа максимума ====
 +
 
 +
* '''Опр.''' сопряжённая система, гамильтониан.
 +
* '''Л.''' скалярное произведение решений прямой и сопряжённой систем константно.
 +
* '''Т.''' (ПМП) <m>\forall (u(t), x(t)) \exists \psi(t): \psi' = H_x'</m>, H(x, u,&psi;) достигает максимума, а максимум постоянен на всём отрезке времени.
 +
* '''Т.''' (тоже ПМП, в другом виде) для оптимальной пары, если начальное и конечное множества выпуклы, существует &psi; такое, что верно условие максимума: (u(t),&psi;(t))=c(U,&psi;(t)) и 2 трансверсальности: (x(t<sub>0</sub>),&psi;(t<sub>0</sub>))=c(M<sub>0</sub>,&psi;(t<sub>0</sub>)) и (x(t<sub>1</sub>),-&psi;(t<sub>1</sub>))=c(M<sub>1</sub>,-&psi;(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}}, а также из {{Скачать|Алексеев - лекции по сложности комбинаторных алгоритмов.pdf}}.
# Метод ветвей и границ (на примере задач целочисленного или булева линейного программирования).
+
 
# Временная сложность решения задач дискретной оптимизации. Основные классы сложности (''P'', ''NP'', ''NPC'').
+
=== Целочисленное линейное программирование (метод Гомори, свойства унимодулярности матрицы ограничений) ===
# ''NP''-трудные задачи (задача о рюкзаке, задача коммивояжера).
+
 
 +
* '''Опр.''' задача ЦЛП (ЛП + x {{in}} Z), унимодулярность матрицы (|det|=1).
 +
* К ней можно многое свести (коммивояжера, расписание, выполнимость КНФ), а вот решать округлением лучше не надо :) также к ней сводятся «нелинейности» — барьер, дихотомия, дискретные переменные.
 +
* '''Т.''' A унимод. &rArr; для целых b угловые точки целочисленны.
 +
* Метод отсечений Гомори — добавляем ограничения, не отсекающие целочисленных точек — целая часть i-ой строки с = заменённым на &ge;.
 +
 
 +
=== Метод ветвей и границ (на примере задач целочисленного или булева линейного программирования) ===
 +
 
 +
* Идея — разбиваем задачу на две взаимодополняющих задачи (либо нецелая x<sub>i</sub> &le; целой части, либо &ge; целой части + 1).
 +
* Вторая идея — при ветвлениях можно не идти во всю глубину, так как меньше чем найденное не-целочисленное решение уже не будет. Если есть другое решение, дающее лучший результат — стоп.
 +
* Ещё пример — [[rupedia:Алгоритм Дейкстры|алгоритм Дейкстры]]. ЦЛП здесь не важно.
 +
 
 +
=== Временная сложность решения задач дискретной оптимизации. Основные классы сложности (''P'', ''NP'', ''NPC'') ===
 +
 
 +
* '''Опр.''' f полиномиально сводится к g, P, NP, NP-полные (NPC).
 +
 
 +
=== ''NP''-трудные задачи (задача о рюкзаке, задача коммивояжера) ===
 +
 
 +
* Можно также почитать [[rupedia:Задача о ранце]], [[rupedia:Задача коммивояжёра]].
 +
* ЗР: из неограниченного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.
 +
* ЗК: отыскание самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
  
 
== Теория функциональных систем ==
 
== Теория функциональных систем ==
  
# Проблема полноты. Теорема о полноте систем функций двузначной логики ''P''<sub>2</sub>.
+
Берётся снова из {{Скачать|Яблонский - Введение в дискретную математику.djvu}}.
# Алгоритм распознавания полноты систем функций ''k''-значной логики ''P<sub>k</sub>''.
+
 
# Теорема Слупецкого.
+
==== Проблема полноты. Теорема о полноте систем функций двузначной логики ''P''<sub>2</sub> ====
# Особенности ''k''-значных логик.
+
 
# Автоматы. Регулярные события и их представление в автоматах.
+
* Формула над системой {''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…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й набор по всем переменным &ge; 2го, тогда f(1го)&ge;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&ge;3 в P<sub>k</sub> {{exists}} замкнутый класс, не имеющий базиса.
 +
* '''Т.''' (Мучника) для всякого k&ge;3 в P<sub>k</sub> {{exists}} замкнутый класс, имеющий счётный базис.
 +
* '''Т.''' для всякого k&ge;3 в P<sub>k</sub> {{exists}} континуум различных замкнутых классов.
 +
* '''Т.''' система полиномов в P<sub>k</sub> полна &hArr; k — простое число.
 +
 
 +
==== Автоматы. Регулярные события и их представление в автоматах ====
 +
 
 +
==== Эксперименты с автоматами ====
 +
 
 +
* Берётся из {{Скачать|Алексеев - лекции по дискретной математике 2002.pdf}}.
 +
* '''Опр.''' автомат с выходом, отличимые состояния, эксперимент.
 +
* '''Л.''' (о существовании отличимых экспериментом данной длины состояний)
 +
* '''Т.''' (Мура) (о максимальной длине эксперимента, +пример)
 +
* '''Т.''' (про отличимые состояния разных автоматов)
 +
* '''Т.''' (о макс. длине эксп. отличающего состояния двух автоматов, +пример)
 +
 
 +
==== Алгоритмическая неразрешимость проблемы полноты для автоматов ====
 +
 
 +
==== Вычислимые функции. Эквивалентность класса рекурсивных функций и класса функций, вычислимых на машинах Тьюринга ====
 +
 
 +
==== Алгоритмическая неразрешимость проблемы эквивалентности слов в ассоциативных исчислениях ====
 +
 
 +
* Берётся из {{Скачать|Мальцев - Алгоритмы и рекурсивные функции.djvu}}, стр. 254.
 +
* '''Опр.''' полугруппа, система порождающих, определяющие соотношения, умножение классов.
 +
* '''Опр.''' ассоциативного исчисления (набор замен); эквивалентные слова.
 +
* '''Т.''' (Пост, Марков) {{exists}} ассоциативное исчисление с алгоритмически неразрешимой проблемой эквивалентности слов.
  
 
== Комбинаторный анализ и теория графов ==
 
== Комбинаторный анализ и теория графов ==
Строка 193: Строка 279:
 
# {{Скачать|Оре - Теория графов.djvu}}
 
# {{Скачать|Оре - Теория графов.djvu}}
  
=== Основные комбинаторные числа ===
+
==== Основные комбинаторные числа ====
  
=== Оценки и асимптотики для комбинаторных чисел ===
+
Число '''подмножеств''' множества = 2<sup>|M|</sup>.
  
=== Графы и сети. Оценки числа графов и сетей различных типов ===
+
[[rupedia:Размещение|Число '''размещений''']] элементов из n по k = (n)<sub>k</sub> (убывающий факториал).
  
=== Плоские и планарные графы. Формула Эйлера для плоских графов. Необходимые условия планарности в теореме Понтрягина—Куратовского (без доказательства достаточности) ===
+
Число '''перестановок''' n элементов = n!.
 +
 
 +
e = <m>lim(1+\frac{1}{n})^n</m>
 +
 
 +
[[rupedia:Сочетание|Число '''сочетаний''']] из n по k, или же биномиальный коэффициент <m>{n \choose k} = C_n^k = \frac{n!}{k!\left(n-k\right)!}</m>.
 +
 
 +
Число '''сочетаний с повторениями''' из n по k <m>H_n^k = {n+k-1 \choose k}</m>
 +
 
 +
[[rupedia:Мультиномиальный коэффициент|Число разбиений]] n-элементного множества на множества мощностей <m>n_1, \dots, n_m</m> равняется <m>{n\choose n_1,\ n_2,\ \dots,\ n_m} = \frac{n!}{n_1!n_2!\dots n_m!}</m>.
 +
 
 +
Число разбиений n-элементного множества на k множеств (число Стирлинга) <m>\Phi(n, k) = \frac{1}{k!}\sum_{n_1+\dots+n_k=n, n_i>0} \frac{n!}{n_1!n_2!\dots n_k!}</m> и число всех разбиений (число Белла) <m>\Phi(n) = \sum_{k=0}^{n} \Phi(n, k) = \sum_0^{n-1}{n-1 \choose i}\Phi(i)</m>
 +
 
 +
==== Оценки и асимптотики для комбинаторных чисел ====
 +
 
 +
* '''Т.''' (логарифм факториала) ln n! ~ (n+0.5) ln n
 +
* '''Т.''' (формула Стирлинга) n! ~ <m>a\sqrt{n}n^n e^{-n}</m>
 +
* '''Т.''' (корень квадратный из пи)
 +
* '''Т.''' (число сочетаний)
 +
* '''Т.''' (сумма числа сочетаний)
 +
* '''Т.''' (числа Белла)
 +
 
 +
==== Графы и сети. Оценки числа графов и сетей различных типов ====
 +
 
 +
* '''Опр.''' граф, цикл, петля, связный граф, сеть, степень сети, степенная структура сети
 +
* '''Т.''' число графов c h рёбрами без изол.вершин меньше a(bh)<sup>h</sup>, a, b = Const.
 +
* '''Т.''' число укладок деревьев с h рёбрами меньше 4<sup>h</sup>.
 +
* '''Т.''' (Лупанова) число сетей с заданной степ.структурой &le; c<sup>h</sup>h<sup>(&mu;-1)h</sup>, c зависит только от числа полюсов, средней степени и числа наборов.
 +
 
 +
==== Плоские и планарные графы. Формула Эйлера для плоских графов. Необходимые условия планарности в теореме Понтрягина—Куратовского (без доказательства достаточности) ====
  
 
* Можно почитать [[rupedia:Планарный граф]].
 
* Можно почитать [[rupedia:Планарный граф]].
* '''Т.''' (П-К) — это про то, что граф планарен, если не содержит гомеоморфных K<sub>5</sub> и K<sub>3,3</sub> подграфов.
+
* '''Т.''' (П-К) это про то, что граф планарен, если не содержит гомеоморфных K<sub>5</sub> и K<sub>3,3</sub> подграфов.
 
* '''Т.''' (ф-ла Эйлера) ''Вершин − Ребёр + Граней = 2'' у всякого связного плоского графа.
 
* '''Т.''' (ф-ла Эйлера) ''Вершин − Ребёр + Граней = 2'' у всякого связного плоского графа.
  
=== Экстремальная теория графов. Теорема Турана ===
+
==== Экстремальная теория графов. Теорема Турана ====
  
=== Теорема Рамсея ===
+
* Можно также почитать [[rupedia:Теорема Турана]].
 +
* '''Т.''' (Турана) (макс. количество ребёр в графе, не содержащем полного n-вершинного подграфа)
 +
 
 +
==== Теорема Рамсея ====
 +
 
 +
* Можно также почитать [[rupedia:Теорема Рамсея]].
 +
* '''Т.''' (Рамсея) («полная неупорядоченность невозможна») для любого набора классов сочетаний r элементов в любом достаточно большом множестве всегда найдётся подмножество, все сочетания r элементов которого будут принадлежать одному классу.
 +
* Условно говоря, если на вечеринке 6 человек, то либо какие-то 3 из них все друг с другом знакомы, либо какие-то 3 из них друг с другом незнакомы.
 +
* Правда «достаточно большое множество» — '''очень большое'''.
  
 
== Теория кодирования ==
 
== Теория кодирования ==
  
=== Алфавитное кодирование. Критерии однозначности декодирования. Неравенство Крафта—Макмиллана ===
+
Первые 3 вопроса берутся из {{Скачать|Яблонский - Введение в дискретную математику.djvu}}, можно также (но хуже) из лекций Алексеева: {{Скачать|Алексеев - лекции по дискретной математике 2002.pdf}}.
  
=== Оптимальное кодирование. Построение кодов с минимальной избыточностью ===
+
Другие 2 можно прочитать в {{Скачать|Макмиллан, Слоэн - Теория кодов, исправляющих ошибки.djvu}}.
  
=== Самокорректирующиеся коды. Граница упаковки. Коды Хемминга, исправляющие единичную ошибку ===
+
==== Алфавитное кодирование. Критерии однозначности декодирования. Неравенство Крафта—Макмиллана ====
  
=== Конечные поля и их основные свойства ===
+
* '''Опр.''' кодирование: алфавитное, взаимно однозначное, равномерное, префиксное, постфиксное; неприводимое слово.
 +
* '''Т.''' (Маркова) если кодирование неоднозначно, существуют два слова не длиннее целой части 0.5(W+1)(L-r+2), имеющие одинаковый код.
 +
* '''Т.''' (Макмиллана) если кодирование однозначно, то <m>\sum{i=1}{r}\frac{1}{q^{l_i}} \le 1</m>.
  
=== Коды Боуза—Чоудхури—Хоквингема ===
+
==== Оптимальное кодирование. Построение кодов с минимальной избыточностью ====
  
* Можно почитать [[rupedia:Код Боуза — Чоудхури — Хоквингема]], как пример - [[rupedia:Код Рида — Соломона]].
+
* '''Опр.''' цена кода, оптимальный код, код Хаффмана.
 +
* '''У.''' если существует оптимальный код, существует оптимальный префиксный код с теми же длинами слов.
 +
* Алгоритм построения кода с мин.избыточностью — редукция списка вероятностей.
 +
* ''Отсебятина: а ещё есть [[rupedia:Арифметическое кодирование|арифметик]]…''
 +
 
 +
==== Самокорректирующиеся коды. Граница упаковки. Коды Хемминга, исправляющие единичную ошибку ====
 +
 
 +
* '''Опр.''' самокорректирующиеся коды.
 +
* [[rupedia:Код Хемминга]] — исправляющий одну ошибку равномерный код, в котором i-ый контрольный разряд — сумма информационных разрядов с номерами, включающими 1 в i-ой позиции двоичной записи.
 +
* '''Т.''' расстояние между любыми двумя кодовыми словами кода Хэмминга &ge; 3.
 +
* '''Т.''' расстояние между кодовыми словами кода, исправляющего k ошибок &ge; 2k+1.
 +
 
 +
==== Конечные поля и их основные свойства ====
 +
 
 +
* Можно почитать [[rupedia:Кольцо (математика)]], [[rupedia:Конечное поле]].
 +
* Поле — коммутативное кольцо с единицей, в котором для всякого ненулевого элемента есть обратный.
 +
* Поле Галуа GF(n) — [[rupedia:Конечное поле|конечное поле]].
 +
* Для каждого простого числа p и натурального n существует конечное поле из q = p<sup>n</sup> элементов, единственное с точностью до изоморфизма. Это поле изоморфно полю разложения многочлена x<sup>q</sup>-x.
 +
 
 +
==== Коды Боуза—Чоудхури—Хоквингема ====
 +
 
 +
* Можно почитать [[rupedia:Код Боуза — Чоудхури — Хоквингема]], [[rupedia:Циклический код]] (а в CD-ROM’ах используется [[rupedia:Код Рида — Соломона]]).
 +
* Коды БЧХ — «обобщение» Хэмминга на случай двух ошибок. Требование решения системы уравнений относительно i и j (позиций ошибок) как раз и приводит к полям…
 +
* '''Опр.''' циклический код, порождающий полином, проверочная матрица.
 +
* '''Т.''' коды БЧХ — циклические коды, задаваемые порождающим полиномом.
 +
* '''Т.''' о границе БЧХ.
  
 
== Управляющие системы ==
 
== Управляющие системы ==
  
# Понятие управляющей системы. Основные модельные классы управляющих систем: дизъюнктивные нормальные формы, формулы, контактные схемы, схемы из функциональных элементов, автоматы, машины Тьюринга, операторные алгоритмы. Основные проблемы теории управляющих систем.
+
Вопрос тут один, ёмкий, аки нецензурное послание.
 +
 
 +
==== Понятие управляющей системы. Основные модельные классы управляющих систем: дизъюнктивные нормальные формы, формулы, контактные схемы, схемы из функциональных элементов, автоматы, машины Тьюринга, операторные алгоритмы. Основные проблемы теории управляющих систем ====
 +
 
 +
Берётся он из {{Скачать|Ложкин С.А. - Лекции по основам кибернетики 2004.djvu}}.
 +
 
 +
* Управляющая система — типа задаёт поведение некоторой системы.
 +
* '''Опр.''' элементарные конъюнкции, ДНФ, КНФ; формула; эквивалентные формулы; КС; эквивалентные КС (&hArr; эквив. все формулы); СФЭ; [[rupedia:Абстрактный автомат|автомат]]; [[rupedia:Машина Тьюринга|МТ]] (ДМТ, НМТ?).
 +
* Операторные алгоритмы — последовательность приказов, приказ = операция + два номера других приказа (ветвление определён / не определён), либо «СТОП».
 +
* Основные задачи:
 +
*# Синтез минимальных по сложности систем.
 +
*# Эквивалентные преобразования.
 +
*# Контроль и надёжность.
  
 
== Дизъюнктивные нормальные формы ==
 
== Дизъюнктивные нормальные формы ==
  
# Проблема минимизации булевых функций. Дизъюнктивные нормальные формы (ДНФ). Постановка задачи в геометрической форме.
+
Берётся из лекций Ложкина по ОК: {{Скачать|Ложкин С.А. - Лекции по основам кибернетики 2004.djvu}}.
# Локальные алгоритмы построения ДНФ. Построение ДНФ ''∑Т'' (сумма тупиковых) с помощью локального алгоритма.
+
 
# Невозможность построения ДНФ ''∑М'' (сумма минимальных) в классе локальных алгоритмов.
+
==== Проблема минимизации булевых функций. Дизъюнктивные нормальные формы (ДНФ). Постановка задачи в геометрической форме ====
 +
 
 +
==== Локальные алгоритмы построения ДНФ. Построение ДНФ ''∑Т'' (сумма тупиковых) с помощью локального алгоритма ====
 +
 
 +
* '''Опр.''' тупиковая ДНФ, ДНФ ΣT и {{cap}}T, ядровая точка, ядровая грань, ядро; пучок, регулярные и нерегулярные точки, регулярные грани; окрестность порядка r, ДНФ Квайна; локальный алгоритм.
 +
* '''Л.''' (о составе ДНФ {{cap}}T)
 +
* '''Т.''' (Журавлева) (о составе ДНФ ΣT), идея о покрытии регулярных точек гранями из меньшего пучка.
 +
 
 +
==== Невозможность построения ДНФ ''∑М'' (сумма минимальных) в классе локальных алгоритмов ====
 +
 
 +
* '''Опр.''' ДНФ ΣM, цепная функция.
 +
* '''Т.''' (Журавлева) (неприменимость локального алгоритма для построения ДНФ ΣM цепной функции).
  
 
== Синтез и сложность управляющих систем ==
 
== Синтез и сложность управляющих систем ==
  
# Асимптотически оптимальный метод синтеза схем из функциональных элементов.
+
Берётся всё из тех же лекций Ложкина: {{Скачать|Ложкин С.А. - Лекции по основам кибернетики 2004.djvu}}.
# Асимптотически оптимальный метод синтеза контактных схем.
+
 
# Инвариантные классы и их свойства.
+
==== Асимптотически оптимальный метод синтеза схем из функциональных элементов ====
# Синтез схем для функций из некоторых инвариантных классов.
+
 
# Нижние оценки сложности реализации булевых функций параллельно-последовательными контактными схемами.
+
* '''Опр.''' дискретно-универсальное множество функций.
# Нижние оценки сложности реализации булевых функций формулами в произвольном базисе.
+
* '''Т.''' (Лупанова) о верхней оценке функции Шеннона в классе СФЭ.
 +
* '''Сл.''' (асимптотика функции Шеннона).
 +
 
 +
==== Асимптотически оптимальный метод синтеза контактных схем ====
 +
 
 +
* '''Опр.''' m-регулярное множество.
 +
* '''Т.''' (Лупанова) то же, но в классе КС.
 +
* Идея метода Лупанова: разложение функции по подфункциям и полосам, построение суперпозиции КС на основе m-регулярного множества.
 +
 
 +
==== Инвариантные классы и их свойства ====
 +
 
 +
* Берётся из {{Скачать|Сапоженко - Некоторые вопросы сложности алгоритмов.djvu}}.
 +
* '''Опр.''' инв.класс, характеристика ИК, сложная функция, правильный алгоритм.
 +
* Пример ИК с характеристикой 0.5.
 +
* '''Т.''' (Яблонского) о существовании ИК с заданной характеристикой.
 +
* '''Т.''' (Яблонского) о работе правильного алгоритма, строящего сложную последовательность функций.
 +
 
 +
==== Синтез схем для функций из некоторых инвариантных классов ====
 +
 
 +
* Из Сапоженко и Ложкина.
 +
* '''Т.''' (Лупанова) о верхней оценке функции Шеннона для ИК с заданной характеристикой.
 +
* '''Т.''' о нижней мощностной оценке функции Шеннона для ИК с характеристикой, большей 1.
 +
 
 +
==== Нижние оценки сложности реализации булевых функций параллельно-последовательными контактными схемами ====
 +
 
 +
* Соотношение между π-схемами и формулами с поднятыми отрицаниями.
 +
* '''Опр.''' каркас.
 +
* Оценка числа формул данной сложности на основе количества каркасов и способов подстановки переменных.
 +
* '''Л.''' о верхней оценке количества π-схем данной сложности через число формул.
 +
* '''Л.''' об обращении степенного неравенства.
 +
* Принцип получения нижних оценок функции Шеннона.
 +
* '''Т.''' о нижней оценке функции Шеннона.
 +
 
 +
==== Нижние оценки сложности реализации булевых функций формулами в произвольном базисе ====
 +
 
 +
* '''Опр.''' приведенный вес, каркас.
 +
* '''Л.''' о соотношении между рангом формулы, ее сложностью и приведенным весом.
 +
* Оценка числа формул данной сложности на основе количества каркасов и способов подстановки переменных.
  
 
== Эквивалентные преобразования управляющих систем ==
 
== Эквивалентные преобразования управляющих систем ==
  
# Эквивалентные преобразования формул двузначной логики ''Р''<sub>2</sub>.
+
Опять-таки берётся из лекций Ложкина {{Скачать|Ложкин С.А. - Лекции по основам кибернетики 2004.djvu}}, кроме примера Линдона, который можно взять из методички Алексеева {{Скачать|Алексеев и др. - Задачи по курсу Основы кибернетики.djvu}}.
# Эквивалентные преобразования контактных схем.
+
 
# Эквивалентные преобразования операторных алгоритмов.
+
==== Эквивалентные преобразования формул двузначной логики ''Р''<sub>2</sub> ====
# Пример Линдона.
+
 
 +
* '''Опр.''' тождество, выводимость, эквивалентное преобразование.
 +
* Тождества: ассоциативности, коммутативности, отождествления переменных, де Моргана, дистрибутивности, поглощения, подстановки констант.
 +
* '''Т.''' Основная и расширенная системы тождеств эквивалентны.
 +
* '''Т.''' основной система тождеств полна (поднятие отрицаний &rarr; раскрытие скобок &rarr; приведение подобных, переход к совершенной ДНФ).
 +
 
 +
==== Эквивалентные преобразования контактных схем ====
 +
 
 +
* '''Опр.''' тождества основные, вспомогательные, обобщенные, каноническая КС, каноническая цепь, цикломатическое число графа (компонент связности + рёбер — вершин), контактной схемы.
 +
* '''Т.''' основная система тождеств полна (принцип индукции &rarr; расширение контактов &rarr; применение тождества «звезда» &rarr; добавление фиктивных цепей &rarr; удаление вершины &rarr; удаление висячих и параллельных цепей &rarr; удаление транзитной проводимости).
 +
* '''Л.''' (об изменении цикломатического числа при эквивалентных преобразованиях).
 +
* '''Т.''' (о неполноте любой конечной системы тождеств).
 +
 
 +
==== (404) Эквивалентные преобразования операторных алгоритмов ====
 +
 
 +
''Специалисты, welcome — дополните секцию и уберите пометку (404) из заголовка!''
 +
 
 +
==== Пример Линдона ====
 +
 
 +
* '''Опр.''' функция Линдона (которая с 1 5 6).
 +
* Основные тождества и их вывод, преобразование к каноническому виду и его единственность.
 +
* '''Т.''' Полнота системы тождеств.
 +
* Свойство C<sup>n</sup> и его инвариантность относительно применения тождеств.
 +
* Невыводимость тождеств.
 +
* '''Т.''' {{notexists}} КПСТ.
  
 
== Надежность и контроль функционирования управляющих систем ==
 
== Надежность и контроль функционирования управляющих систем ==
  
# Построение надежных контактных схем из ненадежных контактов.
+
==== Построение надежных контактных схем из ненадежных контактов ====
# Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты.
+
 
 +
* Из методички по ОК: {{Скачать|Алексеев и др. - Задачи по курсу Основы кибернетики.djvu}}.
 +
* Логико-комбинаторный подход к понятию неисправности. Понятие самокоррекции.
 +
* Способы построения самокорректирующихся КС.
 +
* Представление об асимптотически наилучшем методе синтеза самокорректирующихся КС.
 +
 
 +
==== Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты ====
 +
 
 +
* Из лекций Ложкина: {{Скачать|Ложкин С.А. - Лекции по основам кибернетики 2004.djvu}}.
 +
* Модель источника неисправности и ненадежной схемы (N состояний, реализуемых при неисправностях).
 +
* '''Опр.''' отделимая по столбцам матрица; таблица контроля, цель контроля; диагностика схемы, проверка исправности схемы; тесты: минимальный, тупиковый, диагностический, проверяющий; функция теста.
 +
* '''Л.''' (о формуле для функции теста)
 +
* '''Л.''' (о длине диагностического теста)
  
 
== Математическая экономика ==
 
== Математическая экономика ==
Строка 258: Строка 503:
 
Почти вся берётся из лекций [[rupedia:Шананин,_Александр_Алексеевич|Шананина]]: {{Скачать|Шананин А.А. - Лекции по математическим моделям в экономике 1999.pdf}}.
 
Почти вся берётся из лекций [[rupedia:Шананин,_Александр_Алексеевич|Шананина]]: {{Скачать|Шананин А.А. - Лекции по математическим моделям в экономике 1999.pdf}}.
  
=== Модель межотраслевого баланса В. В. Леонтьева. Продуктивные матрицы. Критерии продуктивности. Теорема Фробениуса—Перрона. Свойства числа Фробениуса—Перрона. Теорема об устойчивости примитивных матриц ===
+
==== Модель межотраслевого баланса В. В. Леонтьева. Продуктивные матрицы. Критерии продуктивности. Теорема Фробениуса—Перрона. Свойства числа Фробениуса—Перрона. Теорема об устойчивости примитивных матриц ====
  
* x-Ax=w, w&ge;0, x&ge;0 — модель Леонтьева.
+
* x-Ax=w, w&ge;0, x&ge;0 — модель Леонтьева.
* '''Опр.''' продуктивная матрица (&#8707;x: x-Ax>0 или Dx>0), разложимая матрица.
+
* '''Опр.''' продуктивная матрица ({{exists}}x: x-Ax>0 или Dx>0), разложимая матрица.
* '''Т.''' (критерии продуктивности) (про любое w и миноры — условия Хокинса-Саймона)
+
* '''Т.''' (критерии продуктивности) (про любое w и миноры — условия Хокинса-Саймона)
* '''Т.''' (Ф-П — про ограничения модулем с.з.) A&ge;0 &rArr; есть с.з. и с.в.&ge;0, (pE-A)<sup>-1</sup>>0 &hArr; p > &lambda;(A), Ay &ge; &mu;y &hArr; &mu; &le; &lambda;(A), |с.з| &le; &lambda;(A).
+
* '''Т.''' (Ф-П — про ограничения модулем с.з.) A&ge;0 &rArr; есть с.з. и с.в.&ge;0, (pE-A)<sup>-1</sup>>0 &hArr; p > &lambda;(A), Ay &ge; &mu;y &hArr; &mu; &le; &lambda;(A), |с.з| &le; &lambda;(A).
 
* '''Т.''' (свойства) не меняется от <sup>T</sup>; сохраняет умножение, степень, &ge; для полож.опр.; =0 когда матрица степенью уходит в 0.
 
* '''Т.''' (свойства) не меняется от <sup>T</sup>; сохраняет умножение, степень, &ge; для полож.опр.; =0 когда матрица степенью уходит в 0.
 
* '''T.''' (об уст.матрицах)
 
* '''T.''' (об уст.матрицах)
  
=== Динамическая модель В. В. Леонтьева. Теорема о магистрали Моришимы. Экономическая интерпретация вектора Фробениуса — Перрона ===
+
==== Динамическая модель В. В. Леонтьева. Теорема о магистрали Моришимы. Экономическая интерпретация вектора Фробениуса — Перрона ====
  
 +
* '''Опр.''' динам.модель Леонтьева (cx &rarr; max, Ax(t+1) &le; x(t)); магистраль (отклоняется не больше чем на заданный угол).
 +
* '''Т.''' (Моришимы) вектор Ф-П матрицы A — магистраль для семейства решений д.м. Л.
  
 +
==== Линейные задачи оптимального распределения ресурсов. Экономическая интерпретация двойственности в задачах линейного программирования ====
  
=== Линейные задачи оптимального распределения ресурсов. Экономическая интерпретация двойственности в задачах линейного программирования ===
+
* Прямая задача — максимизируем прибыль при ограничениях на трудозатраты (не больше).
 +
* Обратная задача — минимизируем зарплату при ограничениях на внутренние цены (не меньше).
  
* Прямая задача — максимизируем прибыль при ограничениях на трудозатраты (не больше).
+
==== Модель Кокса—Росса—Рубинштейна. Оценка стоимости опциона ====
* Обратная задача — минимизируем зарплату при ограничениях на внутренние цены (не меньше).
+
 
+
=== Модель Кокса—Росса—Рубинштейна. Оценка стоимости опциона ===
+
  
 
* Типа, сколько надо просить за опцион, чтобы потом было на что реализовать право покупателя.
 
* Типа, сколько надо просить за опцион, чтобы потом было на что реализовать право покупателя.
* Упрощённая модель, есть две цены акции — «верхняя» и «нижняя».
+
* Упрощённая модель, есть две цены акции — «верхняя» и «нижняя».
 
* <m>\sum{2^n+1}{2^{n+1}}p(j)b(j) = \beta(1)b(1) + \gamma(1)s(1)</m>
 
* <m>\sum{2^n+1}{2^{n+1}}p(j)b(j) = \beta(1)b(1) + \gamma(1)s(1)</m>
  
=== Модель олигополистической конкуренции Курно. Теорема Нэша ===
+
==== Модель олигополистической конкуренции Курно. Теорема Нэша ====
  
 
* '''Опр.''' (бояны) игра N игроков, равновесие по Нэшу.
 
* '''Опр.''' (бояны) игра N игроков, равновесие по Нэшу.
 
* '''Т.''' (Нэша) (боян) игра с непрерывной вогнутой по каждому x функцией имеет равновесие по Нэшу.
 
* '''Т.''' (Нэша) (боян) игра с непрерывной вогнутой по каждому x функцией имеет равновесие по Нэшу.
* Модель Курно: чем больше берём, тем меньше платим.<br><m>u_i(x) = P(\sum_1^n x_j)x_i-c_i(x_i)</m> — целевая функция (c<sub>i</sub> — издержки).
+
* Модель Курно: чем больше берём, тем меньше платим.<br /><m>u_i(x) = P(\sum_1^n x_j)x_i-c_i(x_i)</m> целевая функция (c<sub>i</sub> издержки).
* '''Т.''' (существования решения) c(x) и P(x) &#x02208; C², издержки возрастают и выпуклы, P(x) неотрицательна и убывает в 0 (есть насыщение) &rArr; &#x02203! равновесие по Нэшу.
+
* '''Т.''' (существования решения) c(x) и P(x) {{in}} C², издержки возрастают и выпуклы, P(x) неотрицательна и убывает в 0 (есть насыщение) &rArr; {{exists}}! равновесие по Нэшу.
  
=== Модель Эрроу—Дебре. Конкурентное равновесие. Сведение вопроса о существовании конкурентного равновесия к решению задачи дополнительности. Замкнутость отображений спроса и предложения. Теорема Эрроу—Дебре ===
+
==== Модель Эрроу—Дебре. Конкурентное равновесие. Сведение вопроса о существовании конкурентного равновесия к решению задачи дополнительности. Замкнутость отображений спроса и предложения. Теорема Эрроу—Дебре ====
  
=== Неподвижные точки. Теоремы Брауэра и Какутани. Лемма Гейла — Никайдо — Дебре. Теорема Фань-Цзы ===
+
* '''Опр.''' совершенная конкуренция.
 +
* '''Т.''' (Э-Д) (существования конкурентного равновесия с кучей условий)
  
=== Оптимальность по Парето конкурентного равновесия (первая теорема теории благосостояния). Теорема Дебре (вторая теорема теории благосостояния). Сравнительная статика в моделях конкурентного равновесия ===
+
==== Неподвижные точки. Теоремы Брауэра и Какутани. Лемма Гейла — Никайдо — Дебре. Теорема Фань-Цзы ====
  
=== Проблемы коллективного выбора. Парадокс Эрроу ===
+
* Отсебятина: на неподвижных точках, между прочим, [[rupedia:Алгоритм фрактального сжатия|фрактальное сжатие]] работает. Правда, не на Брауэре, а на Банахе, но это не важно.
 +
* '''Т.''' (Брауэра) у непрерывного отображения выпуклого компакта в себя есть неподвижная точка (f(x)=x).
 +
* '''Опр.''' многозначное отображение, замкнутое м/о.
 +
* '''Т.''' (Какутани) у замкнутого непустого ({{notexists}} x: f(x) = {{emptyset}}) м/о, существует неподвижная точка (x {{in}} f(x)).
 +
* '''Л.''' (Г-Н-Д) замкнутое непустое выпуклое ({{forall}}x f(x) выпукло) м/о из пространства весовых векторов (сумма неотриц. компонент=1) в 2<sup>Rn</sup> и такое, что {{forall}}p, u{{in}}f(p) pu&ge;0 переводит хотя бы один x хотя бы в один неотрицательный вектор.
 +
 
 +
==== Оптимальность по Парето конкурентного равновесия (первая теорема теории благосостояния). Теорема Дебре (вторая теорема теории благосостояния). Сравнительная статика в моделях конкурентного равновесия ====
 +
 
 +
* Можно почитать [[rupedia:Первая теорема благосостояния]], [[rupedia:Вторая теорема благосостояния]].
 +
* '''Т.''' (1-ая) конкурентное равновесие оптимально по Парето.
 +
* '''Т.''' (2-ая) на рынке Парето-оптимальное состояние можно реализовать в качестве равновесия.
 +
* Сравнительная статика: по идее это сравнение «снимков» состояния без прямого учёта фактора времени, но где почитать именно про равновесие — неизвестно.
 +
 
 +
==== Проблемы коллективного выбора. Парадокс Эрроу ====
  
 
* Можно почитать [[rupedia:Теорема Эрроу]], [[rupedia:Парадокс Кондорсе]].
 
* Можно почитать [[rupedia:Теорема Эрроу]], [[rupedia:Парадокс Кондорсе]].
 
* Есть избиратели, сортирующие кандидатов. Есть система выборов, строящая заключительный список, отсортированный по «общему убыванию».
 
* Есть избиратели, сортирующие кандидатов. Есть система выборов, строящая заключительный список, отсортированный по «общему убыванию».
* Классная вещь — Эрроу доказал, что такие выборы чисто математически не могут быть «разумными»!
+
* Классная вещь — Эрроу доказал, что такие выборы чисто математически не могут быть «разумными»!
 
* Не может быть одновременно: универсальность + отсутствие диктатора + независимость от посторонних альтернатив + принцип единогласия.
 
* Не может быть одновременно: универсальность + отсутствие диктатора + независимость от посторонних альтернатив + принцип единогласия.
 
* Также не может быть: универсальность + полнота + монотонность + отсутствие диктатора + независимость от посторонних альтернатив.
 
* Также не может быть: универсальность + полнота + монотонность + отсутствие диктатора + независимость от посторонних альтернатив.
  
=== Индексы неравенства и кривая Лоренца. Теорема мажоризации ===
+
==== Индексы неравенства и кривая Лоренца. Теорема мажоризации ====
 
+
== Основная литература ==
+
  
# Яблонский С. В. Введение в дискретную математику. М.: Высш. школа, 2001.
+
* Можно почитать стр.11-21 книжки {{Скачать|Маршалл, Олкин - Неравенства - теория мажоризации и ее приложения.djvu}}.
# Кудрявцев В.В, Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.: Наука, 1985.
+
* По сути: один конечный ряд (y) мажорирует другой (x), если сумма та же, а кривая x лежит ниже y.
# Мальцев А. И. Алгоритмы и вычислимые функции. М.: Наука, 1986.
+
* Началось со сравнения Лоренцом распределения богатства — чем больше концентрация богатства, тем кривее.
# Оре О. Теория графов. М.: Наука, 1980.
+
* И попёрли развивать какую-то левую теорию, мажоризация, слабая мажоризация, мажоризация как частичное упорядочение<span style="color:#a0a0a0">'', такая мажоризация, сякая мажоризация, групповая мажоризация, любительская мажоризация, извращённая мажоризация''</span>…
# Кибернетический сборник. 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.
+
  
== Дополнительная литература ==
+
== Литература ==
  
# МакВильмс Ф. Дж., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. М.: Связь, 1979.
+
* {{Скачать|Лекции по методам оптимизации 2003.pdf}}
# Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.
+
* {{Скачать|Орлов - лекции по оптимальному управлению 2005.pdf}}
# Сэведж Дж. Э. Сложность вычислений. М.: Факториал, 1998.
+
* {{Скачать|Шананин А.А. - Лекции по математическим моделям в экономике 1999.pdf}}
# Марков А. А. Введение в теорию кодирования. М.: Наука, 1982.
+
* {{Скачать|Ложкин С.А. - Лекции по основам кибернетики 2004.djvu}}
# Орлов В. А. Простое доказательство алгоритмической неразрешимости некоторых задач о полноте автоматных базисов. //Кибернетика. 1973. № 4. С. 109—113.
+
* {{Скачать|Алексеев - лекции по дискретной математике 2002.pdf}}
# Редькин Н. П. Надежность и диагностика схем. М.: Изд-во МГУ, 1992.
+
* {{Скачать|Алексеев и др. - Задачи по курсу Основы кибернетики.djvu}}
# Соловьев Н. А. Тесты (теория, построение, применения). Новосибирск: Наука, 1978.
+
* {{Скачать|Сапоженко - Некоторые вопросы сложности алгоритмов.djvu}}
# Поляк Б. Т. Введение в оптимизацию. М.: Наука, 1984.
+
* {{Скачать|А.А.Васин, В.В.Морозов - Теория игр и модели математической экономики.djvu}}
 +
* {{Скачать|Васин, Морозов - Дополнительные главы теории операций - Глава 5 - Теория принятия решений.djvu}}
 +
* {{Скачать|Яблонский - Введение в дискретную математику.djvu}}
 +
* {{Скачать|Пападимитриу, Стайглиц - Комбинаторная оптимизация.djvu}}
 +
* {{Скачать|Оре - Теория графов.djvu}}
 +
* {{Скачать|Макмиллан, Слоэн - Теория кодов, исправляющих ошибки.djvu}}
 +
* {{Скачать|Алексеев - лекции по сложности комбинаторных алгоритмов.pdf}}
 +
* {{Скачать|Мальцев - Алгоритмы и рекурсивные функции.djvu}}
 +
* {{Скачать|Маршалл, Олкин - Неравенства - теория мажоризации и ее приложения.djvu}}
  
[[Категория:Учёба]]
+
[[Категория:Кандаминимум]]

Текущая версия на 10:12, 27 ноября 2012

Содержание

Математическое программирование

По большей части берётся из лекций по МетОптам: Лекции по методам оптимизации 2003.pdf (application/pdf, 745 КБ). Другие источники описаны отдельно.

Теоремы о достижении нижней грани функции (функционала) на множестве (в ЕN, в метрических пространствах, в гильбертовых пространствах)

Они же Теоремы Вейерштрасса.

  • Полунепрерывная снизу J(u) на компакте в метрическом пространстве достигает своей нижней грани, любая минимальная последовательность сходится к argmin по метрике.
  • Слабый вариант. Гильбертово пространство, компакт слабый, п/н слабо. Слабые п.т. мин. последовательности в Argmin.

Выпуклые множества, выпуклые функции, сильно выпуклые функции, их свойства

  • Опр. множество выпуклое; функция выпуклая, строго выпуклая, сильно выпуклая с k > 0.
  • Т. лок.мин. выпуклой f на выпуклом U = глобальный на U. Argmin выпукло. Argmin={argmin} для строго выпуклой.
  • Т. (сильно вып. Вейерштрасса) J(u) сильно выпукла и п.н. снизу на выпуклом и замкнутом U из Гильбертова H ⇒ достигает inf, Argmin={argmin}, .
  • Т. (критерий вып. для диф-мых функций).
  • Т. (критерий сильной вып. для диф-мых функций).

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

  • Т. , U выпукло ⇒ (1), . Если (1) и J(u) выпукла — значит u argmin (то есть ⇐).
  • Ещё там есть пара примеров.

Правило множителей Лагранжа

  • rupedia:Метод множителей Лагранжа относится к методам снятия ограничений.
  • Задача. J(u) → min при огр. gi ≤ 0.
  • А мы будем минимизировать L(u,λ) = λ0J(u) + сумма λigi, λi — множители Лагранжа.

Теорема Куна-Таккера, двойственная задача, ее свойства

  • Т. (Куна-Таккера) (обоснование метода Лагранжа) — всё существует, λi неотрицательно, λigi=0 (усл.доп.нежёсткости). Для достаточности ещё λi ≠ 0.
  • Опр. Двойственная задача:
  • Т. (свойства дв.задачи). . = только если L имеет седловую точку.

Метод проекции градиента (в ЕN, в гильбертовом пространстве)

  • Условный минимум — минимизируем J(u) на множестве U. В лоб — метод град. спуска проецируем на U = prU(uk-akJ'(uk)).
  • Т. (скорость сходимости)

Метод Ньютона

  • Идея — градиентный (или скорейший) спуск по квадратичной аппроксимации функции J(u) в окрестности uk.
  • Т. (скорость сходимости)

Метод покоординатного спуска

  • Сдвигаемся на ak в одну из сторон по одной координате по очереди, пока удаётся. Потом переходим к следующей. Потом дробим a.
  • Т. (обоснование сходимости)

Метод штрафных функций

  • Можно также почитать machinelearning:Метод штрафных функций.
  • Относится к методам снятия ограничений.
  • Задача. J(u) → min при огр. gi ≤ 0 либо = 0 начиная с gm+1-ой.
  • От задачи переходим к последовательности задач . P(u) — штраф, .
  • Т. (обоснование) индив. штрафы должны давать огран. множество ⇒ всё сходится.

Метод барьерных функций

Метод динамического программирования

  • Нет в МетОптах.
  • Можно почитать книжку Пападимитриу, Стайглиц - Комбинаторная оптимизация.djvu (image/vnd.djvu, 5,6 МБ), страницы 461—464.
  • Или просто Википедию.
  • Идея — поиск пути по минному полю с конца к началу, ибо любой конец оптимальной траектории оптимален (принцип оптимальности Беллмана).
  • Вообще-то ещё есть непрерывный аналог, идея та же, реализация на дифф.исчислении и ощутимо мохнатее.

Устойчивость задач оптимизации. Метод стабилизации (регуляризация по Тихонову)

  • Опр. корректно пост.задача: 1) существует, 2) единственно, 3) из сходимости значений следует сходимость аргументов.
  • Суть метода — в отсутствие (3) добавить к J(u) и минимизировать полученный функционал Тихонова.
  • Т. (обоснование метода).

Линейное программирование. Симплекс-метод. Двойственные задачи линейного программирования

  • Опр. ЗЛП, каноническая ЗЛП (u ≥ 0), угловая точка, невырожденная угловая точка, невырожденная задача.
  • Т. (критерий угловой точки) (про линейную комбинацию r столбцов матрицы A)
  • Симплекс-метод — идея перебора угловых точек в направлении минимизации функции.

Исследование операций, теория игр

Источники — две книжки по тиграм (теории игр) Васина и Морозова:

  1. А.А.Васин, В.В.Морозов - Теория игр и модели математической экономики.djvu (image/vnd.djvu, 1,16 МБ)
  2. Васин, Морозов - Дополнительные главы теории операций - Глава 5 - Теория принятия решений.djvu (image/vnd.djvu, 248 КБ) (только 5-я глава).

Антагонистические игры. Матричные игры, теорема о минимаксе

  • Опр. седловая точка F(x, y); антаг. игра <X,Y,F(x,y)>; игра имеет решение; значение игры; матричная игра; нижнее и верхнее значения игры (sup inf и inf sup); максиминная, минимаксная стратегии.
  • Л. значение игры не зависит от выбора решения.
  • Л. нижнее значение ≤ верхнего.
  • Т. (о минимаксе) 1) есть с.т. ⇔ max inf = min sup. 2) с.т. = стратегии максиминная и минимаксная.

Выпукло-вогнутые антагонистические игры. Теорема существования седловой точки

  • Опр. игра с вогнутой, выпуклой функцией выигрыша.
  • Т.
  • Т. (существование решения)

Бескоалиционные игры n лиц. Равновесие по Нэшу

  • Опр. игра n лиц.
  • Опр. (равновесие по Нэшу) от него никому невыгодно отклоняться в одиночку.
  • Т. (существования равновесия)

Принцип гарантированного результата. Минимаксные задачи

  • Из книжки 2.
  • Можно почитать http://www.intuit.ru/department/algorithms/opres/2/.
  • Опр. оптимальная стратегия (в предположении пессимизма) (так Гермейер стратегии сравнивал); ε-оптимальная стратегия, абсолютно оптимальная стратегия.
  • Т. F1 ≤ F2 ≤ F3 ≤ F4. Противник знает x → не знает → мы знаем y.

Многокритериальная оптимизация. Оптимальность по Парето. Лексикографический подход

  • Из книжки 2.
  • Многокритериальная оптимизация — как выбрать стратегию, если критериев качества несколько?
  • Опт. по Парето = «не улучшишь хотя бы один критерий».
  • Опт. по Слейтеру = «не улучшишь все критерии разом».
  • Лексикографический подход — упорядочиваем их по важности и ORDER BY.

Кооперативные игры (с-ядро, вектор Шепли)

  • Игроки делят выручку.
  • Опр. коалиции, хар.функция, супераддитивная, игра, игра с постоянной суммой, вектор дележа, эквив. игры (масштаб-сдвиг), 0-1 редуц. форма игры.
  • Индивидуальная разумность — выручку в коалиции не меньше, чем индивидуальная игрока.
  • Групповая разумность — выручка любой подкоалиации не меньше, чем её индивидуальная.
  • Ядро (c-ядро) — дележи, удовлетворяющие групповой разумности.
  • Вектор Шепли — состоит из компонент, равных мат.ожиданиям вкладов конкретных игроков.

Задача распределения ресурсов (модель Гросса, принцип уравнивания Гермейера)

  • Из книжки 2.
  • Задача 1: максимизируем минимум эффекта по всем пунктам.
  • Т. (пр. ур. Гермейера) оптимальное решение существует и единственно — идея: вначале распределяем ресурсы по наиболее слабым пунктам так, чтобы эффекта им досталось поровну.
  • Задача 2: максимизируем сумму эффекта по всем пунктам.
  • Т. (критерий Гросса) аналог уравнивания для производных.

Иерархические игры

  • Опр. иерархической игры (есть обмен информацией о стратегиях).
  • Г1: x → y(x) — Y знает стратегию X.
  • Г2: f(y) → y(f(y)) → x=f(y).
  • Г3: f1(g(x)) → g(x) → x=f(g(x)).
  • Т. (Гермейера). В Г2 гарантированный результат игрока X = максимум из 1) гарантированного результата X при наилучшем ответе Y на стратегию наказания, применяемую к нему X и 2) лучшего результата X в случае, если он позволит Y получить больше, чем в первом случае.

Потоки в сетях (теорема Форда-Фалкерсона, задача и алгоритмы поиска кратчайшего пути в графе, задача составления расписаний, транспортная задача)

Оптимальное управление

Частично берётся из лекций Орлов - лекции по оптимальному управлению 2005.pdf (application/pdf, 435 КБ). Но содержит несколько мистические вопросы — например, 3 последних, для которых связных материалов найти не удалось вообще. Дифференциальные игры можно, конечно, почитать по книге Айзекса 1967-го года, но там про это вся книга (480 страниц), но нам-то кратко надо.

Специалисты по оптимальному управлению — welcome! Дополните секцию! (и уберите пометки (404) = (не найдено) из заголовков)

Постановка задач оптимального управления, их классификация

  • Опр. задача ОУ (дифур, доп.множества, нач.усл., функционал), множество достижимости.
  • Задачи: быстродействия, с фикс. временем, с закреплёнными концами, с подвижными концами, с неавтономной системой.

Принцип максимума Понтрягина. Краевая задача принципа максимума

  • Опр. сопряжённая система, гамильтониан.
  • Л. скалярное произведение решений прямой и сопряжённой систем константно.
  • Т. (ПМП) , H(x, u,ψ) достигает максимума, а максимум постоянен на всём отрезке времени.
  • Т. (тоже ПМП, в другом виде) для оптимальной пары, если начальное и конечное множества выпуклы, существует ψ такое, что верно условие максимума: (u(t),ψ(t))=c(U,ψ(t)) и 2 трансверсальности: (x(t0),ψ(t0))=c(M0,ψ(t0)) и (x(t1),-ψ(t1))=c(M1,-ψ(t1)).

(404) Линейная задача быстродействия, ее свойства (существование решения, число переключений)

(404) Принцип максимума и вариационное исчисление

  • Видимо, про те самые вариации Макшейна?

(404) Управляемость и наблюдаемость в линейных системах, их взаимосвязь (взаимодвойственность). Теоремы Калмана, Красовского

  • Опр. Система полностью управляема, если она может быть переведена из любого начального состояния в начало координат под действием управления u(t) за конечное время.
  • Т. (Калмана) Состояние непрерывной системы (x' = Ax + bu) управляемо, если и только если
    rang Ny=[b | Ab | A²b | … | An-1b] = n.

(404) Метод динамической регуляризации в задаче наблюдения

(404) Дифференциальные игры

Дискретная оптимизация

Берётся из Пападимитриу, Стайглиц - Комбинаторная оптимизация.djvu (image/vnd.djvu, 5,6 МБ), а также из Алексеев - лекции по сложности комбинаторных алгоритмов.pdf (application/pdf, 535 КБ).

Целочисленное линейное программирование (метод Гомори, свойства унимодулярности матрицы ограничений)

  • Опр. задача ЦЛП (ЛП + x ∈ Z), унимодулярность матрицы (|det|=1).
  • К ней можно многое свести (коммивояжера, расписание, выполнимость КНФ), а вот решать округлением лучше не надо :) также к ней сводятся «нелинейности» — барьер, дихотомия, дискретные переменные.
  • Т. A унимод. ⇒ для целых b угловые точки целочисленны.
  • Метод отсечений Гомори — добавляем ограничения, не отсекающие целочисленных точек — целая часть i-ой строки с = заменённым на ≥.

Метод ветвей и границ (на примере задач целочисленного или булева линейного программирования)

  • Идея — разбиваем задачу на две взаимодополняющих задачи (либо нецелая xi ≤ целой части, либо ≥ целой части + 1).
  • Вторая идея — при ветвлениях можно не идти во всю глубину, так как меньше чем найденное не-целочисленное решение уже не будет. Если есть другое решение, дающее лучший результат — стоп.
  • Ещё пример — алгоритм Дейкстры. ЦЛП здесь не важно.

Временная сложность решения задач дискретной оптимизации. Основные классы сложности (P, NP, NPC)

  • Опр. f полиномиально сводится к g, P, NP, NP-полные (NPC).

NP-трудные задачи (задача о рюкзаке, задача коммивояжера)

  • Можно также почитать rupedia:Задача о ранце, rupedia:Задача коммивояжёра.
  • ЗР: из неограниченного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.
  • ЗК: отыскание самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.

Теория функциональных систем

Берётся снова из Яблонский - Введение в дискретную математику.djvu (image/vnd.djvu, 7,02 МБ).

Проблема полноты. Теорема о полноте систем функций двузначной логики P2

  • Формула над системой {fk}: 1) fi- формула 2) fi(A1,…,An) — формула, где A — переменная либо формула.
  • Полнота системы {fk}: все функции из P2 можно выразить формулами над {fk}.
  • Замкнутый класс — все формулы над функциями из класса принадлежат тому же классу.
  • Замкнутые классы: T0 (f(0,0…0)=0), T1 (f(1,1…1)=1), S (f(!x1,!x2,…!xn) = !f(!x1,!x2,…!xn)), M (1й набор по всем переменным ≥ 2го, тогда f(1го)≥f(2го)), L (формула над +, &, 1, 0, оно же полином Жегалкина)
  • Теорема о полноте: если система не входит полностью ни в одно из T0, T1, S, M, L — то она полна. Доказывается через получение констант 0 и 1 из не входящих в T0, T1 и S, из них и функции, не принадлежащей L- отрицания, и из них, отрицания и функции, не принадлежащей M — дизъюнкции.

Алгоритм распознавания полноты систем функций k-значной логики Pk

  • Т. существует алгоритм анализа системы на полноту. («в лоб»)
    Док-во: строим мн-ва функций от 2х переменных, подставляя в функции из нашей системы либо функции от 2х переменных с предыдущего шага, либо просто переменную x1 или x2. Так как функций 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 в Pk ∃ замкнутый класс, не имеющий базиса.
  • Т. (Мучника) для всякого k≥3 в Pk ∃ замкнутый класс, имеющий счётный базис.
  • Т. для всякого k≥3 в Pk ∃ континуум различных замкнутых классов.
  • Т. система полиномов в Pk полна ⇔ k — простое число.

Автоматы. Регулярные события и их представление в автоматах

Эксперименты с автоматами

  • Берётся из Алексеев - лекции по дискретной математике 2002.pdf (application/pdf, 752 КБ).
  • Опр. автомат с выходом, отличимые состояния, эксперимент.
  • Л. (о существовании отличимых экспериментом данной длины состояний)
  • Т. (Мура) (о максимальной длине эксперимента, +пример)
  • Т. (про отличимые состояния разных автоматов)
  • Т. (о макс. длине эксп. отличающего состояния двух автоматов, +пример)

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

Вычислимые функции. Эквивалентность класса рекурсивных функций и класса функций, вычислимых на машинах Тьюринга

Алгоритмическая неразрешимость проблемы эквивалентности слов в ассоциативных исчислениях

  • Берётся из Мальцев - Алгоритмы и рекурсивные функции.djvu (image/vnd.djvu, 4,38 МБ), стр. 254.
  • Опр. полугруппа, система порождающих, определяющие соотношения, умножение классов.
  • Опр. ассоциативного исчисления (набор замен); эквивалентные слова.
  • Т. (Пост, Марков) ∃ ассоциативное исчисление с алгоритмически неразрешимой проблемой эквивалентности слов.

Комбинаторный анализ и теория графов

Берётся из книжек:

  1. Яблонский - Введение в дискретную математику.djvu (image/vnd.djvu, 7,02 МБ)
  2. Оре - Теория графов.djvu (image/vnd.djvu, 4,3 МБ)

Основные комбинаторные числа

Число подмножеств множества = 2|M|.

Число размещений элементов из n по k = (n)k (убывающий факториал).

Число перестановок n элементов = n!.

e =

Число сочетаний из n по k, или же биномиальный коэффициент .

Число сочетаний с повторениями из n по k

Число разбиений n-элементного множества на множества мощностей равняется .

Число разбиений n-элементного множества на k множеств (число Стирлинга) и число всех разбиений (число Белла)

Оценки и асимптотики для комбинаторных чисел

  • Т. (логарифм факториала) ln n! ~ (n+0.5) ln n
  • Т. (формула Стирлинга) n! ~
  • Т. (корень квадратный из пи)
  • Т. (число сочетаний)
  • Т. (сумма числа сочетаний)
  • Т. (числа Белла)

Графы и сети. Оценки числа графов и сетей различных типов

  • Опр. граф, цикл, петля, связный граф, сеть, степень сети, степенная структура сети
  • Т. число графов c h рёбрами без изол.вершин меньше a(bh)h, a, b = Const.
  • Т. число укладок деревьев с h рёбрами меньше 4h.
  • Т. (Лупанова) число сетей с заданной степ.структурой ≤ chh(μ-1)h, c зависит только от числа полюсов, средней степени и числа наборов.

Плоские и планарные графы. Формула Эйлера для плоских графов. Необходимые условия планарности в теореме Понтрягина—Куратовского (без доказательства достаточности)

  • Можно почитать rupedia:Планарный граф.
  • Т. (П-К) — это про то, что граф планарен, если не содержит гомеоморфных K5 и K3,3 подграфов.
  • Т. (ф-ла Эйлера) Вершин − Ребёр + Граней = 2 у всякого связного плоского графа.

Экстремальная теория графов. Теорема Турана

  • Можно также почитать rupedia:Теорема Турана.
  • Т. (Турана) (макс. количество ребёр в графе, не содержащем полного n-вершинного подграфа)

Теорема Рамсея

  • Можно также почитать rupedia:Теорема Рамсея.
  • Т. (Рамсея) («полная неупорядоченность невозможна») для любого набора классов сочетаний r элементов в любом достаточно большом множестве всегда найдётся подмножество, все сочетания r элементов которого будут принадлежать одному классу.
  • Условно говоря, если на вечеринке 6 человек, то либо какие-то 3 из них все друг с другом знакомы, либо какие-то 3 из них друг с другом незнакомы.
  • Правда «достаточно большое множество» — очень большое.

Теория кодирования

Первые 3 вопроса берутся из Яблонский - Введение в дискретную математику.djvu (image/vnd.djvu, 7,02 МБ), можно также (но хуже) из лекций Алексеева: Алексеев - лекции по дискретной математике 2002.pdf (application/pdf, 752 КБ).

Другие 2 можно прочитать в Макмиллан, Слоэн - Теория кодов, исправляющих ошибки.djvu (image/vnd.djvu, 8,46 МБ).

Алфавитное кодирование. Критерии однозначности декодирования. Неравенство Крафта—Макмиллана

  • Опр. кодирование: алфавитное, взаимно однозначное, равномерное, префиксное, постфиксное; неприводимое слово.
  • Т. (Маркова) если кодирование неоднозначно, существуют два слова не длиннее целой части 0.5(W+1)(L-r+2), имеющие одинаковый код.
  • Т. (Макмиллана) если кодирование однозначно, то .

Оптимальное кодирование. Построение кодов с минимальной избыточностью

  • Опр. цена кода, оптимальный код, код Хаффмана.
  • У. если существует оптимальный код, существует оптимальный префиксный код с теми же длинами слов.
  • Алгоритм построения кода с мин.избыточностью — редукция списка вероятностей.
  • Отсебятина: а ещё есть арифметик

Самокорректирующиеся коды. Граница упаковки. Коды Хемминга, исправляющие единичную ошибку

  • Опр. самокорректирующиеся коды.
  • rupedia:Код Хемминга — исправляющий одну ошибку равномерный код, в котором i-ый контрольный разряд — сумма информационных разрядов с номерами, включающими 1 в i-ой позиции двоичной записи.
  • Т. расстояние между любыми двумя кодовыми словами кода Хэмминга ≥ 3.
  • Т. расстояние между кодовыми словами кода, исправляющего k ошибок ≥ 2k+1.

Конечные поля и их основные свойства

  • Можно почитать rupedia:Кольцо (математика), rupedia:Конечное поле.
  • Поле — коммутативное кольцо с единицей, в котором для всякого ненулевого элемента есть обратный.
  • Поле Галуа GF(n) — конечное поле.
  • Для каждого простого числа p и натурального n существует конечное поле из q = pn элементов, единственное с точностью до изоморфизма. Это поле изоморфно полю разложения многочлена xq-x.

Коды Боуза—Чоудхури—Хоквингема

  • Можно почитать rupedia:Код Боуза — Чоудхури — Хоквингема, rupedia:Циклический код (а в CD-ROM’ах используется rupedia:Код Рида — Соломона).
  • Коды БЧХ — «обобщение» Хэмминга на случай двух ошибок. Требование решения системы уравнений относительно i и j (позиций ошибок) как раз и приводит к полям…
  • Опр. циклический код, порождающий полином, проверочная матрица.
  • Т. коды БЧХ — циклические коды, задаваемые порождающим полиномом.
  • Т. о границе БЧХ.

Управляющие системы

Вопрос тут один, ёмкий, аки нецензурное послание.

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

Берётся он из Ложкин С.А. - Лекции по основам кибернетики 2004.djvu (image/vnd.djvu, 1,18 МБ).

  • Управляющая система — типа задаёт поведение некоторой системы.
  • Опр. элементарные конъюнкции, ДНФ, КНФ; формула; эквивалентные формулы; КС; эквивалентные КС (⇔ эквив. все формулы); СФЭ; автомат; МТ (ДМТ, НМТ?).
  • Операторные алгоритмы — последовательность приказов, приказ = операция + два номера других приказа (ветвление определён / не определён), либо «СТОП».
  • Основные задачи:
    1. Синтез минимальных по сложности систем.
    2. Эквивалентные преобразования.
    3. Контроль и надёжность.

Дизъюнктивные нормальные формы

Берётся из лекций Ложкина по ОК: Ложкин С.А. - Лекции по основам кибернетики 2004.djvu (image/vnd.djvu, 1,18 МБ).

Проблема минимизации булевых функций. Дизъюнктивные нормальные формы (ДНФ). Постановка задачи в геометрической форме

Локальные алгоритмы построения ДНФ. Построение ДНФ ∑Т (сумма тупиковых) с помощью локального алгоритма

  • Опр. тупиковая ДНФ, ДНФ ΣT и ∩T, ядровая точка, ядровая грань, ядро; пучок, регулярные и нерегулярные точки, регулярные грани; окрестность порядка r, ДНФ Квайна; локальный алгоритм.
  • Л. (о составе ДНФ ∩T)
  • Т. (Журавлева) (о составе ДНФ ΣT), идея о покрытии регулярных точек гранями из меньшего пучка.

Невозможность построения ДНФ ∑М (сумма минимальных) в классе локальных алгоритмов

  • Опр. ДНФ ΣM, цепная функция.
  • Т. (Журавлева) (неприменимость локального алгоритма для построения ДНФ ΣM цепной функции).

Синтез и сложность управляющих систем

Берётся всё из тех же лекций Ложкина: Ложкин С.А. - Лекции по основам кибернетики 2004.djvu (image/vnd.djvu, 1,18 МБ).

Асимптотически оптимальный метод синтеза схем из функциональных элементов

  • Опр. дискретно-универсальное множество функций.
  • Т. (Лупанова) о верхней оценке функции Шеннона в классе СФЭ.
  • Сл. (асимптотика функции Шеннона).

Асимптотически оптимальный метод синтеза контактных схем

  • Опр. m-регулярное множество.
  • Т. (Лупанова) то же, но в классе КС.
  • Идея метода Лупанова: разложение функции по подфункциям и полосам, построение суперпозиции КС на основе m-регулярного множества.

Инвариантные классы и их свойства

  • Берётся из Сапоженко - Некоторые вопросы сложности алгоритмов.djvu (image/vnd.djvu, 222 КБ).
  • Опр. инв.класс, характеристика ИК, сложная функция, правильный алгоритм.
  • Пример ИК с характеристикой 0.5.
  • Т. (Яблонского) о существовании ИК с заданной характеристикой.
  • Т. (Яблонского) о работе правильного алгоритма, строящего сложную последовательность функций.

Синтез схем для функций из некоторых инвариантных классов

  • Из Сапоженко и Ложкина.
  • Т. (Лупанова) о верхней оценке функции Шеннона для ИК с заданной характеристикой.
  • Т. о нижней мощностной оценке функции Шеннона для ИК с характеристикой, большей 1.

Нижние оценки сложности реализации булевых функций параллельно-последовательными контактными схемами

  • Соотношение между π-схемами и формулами с поднятыми отрицаниями.
  • Опр. каркас.
  • Оценка числа формул данной сложности на основе количества каркасов и способов подстановки переменных.
  • Л. о верхней оценке количества π-схем данной сложности через число формул.
  • Л. об обращении степенного неравенства.
  • Принцип получения нижних оценок функции Шеннона.
  • Т. о нижней оценке функции Шеннона.

Нижние оценки сложности реализации булевых функций формулами в произвольном базисе

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

Эквивалентные преобразования управляющих систем

Опять-таки берётся из лекций Ложкина Ложкин С.А. - Лекции по основам кибернетики 2004.djvu (image/vnd.djvu, 1,18 МБ), кроме примера Линдона, который можно взять из методички Алексеева Алексеев и др. - Задачи по курсу Основы кибернетики.djvu (image/vnd.djvu, 4,22 МБ).

Эквивалентные преобразования формул двузначной логики Р2

  • Опр. тождество, выводимость, эквивалентное преобразование.
  • Тождества: ассоциативности, коммутативности, отождествления переменных, де Моргана, дистрибутивности, поглощения, подстановки констант.
  • Т. Основная и расширенная системы тождеств эквивалентны.
  • Т. основной система тождеств полна (поднятие отрицаний → раскрытие скобок → приведение подобных, переход к совершенной ДНФ).

Эквивалентные преобразования контактных схем

  • Опр. тождества основные, вспомогательные, обобщенные, каноническая КС, каноническая цепь, цикломатическое число графа (компонент связности + рёбер — вершин), контактной схемы.
  • Т. основная система тождеств полна (принцип индукции → расширение контактов → применение тождества «звезда» → добавление фиктивных цепей → удаление вершины → удаление висячих и параллельных цепей → удаление транзитной проводимости).
  • Л. (об изменении цикломатического числа при эквивалентных преобразованиях).
  • Т. (о неполноте любой конечной системы тождеств).

(404) Эквивалентные преобразования операторных алгоритмов

Специалисты, welcome — дополните секцию и уберите пометку (404) из заголовка!

Пример Линдона

  • Опр. функция Линдона (которая с 1 5 6).
  • Основные тождества и их вывод, преобразование к каноническому виду и его единственность.
  • Т. Полнота системы тождеств.
  • Свойство Cn и его инвариантность относительно применения тождеств.
  • Невыводимость тождеств.
  • Т. ∄ КПСТ.

Надежность и контроль функционирования управляющих систем

Построение надежных контактных схем из ненадежных контактов

Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты

  • Из лекций Ложкина: Ложкин С.А. - Лекции по основам кибернетики 2004.djvu (image/vnd.djvu, 1,18 МБ).
  • Модель источника неисправности и ненадежной схемы (N состояний, реализуемых при неисправностях).
  • Опр. отделимая по столбцам матрица; таблица контроля, цель контроля; диагностика схемы, проверка исправности схемы; тесты: минимальный, тупиковый, диагностический, проверяющий; функция теста.
  • Л. (о формуле для функции теста)
  • Л. (о длине диагностического теста)

Математическая экономика

Почти вся берётся из лекций Шананина: Шананин А.А. - Лекции по математическим моделям в экономике 1999.pdf (application/pdf, 446 КБ).

Модель межотраслевого баланса В. В. Леонтьева. Продуктивные матрицы. Критерии продуктивности. Теорема Фробениуса—Перрона. Свойства числа Фробениуса—Перрона. Теорема об устойчивости примитивных матриц

  • x-Ax=w, w≥0, x≥0 — модель Леонтьева.
  • Опр. продуктивная матрица (∃x: x-Ax>0 или Dx>0), разложимая матрица.
  • Т. (критерии продуктивности) (про любое w и миноры — условия Хокинса-Саймона)
  • Т. (Ф-П — про ограничения модулем с.з.) A≥0 ⇒ есть с.з. и с.в.≥0, (pE-A)-1>0 ⇔ p > λ(A), Ay ≥ μy ⇔ μ ≤ λ(A), |с.з| ≤ λ(A).
  • Т. (свойства) не меняется от T; сохраняет умножение, степень, ≥ для полож.опр.; =0 когда матрица степенью уходит в 0.
  • T. (об уст.матрицах)

Динамическая модель В. В. Леонтьева. Теорема о магистрали Моришимы. Экономическая интерпретация вектора Фробениуса — Перрона

  • Опр. динам.модель Леонтьева (cx → max, Ax(t+1) ≤ x(t)); магистраль (отклоняется не больше чем на заданный угол).
  • Т. (Моришимы) вектор Ф-П матрицы A — магистраль для семейства решений д.м. Л.

Линейные задачи оптимального распределения ресурсов. Экономическая интерпретация двойственности в задачах линейного программирования

  • Прямая задача — максимизируем прибыль при ограничениях на трудозатраты (не больше).
  • Обратная задача — минимизируем зарплату при ограничениях на внутренние цены (не меньше).

Модель Кокса—Росса—Рубинштейна. Оценка стоимости опциона

  • Типа, сколько надо просить за опцион, чтобы потом было на что реализовать право покупателя.
  • Упрощённая модель, есть две цены акции — «верхняя» и «нижняя».

Модель олигополистической конкуренции Курно. Теорема Нэша

  • Опр. (бояны) игра N игроков, равновесие по Нэшу.
  • Т. (Нэша) (боян) игра с непрерывной вогнутой по каждому x функцией имеет равновесие по Нэшу.
  • Модель Курно: чем больше берём, тем меньше платим.
    — целевая функция (ci — издержки).
  • Т. (существования решения) c(x) и P(x) ∈ C², издержки возрастают и выпуклы, P(x) неотрицательна и убывает в 0 (есть насыщение) ⇒ ∃! равновесие по Нэшу.

Модель Эрроу—Дебре. Конкурентное равновесие. Сведение вопроса о существовании конкурентного равновесия к решению задачи дополнительности. Замкнутость отображений спроса и предложения. Теорема Эрроу—Дебре

  • Опр. совершенная конкуренция.
  • Т. (Э-Д) (существования конкурентного равновесия с кучей условий)

Неподвижные точки. Теоремы Брауэра и Какутани. Лемма Гейла — Никайдо — Дебре. Теорема Фань-Цзы

  • Отсебятина: на неподвижных точках, между прочим, фрактальное сжатие работает. Правда, не на Брауэре, а на Банахе, но это не важно.
  • Т. (Брауэра) у непрерывного отображения выпуклого компакта в себя есть неподвижная точка (f(x)=x).
  • Опр. многозначное отображение, замкнутое м/о.
  • Т. (Какутани) у замкнутого непустого (∄ x: f(x) = ∅) м/о, существует неподвижная точка (x ∈ f(x)).
  • Л. (Г-Н-Д) замкнутое непустое выпуклое (x f(x) выпукло) м/о из пространства весовых векторов (сумма неотриц. компонент=1) в 2Rn и такое, что p, u∈f(p) pu≥0 переводит хотя бы один x хотя бы в один неотрицательный вектор.

Оптимальность по Парето конкурентного равновесия (первая теорема теории благосостояния). Теорема Дебре (вторая теорема теории благосостояния). Сравнительная статика в моделях конкурентного равновесия

  • Можно почитать rupedia:Первая теорема благосостояния, rupedia:Вторая теорема благосостояния.
  • Т. (1-ая) конкурентное равновесие оптимально по Парето.
  • Т. (2-ая) на рынке Парето-оптимальное состояние можно реализовать в качестве равновесия.
  • Сравнительная статика: по идее это сравнение «снимков» состояния без прямого учёта фактора времени, но где почитать именно про равновесие — неизвестно.

Проблемы коллективного выбора. Парадокс Эрроу

  • Можно почитать rupedia:Теорема Эрроу, rupedia:Парадокс Кондорсе.
  • Есть избиратели, сортирующие кандидатов. Есть система выборов, строящая заключительный список, отсортированный по «общему убыванию».
  • Классная вещь — Эрроу доказал, что такие выборы чисто математически не могут быть «разумными»!
  • Не может быть одновременно: универсальность + отсутствие диктатора + независимость от посторонних альтернатив + принцип единогласия.
  • Также не может быть: универсальность + полнота + монотонность + отсутствие диктатора + независимость от посторонних альтернатив.

Индексы неравенства и кривая Лоренца. Теорема мажоризации

  • Можно почитать стр.11-21 книжки Маршалл, Олкин - Неравенства - теория мажоризации и ее приложения.djvu (image/vnd.djvu, 7,33 МБ).
  • По сути: один конечный ряд (y) мажорирует другой (x), если сумма та же, а кривая x лежит ниже y.
  • Началось со сравнения Лоренцом распределения богатства — чем больше концентрация богатства, тем кривее.
  • И попёрли развивать какую-то левую теорию, мажоризация, слабая мажоризация, мажоризация как частичное упорядочение, такая мажоризация, сякая мажоризация, групповая мажоризация, любительская мажоризация, извращённая мажоризация

Литература