Лекция 20. Алгоритмы генерирования перестановок, множества всех подмножеств, к-элементных подмножеств множества, разбиения множеств

Лекция 20. Алгоритмы генерирования перестановок, множества всех подмножеств, к-элементных подмножеств множества, разбиения множеств.

Комбинаторные алгоритмы с их акцентом на разработку, анализ и реализацию практических алгоритмов являются продуктом века вычислительных машин.

Предмет теории комбинаторных алгоритмов - вычисления на дискретных математических структурах. Это новое направление исследований. Лишь в последние несколько лет из наборов искусных приемов и разрозненных алгоритмов сформировалась система знаний о разработке, реализации и анализе алгоритмов.

Комбинаторные вычисления развиваются в следующем направлении:

· интенсивно изобретаются новые алгоритмы;

· происходит быстрый прогресс (главным образом в математическом плане) в понимании алгоритмов, их разработки и анализа;

· происходит переход от изучения отдельных алгоритмов к исследованию свойств, присущих классам алгоритмов.

В отличие от некоторых других разделов математики, комбинаторные вычисления не имеют "ядра", то есть некоторого количества "фундаментальных теорем", составляющих суть предмета, из которых выводится большинство результатов. Сначала может показаться, что в целом эта область состоит из наборов специальных методов и хитрых приемов. Однако после того как было исследовано достаточно много комбинаторных алгоритмов стали вырисовываться некоторые общие принципы. Именно эти принципы делают комбинаторные вычисления связной областью знаний и позволяют изложить ее в систематизированном виде