Задания для самостоятельной работы. Порождение подмножеств

Порождение подмножеств

Реализовать алгоритмы 1[8].

Реализовать алгоритм 2.

Сравнить время работы алгоритмов 1 и 2[9]. Построить графики временной зависимости для алгоритмов 1 и 2.

Реализовать, алгоритм 3.

Подготовить ответы на следующие контрольные вопросы:

понятие множества, подмножества, мощности конечного множества, мультимножества.

способы задания множеств.

теорема о числе подмножеств конечного множества.

общие подходы к порождению комбинаторных объектов.

понятие кода Грея. Рекурсивное определение двоично-отраженного кода Грея и его последовательности переходов.

Порождение перестановок

Реализовать алгоритм 6.

Реализовать алгоритм 7.

Сравнить время работы алгоритмов 6 и 7. Построить графики временной зависимости для алгоритмов 6 и 7.

Реализовать алгоритм 8.

Подготовить ответы на следующие контрольные вопросы:

понятие перестановки. Теорема о числе перестановок n -элементного множества.

понятие перестановки с повторениями. Теорема о числе таких перестановок.

понятие последовательности перестановок в лексикографическом порядке.

понятие последовательности перестановок в порядке минимального изменения. Рекурсивное определение такой последовательности.