Задачи по прикладной математике

Размещено на http://www.allbest.ru/

Параметрический решебник и лабораторный практикум по прикладной математике.

Автор:

Кривошеев О.И.

Студент обязан знать свой номер. Задания, выполненные с неправильными параметрами не зачитываются. Параметры abcd должны быть получены соответственно из числа букв Фамилии, Имени, Отчества

Пример:

Фамилия Имя Отчество	Месяц рождения	abcd
Ломоносов Михаил Васильевич	ноябрь	9-6-10-11
Пушкин Александр Сергеевич	май	6995
Менделеев Дмитрий Иванович	Январь (ст.ст.)	9781
Можайский Александр Фёдорович	март	9993
Мечников Илья Ильич	май	8455
Кулибин Иван Петрович	апрель	7484
Пирогов Николай Иванович	ноябрь	778-11, допустима замена на 7781
Попов Александр Степанович	март	59-10-4, допустима замена на 5914

(Ломоносов (9букв) Михаил(6 букв) Васильевич(10) (в нашем примере получилось а=9. b=6. c=10) и номера месяца рождения, взятых по модулю (остаток от деления на число) 10. т.е

Январь и Ноябрь соответствуют 1. Кроме того, 0 меняем 1.В силу чего 10>0>1 итого с=1.

Каждый параметр пробегает почти 10, точнее 9 значений.

При использовании 3х параметров имеем 729 (около 10000) вариантов

При использовании 4х параметров имеем 6561 (около 1000) вариантов

В порядке инициативы принимаются пополнения в виде интересных обязательно серийных (сформированных на основе параметров abcd) задач. НАДЕЮСЬ, ЧТО ЗАДАЧНИК будет РАСШИРЕН. Поэтому даётся ОБЪЯВЛЕНИЕ: создание хорошей задачи стоит 4-6 задач (очень хорошей - БОЛЬШЕ).

Ответы на стандартные вопросы.

Преподавателям.

Перед Вами небольшой по объёму документ 20-50 страниц. Вы привыкли к задачникам размером со стандартную книгу, 100-200 страниц, однако надо учитывать, что каждая задача эквивалентна 1 главе задачника: в каждом массовом задании 100-10000 вариантов, в этом задачнике их 100, каждое кратности 1000-10000.

О попытке конвертировать всех их на бумагу с подстановкой всех сочетаний букв, разумеется, не может быть и речи, ибо это много больше, чем в ТИПОВОМ сборнике СТАТИЧЕСКИХ вариантов (для самой простой задачи потребуется от 500 страниц - по одной строке на задание, 20 строк на лист, для всех задач - более сотни тысяч страниц). Подходя к проблеме обеспечения потока студентов уникальными заданиями более минималистски, исходя из размера потока, пришлось бы увеличить количество и общую площадь условий не менее чем в 100 раз минималистский вариант неудобен: чтобы избежать коллизий вариантов, со студентом пришлось бы встречаться, чтобы в условиях нехватки вариантов последовательно раздать номера персонально и записывая их, (при большом количестве больших потоков это очень обременительно) - это помимо печати документа размером более 1000 страниц..

Оценочная политика.

В качестве ориентира укажем порог групп факультета Информационных и компьютерных технологий (ИКТ) МЭСИ (36 часов и более, без теста):

50 задач - отлично,

40 задач хорошо,

37+, удовлетворительно.

С учетом дополнительных заданий (тест) порог может быть повышен.

Короткий курс 36 часов менеджеры финансисты и пр.: 16/18/22 и более (не ИКТ).

Заочные группы (все факультеты) 11+ задач на минимум (иногда снижаем до 8). (В программе 2 встречи 4+4=8 часов). (Последний порог приведён для того чтобы студенты очных групп стыдились просить любую оценку выше 2 при менее 20 решённых задач).

Расширение выборки сейчас не практикуется (в частности группам занимающимся у автора на это нужно получить разрешение под роспись преподавателя), но преподавателю укажем одну опцию: возможен вариант, когда та же задача решается с инверсными номерами - числа номера берутся в стандартном представлении и берутся их дополнения до 10. Этим и аналогичными приёмами (оба номера можно сдвинуть на все 3 или на все 5 по модулю 10) преподаватель может решить проблему малого числа вариантов если у него есть возможность и потребность в интенсивной тренировке. Этот же приём (под роспись преподавателя) может быть использован для разрешения СЛУЧАЙНОЙ коллизии вариантов - их полного совпадения.

Подробные указания студентам.

Решения Ваших вариантов хранятся приблизительно ВЕЧНО - до СЕССИИ (и после - потому что многие студенты пытаются подтвердить зачёт, если (что довольно часто) их документы теряются в ДЕКАНАТАХ).

Самое ВАЖНОЕ: при поимке СТУДЕНТА на не своём Варианте все его сданные задания ОБЪЯВЛЯЮТСЯ НЕ СДАННЫМИ И ПРОХОДЯТ ПОВТОРНУЮ проверку, - прежде всего на предмет соответствия ВАРИАНТОВ. Кроме того, в МЭСИ бально-рейтинговый эксель не раз терялся - его съедал вирус. Поэтому, кто не сфотографировал свои задания (и не принял мер к сохранению копии и оригинала), имеет Великолепный и очень Счастливый шанс (Очень нужный по мнению преподавателя) их решить заново - это В ЕГО КОНКРЕТНОМ СЛУЧАЕ решит ПРОБЛЕМУ малого числа повторений конкретной темы из-за перегруженности учебной программы.

Оформление

В начале каждого решения (в левом верхнем углу каждого листа) указывается таблица личного номера автора (это параметры для Пушкина А.С. (как вычислено - смотри выше)).

Данное правило необходимо для мгновенного контроля варианта преподавателем.

В конце решения обязательно приводится ответ.

Желательно, чтобы ответ отражал суть выполненного задания и/или содержал название полученной величины (для дополнительного контроля тех, кто очень любит работать «по образцу»).

Например, в задаче поиска кратчайшего пути:

Верный вариант ответа: Кратчайший путь SABCD, его длина 20 км.

Неверный вариант: SABCD, 20 км.

Переписывать буквенный вариант не требуется. Для проверки соответствия всегда есть соответствующая распечатка.

Задачи теории ИГР

Указывается идентификатор (например, (5х4)) стоимость задачи (1 - 1,5 условных задачи), названия книг с теорией и презентации.

1. (цена 1 условная задача). (4х5) Решить антагонистическую игру. (Презентация Теория Игр)

Вычёркивая убрать доминируемые стратегии. (Подставить параметры в матрицу)

Приведём пример подстановки для студента Ломоносов Михаил Васильевич, abcd=9-6-10-11 (аналогии случайны)

Краткое описание антагонистической игры.

(Представлены два «автомобилиста», которые лихо проезжают на Васильевском острове/Манхеттене) в районе есть вертикальные и горизонтальные улицы. Первый игрок выбирает горизонтальные, Второй игрок выбирает вертикальные, это определяет перекрёсток на котором они столкнутся, после чего они прочитают сумму в миллионах, которую второй игрок, называемый плательщик, должен выплатить первому - получателю.

Для решение удаляются (покомпонентно) большие столбцы и покомпонентно меньшие строки. Строка называется покомпонентно меньшей (доминируемой), если АБСОЛЮТНО все её элементы меньше (точнее не превосходят) соответствующих элементов НЕКОТОРОЙ другой строки. Такую строку можно вычеркнуть, так как она заведомо не выгодна для первого игрока (для получателя).(оформление: в торце линий вычеркивания в скобках подписать номера доминирующих стратегий, являющихся основой их удаления, !!! линии не должны пересекаться, но могут прерываться). В ответе указать цену игры. Иногда игра имеет смешенное равновесие. В этом случае с помощью максимина и минимакса необходимо дать интервальную оценку цены игры(+0,5 задачи). Также указать вектор вероятностей для стратегии 1-го игрока, и 2-го игрока Пример: в этом случае есть решение в чистых стратегиях.

Бывает, остаётся подматрица 2х2 см следующий пример (редко, но бывает 3х3) - в таких случаях удалять стратегии (когда доминирование отсутствует), является ошибкой. Ответ пишется через двойное неравенство. Желающие могут провести интервальную оценку при Седловой точки в чистых стратегиях (+ ещё 0,3-0,4 задачи..)

2. (1/2 уз)Найти решение игры (если нужно, то в смешанных стратегиях) . В ответе указать оптимальную стратегия первого игрока (вектора вероятностей хода), и второго игрока . То же для (Презентация Теория Игр).

3. (1/2 (половина) условной задачи). Решить многошаговую игру , , (Презентация Теория Игр): Для Решени: Вычисляется последовательно цена каждой игры с подстановкой этого численного значения в игру следующего уровня. Сначала рассчитывается цена игры : , результат (как число ) подставляется в (на место ставится рассчитанное число), наконец обе рассчитанных цены игр и подставляются в "материнскую" игру , что позволяет вычислить её цену. Оформить решение как циклическое удаление стратегий.

4. (Цена 1/2 +1/2 за две части)(Презентация Теория Игр)

а) Методом сжимающих отображений решить стохастическую игру - стартовав с . выполнить 4(3) итерации

б) Найти устойчивые точки отображения выполнить десть итераций ; Рекомендуется начать с части б).

б)Решение и теория. Обе эти задачи на метод сжимающих отображений. Пусть ,. Стартуем с точки 10 (это - к счастью - не соответствует никаким параметрам).

,



Ответ неподвижная точка сжимающего отображения (указать точность, исходя из числа стабилизировавшихся разрядов).

б) Приведём конкретный пример. Рассчитать цену игры

Решение части а) основывается на формуле для игры не имеющей решений в чистых стратегиях

Необходимо подставить исходное приближение вместо в матрицу игры, рассчитать по формуле

,

(4 раза). Если результаты ДОСТАТОЧНО высокой степени повторяются, то можно обрывать вычисления, записывая в ответ экстраполяцию ряда цен игры.

,

начав со стартового приближения (у Вас, почти у всех не 0)

,



,

,

,

чрезвычайно мало отличается от , что означает, что мы с высокой точностью решили уравнение

Ответ: цена игры . Погрешность определяется темпом сходимости и модулем последней разности .

(1/1,5 задачи за обе игры)

а)решить игру

(заполнена диагональ, всюду вне её нули) и

б) решить игру существенно воспользовавшись её разложимостью на две игры 2х2:

(Презентация Теория Игр, книга Данилов. Лекции по теории игр.)

Краткие указания:

Второй случай сводится к решению 2х игр 2х2 (одна из которых точно имеет смешенное равновесие - во всех таких случаях применить теорему об активных стратегиях).

В случае(а) необходимо предположить распределение вероятностей вида и применить теорему о равенстве выигрышей на активных стратегиях. Разумеется, для её применения необходимо предварительно обосновать активность каждой стратегии, если она имеет место.

5. (2 условные задачи) рассчитать параметры олигополии

а) Курно , при издержках - первой фирмы и 2-й фирмы.

б) рассчитать параметры олигополии Штакельберга (2я ведомая). Рассмотреть ситуации, когда первая фирма становится ведомой.

Взяв любую разумную процентную ставку из интернет-поисковика (ещё лучше на память) оценить капитализацию обеих фирм.

Для решения воспользоваться уравнениями наилучших ответов

,

смысл которых в том, что при линейной функции затрат монополист берет половину конкурентного рынка , а олигополист, как бы является монополистом на СОБСТВЕННОМ конкурентном рынке, оставленном ему другими игроками.

Иметь ввиду, что объёмы конкурентного рынка у всех игроков-олигополистов разные. Они определяются их индивидуальными издержками .

Для расчёта решить уравнение , где - функция спроса, - уровень (удельных) издержек производства второй фирмы исчисляемых с единицы продукции. Аналогично конкурентное равновесие рассчитывается для первой фирмы.

получим выпуски и (если один из них отрицателен, значит фирма не участвует в рынке, вторая фирма - монополист).

Рассчитываем суммарное предложение двух фирм.

, и, с его помощью, рассчитываем : .

Зная цену можно рассчитать прибыль (вычитая издержки и ) с единицы продукции и прибыль каждой фирмы. (Отрцательность прибыли говорить о том, что фирма не выходит на рынок - а оставшаяся фирма - монополист)

(Презентация Дуополия Курно) (Книга Данилов)

6. Ответить на те же вопросы для дуополии Курно с издержками игроков, соответственно, и . Вычислить установившиеся цены, их доли на рынке и их прибыль при функции спроса . При каком пороге издержек производство второй фирмы станет нерентабельным.

(Презентация Дуополия Курно) (Книга Данилов)

