размещение
Соединение, которое можно образовать из n элементов, собирая в каждое соединение по k элементов, при этом соединения могут отличаться друг от друга как самими элементами, так и порядком их расположения. Число всех возможных размещений равно n(n-1)(n-2)...(n-k+1)
перестановка
Cоединение из n элементов, содержащее все n элементов, отличающееся от других соединений только порядком расположения элементов. Число всех возможных перестановок равно n!
сочетание
Соединение из n элементов по k, отличающееся от других только самими элементами (различие порядка их расположения во внимание не принимается). Число всех возможных сочетаний равно числу размещений, разделенному на число перестановок
класс NP
NP-полные задачи
Дискретные задачи оптимизации (задачи выбора) со свойствами: 1) неизвестны полиномиальные алгоритмы точного решения; 2) любые задачи внутри этого класса могут быть сведены одна к другой за полиномиальное время
NP-трудные задачи
Задачи, для которых не доказана принадлежность к классу NP и алгоритмы точного решения полиномиальной сложности неизвестны
транспортная сеть
Взвешенный орграф без петель с единственными входной и выходной вершинами
поток
Количество субстанции (продукта), перемещаемого по тому или иному участку транспортной сети в единицу времени
поток транспортной сети
Сумма потоков по всем выходным дугам сети
разрез
Множество дуг минимальной мощности, удаление которых превращает транспортную сеть в несвязный граф при условии, что исток и сток оказываются в разных частях несвязного графа
минимальный разрез
Разрез с наименьшей пропускной способностью
теорема Форда-Фалкерсона
:В транспортной сети величина максимального потока равна пропускной способности минимального разреза
раскраска графа
Присвоение номеров (целых чисел) вершинам графа, раскраска называется правильной, если смежные вершины имеют разные номера
задача коммивояжера
Задано: множество городов и матрица расстояний между ними. Найти маршрут однократного посещения всех городов без пересечений в вершинах (гамильтонов цикл) минимальной длины
задача о ранце
задача о рюкзаке
Задано: ранец объема Vmax и множество предметов с известными объемами и ценностью. Найти: упаковку ранца с максимизацией ценности его содержимого при соблюдении ограничения на вместимость ранца
задача о выполнимости
задача k-выполнимости
boolean satisfiability problem
SAT
Задано: булева формула, состоящая из литералов, скобок и операций (И), (ИЛИ) и (HE). Найти: значения литералов, пр и которых формула является истинной
расписание
Распределение заданного множества работ во времени и между обслуживающими приборами.
теория расписаний
Наука, занимающаяся исследованиями детерминированных обслуживающих систем на предмет оптимизации расписаний их функционирования.
DAGSP
DAG Scheduling Problem
Задача синтеза расписаний с работами, взаимосвязанными отношениями предшествования.