Основные комбинаторные задачи
Предмет комбинаторики (теории вероятностей), как отрасли программирования. Краткая историческая справка о ее зарождении и развитии. Комбинаторные задачи, варианты и способы их решения. Основные формулы комбинаторики, правила произведений и суммы.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | реферат |
Язык | русский |
Дата добавления | 15.06.2014 |
Размер файла | 22,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Содержание
Введение
1. Предмет комбинаторики
2. Краткая историческая справка
3. Основные комбинаторные задачи
4. Основные формулы комбинаторики
5. Правило произведений
6. Правило суммы
Заключение
Список использованной литературы
Введение
Задачи дискретной математики, к которым относится большинство олимпиадных задач по информатике, часто сводятся к перебору различных комбинаторных конфигураций объектов и выбору среди них наилучшего, с точки зрения условия той или иной задачи. Поэтому знание алгоритмов генерации наиболее распространенных комбинаторных конфигураций является необходимым условием успешного решения олимпиадных задач в целом. Важно также знать количество различных вариантов для каждого типа комбинаторных конфигураций, так как это позволяет реально оценить вычислительную трудоемкость выбранного алгоритма решения той или иной задачи.
1. Предмет комбинаторики
Наблюдаемые нами события (явления) можно подразделить на следующие три вида: достоверные, невозможные и случайные.
Достоверным называют событие, которое обязательно произойдет, если будет осуществлена определенная совокупность условий S. Например, если в сосуде содержится вода при нормальном атмосферном давлении и температуре 20°, то событие «вода в сосуде находится в жидком состоянии» есть достоверное. В этом примере заданные атмосферное давление и температура воды составляют совокупность условий S.
Невозможным называют событие, которое заведомо не произойдет, если будет осуществлена совокупность условий S. Например, событие «вода в сосуде находится в твердом состоянии» заведомо не произойдет, если будет осуществлена совокупность условий предыдущего примера.
Случайным называют событие, которое при осуществлении совокупности условий S может либо произойти, либо не произойти. Например, если брошена монета, то она может упасть так, что сверху будет либо герб, либо надпись. Поэтому событие «при бросании монеты выпал «герб» -- случайное. Каждое случайное событие, в частности выпадение «герба», есть следствие действия очень многих случайных причин (в нашем примере: сила, с которой брошена монета, форма монеты и многие другие). Невозможно учесть влияние на результат всех этих причин, поскольку число их очень велико и законы их действия неизвестны. Поэтому теория вероятностей не ставит перед собой задачу предсказать, произойдет единичное событие или нет, -- она просто не в силах это сделать.
По-иному обстоит дело, если рассматриваются случайные события, которые могут многократно наблюдаться при осуществлении одних и тех же условий S, т. е. если речь идет о массовых однородных случайных событиях. Оказывается, что достаточно большое число однородных случайных событий независимо от их конкретной природы подчиняется определенным закономерностям, а именно вероятностным закономерностям. Установлением этих закономерностей и занимается теория вероятностей.
Итак, предметом теории вероятностей является изучение вероятностных закономерностей массовых однородных случайных событий.
Знание закономерностей, которым подчиняются массовые случайные события, позволяет предвидеть, как эти события будут протекать. Например, хотя, как было уже сказано, нельзя наперед определить результат одного бросания монеты, но можно предсказать, причем с небольшой погрешностью, число появлений «герба», если монета будет брошена достаточно большое число раз. При этом предполагается, конечно, что монету бросают в одних и тех же условиях. Методы теории вероятностей широко применяются в различных отраслях естествознания и техники: в теории надежности, теории массового обслуживания, в теоретической физике, геодезии, астрономии, теории стрельбы, теории ошибок наблюдений, теории автоматического управления, общей теории связи и во многих других теоретических и прикладных науках. Теория вероятностей служит также для обоснования математической и прикладной статистики, которая в свою очередь используется при планировании и организации производства, при анализе технологических процессов, предупредительном и приемочном контроле качества продукции и для многих других целей.
В последние годы методы теории вероятностей все шире и шире проникают в различные области науки и техники, способствуя их прогрессу.
2. Краткая историческая справка
Первые работы, в которых зарождались основные понятия теории вероятностей, представляли собой попытки создания теории азартных игр (Кардано, Гюйгенс, Паскаль, Ферма и другие в XVI--XVII вв.).
Следующий этап развития теории вероятностей связан с именем Якоба Бернулли (1654--1705). Доказанная им теорема, получившая впоследствии название «Закона больших чисел», была первым теоретическим обоснованием накопленных ранее фактов.
Дальнейшими успехами теория вероятностей обязана Муавру, Лапласу, Гауссу, Пуассону и др.
Новый, наиболее плодотворный период связан с именами П. Л. Чебышева (1821--1894) и его учеников А.А.Маркова(1856--1922) и А. М.Ляпунова (1857--1918). В этот период теория вероятностей становится стройной математической наукой. Ее последующее развитие обязано в первую очередь русским и советским математикам (С. Н. Бернштейн, В. И. Романовский, А. Н. Колмогоров, А. Я. Хинчин, Б. В. Гнеденко, Н. В. Смирнов и др.). В настоящее время ведущая роль в создании новых ветвей теории вероятностей также принадлежит советским математикам.
3. Основные комбинаторные задачи
Основными и типичными операциями и связанными с ними задачами комбинаторики являются следующие:
1) образование упорядоченных множеств, состоящее в установлении определенного порядка следования элементов множества друг за другом, - составление перестановок;
2) образование подмножеств, состоящее в выделении из данного множества некоторой части его элементов, - составление сочетаний;
3) образование упорядоченных подмножеств - составление размещений.
ТИПЫ КОМБИНАТОРНЫХ ЗАДАЧ.
1. Магический квадрат - квадратная таблица (n * n) целых чисел от 1 до n¤ такая, что суммы чисел вдоль любого столбца, любой строки и двух диагоналей таблицы равны одному и тому же числу s=n(n¤+1)/2. Число n называют порядом магического квадрата.
Доказано, что магический квадрат можно построить для любого n Є 3. Уже в средние века был известен алгоритм построения магических квадратов нечетного порядка. Существуют магические квадраты, удоволетворяющие ряду дополнительных условий, например магический квадрат с n=8 , который можно разделить на четыре меньших магических квадрата 4x4. В Индии и некоторых других странах магические квадраты употреблялись как талисманы. Однако общей теории магических квадратов не существует. Неизвестно даже общее число магических квадратов порядка n.
2. Латинский квадрат - квадратная матрица порядка n, каждая строка и каждый столбец которой являются перестановками элементов конечного множества S, состоящего из n элементов.
3. Задача размещения - одна из классических комбинаторных задач, в которой требуется определить число способов размещения m различных предметов в n различных ячейках с заданным числом r пустых ячеек. Это число равно
r n-r mC (r)=C дельта O , r=0,1,2,...,n,nm n
где
k m k j j m дельта O =сигма (-1) C (k-j) j=0 k
Задача коммивояжера, задача о бродячем торговце - комбинаторная задача теории графов. В простейшем случае формулируется следующим образом: даны n городов и известно расстояние между каждыми двумя городами; коммивояжер, выходящий из какого-нибудь города, должен посетить n-1 других городов и вернуться в исходный. В каком порядке должен он посещать города (по одному разу каждый) чтобы общее пройденное расстояние было минимальным?
Методы решения задачи коммивояжера, по существу, сводятся к организации полного перебора вариантов.
МЕТОДЫ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ
1. Метод рекуррентных соотношений.
Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с n предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, которое называется рекуррентным. Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов решение задачи легко находится.
2. Метод включения и исключения.
Пусть N(A) - число элементов множества A. Тогда методом математической индукции можно доказать, что
N(A1 U A2 U ... An) = N(A1) + ... + N(An) - - {N(A1 П A2) + ... + N(An-1 П An)} + + {N(A1 П A2 П A3) + ... + N(An-2 П An-1 П An)} - ...... +(-1)^n-1*N(A1 П A2 П ... П An-1 П An).
Метод подсчета числа элементов объединения множеств по этой формуле, состоящий в поочередном сложении и вычитании, называется методом включения и исключения.
3. Метод траекторий.
Для многих комбинаторных задач можно указать такую геометрическую интерпретацию, которая сводит задачу к подсчету числа путей (траекторий), обладающих определенным свойством.
4. Основные формулы комбинаторики
Комбинаторика изучает количества комбинаций, подчиненных определенным условиям, которые можно составить из элементов, безразлично какой природы, заданного конечного множества. При непосредственном вычислении вероятностей часто используют формулы комбинаторики. Приведем наиболее употребительные из них.
Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок
Pn = n!,
где n! = 1 * 2 * 3 ... n.
Заметим, что удобно рассматривать 0!, полагая, по определению, 0! = 1.
Размещениями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком. Число всех возможных размещений
Amn = n (n - 1)(n - 2) ... (n - m + 1).
Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом. Число сочетаний
С mn = n! / (m! (n - m)!).
примеры перестановок, размещений, сочетаний
Подчеркнем, что числа размещений, перестановок и сочетаний связаны равенством
Amn = PmC mn.
Замечание. Выше предполагалось, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам. Например, если среди n элементов есть n1 элементов одного вида, n2 элементов другого вида и т.д., то число перестановок с повторениями
Pn (n1, n2, ...) = n! / (n1! n2! ... ),
где n1 + n2 + ... = n.
5. Правило произведения
Если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А, В) в указанном порядке может быть выбрана mn способами.
Произведение событий. Произведением двух событий А и В называют событие АВ, состоящее в совместном появлении (совмещении) этих событий. Например, если А -- деталь годная, В -- деталь окрашенная, то АВ -- деталь годна и окрашена.
Произведением нескольких событий называют событие, состоящее в совместном появлении всех этих событий. Например, если А, В, С -- появление «герба» соответственно в первом, втором и третьем бросаниях монеты, то АВС -- выпадение «герба» во всех трех испытаниях.
Условная вероятность. Во введении случайное событие определено как событие, которое при осуществлении совокупности условий S может произойти или не произойти. Если при вычислении вероятности события никаких других ограничений, кроме условий S, не налагается, то такую вероятность называют безусловной; если же налагаются и другие дополнительные условия, то вероятность события называют условной. Например, часто вычисляют вероятность события В при дополнительном условии, что произошло событие А. Заметим, что и безусловная вероятность, строго говоря, является условной, поскольку предполагается осуществление условий S.
Условной вероятностью РA (В) называют вероятность события В, вычисленную в предположении, что событие А уже наступило.
Исходя из классического определения вероятности, формулу РA (В) = Р (АВ) / Р (А) (Р (А) > 0 можно доказать. Это обстоятельство и служит основанием для следующего общего (применимого не только для классической вероятности) определения.
Условная вероятность события В при условии, что событие А уже наступило, по определению, равна
РA (В) = Р (АВ) / Р (А) (Р(A)>0).
Рассмотрим два события: А и В; пусть вероятности Р (А) и РA (В) известны. Как найти вероятность совмещения этих событий, т. е. вероятность того, что появится и событие А и событие В? Ответ на этот вопрос дает теорема умножения.
6. Правило суммы
Если некоторый объект А может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А, либо В можно m + n способами.
Суммой А + В двух событий А и В называют событие, состоящее в появлении события А, или события В, или обоих этих событий. Например, если из орудия произведены два выстрела и А -- попадание при первом выстреле, В -- попадание при втором выстреле, то А + В -- попадание при первом выстреле, или при втором, или в обоих выстрелах.
В частности, если два события А и B -- несовместные, то А + В -- событие, состоящее в появлении одного из этих событий, безразлично какого.
Суммой нескольких событий называют событие, которое состоит в появлении хотя бы одного из этих событий. Например, событие А + В + С состоит в появлении одного из следующих событий: А, В, С, А и В, А и С, В и С, А и В и С.
Пусть события A и В -- несовместные, причем вероятности этих событий известны. Как найти вероятность того, что наступит либо событие A, либо событие В? Ответ на этот вопрос дает теорема сложения.
Теорема. Вероятность появления одного из двух несовместных событий, безразлично какого, равна сумме вероятностей этих событий:
Р (А + В) = Р (А) + Р (В).
Доказательство:
Введем обозначения: n -- общее число возможных элементарных исходов испытания; m1 -- число исходов, благоприятствующих событию A; m2-- число исходов, благоприятствующих событию В.
Число элементарных исходов, благоприятствующих наступлению либо события А, либо события В, равно m1 + m2. Следовательно,
Р (A + В) = (m1 + m2) / n = m1 / n + m2 / n.
Приняв во внимание, что m1 / n = Р (А) и m2 / n = Р (В), окончательно получим
Р (А + В) = Р (А) + Р (В).
Следствие. Вероятность появления одного из нескольких попарно несовместных событий, безразлично какого, равна сумме вероятностей этих событий:
Р (A1 + A2 + ... + An) = Р (A1) + Р (A2) + ... + Р (An).
Доказательство:
Рассмотрим три события: А, В и С. Так как рассматриваемые события попарно несовместны, то появление одного из трех событий, А, В и С, равносильно наступлению одного из двух событий, A + В и С, поэтому в силу указанной теоремы
Р ( А + В + С) = Р [(А + В) + С] = Р (А + В) + Р (С) = Р (А) + Р (В) + Р (С)
Заключение
Перечисленные подзадачи в программировании обычно рассматривают для следующих комбинаторных конфигураций: перестановки элементов множества, подмножества множества, сочетания из n элементов множества по k элементов (k-элементные подмножества множества, состоящего из nk элементов), размещения (упорядоченные подмножества множества, то есть отличающиеся не только составом элементов, но и порядком элементов в них), разбиения множества (множество разбивается на подмножества произвольного размера так, что каждый элемент исходного множества содержится ровно в одном подмножестве), разбиения натуральных чисел на слагаемые, правильные скобочные последовательности (различные правильные взаимные расположения n пар открывающихся и закрывающихся скобок).
Большинство указанных конфигураций были подробно рассмотрены в [1-3]. Однако при генерации различных конфигураций использовались в основном нерекурсивные алгоритмы. Опытные же участники олимпиад в подобных случаях при программировании используют в основном именно рекурсию, с помощью которой решение рассматриваемых задач зачастую можно записать более кратко и прозрачно. Поэтому для полноты изложения данной темы приведем ряд рекурсивных комбинаторных алгоритмов и рассмотрим особенности применения рекурсии в комбинаторике.
комбинаторика вероятность исторический программирование
Список использованной литературы
Окулов С.М. Перестановки. “Информатика”, №7, 2000.
Окулов С.M. Комбинаторные задачи. “Информатика”, №10, 13, 2000.
Усов Б.Б. Комбинаторные задачи. “Информатика”, №39, 2000.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000.
Брудно A.Л., Каплан Л.И. Московские олимпиады по программированию. М.: Наука, 1990.
Кнут Д. Конкретная математика. Основание информатики. М.: “Мир”, 1998.
Липский В. Комбинаторика для программистов. М.: “Мир”, 1988.
Андреева Е.В. Еще раз о задачах на полный перебор вариантов. “Информатика”, №45, 2000.
Размещено на Allbest.ru
...Подобные документы
Предмет, постановка и особенности задач дискретного программирования. Задачи с неделимостями и с разрывными целевыми функциями. Экстремальные комбинаторные задачи. Примеры решений задач дискретного программирования методом ветвей и границ, методом Гомори.
курсовая работа [211,3 K], добавлен 22.05.2013Исследование методов решения задачи о ходе коня. Описание алгоритмов для итеративной и рекурсивной программ. Генерация перестановок элементов по индексам. Построение эйлерова цикла на графе. Поиск кратчайшего пути на графе. Программная реализация задачи.
курсовая работа [411,6 K], добавлен 25.04.2013Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.
курсовая работа [280,8 K], добавлен 17.11.2011Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Решение задач по информатике, перебор различных комбинаторных конфигураций объектов и выбор наилучшего, с точки зрения условия задачи. Генерация k-элементных подмножеств, всех подмножеств данного множества, всех перестановок n-элементного множества.
реферат [44,0 K], добавлен 03.01.2010Краткая историческая справка и описание современной версии системы. Основные возможности современной версии MathCad, ее интерфейс. Ввод и редактирование выражений. Средства повышения эффективности вычислений и их оптимизация. Обзор программных операторов.
курсовая работа [1,1 M], добавлен 13.05.2016Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
курсовая работа [581,5 K], добавлен 13.10.2008Элементарные подзадачи, на решение которых опираются решения задач вычислительной геометрии. Основные формулы и алгоритмы. Олимпиадные задачи, связанные с геометрическими понятиями. Подробные численные решения геометрических разных задач с пояснениями.
реферат [42,4 K], добавлен 06.03.2010Задачи, решаемые методом динамического программирования. Основные этапы нахождения деревянного алгоритма решения задачи. Выполнение алгоритма Прима. Построение Эйлерового цикла. Решение задач средствами Excel. Алгоритм основной программы - Derevo.
курсовая работа [586,3 K], добавлен 04.04.2015Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса.
курсовая работа [232,4 K], добавлен 01.06.2009Описание предметной области решаемой задачи. Входные документы, необходимые для решения задачи, ее функции. Разработка информационного обеспечения задачи и реквизиты входной информации. Технология и алгоритмов решения задачи и их машинная реализация.
контрольная работа [15,1 K], добавлен 21.10.2010Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания.
контрольная работа [2,0 M], добавлен 02.05.2012Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.
контрольная работа [196,1 K], добавлен 15.01.2009Описание симплекс метода решения задачи линейного программирования. Решение задачи методом Литла на нахождение кратчайшего пути в графе, заданном графически в виде чертежа. Из чертежа записываем матрицу расстояний и поэтапно находим кратчайший путь.
задача [390,4 K], добавлен 10.11.2010Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
курсовая работа [607,2 K], добавлен 13.03.2015Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015Характеристика основных методов линейного программирования с n- переменными, в частности, графического и симплекс-метода. Способы решения задачи по определению оптимальной структуры товарооборота, обеспечивающей торговому предприятию максимум прибыли.
курсовая работа [678,7 K], добавлен 03.04.2011Классификация прикладных программ. Назначение и основные функциональные возможности текстовых редакторов, табличных процессов, систем управления базами данных, графических редакторов. Комбинаторика, как отрасль математики. Основные ее соотношения.
реферат [175,6 K], добавлен 01.03.2009Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010