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

Скачать тест — (Теория алгоритмов.ти ЭБС_67306645.pdf)

Вектор инструментальных переменных х называется допустимым, если он:
Если вектор инструментальных переменных x* принадлежит допустимому множеству и на нём достигается значение целевой функции, большее или равное значениям функции в некоторой малой окрестности этого вектора, то он является:
Выберите определения: «Задача математического программирования состоит:…»
Какие понятия являются основными при формальной постановке задачи?
Алгоритм – совокупность правил….
Что принято понимать под целевой функцией? Выберите несколько правильных ответов.
Сколько основных видов общей задачи математического программирования выделяют?
Назовите основные виды общей задачи математического программирования
Что представляют собой все ограничения в классической задаче математического программирования?
В нелинейном программировании система ограничений состоит из:
В линейном программировании система ограничений состоит из:
В каком из видов общей задачи математического программирования целевая функция является линейной формой?
Как называют точку х, в которой выполняются необходимые условия локального минимума функции, ϕ(х) на множестве Х?
Что характерно для задач выпуклого программирования?
Для решения задач выпуклого программирования разработаны многочисленные численные методы, приспособленные для решения на ЭВМ, в основном связанные с:
Какие из перечисленных методов используются для решения задач выпуклого программирования?
Как называют точку х* = argmin { ϕ(x): x∈X}? Выберите несколько вариантов ответов.
Из какой теоремы следует, что во всех точках локального минимума выпуклая функция имеет одинаковые значения?
Какая теорема даёт условие существования решения задачи выпуклого программирования?
Какие задачи можно рассматривать как частный случай задач выпуклого программирования?
Что из перечисленного характеризует метод множителей Лагранжа?
Характерные свойства алгоритма (укажите неверный ответ):
Как называется вектор-строка из m новых переменных y = (y1, y2, …, ym)?
Основные свойства алгоритма:
Как в соответствии с методом множителей Лагранжа задача f(x)→ min, x∈Rn, h1(x) = 0 преобразуется в задачу безусловной минимизации?
Дана задача: f(x) = x12 + x22, при ограничении h1(x) = 2×1 + x2 – 2 = 0. Найдите минимальное значение f(x0; λ0).
Как называются ограничения первого вида?
Частично-рекурсивные функции – это…
Если вектор инструментальных переменных x* принадлежит допустимому множеству и целевая функция принимает на этом векторе значение не меньшее, чем в любой другой допустимой точке, то он является:
Глобальный максимум является строгим (сильным), если:
Какая теорема формулирует условия существования глобального максимума?
Теорема. Класс функций, вычислимых на машинах Тьюринга, ….
Алгебра высказываний – это…
Массовость – это …
Дайте название теоремы, условия которой звучат следующим образом: «Пусть допустимое множество не пусто и является компактным и выпуклым, а непрерывная функция F(x) вогнута на Х. Тогда локальный максимум является глобальным, а множество точек, на котором достигается максимум, выпукло.
Определённость алгоритма – это …
Машина Тьюринга – это
Что характеризует симплексный алгоритм?
Какой алгоритм позволяет найти решение задач линейного программирования с помощью итеративной процедуры?
Если перемещение в любую соседнюю вершину уменьшает целевую функцию, то:
Если смещение в некоторую другую вершину не уменьшает целевую функцию, то:
Какие варианты реализации симплекс-метода возможны (принять во внимание тот факт, что число вершин допустимого множества конечно)?
Преобразование, с помощью которого определяются новые базисные переменные, а целевая функция становится при этом линейной функцией небазисных переменных, называется:
Матрица, служащая средством перебора допустимых базисных решений (невырожденной) задачи линейного программирования при ее решении симплексным методом, называется:
Симплекс-таблица образуется из (выберите один ответ):
Последовательное преобразование симплекс-таблицы по симплексному алгоритму позволяет:
Задача линейного программирования является невырожденной тогда, когда:
Задача линейного программирования является вырожденной тогда, когда:
Вырожденная задача линейного программирования отличается от невырожденной задачи тем, что:
Невырожденная задача линейного программирования характеризуется тем, что:
Выберите правильное утверждение:
В чём заключается борьба с выраженностью?
С точки зрения геометрических интерпретаций, ситуация вырожденности означает, что:
Матрицей перехода к новому базису называется:
Что привело к осознанию вырожденности как самостоятельной проблемы в линейном программировании и необходимости разработки и внедрения специальных методов борьбы с вырожденностью?
Назовите методы, позволяющие эффективно преодолевать вырожденность:
Какие переменные называют базисными?
Базисное решение называется допустимым, если:
Новая базисная переменная в симплекс-таблице, это:
В чём заключается практическое значение установленной связи между угловыми точками и допустимыми базисными решениями?
К логической операции относя:
Композиция машин – это …
Операторы – это …
Базисный план х называется невырожденным, если:
Для чего используется симплекс-таблица?
Какая теорема трактует понятие базисного плана в терминах первой геометрической интерпретации задач линейного программирования?
Как называется исходная задача линейного программирования, являющаяся задачей на максимум?
Как называется задача линейного программирования, представляющая собой задачу на минимум?
Выберите из перечисленных характеристик те, что относятся к прямой задаче:
Выберите из перечисленных характеристик те, что относятся к двойственной задаче:
Какие взаимно-обратные зависимости характеризуют прямую и двойственную задачи?
Задача, двойственная к двойственной задаче, представляет собой:
Дана таблица двойственных задач: Как следует читать эту таблицу, чтобы получить задачу максимизации?
Дана таблица двойственных задач: Как следует читать эту таблицу, чтобы получить задачу минимизации?
Какие действия можно производить с нулевым элементом, расположенным в нижнем правом углу таблицы?
В каких годах 20-го века была переформулирована на язык современной математики и решена транспортная задача?
Кем была переформулирована и решена транспортная задача?
От какого года ведёт историю транспортная задача?
Кто является первооснователем классической идеи транспортной задачи?
Как первоначально выглядела формулировка транспортной задачи?
Важным шагом в работах Канторовича было:
В чем заключаются условия новой транспортной задачи?
Какая транспортная задача называется закрытой?
Какая транспортная задача называется открытой?
В каком из приведённых случаев потребность не может быть покрыта, и чтобы свести условия к обычной транспортной задаче с правильным балансом, нужно ввести фиктивный пункт отправления m+1 с запасом. и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.
Что представляет собой динамическое программирование в широком смысле?
Что определило появление термина динамического программирования?
В каких задачах успешно применяются методы динамического программирования?
Кто сформулировал данный принцип оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения.
Одним из разделов какого программирования является динамическое программирование?
Область применения динамического программирования включает разрешение следующих задач:
Укажите примеры задач динамического программирования, в которых поиск оптимума возможен при поэтапном подходе:
Какой характер могут иметь зависимости между критериальной функцией и переменными?
Что можно отнести к достоинствам комплекса методов динамического программирования?
Что относится к недостаткам динамического программирования?
В чём состоит сущность подхода динамического программирования?
Как называется основное дифференциальное уравнение в частных производных, вытекающее из главного рекуррентного соотношения?
Кто из авторов выразил принцип оптимальности в следующих словах: «Если вы не используете наилучшим образом то, чем вы располагаете, то вы никогда не распорядитесь наилучшим образом и тем, что вы могли бы иметь в дальнейшем».
Для управления какими объектами применим принцип оптимальности?
Как называется максимальное значение целевого функционала задачи с начальным состоянием х и начальным временем t?
Основное рекуррентное соотношение в математической форме имеет следующий вид:
Какое предположение в динамическом программировании играет существенную роль?
Какое ограничение связано с уравнением Беллмана, в качестве граничного условия, налагаемого на конечное состояние?
С чем связаны трудности решения уравнения Беллмана на цифровых электронно-вычислительных машинах с большим быстродействием?
Дерево решений это:
Для чего применяется дерево решений?
Что отображают ветви дерева?
Что отображают узлы (вершины) дерева?
Когда применяется дерево решений?
Какова логика анализа методом «Дерева решений»?
Что изучает теория графов?
Как называют кружки схемы?
Как называются линии, соединяющие кружки схемы?
Как называются две вершины графа, соединенные ребром?
Каким условиям должна удовлетворять задача, чтобы для ее решения мог быть применен алгоритм динамического программирования?
Какое свойство является основным с точки зрения идеологии динамического программирования?
Какое свойство называют «отсутствием последействия»?
В каком направлении решается задача при использовании алгоритмов динамического программирования, если задано начальное состояние управляемой системы?
В каком направлении решается задача при использовании алгоритмов динамического программирования, если задано конечное состояние управляемой системы?
Какие трудности связаны с вычислительными алгоритмами динамического программирования?
Что определяет направление решения задачи в алгоритмах динамического программирования?
Что является особенностью задач последовательного принятия решений?
В каком случае при использовании алгоритмов динамического программирования иногда прибегают к компромиссу: отказываются от оптимизации на первом или последнем этапе?
Задача коммивояжёра это:
Гамильтонов цикл – это:
Задача коммивояжёра называется геометрической, когда:
Задача коммивояжёра называется треугольной, когда:
Различают следующие частные случаи общей постановки задачи:
К числу каких задач относится задача коммивояжёра?
Что является непременным условием и единственным смыслом задачи коммивояжёра?
Поиск самого выгодного пути осуществляется следующим образом:
Известно, что проверка решения задачи коммивояжёра: