Домашнее задание 3

Мягкий дедлайн: 25 ноября, 23:55. Жёсткий дедлайн: 2 декабря, 23:55.

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

Игра «Жизнь»

  1. Описать все возможные потомства и очерёдность их смены для популяции «Жаба» в игре «Жизнь» на бесконечном поле:
    | | |•| |
    |•| | |•|
    |•| | |•|
    | |•| | |

Элементарные клеточные автоматы

  1. Определите, к какому типу в классификации Стивена Вольфрама относится Правило 104, если его работа для случайной популяции выглядит следующим образом:
  2. Изучение элементарных клеточных автоматов (таких, как правило 110) часто начинается с рассмотрения популяций, порождаемых одной живой клеткой, расположенной на бесконечном поле. Можно выделить несколько правил, которые порождают одинаковые потомства указанной исходной популяции (одной живой клетки). Напишите программу, которая находит все правила, первые 15 поколений которых для одной клетки совпадают с тем, что получается для правила 114. Программа должна также печатать эти первые 15 поколений (как обычно, такие поколения располагаются друг под другом, составляя двумерный узор). Замечание: в случае 15 поколений-наследников видимую часть игрового поля стоит делать длиной ровно в 31 клетку и размещать исходную живую клетку ровно в центре поля.
  3. Продолжая исследовать потомства единственной клетки, можно заметить следующее: если порождающее правило составлено так, что 000 порождает 0, то есть правило чётно, то каждая следующая популяция на бесконечном поле является всё же конечной. В этом случае её можно рассматривать как двоичное представление некоторого (конечного) целого числа. Напишите программу, которая применяет правило 28 к одной живой клетке и печатает последовательность из первых N целых чисел, соответствующих первым N поколениям-потомкам одной клетки, рядом с самими поколениями. С помощью Google найдите название этой последовательности (достаточно ввести в поисковую систему первые восемь чисел). Пусть ваша программа печатает в начале своей работы название этой последовательности.

Автоматы-генераторы

Ответы к задачам 1–3 следует записать на листике, отсканировать (сфотографировать) и загрузить на этой странице. Ответы к задачам 4–5 должны быть оформлены в виде файлов с исходным текстом на C++. Придумайте человекопонятные названия к файлам с ответами.

  1. Привести пример линейного конгруэнтного генератора (ЛКГ) с полным периодом от 10 до 20. Выписать один период псевдослучайной последовательности, которая порождается этим ЛКГ и имеет полный период.
  2. Найдите период регистра сдвига с линейной обратной связью (LFSR), заданного многочленом  f(x) = x4 + x3 + x + 1. На основе этого сделайте заключение, является ли многочлен примитивным.
  3. Предположим, что ячейки регистра сдвига могут хранить произвольные целые числа, функция обратной связи должна линейно зависеть от значений ячеек, но может использовать любые арифметические операции. Спроектировать регистр сдвига, порождающий последовательность Фибоначчи. Указать длину полученного регистра, выписать первые пять заполнений этого регистра, при этом выбрать такое начальное заполнение, чтобы на выходе получалась последовательность Фибоначчи.
  4. По данным Википедии, в реализации стандартной библиотеки C++, поставляемой с компилятором Microsoft Visual C++, функция rand() представляет собой линейный конгруэнтный генератор с 232 состояниями и со слагаемым c = 269EC316 (16-разрядная система счисления). Функция rand() возвращает биты 30..16 своего очередного состояния. Напишите программу на C++, которая доказывает, что 30..16 биты слагаемого c действительно совпадают со значением, данным в Википедии.
    Подсказка: используйте функцию srand, задающую исходное состояние X0 ЛКГ.
  5. Напишите программу на C++, в которой определяется функция 
    int LFSR()
    возвращающая очередной бит регистра сдвига, рассмотренного в примере на лекции 5 (x3 + x + 1). Программа должна печатать на консоль один период псевдослучайной последовательности, порождаемой регистром. Состояние регистра должно храниться в глобальной переменной типа int: младшие четыре бита переменной описывают текущее состояние РСЛОС. Реализация функции LFSR не должна использовать целочисленных арифметических операций и должна применять только битовые операции:
    • >> / << — битовый сдвиг вправо / влево,
    • ^ — побитовый xor
    • | — побитовый or
    • & — побитовый and.

    Указание. Разумеется, реализацию подобной функции легко нагуглить. Постарайтесь обойтись без этого. При возникновении затруднений постарайтесь найти доступное описание и примеры работы с битовыми операциями.
    Замечание. У вас есть выбор: реализовывать функцию LFSR с жёстко зашитым в неё РСЛОС или параметризовать её правило РСЛОС (например, сделать ещё одну глобальную переменную, которая хранила бы внутри себя связи РСЛОС).