Основные задачи комбинаторики

        Тема: Основные задачи комбинаторики

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ                                                                                        3

ГЛАВА 1. ЧТО ТАКОЕ КОМБИНАТОРИКА. ОСНОВНЫЕ ПРОБЛЕМЫ ИЗУЧЕНИЯ КОМБИНАТОРИКИ        

1.1. Понятие комбинаторики                                                                        5

1.2. Понятие комбинаторной задачи и ее виды        6

ГЛАВА 2. АЛГОРИТМ РЕШЕНИЯ КОМБИНАТОРНОЙ ЗАДАЧИ                11

2.1. Жадный алгоритм        11

2.2. Деревянный алгоритм        14

2.3. Метод ветвей и границ        18

2.4. Алгоритм Дейкстры        25

ЗАКЛЮЧЕНИЕ                                                                                        29

БИБЛИОГРАФИЧЕСКИЙ СПИСОК ИСТОЧНИКОВ И ЛИТЕРАТУРЫ      30

ВВЕДЕНИЕ

Актуальность темы обусловлена тем, что изучение комбинаторики необходимо в наше время, т.к. знания, приобретенные в ходе её изучения необходимы во многих науках (информатика, математика) для исследований, эффективность которых определяется успешным применением комбинаторики и ее приложений в разработке стратегии и тактики ведения игр, поиска алгоритма решения комбинаторных задач.

На практике часто приходится выбирать из некоторого множества объектов подмножества элементов, обладающих теми или иными свойствами, располагать элементы одного или нескольких множеств в определенном порядке и т.д. Поскольку в таких задачах речь идет о тех или иных комбинациях объектов, их называют "комбинаторные задачи".

Комбинаторика занимается различного рода соединениями, которые можно образовать из элементов некоторого конечного множества. Термин "комбинаторика" происходит от латинского combina – сочетать, соединять.

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

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

   Исследуемая нами проблема нашла отражение в работах таких авторов, как В.Б. Алексеев, Д.А. Андерсен, Е.В. Андреева, Н.Я. Виленкин, С. Гудман, С. Хидетниеми, С.С. Епонешников, Б.Н. Иванов, Д.Э. Кнут, Н.Н. Кузюрин, С.А. Фомин и др.

Актуальность данного вопроса обосновывает выбор темы нашей работы: «Основные задачи комбинаторики».

Цель исследования – на основе анализа рассмотреть основные задачи комбинаторики.

Объект исследования: комбинаторика.

Предмет исследования: основные задачи комбинаторики.

Задачи исследования: