Основы комбинаторного анализа.

↑

▷ Содержание

Стр 1 из 5Следующая ⇒

Основы комбинаторного анализа.

Основные цели и задачи.

Комбинаторика (комбинаторный анализ (КА)) – раздел дискретной математики, посвященный решению задач выбора и расположения элементов некоторого множества в соответствии с заданными правилами.

Каждое такое правило определяет способ построения некоторых конструкций из элементов рассматриваемого множества. Такая конструкция называется комбинаторной конфигурацией.

Целью КА и является изучение комбинаторных конфигураций.

К основным задачам КА относят:

а) задачи на доказательство существования комбинаторных конфигураций;

б) задачи поиска алгоритмов построения комбинаторных конфигураций и оптимизации алгоритмов;

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

Основное правило комбинаторики (правило умножения).

Пусть необходимо решить задачу: Из Киева в Чернигов можно добраться поездом, автобусом, самолетом, а из Чернигова в Новгород - Северский – пароходом и автобусом. Сколько есть способов попасть из Киева в Новгород - Северский?                       Очевидно, что число всех возможных способов 8.

          пароход

            автобус

                       самолет                        пароход

                        поезд                             автобус

    Киев                               Чернигов                  Новгород-Северский

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

Пусть требуется выполнить одно за другим К действий. Если первое действие можно выполнить n1 способом, второе – n2 способами, …, а К-ое действие nк способами, то все К действия можно выполнить n1*n2*…*nк способами.

Познавательные статьи:



Алгоритмические операторы Matlab

Конструирование и порядок расчёта дорожной одежды

Исследования учёных: почему помогают молитвы?

Почему терпят неудачу многие предприниматели?