7. (1у.з.) Оценить 4 пакета акций размера a,b,c и d соответственно, считая, что выигрывающая коалиция (50+1% акций) получает всё, т.е. 100% или цену предприятия (остальные ничего) (простая игра).

ВНИМАНИЕ ВАЖНО: в случае наличия контрольного пакета все пакеты увеличиваются в 2 (и более, если не достаточно) раз (пока контрольный пакет не исчезнет - иначе задача бессмысленно тривиальна).

Общая стоимость предприятия S=200 млн. долл. В ответе указываются цены 4х пакетов акций (Вектор Шепли).Указание: Для решения рассмотреть все 24=4! (факториал) перестановок - вариантов входа игроков.(презентация «1234») (книга Оуэн)

8. УЗ (1 условная задача) Решить задачу управления запасами - рассчитать оптимальную сумму снимаемую гражданином в банкомате, банковский процент (ЦЕНА хранения денег) 0,01(2b+d) 1/год, доход и расход гражданина р./мес., оценка затрат на снятие денег в банкомате - цена заказа 40(c+6) р. Указание: Все расчеты Обязательно производить В СТАНДАРТНОМ представлении с плавающей точкой (и с РАЗМЕРНОСТЬЮ).

Указание (или ).

Одновременно оценить спрос на деньги населения N=(c+d)20*106 (1у.з.) (презентация ММИО-исследование операций)(книги Таха, Кремер).

9. Решить задачу управления запасами.

Стоимость заказа S=(a+2) тысяч рублей,

Величина удельных издержек на хранение С=с руб/(шт.*день). (С=0.001*с тыс. руб/(шт.*день).)

Величина постоянного спроса на товар шт./день

Рассчитать объем заказа(Q) при котором средние издержки на заказ и хранение минимальны (оптимальный объем заказа).

Указание: считать, что надо минимизировать функцию затрат

.

Считая, что на выполнение заказа требуется b дней. При каком объёма запасов на складе работники склада должны выписывать новые партии товара.

Теория



имеет минимум в точке , что обнаруживается приравниванием производной к 0, аналогично

,

и

При управлении запасами издержки по их хранению определяются (объём в денежном выражении умноженный на банковский процент), время между заказами (время вытекания со скоростью воды из «аквариума» объёма , в роли которого объём партии поставки), расход на доставки - отношение стоимость доставки S к времени между доставками:

.

Имеем минимизируемый функционал, . Откуда, установив связь , ,, использовав получим . Тот же оптимальный объём может быть найден из

.

(1.5/2 у.з.) решить многопериодную дилемму заключенного.



Найти порог устойчивости коллективно оптимального секвенциального равновесия. Вычислит минимальное совместимое с устойчивостью коллективного решения время между играми. (заседаниями совета директоров) Принять процентную ставку в экономике равной процентной ставке ЦБ (если не помните, взять в Яндексе).(Презентация СПРН)(Книга Данилов). Задача имеет приложение как модель развала-сохранения картеля.

10. (решить игру в позиционной форме с 1й лотереей). (Презентация Теория Игр) (1 условная задача)

Условие: Из центральной большой точки (с аэродрома) по системе подземных туннелей идут двое «десантников», агентурные имена которых 1-й и 2-й соответственно. На каждой развилке написана фамилия того десантника, который в данный момент в этой ситуации принимает решение куда повернуть. В некоторых случаях решение вообще не принимается, но подбрасывается в общем случае монета (на исходящих рёбрах тогда стоят вероятности исходов, в сумме равные 1

(См. Данилов Теория Игр) Требования на параметры .(во избежание отрицательных весов в Лотерее) (Презентация Теория Игр)

Последовательность решения: Рассчитываем цены всех подигр. на первом этапе рассчитываем цены только подигр опирающихся на концевые вершины (листья). на втором и всех последующих этапах рассчитываем вершины целиком опирающиеся только на рассчитанные вершины.

11. (3)Найти коррелированное равновесие в классической игре Перекрёсток



В ответе указать область коррелированных равновесий и, в частности, угловую точку, не являющуюся ни одним из чистых равновесий.

Легенда игры на условный перекрёсток (подразумевают ситуацию раздела некоего ресурса) выезжают два игрока. ситуацию можно разрешить к обоюдной выгоде (не равновесие по Нэшу), один, например, первый игрок может уклониться, от столкновения, к выгоде другого (как и наоборот), наконец оба игрока могут пойти на жесткое столкновение.

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

Внешний арбитр может давать игрокам сигналы которые также не обязательны к исполнению, непредсказуемо "по очереди" с заданной вероятностью указывая, что играть войну или мир, причем второй игрок не знает какой сигнал получил первый игрок, первый тоже не знает какой сигнал получил второй, в противном случае, например, при сигнале ми-мир каждый по-прежнему стремился бы уклониться в свою пользу.

Презентация би-матричные игры.

Решение: В отсутствии внешнего арбитра в игре имеется два чистых равновесия и одно смешанное. внешний арбитр показывая игрокам необязательные команды (мир-мир) (мир-война) и (война мир), может обеспечить их больший выигрыш при следовании данным стратегиям, чем при отклонении от них.

Напомним, что при этом второй игрок не знает какую команду получил первый и наоборот.

Обозначим вероятности каждой пары команд (война мир) (мир-мир) (мир-война) (команда война-война не участвует - это то сочетание, которого всем хотелось бы избежать), соответственно вероятностями ,, - см. матрицу. Условия предпочтения следования командам арбитра описываются линейными неравенствами в пространстве трех чисел в сумме равных 1. , поэтому, ограничимся вероятностями ,, они соответствуют парам война-мир и мир-война (для симметрии).

12. Найти оптимальную стратегию инвестирования (и рассчитать равновесие Нэша). (зачитывается одна из двух задач)

(1,5 задачи)

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

13. (1.5 у.з. если обе части и 1 у.з. за 1часть) дана эволюционная игра Ястреб-Голубь

, где .

Выписать количество игроков второго и первого типов в равновесии и их выигрыш. По последнему показателю сравнить два варианта. I и II . В каком обществе жить лучше?.. - мера наказания (репрессии), - ресурс являющийся предметом конкуренции 2х членов общества, - сожаления голубя не получившего ресурс, - небольшие переговорные доп. издержки голубей. (Данилов Теория Игр) (Презентация Ястреб-Голубь).

14. (1,5 условных задач) (решается только один из двух АНАЛОГИЧНЫХ примеров)рассчитать все 10 основных критериев для 4х альтернатив

вначале веса даны для критерия Байеса. Для критерия Гурвица и Ходжа-Лемона взять любой допустимый вес (из отрезка [0;1]) отличный от 0, Ѕ и 1. Допустимы пары [0,7;0,3], [0,2;0,8] [0,4;0,6], [0,9;0,1] (Кузьмич методы принятия решений) (Презентация критерии)

15. (1.5 уз) Рассчитать 10 критериев для 4 альтернатив. Обвести кружком победителей по каждому критерию (Кузьмич методы принятия решений)

- элементарные, первичные критерии, например дешевизна, вес, время работы.

Расчёт критерия Байеса произвести при весах элементарных критериев (в сумме это 1).

Расчет критерия Гурвица при уровне оптимизма ,

Ходжа-Лемона при уровне доверия

(Учебное пособие А.М.Кузмича по Управленческим решениям и Презентация Критерии. )

Последовательность решения.

a. Начинаем с 4й колонки - критерия Вальда - критерий гарантированного результата- критерий осторожного инвестора. Считается как минимум в вектор-строке оценок. данной альтернативы. в случае равноправности оценок имеет смысл гарантированного результата, например, гарантированного уровня прибыли, который Обязан быть получен, вне зависимоси от сценария развития событий.

b. Критерий оптимизма - максимум по строке оценок данной альтернативы. Критерий пригоден для отбора в школу чемпионов. Какие бы человек не имел оценки, скажем условно, по шахматам и штанге нам предстоит определить по какой одной-единственной дисциплине и на сколько он близок к чемпионскому званию.

c. Критерий Гурвица есть линейная «смесь» предыдущих двух критериев с весами и соответственно. по мнению разработчиков критерия отражает меру оптимизма или склонности к риску лица использующего критерий.

d. Критерий Лапласа - среднее арифметическое по всем первичным критериям: сумма критериев нормированная на число входящих в неё критериев.

e. Критерий Байеса - взвешенное среднее с весами отражающими либо важность каждого критерия, либо вероятность наступления сценария несущего данный уровень прибыли. В последнем случае критерий Байеса есть просто математическое ожидание случайной величины. Независимо от смысла вкладываемого в веса их сумма всегда должна равняться единице.

f. Критерий Ходжа-Лемона - как и в критерии Гурвица, есть взвешенное среднее, составленное из критерия Байеса с весом и критерия гарантированного результата с дополняющим весом . Вес отражает меру доверия к прогнозу, оставшуюся долю «закрываем» по критерию гарантированного результата.

g. Главный критерий (ГК) и главный критерий при ограничениях - отражают спицифику человеческой системы обработки информации. Не будучи способен оценить сложную обстановку по многим критериям, человек может ограничиться либо одним критерием полностью отбросив остальные

,

либо см. следующий пункт:

h. Как это делается в главном критерии при ограничениях покупается самая-самая машина (самая быстрая, самая грузоподъёмная, самая экономичная - выбирается один из критериев, наиболее важный для данного лица принимающего решения), но при допустимых параметрах по другим критериям (достаточно ограниченная цена, меньшая некоего определённого ЛПР порога, ограниченный вес, меньший другого порога вес…)

i. Два критерия справедливого компромисса - оба родственники критерия Байеса и критерия Лапласа. Чтобы это понять, достаточно посмотреть на них в логарифмических координатах. В одном случае максимизируется сумма логарифмов (- простое произведение элементарных критериев), в другом - взвешенный справедливый компромисс, сумма берется с весами суммарно равными единице, которые могут выступать и выступают степенями, в которые возводятся элементарные критерии (пригодны веса доставшиеся от критерия Байеса). Критерий справедливого компромисса помимо прочего используется в играх с угрозами. В рамках некоей почти общепринятой на сегодняшний день аксиоматики считается, что перераспределение когда один участник беднее в k раз, а другой богатеет в k раз общественно нейтрально, откуда следует, что надо следить исключительно за произведениями выигрышей участников - отсюда и возникает идея рассчитать произведение по всем критериям (которые полагаются положительными). Взвешенный справедливый компромисс, как было сказано выше предполагает перед перемножением возведение в степень. Возвращаясь к теории игр - такая степень может иметь смысл переговорной силы каждого участника.

или .

Для невзвешенного справедливого компромисса возможна формула , которая делает удобным встраивание в любой составной критерий, делая критерий масш

Пример расчета критериев

16. (цена: 2 задачи в зависимости от качества оформления) Игра в угрозах (решить один из двух вариантов) ( Презентация Теория Игр, впоследствии Игра в угрозах):

a. Вариант I ,

Вариант II

b. Отражающая ведение переговоров антагонистическая игра описывается .

c. Цена этой игры, , а равновесная стратегия переговоров , , .

d. Коалиционная стратегия и , выигрыш.система решений

e. Точка и условия заключения контракта представляют собой .

для облегчения понимания пойти на доппостроение: отметить все пары чисел биматрицы на плоскости, построить бюджетную линию, опустить на неё перпендикуляры и сравнить точки крепления перпендикуляров на бюджетной линии. отразить результаты сравнений на матрице , в соответствии с ними провести удаление стратегий, найти равновесие Неша.

17. Решить игру в угрозах(пример):

, пары стратегий обозначить по матрице:

Решение: Разность выигрышей определяется (равна) разностью выигрышей в позиции равновесных угроз. Для нахождения

В итоге получим уравнение - приращение выигрыша одного игрока при отказе от угроз

Коалиционный выигрыш С задаёт границу бюджетного множества определяется элементом с максимальной суммой, в каждом конкретном случае он разный - в нашем случае это , откуда ,

;

;

Ответ: коалиционный выигрыш 210, равновесие по 2-й схеме в угрозах (d,r): 20;-240; приводит к разделу выигрыша: .

Проверка решения системы: переходит в , что ВЕРНО.

18. решить задачу оптимального инвестирования(1,5-2 условные задачи)

a. 2хn игра (презентация теория игр).

Теория и методы принятия РЕШЕНИЙ

19. (2 у.з.) Методом ЗАПРОС (книга Ларичева) сравнить(попарно)5альтернатив a1=A2Б1B3, a2= A1Б2В1, a3= A2Б2В2, a4=A3Б1В2, a5=А1Б3В2 (без вариантов). Предпочтения задаются графами частичного порядка Паре AБ () - остаток от деления на 6,АВ (), БВ () (см.число в скобках на рисунке), 216 вариантов. По результатам попарного сравнения альтернатив на плоскости построить граф их сравнения (10 пар). в случае если при построении ЕПШ выяснится противоречие -цикл -, надлежит его исправить с момента его обнаружения произвольным образом пересмотрев предпочтения в цепочках.

Теория. В методе Павельева-Ларичева ЗАПРОС решена задача перехода от линейности анализа иерархий к нелинейным сравнениям. Опыт развития методов принятия решений показал, негативные результаты при попытках учесть нелинейность на непрерывных шкалах. Ларичев и Павельев применили шкалу дискретных градаций, типа хорошо, плохо (средне, средне - плохо,..). Канонический вариант использовать в качестве градаций числа 1,2,3, 1 - идеально, 3 - плохо, 2 - средне (промежуточный результат). такие оценки вводятся по всем выбранным для учёта критериям. Для инвест-проекта это может быть технический риск, величина спроса, время окупаемости и др. Для ноутбука вес, диагональ, цена. Для автомобиля - характеристика мотора, салона и внешнего вида.

Пример:

Выбрать ноутбук. Градации от хорошего к плохому:

Время Цена Диагональ

В1- 9 часов Ц1 - 10 000р Д1- 15''

В2-4,5 часа Ц2 - 17 000р Д2- 12''

В3-2,5 часа Ц3 - 24 000р Д3- 10''

Альтернативы:

Теория Расчёта по методу анализа иерархий.

Обработка матриц парных сравнений:

Для применения метода анализа иерархий нам требуется разбить оценки так, чтобы их сумма была равна единице. Для лица принимающего решения (эксперта) представляет сложность распределить оценки между несколькими объектами сразу, когда их число значительно более двух. Матрицы парных сравнений вводятся для облегчения жизни экспертов, с учётом особенностей человеческой системы обработки информации. Все помнят сюжет советского «школьного» мультика о единицах измерения, в котором друг относительно друга измерялись различные животные.

По мотивам известного мультфильма в котором обсуждались единицы измерения, организуем выбор домашнего животного. Конечное решение принимает Вася (условно "сын режиссёра мультфильма"). Он впредь вынужден выступать под агентурным псевдонимом ЛПР - лицо принимающее решения.

Рассчитаем веса - найдем главный собственный вектор. Все столбцы согласованной матрицы являются этим собственным вектором (остальным векторам соответствую нулевые собственные значения)

Обычно считается это итерационным методом сжимающих отображений в общем случае. В этом случае берётся произвольный стартовый вектор, запускается процесс . Независимо от начальных условий получаем главный собственный вектор (в ситуации единственности главного значения он примерно однозначен).

В связи с нулевым рангом матрицы парных сравнений, когда она согласованна, стартуя с вектора из всех 1: = (1,1,..,1,1).



Полученный вектор весов-вероятностей не нормированный. Поделим его на суму компонент, чтобы получить вектор с единичной суммой компонент при сохранении относительной величины весов

(считать разрешаем почти сколь угодно приближённо, важно чтобы сумма была равна 1. Рекомендуется сначала вычислить маленькие значения, а потом посчитать большое).

Аналогично можно вычислить

Красота



Сравним важность ума, габаритов (длины) и красоты.

(Последняя матрица очевидно несогласованная)

Произведём синтез. Для этого транспонируем последний ответ и умножим его на матрицу составленную из столбцов

,,

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



.

Осталось посчитать ошибку.

Матрицы критериев нижнего уровня очевидно согласованны их главные собственные значения 3, и ИС=0. При решении мы это не проверяли. Поясним как это посчитать: для расчета собственного значения для уже данного собственного вектора нужно его преобразовать матрицей , в результате (по определению собственного вектора) получим удлинённый в раз вектор . Имеет место равенство - искомое значение. Отсюда (эту формулу не надо путать с ранее применяемой для расчёта самого формулой

или ).

Для ЛПРа Васи

, ,,.

Рассчитаем ошибку иерархии. Для этого просуммируем ошибку ЛПРа 100%, вес критериев остальных уровней поочерёдно - последовательно находится на всех промежуточных этапах синтеза. Ошибку каждого критерия надо умножить на его вес, т.е. на меру его вклада в итоговое решение, например ошибки второго уровня умножаются на веса критериев второго уровня, которые, в отличие от критериев более низкого уровня - не присутствующих в данной задаче - известны непосредственно из матрицы ЛПР: .

Примерно ясно, что нам нужно отнормировать на интенсивность, точнее матожидание порождения ошибки матрицей конкретного размера и на число этажей. Это и делается в один приём: делением на сумму матожиданий ошибок случайных матриц размеров, представленных на каждом критериальном этаже нашей иерархии - в нашем случае представлены два этажа . Сами матожидания известны из справочной таблицы приведённой в начале данного раздела. Вам рекомендуется помнить три значения

Ответ:

По суме набранных очков с точки зрения ЛПР Васи победила Обезьяна (с оценкой 0,44). Ошибка синтеза , что составляет приемлемую величину и позволяет отделить результат победителя от второго места (0,30 - Удав).

Таблица нормировки ошибок

n	1	2	3	4	5	6	7	8	9	10	11
Mnxn	0	0	0,58	0,90	1,12	1,24	1,32	1,41	1,45	1,49	1,51

Другие примеры расчета весов на базе матриц парных сравнений:

Расчёт ошибки с помощью собственного вектора

При расчёте ошибки нормировка исходного вектора не важна:

Нам пришлось делить на 10, ибо в данном примере был взят вектор длины 10.



Расчет ошибки

Приблизительно

20. АИ3 (За 3 задачи). Методичка Дмитриев. Презентация Анализ иерархий.

Решить методом анализа иерархий задачу сравнения трёх автомобилей. Все автомобили были сравнен по двум критериям грузоподъёмность и скорость в результате чего были получены две матрицы парных сравнений размера 3х3.

Важность каждого критерия оценивала тройка экспертов в том числе дедушка, мама, папа. Их мнения отражают матрицы 2х2, приведённые на рисунке.

Мнение дедушки отражает матрица

 и т.д.

Значимость (компетенция) каждого эксперта была оценена матрицей парных сравнений

.

В ответе написать одноуровневую новую иерархию с новыми весами. В процессе оформления на исходной иерархии отметить индексы согласованности, на графе иерархии отметить все веса и индексы согласованности.

Для подсказки приведём схему умножения матриц при проведении конечного синтеза

и оценку согласованности всей иерархии через ошибки матриц парных сравнений

(1 условная задача)Рассчитать 10 критериев для 4 альтернатив. Обвести кружком победителей по каждому критерию

21. Методом анализа иерархий решить задачу

22. (б)отчасти используя численные результаты предыдущего решения:

а). Сравнить две (а1,а2)-альтернативы по 3м критериям. Матрица важности критериев 1го уровня ЛПР у второго уровня М1, М2. Матрицы сравнения альтернатив по критериям нижнего (3го) уровня:, , . Рассчитать погрешность метода с помощью индекса согласованности (). *Если параметр в обратносимметрической матрице оказывается нулевой заменить его на 1.

б) Рассчитать ошибку метода по формуле



**Указание: Главные собственные вектора приближенно вычислить как сумму элементов в строках . Затем отнормировать, так чтобы сумма координат составляла 1. Расчет приоритета альтернатив (в данной постановке) сведётся к сложению (нормироанных) собственных векторов последних трех матриц с коэффициентами равными координатам нормированного главного собственного вектора первой матрицы, а расчет СЗ , где А - матрица парных сравнений.

23. (2 условные задачи)Сравнить методом ELECTRE 4 альтернативы по критериям

При весах критериев .

Чтобы устранить неопределённость сумму коэффициентов согласия б и несогласия в можно держать 1: в=1-б.

24. Пример двухуровневый анализ иерархий (классический ВАРИАНТ)

Легенда - лицо принимающее решение по трем критериям выбирает машину из трёх альтернатив

Рассчитаем веса критериев

,

Последовательно рассчитаем оценки

,

,

,

.

Исследование Операций

Указание ПРЕПОДАВАТЕЛЯМ - с этой задачи крайне рекомендуется начинать СЕМЕСТР.

Указание: Ответ должен содержать все шаги алгоритма (включаемые в сеть дорог отрезки) в правильной последовательности их выбора. В алгоритме построения минимального остовного дерева последовательно выбираются ребра (отрезки возможных путей) минимальные из оставшихся. (Презентация ИССЛЕДОВАНЕ ОПЕРАЦИЙ).

