logo
флеров

Введение

Сейчас трудно было бы, пожалуй, назвать раздел теоретической информатики, в котором в течение последнего десятилетия были бы достигнуты большие успехи, нежели в конструировании и анализе комбинаторных алгоритмов - важнейшей проблемы комбинаторики. С одной стороны, было обнаружено много новых, более эффективных методов решения комбинаторных задач с помощью ЭВМ, с другой стороны - получены теоретические результаты, свидетельствующие все более явно о том, что для широкого класса проблем не существует достаточно эффективных алгоритмов. Эффективные комбинаторные алгоритмы находят применение во многих областях нечисленной обработки информации, особенно в дискретной оптимизации и в исследовании операций, в вычислительной математике.

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

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

Основная проблема комбинаторики - подсчет числа элементов в конечном множестве. В этой широкой проблеме можно условно выделить следующие основные направления исследований: