Введение в параллельные алгоритмы

Упражнение 1:

Номер 1

Чему равен период генератора u[i+1]=(5* u[i]+7) mod 16, i>0:

Ответ:

(1) 16

(2) 7

(3) зависит от значения u[0]

Номер 2

Чему равен период генератора u[i+1]=(3* u[i]+2) mod 8, i>0:

Ответ:

(1) 7

(2) 8

(3) зависит от значения u[0]

Номер 3

Чему равен период генератора (5*u[i]+2) mod 8:

Ответ:

(1) 9

(2) 8

(3) 7

(4) 6

Упражнение 2:

Номер 1

Чему равен период генератора x^k mod (x²+1), x>1?

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

Номер 2

Чему равен период генератора x^k mod (x²+x+1):

Ответ:

(1) 3

(2) 4

(3) 2

Номер 3

Чему равен период генератора x^k mod (x⁴+x+1):

Ответ:

(1) 16

(2) 4

(3) 15

Упражнение 3:

Номер 1

Чему равно u[33], если u[i+1]=(1 * u[i]+3) mod 5 при u[0]=3:

Ответ:

(1) 2

(2) 1

(3) 0

Номер 2

Чему равно u[34], если u[i+1]=(5 * u[i]+1) mod 32 при u[0]=0

Ответ:

(1) 16

(2) 6

(3) 15

Номер 3

Чему равно u[134], если u[i+1]=(2 * u[i]+2) mod 16 при u[0]=6

Ответ:

(1) 6

(2) 14

(3) правильного ответа нет

Упражнение 4:

Номер 1

Чему равно x¹⁰ mod (x²+x+1):

Ответ:

(1) х

(2) x+1

(3) x²

Номер 2

Чему равно x³² mod (x⁴+x+1):

Ответ:

(1) 1

(2) x

(3) x²

Номер 3

Чему равно x¹² mod (x²+1):

Ответ:

(1) 1

(2) x

(3) x²

Упражнение 5:

Номер 1

Отметьте за какое время можно ли вычислить значение любого u[k]=(a* u[k-1]+c) mod M.

Ответ:

(1) за время, пропорциональное k

(2) за время, равное времени вычисления u[100]

(3) за время, пропорциональное log(k)

Номер 2

Справедливо ли, что:

Ответ:

(1) точки, имеющие координаты x[i]=(a* u[2*i]+c) mod M и y[i]=(a* u[2*i+1]+c) mod M, расположены на небольшом, по сравнению с M, количестве параллельных прямых

(2) период линейно-конгруэнтного генератора { u[i]=(a* u[2*i]+c) mod M } всегда меньше M

(3) период генератора { x^k mod G(x) }, где G(x) – полином степени k может иметь период 2^k

Номер 3

За какое время можно вычислить значение любого { xⁱ mod G(x) }, где G(x) – полином степени k?

Ответ:

(1) за время, равное времени вычисления x¹⁰⁰ mod G(x)

(2) за время, пропорциональное i

(3) за время, пропорциональное log(i)

Упражнение 6:

Номер 1

Верно ли, что использование генератора, основанного на физических принципах, а не на рекуррентных соотношениях, гарантирует, что:

Ответ:

(1) будет сформирована последовательность высокого, с точки зрения батареи тестов Diehard, качества

(2) будет обеспечена воспроизводимость результатов при разных запусках на одном и том же процессоре

(3) будет обеспечена возможность формирования разных последовательностей на разных процессорах

Номер 2

Верно ли, что для многопроцессорных систем важны следующие свойства генераторов псевдослучайных чисел:

Ответ:

(1) воспроизводимость результатов при разных запусках программы

(2) возможность согласованной генерации разных фрагментов одной последовательности на разных вычислительных узлах

(3) возможность формирование последовательности, длина которой превышает 2³² элементов

Номер 3

Верно ли, что для многопроцессорных систем важны следующие свойства генераторов псевдослучайных чисел:

Ответ:

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

(2) для тестирования последовательности с помощью батареи тестов Diehard необходима многопроцессорная система

(3) одна и та же последовательность может быть сформирована с помощью каждого из трех методов: 1) M-последовательностей, 2) генератора на сдвиговом регистре, 3) генератора на основе примитивных полиномов

Введение в параллельные алгоритмы - тест 6