2015-04-01
584
1. Реализуйте на языке высокого уровня рассмотренные алгоритмы:
· Алгоритм порождения подмножеств по 1-й схеме.
· Алгоритм порождения подмножеств по 2-й схеме.
· Алгоритм порождение двоично-отраженного кода Грея.
· Алгоритм порождения сочетаний в лексикографическом порядке.
· Алгоритм порождения случайного сочетания.
· Алгоритм порождения перестановок в лексикографическом порядке.
· Алгоритм порождения перестановок в порядке минимального изменения.
· Алгоритм порождения случайной перестановки.
· Алгоритм порождения разбиений в словарном порядке.
2. Постройте графики времени работы каждой программной реализации рассмотренных алгоритмов. Для снятия временных характеристик используйте функции времени встроенные в используемую систему программирования. При снятии временных характеристик учтите, что время, затрачиваемое на порождение очередного комбинаторного объекта, как правило, намного меньше, чем время, затрачиваемое на вывод этого объекта на экран. Поэтому для получения адекватных временных характеристик работы алгоритмов вывод на экран лучше отключить.
3. Разработать следующие алгоритмы:
· Алгоритм порождения размещений
· Алгоритм порождения сочетаний с повторениями.
· Алгоритм порождения композиций n.
· Алгоритм порождения композиций n из k частей при рi>0.
· Алгоритм порождения композиций n из k частей при рi³0.
Вопросы для повторения
1. Понятие мультимножества.
2. Теорема о числе подмножеств конечного множества.
3. Общие подходы к порождению комбинаторных объектов.
4. Понятие кода Грея.
5. Рекурсивное определение двоично-отраженного кода Грея и его последовательности переходов.
6. Понятие перестановки.
7. Теорема о числе перестановок n -элементного множества.
8. Понятие перестановки с повторениями.
9. Теорема о числе перестановок с повторениями.
10. Понятие последовательности перестановок в лексикографическом порядке.
11. Понятие последовательности перестановок в порядке минимального изменения. Рекурсивное определение такой последовательности.
12. Понятие сочетания.
13. Теорема о числе сочетаний из n элементов по k.
14. Свойства сочетаний.
15. Понятие сочетания с повторениями.
16. Теорема о числе сочетания с повторениями.
17. Понятие последовательности сочетаний в возрастающем лексикографическом порядке.
18. Понятие размещения.
19. Теорема о числе размещений.
20. Понятие композиции.
21. Теорема о числе композиций n.
22. Теорема о числе композиций n из k частей при рi >0.
23. Теорема о числе композиций n из k частей при рi ³0. Связь таких композиция с сочетаниями из k элементов по n с повторениями.
24. Понятие разбиения.
25. Понятие последовательности разбиений в словарном порядке.
