Тесты СинергияАртём Хелп
Артём Help онлайнПолучить расчёт
Бесплатно оценим сроки и стоимостьОтправить задание в Telegram
Теория алгоритмов.ти ЭБС

Теория алгоритмов.ти ЭБС

Просмотрите все вопросы и варианты бесплатно. Правильные ответы скрыты и открываются только после получения доступа.

133 вопроса Вариант 1 Доступ 7 дней
Содержание теста

Вопросы и варианты

Без отметок и подсказок к правильным ответам

Вопрос 1

Вектор инструментальных переменных х называется допустимым, если он:

  1. Удовлетворяет ограничениям задачи
  2. Не удовлетворяет ограничениям задачи
  3. Частично удовлетворяет ограничениям задачи
  4. Частично не удовлетворяет ограничениям задачи
Вопрос 2

Если вектор инструментальных переменных x* принадлежит допустимому множеству и на нём достигается значение целевой функции, большее или равное значениям функции в некоторой малой окрестности этого вектора, то он является:

  1. Точкой глобального максимума
  2. Точкой локального максимума
  3. Точкой глобального минимума
  4. Точкой локального минимума
Вопрос 3

Выберите определения: «Задача математического программирования состоит:…»

  1. В нахождении значений переменных, максимизирующих заданную функцию и удовлетворяющих системе ограничений
  2. В нахождении значений переменных для заданной функции и удовлетворяющих системе ограничений
  3. В выборе вектора инструментальных переменных из множества возможностей, максимизирующего значение целевой функции
  4. В формулировке последовательного алгоритма действий, позволяющего найти оптимальное решение
Вопрос 4

Какие понятия являются основными при формальной постановке задачи?

  1. «инструментальные» переменные
  2. Допустимое множество
  3. Целевая функция
  4. Константы
Вопрос 5

Алгоритм – совокупность правил….

  1. определяющих данный вычислительный процесс (точное предписание, определяющее вычислительный процесс, ведущий от варьируемых исходных данных)
  2. в математике, физике и геометрии
  3. частично удовлетворяющих ограничениям задачи
  4. частично не удовлетворяющих ограничениям задачи
Вопрос 6

Что принято понимать под целевой функцией? Выберите несколько правильных ответов.

  1. Краткое математическое изложение цели данной задачи
  2. Она представляет собой действительную непрерывно дифференцируемую функцию вектора инструментальных переменных F = F(x) = F(x, x, …, xn).
  3. Функция, экстремальное значение которой ищется вне пределов обозначенного допустимого множества
  4. Функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными и допустимым множеством в задаче оптимизации
Вопрос 7

Сколько основных видов общей задачи математического программирования выделяют?

  1. 2
  2. 3
  3. 4
  4. 5
Вопрос 8

Назовите основные виды общей задачи математического программирования

  1. Классическая задача математического программирования
  2. Задача нелинейного программирования
  3. Задача линейного программирования
  4. Задача динамического программирования
Вопрос 9

Что представляют собой все ограничения в классической задаче математического программирования?

  1. Равенства
  2. Неравенства
  3. Условия неотрицательности
  4. Условия константности
Вопрос 10

В нелинейном программировании система ограничений состоит из:

  1. Условий неотрицательности
  2. Ограничений в виде неравенств
  3. Ограничений в виде равенств
  4. Условий константности
Вопрос 11

В линейном программировании система ограничений состоит из:

  1. Ограничений в виде неравенств
  2. Условий неотрицательности
  3. Условий неположительности
  4. Ограничений в виде равенств
Вопрос 12

В каком из видов общей задачи математического программирования целевая функция является линейной формой?

  1. В задаче линейного программирования
  2. В задаче нелинейного программирования
  3. В классической задаче математического программирования
  4. В задаче динамического программирования
Вопрос 13

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

  1. Стационарной
  2. Допустимой
  3. Оптимальной
  4. Точкой глобального минимума
Вопрос 14

Что характерно для задач выпуклого программирования?

  1. Любой локальный минимум является глобальным
  2. Все действия сводятся к нахождению единственного минимума
  3. Любой глобальный минимум является локальным
  4. Поиск всех локальных минимумов
Вопрос 15

Для решения задач выпуклого программирования разработаны многочисленные численные методы, приспособленные для решения на ЭВМ, в основном связанные с:

  1. Понятием градиента целевой функции
  2. Основной идеей того, что функция наиболее быстро убывает, если двигаться в направлении, противоположном градиенту
  3. Основной идеей того, что функция наиболее быстро возрастает, если двигаться в направлении, противоположном градиенту
  4. Основной идеей того, что функция стабильна, если двигаться в направлении, противоположном градиенту
Вопрос 16

Какие из перечисленных методов используются для решения задач выпуклого программирования?

  1. Метод градиентного спуска
  2. Метод сопряженных градиентов
  3. Метод штрафных функций
  4. Метод случайного поиска
  5. Метод гессиан
Вопрос 17

Как называют точку х* = argmin { ϕ(x): x∈X}? Выберите несколько вариантов ответов.

  1. Решением
  2. Оптимальной точкой
  3. Точкой глобального минимума
  4. Допустимой точкой
Вопрос 18

