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

Версия 21:47, 25 ноября 2009

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

По большей части берётся из лекций по МетОптам: Лекции по методам оптимизации 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)
• Симплекс-метод — идея перебора угловых точек в направлении минимизации функции.

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

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

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: максимизируем сумму эффекта по всем пунктам.
• Т. (критерий Гросса) аналог уравнивания для производных.

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

• Опр. иерархической игры (есть обмен информацией о стратегиях).
• Г₁: 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.
• Опр. полугруппа, система порождающих, определяющие соотношения, умножение классов.
• Опр. ассоциативного исчисления (набор замен); эквивалентные слова.
• Т. (Пост, Марков) ∃ ассоциативное исчисление с алгоритмически неразрешимой проблемой эквивалентности слов.

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

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

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 рёбрами меньше 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. Контроль и надёжность.

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

Берётся из лекций Ложкина по ОК:.

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

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

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

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

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

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

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

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

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

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

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

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

• Берётся из Сапоженко - Некоторые вопросы сложности алгоритмов.pdf («Файл:Сапоженко - Некоторые вопросы сложности алгоритмов.pdf» не существует, «Файл:Сапоженко - Некоторые вопросы сложности алгоритмов.pdf» не существует).
• Опр. инв.класс, характеристика ИК, сложная функция, правильный алгоритм.
• Пример ИК с характеристикой 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.
• Началось со сравнения Лоренцом распределения богатства — чем больше концентрация богатства, тем кривее.
• И попёрли развивать какую-то левую теорию, мажоризация, слабая мажоризация, мажоризация как частичное упорядочение, такая мажоризация, сякая мажоризация, групповая мажоризация, любительская мажоризация, извращённая мажоризация…

Литература

• Лекции по методам оптимизации 2003.pdf (application/pdf, 745 КБ)
• А.А.Васин, В.В.Морозов - Теория игр и модели математической экономики.djvu (image/vnd.djvu, 1,16 МБ)
• Васин, Морозов - Дополнительные главы теории операций - Глава 5 - Теория принятия решений.djvu (image/vnd.djvu, 248 КБ)
• Орлов - лекции по оптимальному управлению 2005.pdf (application/pdf, 435 КБ)
• Яблонский - Введение в дискретную математику.djvu (image/vnd.djvu, 7,02 МБ)
• Шананин А.А. - Лекции по математическим моделям в экономике 1999.pdf (application/pdf, 446 КБ)
• Ложкин С.А. - Лекции по основам кибернетики 2004.djvu (image/vnd.djvu, 1,18 МБ)
• Алексеев - лекции по дискретной математике 2002.pdf (application/pdf, 752 КБ)
• Алексеев и др. - Задачи по курсу Основы кибернетики.djvu (image/vnd.djvu, 4,22 МБ)
• Пападимитриу, Стайглиц - Комбинаторная оптимизация.djvu (image/vnd.djvu, 5,6 МБ)
• Оре - Теория графов.djvu (image/vnd.djvu, 4,3 МБ)
• Макмиллан, Слоэн - Теория кодов, исправляющих ошибки.djvu (image/vnd.djvu, 8,46 МБ)
• Алексеев - лекции по сложности комбинаторных алгоритмов.pdf (application/pdf, 535 КБ)
• Мальцев - Алгоритмы и рекурсивные функции.djvu (image/vnd.djvu, 4,38 МБ)
• Маршалл, Олкин - Неравенства - теория мажоризации и ее приложения.djvu (image/vnd.djvu, 7,33 МБ)

Дополнительная литература

1. МакВильмс Ф. Дж., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. М.: Связь, 1979.
2. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.
3. Сэведж Дж. Э. Сложность вычислений. М.: Факториал, 1998.
4. Марков А. А. Введение в теорию кодирования. М.: Наука, 1982.
5. Орлов В. А. Простое доказательство алгоритмической неразрешимости некоторых задач о полноте автоматных базисов. //Кибернетика. 1973. № 4. С. 109—113.
6. Редькин Н. П. Надежность и диагностика схем. М.: Изд-во МГУ, 1992.
7. Соловьев Н. А. Тесты (теория, построение, применения). Новосибирск: Наука, 1978.
8. Поляк Б. Т. Введение в оптимизацию. М.: Наука, 1984.