Адаптированный под бумажно-ручное решение алгоритм Крускалла:

1) выбираем самое короткое из ребер.

2) выбираем второе за ним (может быть равное предыдущему).

3) начиная с третьего ребра добавляем самые короткие рёбра из оставшихся, при условии, что они не порождают зацикливаний вместе с ранее выбранными рёбрами. В любом остовном дереве должно быть n-1 ребро, что можно считать простейшим критерием остановки алгоритма. (Забывание этого критрия не приведёт к ошибке, т.к. все остальные ребра придётся последовательно запретить).

25. Комм5х5 (Засчитывается за 4 условные задачи) 2 пары) (Презентация КОММИВОЯЖЁР) Самая сложная задача исследования операций

.

Методом ветвей и границ требуется найти Кратчайший маршрут объезда 5 городов с возвратом в исходный, при КОТОРОМ КАЖДЫЙ ГОРОД ПОСЕЩАЕТСЯ в ТОЧНОСТИ 1 раз(в матрице даны цены проезда из «левого» города в «верхний»).

Решение Методом ветвей и границ

a. Шаг №0 Оцениваем цикл 1-2-3-4-5-1 - это первое приближение верхней оценки. Далее, если на любой ветви дерева ветвления нижняя оценка подмножества решений окажется выше верхней эта ветвь «отмирает» , т.к. все её решения хуже уже имеющегося.

b. Шаг №1а) Выписываем константы редуцирования по строкам. Это минимальные числа в строках. Их надо вычесть из элементов своих строк (при этом появится не менее одного нуля в каждой строке).

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

d. Шаг №1в) Вычисляем сумму констант редуцирования полученных на шагах а) и б). Очевидно, никакой маршрут не может стоить дешевле - поэтому это оценка снизу. Далее мы будем увеличивать эту оценку на величину и (эти величины опишем ниже), где - пара индексов ребра, по которому выбрано производить ветвление.

e. Опишем, как будет происходить ветвление: выбираем ребро i,j (удовлетворяющее требованиям следующего пункта) множество гамильтоновых маршрутов можно мыслить как комбинаторно большое множество своеобразных «бус» составленных из звеньев типа Петербург-Москва, Москва-Одесса, Одесса-Белград и т.д. Примем способ разделить всё множество замкнутых путей на те, где есть дорога Одесса-Белград и те где её нет (первое множество меньше второго).

f. Теоретически можно производить ветвление по любому ребру, но наша задача в том, чтобы на одном множестве нижняя оценка цены маршрута не изменилась, а на другом максимально выросла - это может способствовать тому, что в большинстве случаев комбинаторный перебор, вообще говоря, экспоненциального алгоритма решения NP полной задачи окажется не слишком большой.

g. Для этого: Шаг №2. Вычисляем стоимости обхода для каждого нулевого элемента (если он превратился в бесконечность ?) - величина на которую увеличиваются константы редуцирования соответствующей строки и столбца.

h. Разбиваем текущее множество решений на два:

i. Большое - правое на дереве ветвления, где элемент i,j запрещён - ПОД-задача с матрицей на месте элемента i,j стоит бесконечность и

ii. Малое - левое, где элемент i,j на пути обязателен ПОД-задача, где города i на въезд и j на выезд отождествлены. В этой второй задаче требуется нетривальная дополнительная подготовка матрицы - в ответ на каждое такое отождествление нужно запретить одно и только одно дополнительное ребро. Это совсем легко и понятно на первом шаге, когда запрещается просто встречное ребро. Общее правило в той же логике. После n отождествлений существует набор звеньев обязательных к прохождению. Они могут, так сказать, «полимеризоваться» в длинные и не очень цепочки. Они могут быть однозвеные - тогда как ранее нужно запретить встречное ребро. Если цепочка длинная 3-4-5 - состоит из двух ребер 3-4 и 4-5, одно из которых - не важно какое, только что добавилось, то запрещается ребро, замыкающее всю цепочку - это ребро 5-3 - именно его надо запретить (кстати, встречного ребра, в этот момент, в матрице уже просто нет, Вы его не сможете запретить, даже если захотите: оно исчезло с предыдущими вычеркиваниями строк и столбцов).