Из какой теоремы следует, что во всех точках локального минимума выпуклая функция имеет одинаковые значения?

  1. Если внутренняя точка Х* множества Д является точкой локального минимума в задаче выпуклого программирования, то в этой точке функция F(X) достигает глобального минимума.
  2. Функция F(X), строго выпуклая функция на выпуклом множестве, имеет в этом множестве не более одной точки глобального минимума.
  3. Пусть функция F(X) выпукла на выпуклом множестве D⊂Rn и дифференцируема в точке Х*∈D. Тогда для того чтобы эта точка была точкой минимума функции F(X), необходимо и достаточно, чтобы для любой точки Х∈D выполнялось неравенство (∇F(X*), (X-X*))≥0.
Вопрос 19

Какая теорема даёт условие существования решения задачи выпуклого программирования?

  1. Если внутренняя точка Х* множества Д является точкой локального минимума в задаче выпуклого программирования, то в этой точке функция F(X) достигает глобального минимума.
  2. Функция F(X), строго выпуклая функция на выпуклом множестве, имеет в этом множестве не более одной точки глобального минимума.
  3. Пусть функция F(X) выпукла на выпуклом множестве D ⊂Rn и дифференцируема в точке Х*∈D. Тогда для того чтобы эта точка была точкой минимума функции F(X), необходимо и достаточно, чтобы для любой точки Х∈D выполнялось неравенство (∇F(X*), (X-X*))≥0.
Вопрос 20

Какие задачи можно рассматривать как частный случай задач выпуклого программирования?

  1. Задачи линейного программирования
  2. Задачи нелинейного программирования
  3. Задачи динамического программирования
  4. Задачи параметрического программирования
Вопрос 21

Что из перечисленного характеризует метод множителей Лагранжа?

  1. Используется в качестве основного подхода к решению почти всех видов задач оптимизации
  2. Является одним из наиболее эффективных методов решения классических задач программирования
  3. С его помощью можно получить ценную информацию о том, в какой степени оптимальное значение целевой функции чувствительно к изменениям констант ограничений
  4. Решаемая этим методом задача «погружается» в более широкий класс задач, описываемых рядом параметров, и вслед за этим с помощью принципа оптимальности определяется основное рекуррентное соотношение
Вопрос 22

Характерные свойства алгоритма (укажите неверный ответ):

  1. Формальность
  2. Определенность
  3. Результативность
Вопрос 23

Как называется вектор-строка из m новых переменных y = (y1, y2, …, ym)?

  1. Вектором множителей Лагранжа
  2. Вектором функции Лагранжа
  3. Вектором переменной Лагранжа
  4. Вектором градиента функции
Вопрос 24

Основные свойства алгоритма:

  1. Дискретность
  2. Определенность
  3. Массовость
  4. Неопределённость
Вопрос 25

Как в соответствии с методом множителей Лагранжа задача f(x)→ min, x∈Rn, h1(x) = 0 преобразуется в задачу безусловной минимизации?

  1. L(x;λ) = f(x) = λh1(x) → min, x∈Rn
  2. L = L(x, y) =f(x) + y(b – g(x))
  3. L(x*,y*) = F(x*) + y*(b – g(x*)) = F(x*)
  4. L(x, y) = cx + y(b – Ax) = cx + yb – yAx
Вопрос 26

Дана задача: f(x) = x12 + x22, при ограничении h1(x) = 2x1 + x2 – 2 = 0. Найдите минимальное значение f(x0; λ0).

  1. 2
  2. 4/5
  3. 2/5
  4. 1/2
Вопрос 27

Как называются ограничения первого вида?

  1. Активными ограничениями
  2. Неактивными ограничениями
  3. Регулярными ограничениями
  4. Нерегулярными ограничениями
Вопрос 28

Частично-рекурсивные функции – это…

  1. функции, определяемые особым образом с достаточной математической строгостью
  2. функции, с условием активности ограничивающих функций в точке x*
  3. функции, условием неактивности ограничивающих функций в точке y*
Вопрос 29

Если вектор инструментальных переменных x* принадлежит допустимому множеству и целевая функция принимает на этом векторе значение не меньшее, чем в любой другой допустимой точке, то он является:

  1. Точкой глобального максимума
  2. Точкой локального максимума
  3. Точкой глобального минимума
  4. Точкой локального минимума
Вопрос 30

Глобальный максимум является строгим (сильным), если:

  1. Значение целевой функции при Х = Х* строго больше любого другого значения функции на допустимом множестве
  2. Значение целевой функции при Х = Х* строго меньше любого другого значения функции на допустимом множестве
  3. Значение целевой функции при Х = Х* больше или равно любому другому значению функции на допустимом множестве
  4. Значение целевой функции при Х = Х* строго меньше или равно любому другому значению функции на допустимом множестве
Вопрос 31

Какая теорема формулирует условия существования глобального максимума?

  1. Теорема Вейерштрасса
  2. Теорема двойственности
  3. Теорема о магистрали
  4. Теорема Куна-Таккера
Вопрос 32

Теорема. Класс функций, вычислимых на машинах Тьюринга, ….

  1. совпадает с классом частично-рекурсивных функций.
  2. не совпадает с классом частично-рекурсивных функций.
  3. совпадает со всеми классами функций.
Вопрос 33

Алгебра высказываний – это…

  1. Точное предписание, определяющее вычислительный процесс, ведущий от варьируемых исходных данных к конечному результату
  2. Простейшая из формальных логических теорий
  3. Логическая функция
  4. Элемент абстрактной машины
Вопрос 34

