Редактирование: Тигры, контрольная 1
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
==Описание== | ==Описание== | ||
- | + | в 2012 году лектор дал всего две задачи. В обеих был параметр '''N''', который на самом деле мало на что влиял. Его надо было посчитать как сумму длин составляющих вашего ФИО, то есть для '''Потапенко Виктор Алексеевич''' '''N''' = 25. Оценка складывалась из 2 за присутствие и по 1,5 за каждую из задач (за каждый из трех подпунктов первой задачи по 0,5). При неправильно посчитанном '''N''' лектор ставил 2. В проходе аудитории (П8) стоял стол, который мешал ходить, и, возможно поэтому, лектор не ходил и не проверял валидность конспектов, отсутствие телефонов и пр. На все давалось примерно 20 минут | |
==Теория== | ==Теория== | ||
Строка 41: | Строка 41: | ||
* Вектор '''a''' слабо доминирует вектор '''b''', если любой i-ый элемент '''а''' больше или равен i-му элементу '''b'''. | * Вектор '''a''' слабо доминирует вектор '''b''', если любой i-ый элемент '''а''' больше или равен i-му элементу '''b'''. | ||
- | * Выпуклой комбинацией | + | * Выпуклой комбинацией называет линейную комбинацию векторов, в которой коэффициенты неотрицательны и в сумме дают единицу. Например 0.2'''a''' + 0.3'''b''' + 0.5'''c''' это выпуклая комбинация векторов '''a''', '''b''' и '''c''' |
Итак, строку мы можем выкинуть, если существует выпуклая комбинация остальных строк, слабо доминирующая эту строку. А столбец мы можем выкинуть, только если '''он''' слабо доминирует какую-нибудь выпуклую комбинацию остальных столбцов. | Итак, строку мы можем выкинуть, если существует выпуклая комбинация остальных строк, слабо доминирующая эту строку. А столбец мы можем выкинуть, только если '''он''' слабо доминирует какую-нибудь выпуклую комбинацию остальных столбцов. | ||
[[Изображение:Tig8.png]] | [[Изображение:Tig8.png]] | ||
- | |||
- | ==Задачи== | ||
- | ===Задача 1=== | ||
- | ====Пункт а==== | ||
- | Ответить на вопрос и обосновать, может ли у матрицы '''''N'''''x'''''N''''' быть ровно [[Изображение:Tig9.png]] (округлено вверх) седловых точек? | ||
- | |||
- | '''Решение''' | ||
- | |||
- | * Для четного N да, так как [[Изображение:Tig9.png]] это ровно половина элементов матрицы. Так что заполним левую половину нулями, а правую единицами. Получим точно нужное количество элементов, так как все нули у нас - наибольшие в столбцах и наименьшие в строках | ||
- | |||
- | [[Изображение:Tig10.png]] | ||
- | |||
- | * Для нечетного N нет, так как метод нахождения седловых точек, описанный в разделе Теория, основан на теореме, следствием из которой является то, что множество седловых точек представляется как прямоугольник, то есть множество точек ['''x''','''y'''] где '''x''' принадлежит '''X''', а '''y''' принадлежит '''Y'''. То есть количество седловых точек должно раскладываться на два множителя, оба из которых меньше или равны '''N'''. Таким образом, у матрицы 3x3 не может быть 7 седловых точек, так как 7 - простое число. А для N =25 [[Изображение:Tig9.png]] =313, а это число не делится нацело ни на одно из чисел от 2 до 25 | ||
- | |||
- | ====Пункт б==== | ||
- | Ответить на вопрос и обосновать, может ли у матрицы '''''N'''''x'''''N''''' не быть седловых точек? | ||
- | |||
- | '''Решение''' | ||
- | |||
- | Да, конечно. И это даже не зависит от N (при N > 1). Пример | ||
- | |||
- | [[Изображение:Tig11.png]] | ||
- | |||
- | Любой '''0''' является наименьшим в своей строке, но не является наибольшим в своем столбце. | ||
- | |||
- | Любая '''1''' является наибольшей в своем столбце, но не является наименьшей в своей строке. | ||
- | |||
- | ====Пункт в==== | ||
- | Ответить на вопрос и обосновать, может ли у матрицы '''''N'''''x'''''N''''' быть ровно одна седловая точка? | ||
- | |||
- | '''Решение''' | ||
- | |||
- | Да, конечно. И это даже не зависит от N. Пример | ||
- | |||
- | [[Изображение:Tig12.png]] | ||
- | |||
- | Единственная седловая точка здесь это '''1''' (легко проверить) | ||
- | |||
- | ===Задача 2=== | ||
- | |||
- | Найти решение игры для матрицы стратегий | ||
- | |||
- | [[Изображение:Tig13.png]] | ||
- | |||
- | Будем решать для '''N''' = 25, но на самом деле здесь мало что зависит от '''N'''. Мы видим, что здесь нет седловых точек, а значит решение существует (причем обязательно) только в смешанных стратегиях | ||
- | |||
- | Воспользуемся графическим методом, который рассчитан на матрицы 2x'''n''' и '''m'''x2 | ||
- | |||
- | Используя коэффициенты из трех столбцов нашей матрицы, запишем три уравнения прямых | ||
- | |||
- | [[Изображение:Tig14.png]] | ||
- | |||
- | Вычислив точки пересечения, построим графики ('''p''' принимает значения от 0 до 1) | ||
- | |||
- | [[Изображение:Tig15.png]] | ||
- | |||
- | Из всех пересечений выбираем те, под которыми не проходят другие прямые, и из них выбираем то, что левее. В нашем случае все просто, это пересечение прямых '''l1''' и '''l3'''. Значение '''p''' в этой точке 1/2, а значит распределение стратегий первого игрока у нас '''P''' = {'''p''', 1-'''p'''} = {1/2, 1/2}. Значение игры у нас 15,5 (значение l1 или l3 в точке пересечения). Осталось найти распределение стратегий второго игрока. Для этого нам надо решить еще одно уравнение. У нас пересеклись прямые l1 и l2, поэтому возьмем первый и третий столбец исходной матрицы. В каждом из них из верхнего элемента вычтем нижний (так мы получаем коэффициенты для уравнения второго игрока): '''k1''' = 1 - 30 = -29, '''k3''' = 30 - 1 = 29. Подставим их в уравнение | ||
- | |||
- | [[Изображение:Tig16.png]] | ||
- | |||
- | теперь '''Q'''= {'''q''', 0, 1 -'''q'''} (для прямых, не участвовавших в пересечении проставляем нулевую вероятность), следовательно '''Q''' = {1/2, 0, 1/2} | ||
- | |||
- | '''Ответ:''' '''P''' = {1/2, 1/2}, '''Q''' = {1/2, 0, 1/2}, '''v''' = 15,5 | ||
- | |||
- | '''P.S.''' Есть решение еще проще. Если '''N'''>15, то можно выкинуть средний столбец, потому что он доминирует полусумму первого и третьего столбца. Тогда у нас получается циклическая матрица 2x2, которая легко решается и без графического метода |