Министерство образования Республики Беларусь

Учреждение образования

«Гомельский государственный университет им.  Ф. Скорины»

Математический факультет

Кафедра МПУ

 

Реферат

Комбинаторные задачи

Исполнитель:

Студентка группы М-42 Макарченко А.Ю.

Научный руководитель: Долинский М.С.

Гомель 2005

Содержание

 

Введение

Генерация k-элементных подмножеств

Генерация всех подмножеств данного множества

Генерация всех перестановок n-элементного множества

Разбиения множества

Заключение

Литература

Введение

 

Задачи дискретной математики, к которым относится большинство олимпиадных задач по информатике, часто сводятся к перебору различных комбинаторных конфигураций объектов и выбору среди них наилучшего, с точки зрения условия той или иной задачи. Поэтому знание алгоритмов генерации наиболее распространенных комбинаторных конфигураций является необходимым условием успешного решения олимпиадных задач в целом. Важно также знать количество различных вариантов для каждого типа комбинаторных конфигураций, так как это позволяет реально оценить вычислительную трудоемкость выбранного алгоритма решения той или иной задачи на перебор вариантов и, соответственно, его приемлемость для решения рассматриваемой задачи, с учетом ее размерности. Кроме того, при решении задач полезным оказывается умение для каждой из комбинаторных конфигураций выполнять следующие операции: по имеющейся конфигурации получать следующую за ней в лексикографическом порядке; определять номер данной конфигурации в лексикографической нумерации всех конфигураций; и, наоборот, по порядковому номеру выписывать соответствующую ему конфигурацию.

Генерация k-элементных подмножеств

В комбинаторике такие подмножества называют сочетаниями из n элементов по k элементов и обозначают Cnk . Их количество выражается следующей формулой:

Однако при программировании гораздо удобнее использовать следующие рекуррентные соотношения:

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

При фиксированном значении n максимального значения число сочетаний достигает при k = n/2 (вернее, для четного n максимум один и он указан, а для нечетного — максимум достигается на двух соседних значениях k: [n/2] и

[n/2]+1). Поэтому особенно полезной оказывается следующая оценка для четных n [4] (очевидно, что при нечетных n отличия будут минимальными), основанная на формуле Стирлинга:

Если допустить, что за время, отведенное для решения задачи, мы можем перебрать около 106 вариантов, то из формулы (3) следует, что генерацию всех сочетаний из n элементов для любого фиксированного k можно проводить для n £ 24.

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