Массовость – это …

  1. Свойство алгоритма служить для решения класса задач
  2. Свойство алгоритма служить для решения одного типа задач
  3. Специальным образом определяемое устройство, работа которого обладает свойствами алгоритмического процесса
  4. свойство алгоритма, характеризующее однозначность преобразований
Вопрос 35

Дайте название теоремы, условия которой звучат следующим образом: «Пусть допустимое множество не пусто и является компактным и выпуклым, а непрерывная функция F(x) вогнута на Х. Тогда локальный максимум является глобальным, а множество точек, на котором достигается максимум, выпукло.

  1. Теорема достаточного условия глобального максимума
  2. Теорема Вейерштрасса
  3. Теорема двойственности
  4. Теорема Куна-Таккера
Вопрос 36

Определённость алгоритма – это …

  1. Свойство алгоритма, характеризующее однозначность преобразований
  2. Линия уравнений
  3. Градиент
  4. Установление, находятся ли конъюнкция посылок и заключение в отношении следования
Вопрос 37

Машина Тьюринга – это

  1. Специальным образом определяемое устройство, работа которого обладает свойствами алгоритмического процесса
  2. Специально определяемый вид формул алгебры
  3. Специальные преобразования функций в теории рекурсивных функций: оператор-подстановки, оператор примитивной рекурсии, оператор минимизации
  4. Функциональная диаграмма
Вопрос 38

Что характеризует симплексный алгоритм?

  1. Выбор начальной точки осуществляется с учётом ограничений
  2. Выбор начальной точки осуществляется без учёта ограничений
  3. Начальная точка задана изначально условиями
  4. В выборе начальной точки нет необходимости, так как в процессе исследования используется комплексный подход
Вопрос 39

Какой алгоритм позволяет найти решение задач линейного программирования с помощью итеративной процедуры?

  1. Симплексный алгоритм
  2. Алгоритм Флойда
  3. Дробный алгоритм
  4. Первый алгоритм Гомори
Вопрос 40

Что характеризует симплексный алгоритм?

  1. Выбор начальной точки осуществляется с учётом ограничений
  2. Выбор начальной точки осуществляется без учёта ограничений
  3. Начальная точка задана изначально условиями
  4. В выборе начальной точки нет необходимости, так как в процессе исследования используется комплексный подход
Вопрос 41

Если перемещение в любую соседнюю вершину уменьшает целевую функцию, то:

  1. Найденное решение единственное
  2. Все вершины являются решениями
  3. Все точки между вершинами являются решениями
  4. Все вершины являются решениями, а также все точки между этими вершинами
Вопрос 42

Если смещение в некоторую другую вершину не уменьшает целевую функцию, то:

  1. Найденное решение единственное
  2. Все вершины являются решениями
  3. Все точки между вершинами являются решениями
  4. Все вершины являются решениями, а также все точки между этими вершинами
Вопрос 43

Какие варианты реализации симплекс-метода возможны (принять во внимание тот факт, что число вершин допустимого множества конечно)?

  1. Приведёт к решению задачи
  2. Через конечное число шагов покажет, что целевая функция не ограничена
  3. Потребует введения дополнительных условий через определённое количество шагов
Вопрос 44

Преобразование, с помощью которого определяются новые базисные переменные, а целевая функция становится при этом линейной функцией небазисных переменных, называется:

  1. Ведущим преобразованием
  2. Базисным преобразованием
  3. Небазисным преобразованием
  4. Линейным преобразованием
Вопрос 45

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

  1. Симплексной таблицей
  2. Симплексной матрицей
  3. Симплексной системой уравнений
  4. Матрицей линейного преобразования
Вопрос 46

Симплекс-таблица образуется из (выберите один ответ):

  1. Матрицы коэффициентов системы уравнений линейного программирования, приведенной к «канонической форме»
  2. Базисных переменных
  3. Свободных членов в ограничениях
  4. Небазисных переменных
Вопрос 47

Последовательное преобразование симплекс-таблицы по симплексному алгоритму позволяет:

  1. За ограниченное количество шагов (итераций) получить искомый результат — план, обеспечивающий экстремальное значение целевой функции.
  2. За неограниченное количество шагов (итераций) получить искомый результат — план, обеспечивающий экстремальное значение целевой функции.
  3. Получить искомый результат, обеспечивающий максимальное значение целевой функции.
  4. Получить искомый результат, обеспечивающий минимальное значение целевой функции.
Вопрос 48

Задача линейного программирования является невырожденной тогда, когда:

  1. Каждый опорный план содержит ровно m положительных компонент, где m – число ограничений в задаче.
  2. В опорном плане число положительных компонент оказывается меньше числа ограничений: некоторые базисные переменные, соответствующие данному опорному плану, принимают нулевые значения.
  3. Каждый опорный план содержит m отрицательных компонент, где m – число ограничений в задаче.
  4. В опорном плане число отрицательных компонент оказывается меньше числа ограничений.
Вопрос 49

Задача линейного программирования является вырожденной тогда, когда:

  1. Каждый опорный план содержит ровно m положительных компонент, где m – число ограничений в задаче.
  2. В опорном плане число положительных компонент оказывается меньше числа ограничений: некоторые базисные переменные, соответствующие данному опорному плану, принимают нулевые значения.
  3. Каждый опорный план содержит m отрицательных компонент, где m – число ограничений в задаче.
  4. В опорном плане число отрицательных компонент оказывается меньше числа ограничений.
Вопрос 50

