Введение понятие комбинаторики

Содержание


ВВЕДЕНИЕ……………………………………………………………………3
1. Понятие комбинаторики…………………………………………......5
2. Понятие комбинаторной задачи и ее виды…………………………8
3. Жадный алгоритм……………………………………………………12
4. Деревянный алгоритм……………………………………………….16
5. Метод ветвей и границ…………………………………………..…..20
6. Алгоритм Дейкстры…………………………………………………28
Заключение……………………………………………………………...33
Список использованной литературы……………………...34

ВВЕДЕНИЕ
Актуальность темы обусловлена тем, что изучение комбинаторики необходимо в наше время, т.к. знания, приобретенные в ходе её изучения необходимы во многих науках (информатика, математика) для исследований, эффективность которых определяется успешным применением комбинаторики и ее приложений в разработке стратегии и тактики ведения игр, поиска алгоритма решения комбинаторных задач.
На практике часто приходится выбирать из некоторого множества объектов подмножества элементов, обладающих теми или иными свойствами, располагать элементы одного или нескольких множеств в определенном порядке и т.д. Поскольку в таких задачах речь идет о тех или иных комбинациях объектов, их называют "комбинаторные задачи".
Комбинаторика занимается различного рода соединениями, которые можно образовать из элементов некоторого конечного множества. Термин "комбинаторика" происходит от латинского combina – сочетать, соединять.
Комбинаторикой называется раздел математики, изучающей вопрос о том, сколько комбинаций определенного типа можно составить из данных предметов (элементов). Наиболее широкое применение комбинаторные задачи находят при решении задач теории вероятностей. Как при решении задач с использованием классического определения вероятности, так и в других ситуациях нам понадобятся некоторые формулы комбинаторики.
С задачами, в которых приходится выбирать те или иные предметы, располагать их в определенном порядке и отыскивать среди разных расположений наилучшие, люди столкнулись еще в доисторическую эпоху, выбирая наилучшие расположения охотников во время охоты, воинов во время битвы, инструментов во время работы. Определенным образом располагались украшения на одежде, узоры на керамике, перья в оперении стрелы. По мере усложнения производственных и общественных отношений все шире приходилось пользоваться общими понятиями о порядке, иерархии, группировании В том же направлении действовало развитие ремесел и торговли. Комбинаторные навыки оказались полезными и в часы досуга. Нельзя точно сказать, когда наряду с состязаниями в беге, метании диска, прыжках появились игры, требовавшие в первую очередь умения рассчитывать, составлять планы и опровергать планы противника.
Исследуемая нами проблема нашла отражение в работах таких авторов, как В.Б. Алексеев, Д.А. Андерсен, Е.В. Андреева, Н.Я. Виленкин, С. Гудман, С. Хидетниеми, С.С. Епонешников, Б.Н. Иванов, Д.Э. Кнут, Н.Н. Кузюрин, С.А. Фомин и др.
Актуальность данного вопроса обосновывает выбор темы нашей работы: «Основные задачи комбинаторики».
Цель исследования – на основе анализа рассмотреть основные задачи комбинаторики.
Объект исследования: комбинаторика.
Предмет исследования: основные задачи комбинаторики.
Задачи исследования: