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

Версия 00:55, 26 ноября 2009

Содержание

1 Математическое программирование
2 Исследование операций, теория игр
3 Оптимальное управление
4 Дискретная оптимизация
5 Теория функциональных систем
6 Комбинаторный анализ и теория графов
7 Теория кодирования
8 Управляющие системы
- 8.1 Понятие управляющей системы. Основные модельные классы управляющих систем: дизъюнктивные нормальные формы, формулы, контактные схемы, схемы из функциональных элементов, автоматы, машины Тьюринга, операторные алгоритмы. Основные проблемы теории управляющих систем
9 Дизъюнктивные нормальные формы
10 Синтез и сложность управляющих систем
11 Эквивалентные преобразования управляющих систем
12 Надежность и контроль функционирования управляющих систем
- 12.1 Построение надежных контактных схем из ненадежных контактов
- 12.2 Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты
13 Математическая экономика
14 Литература

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

По большей части берётся из лекций по МетОптам: Лекции по методам оптимизации 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 при огр. g_i ≤ 0.
А мы будем минимизировать L(u,λ) = λ₀J(u) + сумма λ_ig_i, λ_i — множители Лагранжа.

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

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

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

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

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

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

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

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

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

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

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

Можно почитать mlwiki:Метод штрафных функций#Метод барьерных функций.
По сути то же, что и метод штрафных функций, только штраф другого вида.

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

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

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

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

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

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

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

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

А.А.Васин, В.В.Морозов - Теория игр и модели математической экономики.djvu (image/vnd.djvu, 1,16 МБ)
Васин, Морозов - Дополнительные главы теории операций - Глава 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: максимизируем сумму эффекта по всем пунктам.
Т. (критерий Гросса) аналог уравнивания для производных.

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

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

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

В книжках нет.
Можно почитать rupedia:Теорема Форда — Фалкерсона, rupedia:Транспортная задача, rupedia:Алгоритм Дейкстры.
Опр. транспортная сеть, поток, сечение графа, величина сечения.
Т. (Ф-Ф, очевидная — «пропускная способность определяется слабым звеном») максимальный поток между истоком и стоком равен величине минимального сечения.
Решение транспортной задачи аналогично Ф-Ф.
Поиск кратчайшего пути — динамическое программирование, алгоритм Дейкстры (жадный).

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

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

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

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

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

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

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

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

∄ :( Дифференциальные игры

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

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

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

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

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

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

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

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

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

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

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

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

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

Формула над системой {f_k}: 1) f_i- формула 2) f_i(A₁,…,A_n) — формула, где A — переменная либо формула.
Полнота системы {f_k}: все функции из P₂ можно выразить формулами над {f_k}.
Замкнутый класс — все формулы над функциями из класса принадлежат тому же классу.
Замкнутые классы: T₀ (f(0,0…0)=0), T₁ (f(1,1…1)=1), S (f(!x₁,!x₂,…!x_n) = !f(!x₁,!x₂,…!x_n)), M (1й набор по всем переменным ≥ 2го, тогда f(1го)≥f(2го)), L (формула над +, &, 1, 0, оно же полином Жегалкина)
Теорема о полноте: если система не входит полностью ни в одно из T₀, T₁, S, M, L — то она полна. Доказывается через получение констант 0 и 1 из не входящих в T₀, T₁ и S, из них и функции, не принадлежащей L- отрицания, и из них, отрицания и функции, не принадлежащей M — дизъюнкции.

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

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

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

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

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

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

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

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

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

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

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

Яблонский - Введение в дискретную математику.djvu (image/vnd.djvu, 7,02 МБ)
Оре - Теория графов.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 рёбрами меньше 4^h.
Т. (Лупанова) число сетей с заданной степ.структурой ≤ c^hh^(μ-1)h, c зависит только от числа полюсов, средней степени и числа наборов.

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

Можно почитать rupedia:Планарный граф.
Т. (П-К) — это про то, что граф планарен, если не содержит гомеоморфных K₅ и K_3,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 = pⁿ элементов, единственное с точностью до изоморфизма. Это поле изоморфно полю разложения многочлена x^q-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 МБ).

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

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

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

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

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

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

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

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

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

Из методички по ОК: Алексеев и др. - Задачи по курсу Основы кибернетики.djvu (image/vnd.djvu, 4,22 МБ).
Логико-комбинаторный подход к понятию неисправности. Понятие самокоррекции.
Способы построения самокорректирующихся КС.
Представление об асимптотически наилучшем методе синтеза самокорректирующихся КС.

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

Из лекций Ложкина: Ложкин С.А. - Лекции по основам кибернетики 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 функцией имеет равновесие по Нэшу.
Модель Курно: чем больше берём, тем меньше платим.
— целевая функция (c_i — издержки).
Т. (существования решения) c(x) и P(x) ∈ C², издержки возрастают и выпуклы, P(x) неотрицательна и убывает в 0 (есть насыщение) ⇒ ∃! равновесие по Нэшу.

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

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

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

Отсебятина: на неподвижных точках, между прочим, фрактальное сжатие работает. Правда, не на Брауэре, а на Банахе, но это не важно.
Т. (Брауэра) у непрерывного отображения выпуклого компакта в себя есть неподвижная точка (f(x)=x).
Опр. многозначное отображение, замкнутое м/о.
Т. (Какутани) у замкнутого непустого (∄ x: f(x) = ∅) м/о, существует неподвижная точка (x ∈ f(x)).
Л. (Г-Н-Д) замкнутое непустое выпуклое (∀x f(x) выпукло) м/о из пространства весовых векторов (сумма неотриц. компонент=1) в 2^Rn и такое, что ∀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.
Началось со сравнения Лоренцом распределения богатства — чем больше концентрация богатства, тем кривее.
И попёрли развивать какую-то левую теорию, мажоризация, слабая мажоризация, мажоризация как частичное упорядочение, такая мажоризация, сякая мажоризация, групповая мажоризация, любительская мажоризация, извращённая мажоризация…

Литература

@@ Строка 408: / Строка 408: @@
 ==== Инвариантные классы и их свойства ====
-* Берётся из {{Скачать|Сапоженко - Некоторые вопросы сложности алгоритмов.pdf}}.
+* Берётся из {{Скачать|Сапоженко - Некоторые вопросы сложности алгоритмов.djvu}}.
 * '''Опр.''' инв.класс, характеристика ИК, сложная функция, правильный алгоритм.
 * Пример ИК с характеристикой 0.5.