Вырожденная задача линейного программирования отличается от невырожденной задачи тем, что:

  1. В одной вершине многогранника условий пересекается более двух прямых, описываемых уравнениями вида xi = 0.
  2. Одна или несколько сторон многоугольника условий стягиваются в точку.
  3. Находится только одно значение, по которому. определяется ингдекс выводимого из базиса вектора условий.
  4. Минимум может достигаться на нескольких индексах сразу (для нескольких строк).
Вопрос 51

Невырожденная задача линейного программирования характеризуется тем, что:

  1. В одной вершине многогранника условий пересекается более двух прямых, описываемых уравнениями вида xi = 0.
  2. Одна или несколько сторон многоугольника условий стягиваются в точку.
  3. Находится только одно значение, по которому определяется индекс выводимого из базиса вектора условий.
  4. Минимум может достигаться на нескольких индексах сразу (для нескольких строк).
Вопрос 52

Выберите правильное утверждение:

  1. Если задача линейного программирования оказывается вырожденной, то при плохом выборе вектора условий, выводимого из базиса, может возникнуть бесконечное движение по базисам одного и того же опорного плана.
  2. Если задача линейного программирования оказывается невырожденной, то при плохом выборе вектора условий, выводимого из базиса, может возникнуть бесконечное движение по базисам одного и того же опорного плана.
  3. Если задача линейного программирования оказывается вырожденной, то при любом выборе вектора условий, выводимого из базиса, возникает бесконечное движение по базисам одного и того же опорного плана.
  4. Если задача линейного программирования оказывается невырожденной, то при любом выборе вектора условий, выводимого из базиса, возникает бесконечное движение по базисам одного и того же опорного плана.
Вопрос 53

В чём заключается борьба с выраженностью?

  1. В преобразовании задачи путём «незначительного» изменения вектора правых частей системы ограничений на величины εi таким образом, чтобы это изменение не повлияло реально на оптимальный план задачи.
  2. В преобразовании задачи путём «незначительного» изменения левых частей системы ограничений на величины εi таким образом, чтобы это изменение не повлияло реально на оптимальный план задачи.
  3. В Увеличении правых частей системы строго на определенный коэффициент
  4. Избегать любых преобразований задачи
Вопрос 54

С точки зрения геометрических интерпретаций, ситуация вырожденности означает, что:

  1. Через некоторую угловую точку многогранного множества допустимых планов задачи, соответствующую текущему базисному плану, проходит более чем m гиперплоскостей ограничений задачи.
  2. Одно или несколько ограничений в некоторой угловой точке многогранного множества допустимых планов задачи являются избыточными.
  3. «попадание» линии, проходящей через вершину вектора b параллельно оси аппликат, в ребро конуса, натянутого на систему расширенных векторов текущего базиса.
  4. Через некоторую угловую точку многогранного множества допустимых планов задачи, соответствующую текущему базисному плану, проходит менее чем m гиперплоскостей ограничений задачи.
Вопрос 55

Матрицей перехода к новому базису называется:

  1. Матрица, столбцами которой являются координаты векторов нового базиса в их разложении по векторам старого.
  2. Скалярная матрица порядка n, диагональные элементы которой равны 1.
  3. Матрица, которая содержит m строк и у которой первые r≤m диагональных элементов ненулевые, а элементы, лежащие ниже главной диагонали и элементы последних m-r строк равны нулю.
  4. Диагональная матрица S, у которой все диагональные элементы равны между собой.
Вопрос 56

Что привело к осознанию вырожденности как самостоятельной проблемы в линейном программировании и необходимости разработки и внедрения специальных методов борьбы с вырожденностью?

  1. Зацикливание симплекс-метода
  2. «Застревание» симплекс-метода
  3. Невозможность применения симплекс-метода
Вопрос 57

Назовите методы, позволяющие эффективно преодолевать вырожденность:

  1. Метод А. Чарнса
  2. Метод П. Вольфа
  3. Метод Б.Ц. Бахшияна
  4. Метод Лагранжа
Вопрос 58

Какие переменные называют базисными?

  1. Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
  2. Это переменные, которые встречаются только в левой части системы ограничений
  3. Любые переменные, входящие в систему ограничений
  4. Это переменные, встречающиеся в системе ограничений только 1 раз
Вопрос 59

Базисное решение называется допустимым, если:

  1. Оно неотрицательно
  2. Оно неположительно
  3. Оно положительно
  4. Оно отрицательно
Вопрос 60

Новая базисная переменная в симплекс-таблице, это:

  1. Элемент, находящийся на пересечении ведущих строки и столбца
  2. Минимальный элемент в ведущей строке
  3. Элемент, находящийся на пересечении последних строки и столбца
  4. Минимальный элемент в ведущем столбце
Вопрос 61

В чём заключается практическое значение установленной связи между угловыми точками и допустимыми базисными решениями?

  1. Она позволяет формализовать (и тем самым существенно упростить) процесс перехода от одной угловой точки к другой.
  2. Помогает находить новые угловые точки
  3. Помогает находить новые решения
  4. Она позволяет формализовать (и тем самым существенно упростить) процесс перехода от одного базисного решения к другому.
Вопрос 62

К логической операции относя:

  1. Дизъюнкция
  2. Двойная импликация
  3. Импликация
  4. Фильтрация
Вопрос 63

Композиция машин – это …

  1. Операция, объединения машин, приводящая к последовательному выполнению программы первой машины, а затем программы второй машиной.
  2. Если все базисные неизвестные программы приравнять к одному типу программ.
  3. Если все базисные функции входят в него с единичным коэффициентом по базисной функции.
Вопрос 64

Операторы – это …

  1. Специальные преобразования функций в теории рекурсивных функций: оператор-подстановки, оператор примитивной рекурсии, оператор минимизации.
  2. Система логических операций, обладающая свойством: всякая формула алгебры логики, равносильна некоторой формуле, содержащей только операции этой системы.
  3. Коэффициенты симплекс-таблицы.
  4. Переменные по установлению связи между угловыми точками и допустимыми базисными решениями
Вопрос 65

Базисный план х называется невырожденным, если:

  1. Все его базисные компоненты строго положительны
  2. Все его базисные компоненты неположительны
  3. Все его базисные компоненты строго отрицательны
  4. Все его базисные компоненты неотрицательны
Вопрос 66

Для чего используется симплекс-таблица?

  1. За ограниченное количество шагов (итераций) получают искомый результат — план, обеспечивающий экстремальное значение целевой функции.
  2. За неограниченное количество шагов (итераций) получают искомый результат — план, обеспечивающий экстремальное значение целевой функции.
  3. Получают искомый результат, обеспечивающий максимальное значение целевой функции.
  4. Получают искомый результат, обеспечивающий минимальное значение целевой функции.
Вопрос 67

Какая теорема трактует понятие базисного плана в терминах первой геометрической интерпретации задач линейного программирования?

  1. Каждый допустимый базисный план является угловой точкой множества допустимых планов D.
  2. Если система векторов содержит m линейно независимых векторов, то допустимый план является крайней точкой многогранника планов.
  3. Если задача имеет решение, то целевая функция достигает экстремального значения хотя бы в одной из крайних точек многогранника решений. Если же целевая функция достигает экстремального значения более чем в одной крайней точке, то она достигает того же значения в любой точке, являющейся их выпуклой линейной комбинацией.
  4. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.
Вопрос 68

Как называется исходная задача линейного программирования, являющаяся задачей на максимум?

  1. Прямой задачей
  2. Косвенной задачей
  3. Основной задачей
  4. Двойственной задачей
Вопрос 69

Как называется задача линейного программирования, представляющая собой задачу на минимум?

  1. Прямой задачей
  2. Косвенной задачей
  3. Основной задачей
  4. Двойственной задачей
Вопрос 70

Выберите из перечисленных характеристик те, что относятся к прямой задаче:

  1. Определяются значения n переменных – компонент вектора-столбца х
  2. Определяются значения m переменных – компонент вектора-строки y
  3. Определяется максимум
  4. Определяется минимум
Вопрос 71

Выберите из перечисленных характеристик те, что относятся к двойственной задаче:

  1. Определяются значения n переменных – компонент вектора-столбца х
  2. Определяются значения m переменных – компонент вектора-строки y
  3. Определяется максимум
  4. Определяется минимум
Вопрос 72

Какие взаимно-обратные зависимости характеризуют прямую и двойственную задачи?

  1. Различны знаки неравенств
  2. Константы ограничений одной из задач являются коэффициентами целевой функции другой
  3. Определяется максимум/минимум
  4. Определяются значения n переменных – компонент вектора-строки х/ значения m переменных – компонент вектора-столбца y
Вопрос 73

Задача, двойственная к двойственной задаче, представляет собой:

  1. Исходную задачу
  2. Прямую задачу
  3. Основную задачу
  4. Двойственную задачу
Вопрос 74

Дана таблица двойственных задач: Как следует читать эту таблицу, чтобы получить задачу максимизации?

  1. Слева направо
  2. Справа налево
  3. Сверху вниз
  4. Снизу вверх
Вопрос 75

Дана таблица двойственных задач: Как следует читать эту таблицу, чтобы получить задачу минимизации?

  1. Слева направо
  2. Справа налево
  3. Сверху вниз
  4. Снизу вверх
Вопрос 76

Какие действия можно производить с нулевым элементом, расположенным в нижнем правом углу таблицы?

  1. Его можно заменить любой другой константой, вычитаемой из обеих целевых функций.
  2. Его можно заменить любой другой константой, общей для обеих целевых функций.
  3. Его можно заменить любой другой константой, слагаемой с обеими целевыми функциями.
  4. Его нельзя заменить никакой другой константой.
Вопрос 77

В каких годах 20-го века была переформулирована на язык современной математики и решена транспортная задача?

  1. В 40-х годах
  2. В 20-х годах
  3. В 50-х годах
  4. В 60-х годах
Вопрос 78

Кем была переформулирована и решена транспортная задача?

  1. Л. Канторовичем
  2. Г. Монжа
  3. А. Н. Тихоновым
  4. Л. Фордом
Вопрос 79

От какого года ведёт историю транспортная задача?

  1. 1781 г.
  2. 1871 г.
  3. 1681 г.
  4. 1861 г.
Вопрос 80

Кто является первооснователем классической идеи транспортной задачи?

  1. Л. Канторович
  2. Г. Монжа
  3. А. Н. Тихонов
  4. Л. Форд
Вопрос 81

Как первоначально выглядела формулировка транспортной задачи?

  1. Имеется куча песка и яма одинаковых объёмов. Как засыпать песком яму, потратив наименьшие усилия на перевозку?
  2. Имеется куча песка и яма одинаковых объёмов. Как засыпать песком яму, потратив наименьшее время на перевозку?
  3. Имеется куча песка и яма разных объёмов. Как рационально засыпать песком яму, потратив наименьшие усилия на перевозку?
  4. Имеется куча песка и яма разных объёмов. Как рационально засыпать песком яму, потратив наименьшее время на перевозку?
Вопрос 82

Важным шагом в работах Канторовича было:

  1. Применение метода двойственности
  2. Формулировка транспортной задачи на языке теории меры
  3. Формулировка транспортной задачи на языке функционального анализа
  4. Применение симплекс-метода
Вопрос 83

В чем заключаются условия новой транспортной задачи?

  1. Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n который, потребовал бы минимальных затрат.
  2. Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n который, потребовал бы минимальных временных затрат.
  3. Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n который, потребовал бы минимальных финансовых затрат.
  4. Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n который, потребовал бы рациональных затрат.
Вопрос 84

  Какая транспортная задача называется закрытой?

  1. 1
  2. 2
  3. 3
Вопрос 85

Какая транспортная задача называется открытой?

  1. 1
  2. 2
  3. 3
Вопрос 86

  В каком из приведённых случаев потребность не может быть покрыта, и чтобы свести условия к обычной транспортной задаче с правильным балансом, нужно ввести фиктивный пункт отправления m+1 с запасом. и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.    

  1. 1
  2. 2
  3. 3
Вопрос 87

Что представляет собой динамическое программирование в широком смысле?

  1. Способ решения сложных задач путём разбиения их на более простые подзадачи.
  2. Математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах N-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
  3. Случай математического программирования, в котором целевой функцией или ограничением является нелинейная функция.
  4. Раздел математического программирования, в котором на все или некоторые переменные дополнительно накладывается ограничение целочисленности.
Вопрос 88

Что определило появление термина динамического программирования?

  1. Особенности решения задач: по этапам, через фиксированные интервалы, промежутки времени.
  2. Решение задач для исследования движущихся целей.
  3. Необходимость быстрого написания программ.
  4. Особенности решения задач: нахождение решения сразу на всем временном интервале.
Вопрос 89

В каких задачах успешно применяются методы динамического программирования?

  1. В задачах без учёта фактора времени
  2. В задачах с учетом фактора времени
  3. В задачах на определение положения движущихся предметов
  4. В задачах с большим количеством вычислений
Вопрос 90

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

  1. Р.Э. Беллман
  2. А. Эйнштейн
  3. Д. Гильберт
  4. А. Н. Колмогоров
Вопрос 91

Одним из разделов какого программирования является динамическое программирование?

  1. Оптимального программирования
  2. Структурного программирования
  3. Линейного программирования
  4. Программирования игр
Вопрос 92

Область применения динамического программирования включает разрешение следующих задач:

  1. Вариантные оптимизационные задачи с заданными критериями оптимальности, с определенными связями между переменными и целевой функцией, выраженными системой уравнений или неравенств.
  2. Задачи, связанные с динамикой процесса или системы.
  3. Статические задачи, связанные с распределением ресурсов.
  4. Задачи сортировки данных.
Вопрос 93

Укажите примеры задач динамического программирования, в которых поиск оптимума возможен при поэтапном подходе:

  1. Распределение дефицитных капитальных вложений между новыми направлениями их использования.
  2. Разработка правил управления спросом или запасами, устанавливающими момент пополнения запаса и размер пополняющего заказа.
  3. Разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию.
  4. Вычисление корней квадратного уравнения.
Вопрос 94

Какой характер могут иметь зависимости между критериальной функцией и переменными?

  1. Линейный
  2. Нелинейный
  3. Произвольный
  4. Экспоненциальный
Вопрос 95

Что можно отнести к достоинствам комплекса методов динамического программирования?

  1. Возможность упрощения процесса решения, за счет ограничения области и количества исследуемых при переходе к очередному этапу вариантов.
  2. Сокращение объема используемой памяти.
  3. Единый универсальный метод решения.
  4. Уменьшение времени, затраченного на вычисление.
Вопрос 96

Что относится к недостаткам динамического программирования?

  1. Нет единого универсального метода решения.
  2. Каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения.
  3. Большие объемы и трудоемкость решения многошаговых задач, имеющих множество состояний, приводят к необходимости отбора задач малой размерности либо использования сжатой информации.
  4. Нельзя упростить процесс решения за счет ограничения области и количества исследуемых при переходе к очередному этапу вариантов.
Вопрос 97

В чём состоит сущность подхода динамического программирования?

  1. В замене решения исходной многомерной задачи последовательностью задач меньшей размерности.
  2. С помощью «принципа оптимальности» определяется основное рекуррентное соотношение.
  3. Если некоторые дополнительные предположения относительно гладкости участвующих в рассмотрении функций не выполняются, то из главного рекуррентного соотношения вытекает основное дифференциальное уравнение в частных производных, решая которое можно найти решение широкого класса задач.
  4. Определяется решение данной конкретной задачи.
Вопрос 98

Как называется основное дифференциальное уравнение в частных производных, вытекающее из главного рекуррентного соотношения?

  1. Уравнение Беллмана
  2. Уравнение Гельмгольца
  3. Обобщенное рекуррентное соотношение
  4. Динамическое уравнение
Вопрос 99

Кто из авторов выразил принцип оптимальности в следующих словах: «Если вы не используете наилучшим образом то, чем вы располагаете, то вы никогда не распорядитесь наилучшим образом и тем, что вы могли бы иметь в дальнейшем».

  1. Арис
  2. Беллман
  3. Дрейфус
  4. Алексеев
