в некоторых пробных прогонах, когда элементы матрицы выбирались наугад из множества {0,1,2,3,4}, для нахождения решения методом 1 требовалось время, примерно равное 730и, а решение методом 2 занимало приблизительно 530и времени. Если матрица состоит из одних нулей, то метод 1 позволит найти седловую точку за 137и, а метод 2 - за 524и.

Если матрица размера m х п состоит из различных элементов, то задачу можно решить, просмотрев только 0{т + п) элементов и выполнив 0(т log п) вспомогательных операций. (См. работу Bienstock, Chung, Predman, Schaffer, Shor, Suri, AMM 98 (1991), 418-419 )

11. Предположим, что матрица имеет размер тпхп. (а) По теореме, сформулированной в ответе к упр. 10, все седловые точки матрицы имеют одно значение, поэтому (вследствие предположения о том, что элементы матрицы различны) существует максимум одна седловая точка. Согласно свойству симметрии искомая вероятность равна тп, умноженному на вероятность того, что оц является седловой точкой. А эта последняя вероятность равна l/(mn)!, умноженному на число перестановок с 012 > оц, oin > on, on > 021,

On > Omi- Это равно l/(m + n - 1)!, умноженному на число перестановок т + п - 1 элементов, в которых первый элемент больше следующих (т - 1) элементов и меньше оставшихся (п - 1) элементов, т. е. равно (т - 1)! (п - 1)!. Поэтому в ответе получим

тп{т - 1)! (п - 1)!/(т + п - 1)! = (т + п) Д" .

В нашем случае получаем 17/( g), т. е. только один шанс из 1 430. (Ь) Вследствие второго предположения необходимо использовать совершенно другой метод, так как может быть несколько седловых точек; фактически вся строка (либо весь столбец) должна полностью состоять из седловых точек. Искомая вероятность равна вероятности того, что существует седловая точка с нулевым значением, плюс вероятность того, что существует седловая точка со значением 1. Первое представляет собой вероятность того, что существует по меньшей мере один столбец, полностью состоящий из нулей, а последнее - вероятность того, что существует по меньшей мере одна строка, полностью состоящая из единиц. Поэтому в ответе получаем (1 - (1 - 2""")") + (1 - (1 - 2"")™). В нашем случае это будет 924744796234036231/18446744073709551616, т. е. приблизительно 1 шанс из из 19.9. Приближенный вид искомой формулы: 712""" + т2~".

12. М. Хофри (М. Hofri) и Ф. Жаке (Р. Jacquet) [Algorithmica 22 (1998), 516-528] проанализировали случай, когда элементы матрицы размера т х п различны и выбраны в случайном порядке. Тогда время выполнения двух приведенных программ для MIX составляет соответственно (6mn +5тЯп + 8т +6 + 5(т + 1)/(п - l))u + 0((m + n)7("m")) и (5тп + 2пНт -Ь 7т + 7п + 9Яп)и + 0{1/п) + 0{{\ognf/m) при т->ооип->оов предположении, что (log n)/m -> 0.

13. * ЗАДАЧА ДЕШИФРОВКИ (СЕКРЕТНО)

ТАРЕ EQU 20 Ввести номер устройства.

TYPE EQU 19 Вывести номер устройства.

SIZE EQU 14 Ввести размер блока.

OSIZE EQU 14 Вывести размер блока.

TABLE EQU 1000 Таблица результатов

ORIG TABLE (первоначально с нулевыми значениями,

CON -1 кроме результатов

ORIG TABLE+46 для пробелов и

CON -1 звездочки).

ORIG 2000

BUF1 ORIG *+SIZE Первая буферная область.

BUF2

BEGIN IH

2H ЗН

ЗН 2Н

CHAR FREQ

ORIG

ENT6

ENT5

INCA

SLAX

ENTl

JANN

JINZ

INC5

JXNN

ENTl

JANP

CHAR

JBUS

CMPl

INCl

ORIG

-1 *+l

♦+SIZE -1

BUFl

BUFl(TAPE) BUF2

0,6(TAPE)

SIZE+1,6

TABLE,1 1

*+l(2:2) 0

TABLE.1

0,5 3B IB 1

TABLE.1 IF

*(TYPE) CHAR(1:1) CHAR(4:5) FREQ

ANS (TYPE)

=63=

С NN NNNNN ANS+OSIZE BEGIN

Признак конца буфера. Ссылка на второй буфер. Второй буфер. Признак конца буфера. Ссылка на первый буфер. Ввести первый блок.

Ввести следующий блок. Во время ввода этого блока подготовиться к обработке предыдущего.

Основной

цикл,

должен

выполняться

настолько быстро,

насколько это возможно.

Обновить элементы таблицы. гП <- следующий символ

Нормальный символ? Звездочка? Пропустить пробел.

гХ <- пять символов.

Перейти, если это не признак конца буфера.

Обработка блока закончена.

Приступить к завершающей фазе. гП <- "А".

Опустить нулевые результаты. Преобразовать в десятичную форму. Ждать готовности терминала.

Вывести один ответ.

Подсчитано до 63 кодов символов.

Буфер вывода.

Оставшаяся часть буфера пуста

Здесь получаем литеральную константу =63=

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

14. Чтобы сделать эту задачу более сложной и интересной, в приведенном ниже решении, частично принадлежащем Дж. Петолино (J. Petolmo), используется множество различных ухищрений, позволяющих сократить время выполнения. Может ли читатель сэкономить еще несколько .микросекунд?

ДАТА ПАСХИ