iii. Рассчитываются приращения суммы констант редуцирования в каждой задаче. В правой - большой задаче это выбранное . В левой малой задаче - обусловленное, главным образом запрещением замыкающего (встречного или иного) ребра в предыдущем пункте в малой задаче.

iv. Полученные матрицы подвергаются редуцированию. На практике сиюминутно редуцировать надо только матрицу, опсывающую лучшее множество, которое и предстоит ветвить.

v. Ветвить на каждом шаге предстоит наиболее перспективную задачу - таковой считается задача с наименьшей нижней оценкой.

i. Процесс отчасти заканчивается после выбора k-2 ребер, где k общее число вершин. В задаче 2х2 решение однозначно, оно (обычно) приводит к коррекции верхней оценки. Если все (остальные) нижние оценки хуже, ответ получен. В таком примере как приведенный в этом задании как правило имеет место эта ситуация, но в более большом и сложном графе (при создании универсального алгоритма), требуется описать дальнейшие действия. Если всё ещё не все нижние оценки хуже чем скорректированная верхняя оценка, то выжившие нетривиальные множества придется ветвить до тех пор пока либо они не исчезнут из-за высокой, т.е. плохой нижней оценки, либо (что редко) до того как будет получена новая верхняя оценка - новое решение, превосходящее по качеству предыдущее. Процесс продолжается до тех пор, пока полученное решение не останется безальтернативным.

26. Ком4х4, (3 задачи - засчитывается только 1 из двух задач) Сокращённая задача Коммивояжера

4х4

Презентация КОММИВОЯЖЁР

Проверяется по дереву ветвления, в вершинах дерева отобразить нижние оценки целевых функций, на рёбрах дерева д.б. обязательно отображены все и(правый поворот), все ДZ(сумма констант редуцирования). В ответе дается цепочка Рёбер вида (1,k)(k,l)(l,m)..(r,1)(по размеру задачи), стоимость маршрута состоит из начальной нижней оценки и её приращений ДZ(если были только ВЫЧЁРКИВАНИЯ - левые ПОВОРОТЫ) и - что бывает очень редко - ДZ и и, если КРОМЕ левых ПОВОРОТОВ присутствовали один или несколько правых поворотов. Провести проверку стоимости ПОЛУЧЕНОГО решения по исходной матрице, объяснить причины несовпадения - если имелись (не совпадений быть не должно).

a. (irr)(1 задача) (45 мин) Рассчитать рентабельность проекта на рисунке. Время между платежами 1,5 года.

Сравнить IRR cо ставкой банка, взятой на память (или же из Яндекса), принять решение, целесообразны ли инвестиции в данный проект. Ответ (как и ВСЕ промежуточные вычисления во время решения) данные без размерности не засчитываются.

27. (2 задачи, пара 90 мин). Алгоритмом Форда-Фалкерсона найти максимальный поток в сети

(Презентация ИССЛЕДОВАНЕ ОПЕРАЦИЙ)

При решении только САМ граф перерисовывается 5-6 раз). При выполнении каждой итерации необходимо нарисовать новый граф и произвести его разметку в соответствии с алгоритмом, найти новый поток и, пересчитав веса нарисовать новый граф, повторяя итерации пока возможно проводить потоки.

В ответе

1)Восстановить граф потоков по разности пропускных способностей на старом и новом графе

2)построить матрицу потоков

3) дать СУММУ потоков, Проверить совпадение с суммой выходящих из S и входящих в F по матрице.

28. (2 задачи, почти пара)Решить задачу поиска кратчайших путей. (Презентация ИССЛЕДОВАНЕ ОПЕРАЦИЙ)

Образец оформления

Алгоритм.

Начало.

В стартовой вершине S ставим (0,-) -ВЕЧНАЯ МЕТКА (Она читается 0 «из ниоткуда»).

Из стартовой вершины мы рассылаем ВО все соседние ВЕРШИНЫ ВРЕМЕННЫЕ МЕТКИ «метастазы» - в них ставится сумма 0 (из позиции (0,-)) и расстояния до стартовой вершины S

29. (СПУ1) Рассчитать минимальное время выполнения проекта.

30. (СПУ2): чтобы не производить сложных расчетов - заменим в предыдущем условии ВСЕ веса на их разности с 10, взятые по модулю(таким образом все веса положительны). Перейдём в представление УЗЕЛ-РАБОТА. (построить граф на весь лист, предварительно повернув его альбомно) Пользуясь 10ти компонентным представлением отразить сведения о работе (название, центр-длительность, времена начала-окончания в углах. Запасы в серединах сторон. По одной из этих задач построить график Ганта. Задача обязательна по дисциплине управление проектами.

31. (1 условная задача) Рассчитать методом динамического программирования (решения полученные другими способами не принимаются) кратчайший путь по системе дорог.

Найти кратчайший путь из S до T.

На каждом шаге в очередном слое расставляются наименьшие возможные расстояния до Т на основе длин путей до предыдущего слоя (указаны возле стрелок) и ранее вычисленных расстояний предыдущего слоя. Результаты вычислений должны быть записаны рядом с вершинами, в противном случае в процессе проверки не возможно установить факт использования алгоритма. Кроме того, напротив каждой вершины одна из исходящих стрелок должна быть помечена как решение оптимизационной задачи поиска кратчайшего пути в этой вершине. Это даст возможность восстановить оптимальный путь.

Алгоритм решения:

1) В концевой вершине (в нашем случае это Т) ставится метка Z=0/галочка не ставится (в общем случае терминальные вершины образуют - некое множество, в непрерывном случае говорят о границе, которую требуется достичь).

2) В вершинах опирающихся на концевую (на терминальную поверхность), т.е. в вершинах первого слоя можно рассчитать целевые функции.

3) Общее правило целевые функции рассчитывать в тех вершинах, которые опираются только на уже рассчитанные вершины (и не опираются ни на одну нерассчитанную).

4) Расчет в каждом случае происходит как прибавление к большой накопленной сумме записанной в вершине, на которую опирается данная и расстояния до неё. Среди всех таких сумм берётся минимум, на соответствующем направлении ставится галочка. Против рассчитываемой вершины ставится оптимальное значение Z=…

5) Расчёт длится до тех пор, пока не достигнем стартовую вершину S. Перед этим обязаны рассчитать все остальные вершины, т.к. стартовая вершина S прямо или опосредованно опирается на все следующие за ней вершины.