Вопрос 100

Для управления какими объектами применим принцип оптимальности?

  1. Объектами, у которых выбор оптимального управления не зависит от предыстории управляемого процесса, т. е. от того, каким путем система пришла в текущее состояние.
  2. Любыми, принцип применим без ограничений.
  3. Объектами, для которых известна полная история состояний.
  4. Объектами, состояние которых задается только одним числом
Вопрос 101

Как называется максимальное значение целевого функционала задачи с начальным состоянием х и начальным временем t?

  1. Функцией оптимального поведения
  2. Оптимальным решением
  3. Функцией оптимального решения
  4. Точкой бифуркации
Вопрос 102

Основное рекуррентное соотношение в математической форме имеет следующий вид:

  1. J*(x, t) = max[I(x, u, t)Δt + {u(t)} J*(x + Δx, t + Δt)].
  2. J*(x, t) = min [I(x, u, t)Δt + {u(t)} J*(x + Δx, t + Δt)].
  3. J*(x, t) = max[I(x, u, t)Δt + {u(t)} J*(x - 2Δx, t -2 Δt)].
  4. J*(x, t) = min[I(x, u, t)Δt + {u(t)} J*(x * Δx, t * Δt)].
Вопрос 103

Какое предположение в динамическом программировании играет существенную роль?

  1. Функция оптимального поведения J*(x, t) представляет собой однозначную и непрерывно дифференцируемую функцию от n + 1 переменных.
  2. Решения задач более широкого класса являются однозначными и непрерывными функциями относительно изменений начальных параметров.
  3. Функция оптимального поведения J*(x, t) представляет собой однозначную и непрерывно дифференцируемую функцию от n переменных.
  4. Решения задач более широкого класса являются однозначными и непрерывно дифференцируемыми функциями относительно изменений начальных параметров.
Вопрос 104

Какое ограничение связано с уравнением Беллмана, в качестве граничного условия, налагаемого на конечное состояние?

  1. J*(x(t1), t1) = F(x1, t1).
  2. J*(x(t1), t1) = F(x2, t2).
  3. J*(x(t1),u1, t1) = F(x1, u1, t1).
  4. J*(x(t1), t1) =max F(x, t1).
Вопрос 105

С чем связаны трудности решения уравнения Беллмана на цифровых электронно-вычислительных машинах с большим быстродействием?

  1. Недостаточная машинная память
  2. Высокая стоимость таких машин
  3. Недостаточное место на диске
  4. Сильный нагрев процессора
Вопрос 106

Дерево решений это:

  1. Граф, схема, отражающая структуру задачи оптимизации многошагового процесса принятия решений.
  2. Готовый алгоритм решения задачи для реализации на компьютере
  3. Блок-схема для написания программы
  4. граф, схема, отражающая готовое решение задачи оптимизации.
Вопрос 107

Для чего применяется дерево решений?

  1. Для структуризации проблем
  2. Для поиска правильного ответа
  3. Для наглядного изображения решения задачи
  4. Для численного решения задачи на компьютере
Вопрос 108

Что отображают ветви дерева?

  1. Различные события, которые могут иметь место
  2. Состояния, в которых возникает необходимость выбора
  3. Варианты решения
  4. Различные состояния задачи
Вопрос 109

Что отображают узлы (вершины) дерева?

  1. Состояния, в которых возникает необходимость выбора
  2. Различные события, которые могут иметь место
  3. Варианты решения
  4. Различные состояния задачи
Вопрос 110

Когда применяется дерево решений?

  1. Когда количество альтернатив и количество шагов принятия решений ограниченно (конечно)
  2. Когда количество альтернатив и количество шагов принятия решений бесконечно
  3. Когда требуется численное решение задачи на компьютере
  4. Когда количество шагов принятия решений не превышает 1024
Вопрос 111

Какова логика анализа методом «Дерева решений»?

  1. Движение от конечного состояния к начальному, последовательный выбор оптимального в каждой точке
  2. Отсечение менее эффективной альтернативы и исключение её из дальнейшего рассмотрения
  3. движение от начального состояния к конечному
  4. Выбор оптимального состояния среди всех вершин дерева
Вопрос 112

Что изучает теория графов?

  1. Математические объекты, которые можно изображать в виде рисунков, содержащих кружки и соединяющие их линии.
  2. Деревья решений
  3. Блок-схемы
  4. Задачи оптимизации
Вопрос 113

Как называют кружки схемы?

  1. Вершинами (узлами) графа
  2. Ребрами графа
  3. Корнями графа
  4. Листьями графа
Вопрос 114

Как называются линии, соединяющие кружки схемы?

  1. Ребрами графа
  2. Вершинами графа
  3. Узлами графа
  4. Ветвями графа
Вопрос 115

Как называются две вершины графа, соединенные ребром?

  1. Смежными вершинами
  2. Висячими вершинами
  3. Изолированными вершинами
  4. Связанными вершинами
Вопрос 116

Каким условиям должна удовлетворять задача, чтобы для ее решения мог быть применен алгоритм динамического программирования?

  1. Объектом исследования должна служить управляемая система (объект) с заданными допустимыми состояниями и допустимыми управлениями
  2. Задача должна позволять интерпретацию как многошаговый процесс, каждый шаг которого состоит из принятия решения о выборе одного из допустимых управлений, приводящих к изменению состояния системы
  3. Задача должна зависеть от количества шагов и быть определенной на каждом из них
  4. Состояние системы на каждом шаге должно описываться одинаковым (по составу) набором параметров
Вопрос 117

Какое свойство является основным с точки зрения идеологии динамического программирования?

  1. Последующее состояние, в котором оказывается система после выбора решения на k-м шаге, зависит только от данного решения и исходного состояния к началу k-го шага
  2. Количество состояний не должно превышать 1024
  3. Последующее состояние, в котором оказывается система после выбора решения на k-м шаге, зависит от всех предыдущих состояний
  4. Задача не должна зависеть от количества шагов и быть определенной на каждом из них
Вопрос 118

Какое свойство называют «отсутствием последействия»?

  1. Последующее состояние, в котором оказывается система после выбора решения на k-м шаге, зависит только от данного решения и исходного состояния к началу k-го шага
  2. Задача не должна зависеть от количества шагов и быть определенной на каждом из них
  3. Состояние системы на каждом шаге должно описываться одинаковым (по составу) набором параметров
  4. Задача не должна зависеть от количества шагов
Вопрос 119

В каком направлении решается задача при использовании алгоритмов динамического программирования, если задано начальное состояние управляемой системы?

  1. В обратном направлении
  2. В прямом направлении
  3. В произвольном направлении
  4. В направлении, заданном графом решений
Вопрос 120

В каком направлении решается задача при использовании алгоритмов динамического программирования, если задано конечное состояние управляемой системы?

  1. В прямом направлении
  2. В обратном направлении
  3. В произвольном направлении
  4. В направлении, заданном графом решений
Вопрос 121

Какие трудности связаны с вычислительными алгоритмами динамического программирования?

  1. При наличии нескольких ограничений состояние управляемого объекта на каждом шаге характеризуется набором параметров и табулировать значения функций необходимо для многократно большего количества точек.
  2. Не достаточно мощности современных процессоров
  3. Требуется много оперативной памяти
  4. Большие погрешности приближения
Вопрос 122

Что определяет направление решения задачи в алгоритмах динамического программирования?

  1. Состояние управляемой системы
  2. Вид дерева решений
  3. Начальные условия
  4. Направление решения может быть выбрано произвольно
Вопрос 123

Что является особенностью задач последовательного принятия решений?

  1. Искомые переменные должны определяться в строгой временной последовательности и не должны меняться местами
  2. Искомые переменные могут определяться в произвольном порядке
  3. Использование дерева решений
  4. На каждом шаге обязательно определяется одна переменная
Вопрос 124

В каком случае при использовании алгоритмов динамического программирования иногда прибегают к компромиссу: отказываются от оптимизации на первом или последнем этапе?

  1. Если задано начальное состояние управляемой системы
  2. Если конечное состояние управляемой системы
  3. Если заданы начальное и конечное состояния
  4. Если недостаточно данных ни в начальном, ни в конечном состояниях
Вопрос 125

Задача коммивояжёра это:

  1. Задача, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные пункты хотя бы по одному разу с последующим возвратом в исходный пункт
  2. Задача на поиск кратчайшего пути между двумя вершинами в графе
  3. Задача на поиск ребра с наибольшим весом в графе
  4. Задача на поиск Гамильтонова пути в графе
Вопрос 126

Гамильтонов цикл – это:

  1. Гамильтонов путь, начальная и конечная вершины которого совпадают
  2. Самый длинный цикл в графе
  3. Цикл с наименьшим весом ребер
  4. Цикл с наибольшим весом ребер
Вопрос 127

Задача коммивояжёра называется геометрической, когда:

  1. Матрица расстояний отражает расстояния между точками на плоскости
  2. На матрице стоимостей выполняется неравенство треугольника
  3. если относительно длин ребер выполняется неравенство треугольника, т.е. ребро от вершины i до вершины j никогда не бывает длиннее пути через промежуточную вершину k
  4. Граф является планарным
Вопрос 128

Задача коммивояжёра называется треугольной, когда:

  1. На матрице стоимостей выполняется неравенство треугольника
  2. Количество вершин графа кратно трем
  3. если относительно длин ребер выполняется неравенство треугольника, т.е. ребро от вершины j до вершины j никогда не бывает длиннее пути через промежуточную вершину k
  4. Количество ребер графа кратно трем
Вопрос 129

Различают следующие частные случаи общей постановки задачи:

  1. Геометрическая задача коммивояжёра
  2. Треугольная задача коммивояжёра
  3. Симметричная задача коммивояжёра
  4. Линейная задача коммивояжера
Вопрос 130

К числу каких задач относится задача коммивояжёра?

  1. Трансвычислительных
  2. Полиномиальных
  3. Логарифмических
  4. Невычислимых
Вопрос 131

Что является непременным условием и единственным смыслом задачи коммивояжёра?

  1. Поиск самого выгодного пути
  2. Поиск самого короткого пути
  3. Поиск самого длинного пути
  4. Поиск корневой вершины
Вопрос 132

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

  1. Необходимо найти и описать все возможные пути при любом из вариантов способов поиска решения
  2. Необходимо выбирать на каждом шаге лучший путь
  3. Необходимо вычислить собственные значения матрицы стоимостей
  4. Найти гамильтонов путь
Вопрос 133

Известно, что проверка решения задачи коммивояжёра:

  1. Равна или больше самого решения
  2. Равна самому решению
  3. Равна или меньше самого решения
  4. Меньше решения