32. Расчёт длиннейшего - критического пути (задача сетевого планирования) ведется в идеологии предшествующего примера, с небольшой разницей -

a. ПРВЫЙ ПРОХОД Метка Тр=0 ставится в левой стартовой вершине проекта. Рассчитываются любые вершины, которым предшествуют только уже рассчитанные вершины (и никакие более). В каждой вершине суммируется время предшествующей вершины и длина работы, от неё отделяющее. Среди всех таких сумм мы находим максимум, мотивировка которого в том, что, для того чтобы состоялось событие и могли стартовать работы исходящие из вершины должны закончится все входящие в неё работы. Четкую структуру слоёв в ГРАФЕ ПРОЕКТА на первый взгляд обычно выделить не удаётся (хотя можно выделить слои по этапам расчёта). Расчет ведется до тех пор, пока не будут рассчитаны все вершины.

b. Критический путь восстанавливается с концевой вершины по меткам (галочкам). Он сам и его длина (Тр концевой вершины) пишется в ответ.

c. ОБРАТНЫЙ ПРОХОД. На концевой вершине копируется значение стоящей в ней метки Тр=.. в Тп=.. Это позднее время наступления события. Рассчитываются поздние времена наступления событий. Всё также как в предыдущем первом проходе, но для расчёта должны быть рассчитаны поздние времена Тп в последующих вершинах. Расчет производится на минимум: вычитается длина работы до каждого ранее рассчитанного последующего события из позднего времени его наступления, худшая,т.е. минимальная из этих разностей и есть максимально возможное - т.е. самое позднее время наступления события, не приводящее к срыву максимально возможно ранних сроков сдачи проекта, рассчитанных в первом проходе. Критический путь не рассчитывается галочки не ставятся.

d. В третьей части для двенадцати работ не лежащих на криическом пути и не являющихся ни начальными ни концевыми считаются полный, собственный, ранний и поздний резервы времени.

e. Для студентов специализации СПУ строится график Ганта.

33. Решить задачу линейного программирования (прямая задача 2 условные задачи, двойственная 1 условная задача, все вместе -3 у.з.)

Условие: антагонистический матрица линейный фурье

34. Решить задачу двойственную к предыдущей. Сравнить ответ. (задачи решаются комплектом).

35. (2 условных задачи)Решить задачу теории массового обслуживания

b. Дано , интенсивность поломок оборудования (где (условие оптимизировано под данные из Ф.И.О.), если не так ПРИБАВИТЬ ровно 10: ) -

c. - скорость(интенсивность) ремонта. Ремонтом занимаются два человека, обслуживающих К=4 автомата (См. Хемеди А Таха Исследование операций).

36. (устаревшая задача) Решить графическим методом. В решении должны фигурировать для каждого ограничения пары точек(1 точка это две координаты, их порядок важен) удовлетворяющие соответствующему равенству, тестовая точка - (0,0) или другая, и то, отвечает она неравенству или нет. На графике: градиент, отложенный от начала координат, прямые, соответствующие ограничениям, штриховка по одну из сторон каждой прямой, включая координатные оси, обозначающая полупространство определяемое соответствующим неравенством и их пересечение - область допустимых решений должна быть обведена специальным цветом. В ответе должны быть даны координаты точки пересечения активных ограничений

(задача оптимизации производства: - объёмы выпуска на конвейерах, коэффициенты при них в неравенствах - объёмы ресурсных затрат, числа в правой части - наличествующий ресурс каждого типа, - прибыль, коэффициенты при переменных (компоненты вектора градиента) - цены продукции ).

Теория сложности и преобразование Фурье:

Вычислительная математика и теория алгоритмов

37. Вычислить быстрое преобразование Фурье на степенях от многочлена ( - они образуют геометрическую прогрессию с коэффициентом ), найти обратное преобразование.

38. (4 задачи) (БПФ)Вычислить быстрое преобразование Фурье на степенях от

d. . Проверить обратным преобразованием(проверку сделать для только для Фурье образа четного полинома, см. пример)

e. (решать a) этот запасной).

Пример проверки - расчёт обратного преобразование Фурье к преобразованному четному полиному.

39. (1 задача, действ.Фурье2) и представить в виде вектора значений на точках . Перемножить значения, восстановить полином 4й степени по значениям, перевести в число с помощью поразрядного сдвига.

Схема решения:

Подставим наши аргументы, чтобы найти четыре уравнения на четыре (не известные нам пока) коэффициента:



( известно, для ускорения процесса второе уравнение вычесть из 4-го и посчитать их сумму найдется и связь и , подставив в первую строку найдете и ).

40. (1,5 задачи, комп. Фурье, Ш.Ш.) Перемножить алгоритмом типа Шеханге-Штрассена и . Использовать корни четвертой степени из 1: . ( - они образуют геометрическую прогрессию с коэффициентом ) Пусть

41. (0,5 задачи, действ.Фурье - начало) и перемножить как полиномы. Восстановить с помощью поразрядного сдвига. Сопоставить результат с прямым перемножением чисел. Пример



Подставляем 10 вместо х, чтобы найти результат перемножения

Проверка прямым перемножением

(т.е. решение верно).

//Пример2: ,

42. битовое преобразование Фурье. перемножить с помощью дискретного битового преобразования Фурье по модулю простого числа (7) (по желанию Можно взять больший простой модуль, например 11,17 и т.д.). два числа c и d. если их произведение оказывается больше 63. одно из них разделить пополам, взять целую часть. желательно, чтобы при этом не получилось число 5 - чтобы этого избежать поделите другое число (ибо пример с числом 5 разобран нами ниже).

обратная матрица или , что тоже , потому что .

пример перемножим число 5 и 5 (у нас слишком мало примеров ограниченной сложности, поэтому не будем показывать два разных числа)

, второе число совпадает с первым поэтому результат тот же

=

Восстановим результат перемножения полиномов с помощью поразрядного сдвига

.

теория. Преобразование Фурье

,

где - примитивный корень n+1 степени из 1. Обычно корни бывают в комплексной плоскости вида над полем комплексных чисел, - обычно берётся корень n+1 степени из 1: (для удобства проведения быстрого преобразования Фурье важно, чтобы , ), либо корни по модулю натурального числа. здесь тоже бывает важно, чтобы это был корень степени .