ПОМОГИТЕ: ТЕОРИЯ АЛГОРИТМОВ

[Sergg]

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

[Jack91]

Итоговые тесты совпадают с промежуточными.

Вот результаты моих запар, ребят, пришлось применять теорию алгоритмов к тестам по теории алгоритмов() чтобы отобрать правильные ответы, и ещё погуглить. К сожалению, мне дико не хватило ответов на вопросы, когда я их искал, и эта ветка - единственная во всём интернете (хотя бы с частичными вариантами ответов); поэтому я решил, что если получится сдать, то выложу и выручу тех, кто будет искать так же, как и я
Сдал на отлично.

P.S. К слову сказать, учебный курс я, будучи ответственным студентом, прошёл и рекомендуемую литературу перечитал.

Первый раздел уже выложили, по большому счёту он подходит.

Вот, второй раздел, "Симпликс-метод":
(плюсы - верно, минусы - точно не подходит)

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

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



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

+++Метод А.Чарнса

+++ Метод П.Вольфа

+++Метод Б.Ц.Бахшияна



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

+++Выбор начальной точки осуществляется с учётом ограничений



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

+++Л. Канторовичем



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


+++Прямой задачей



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

+++Различны знаки неравенств



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

+++Каждый опорный план содержит ровно m положительных компонент, где m – число ограничений в задаче



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

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



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

+++Симплексный алгоритм



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

+++Двойственной задачей



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

+++Его можно заменить любой другой константой, вычитаемой из обеих целевых функций.



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

+++Еа<Еб



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

+++Матрицей которая из старой, тыры-пыры



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

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



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

+++Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n который, потребовал бы минимальных затрат.



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

+++Через некоторую угло*вую точку многогранного множества допустимых планов зада*чи, соответствующую текущему базисному плану, проходит более чем m гиперплоскостей ограничений задачи.

+++«попадание» линии, проходящей через вершину вектора b параллельно оси аппликат, в ребро кону*са, натянутого на систему расширенных векторов текущего базиса.

+++Одно или несколько ограничений в некоторой угло*вой точке многогранного множества допустимых планов зада*чи являют*ся избыточными.



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

+++Все вершины являются решениями, а также все точки между этими вершинами



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

+++Найденное решение единственное



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

+++В преобразовании задачи путём «незначительного» изменения вектора правых частей системы ограничений на величины ?i таким образом, чтобы это изменение не повлияло реально на оптимальный план задачи.

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

+++Матрицы коэффициентов системы уравнений линейного программирования, приведенной к “канонической форме”


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

+++Г. Монжа


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

+++Еа>Еб

+++Еа<Еб



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

+++Еа=Еб


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

+++Приведёт к решению задачи

+++Через конечное число шагов покажет, что целевая функция не ограничена


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

+++В 40-х годах


Базисный план х называется невырожденным, если:
+++Все его базисные компоненты строго положительны


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

+++Операция, объединения машин, приводящая к последовательному выполнению программы первой машины, а затем программы второй машиной.



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


+++В одной вершине многогранника условий пересекается более двух прямых, описываемых уравнениями вида xi = 0.

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


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

+++"Застревание"симплекс-метода


Процесс поиска глобального оптимума состоит из таких этапов:

Берётся любая соседняя вершина по такому направлению, в котором целевая функция возрастает

Берётся любая вершина допустимого множества

Находится такая вершина, что при перемещении в любую соседнюю вершину целевая функция не возрастает

Берётся очередная соседняя вершина по такому направлению, в котором целевая функция возрастает

Определите порядок осуществления данных этапов.

+++2, 1, 4, 3



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

+++Определяются значения m переменных – компонент вектора-строки y

+++Определяется минимум



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

+++Определяются значения n переменных – компонент вектора-столбца х

+++Определяется максимум



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

+++Сверху вниз



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

+++Слева Направо



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

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



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

+++Оно неотрицательно



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

+++Исходную задачу



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

+++Импликация

+++Дизъюнкция

+++Двойная Импликация



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

+++Макс Ф, А<б, х>0



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

+++Имеется куча песка и яма одинаковых объёмов. Как засыпать песком яму, потратив наименьшие усилия на перевозку?



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

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



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

+++Каждый допустимый базисный план является угловой точкой множества допустимых планов D.



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

+++Применение метода двойственности

+++Формулировка транспортной задачи на языке теории меры

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



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

+++Элемент, находящийся на пересечении ведущих строки и столбца

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

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



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

+++Симплексной таблицей



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

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



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

+++Ведущим преобразованием

_______________________________________________________
Раздел третий, "Динамическое программирование":

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

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



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

+++Поиск самого выгодного пути



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

+++Смежными вершинами



Путь, содержащий каждую вершину графа ровно один раз, называется:

+++Гамильтонов путь

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

+++Способ решения сложных задач путём разбиения их на более простые подзадачи.


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

---Разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию.

---Вычисление корней квадратного уравнения



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

---Каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения.

---Нельзя упростить процесс решения за счет ограничения области и количества исследуемых при переходе к очередному этапу вариантов.



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


+++Линейный
+++Нелинейный

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


+++Движение от конечного состояния к начальному, последовательный выбор оптимального в каждой точке

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

+++Треугольная задача коммивояжёра

+++Симметричная задача коммивояжёра

+++Геометрическая задача коммивояжёра


Типовой алгоритм решения задач методом динамического программирования содержит следующие этапы:

Описать строение оптимальных решений.

Выписать рекуррентное соотношение, связывающие оптимальные значения параметра для подзадач.

Двигаясь снизу вверх, вычислить оптимальное значение параметра для подзадач.

Пользуясь полученной информацией, построить оптимальное решение.

---3,4,1,2
---2,1,4,3
---2,4,3,1

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

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

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

+++Искомые переменные должны определяться в строгой временной последовательности и не должны меняться местами

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

+++Ребрами графа



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

+++Необходимо найти и описать все возможные пути при любом из вариантов способов поиска решения



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

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

+++В ОБРАТНОМ

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

+++Особенности решения задач: по этапам, через фиксированные интервалы, промежутки времени.



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

+++J*(x(t1), t1) = F(x1, t1).

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

+++Вершинами (узлами) графа



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

+++Матрица расстояний отражает расстояния между точками на плоскости



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

+++Арис



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

+++Различные события, которые могут иметь место


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

+++Трансвычислительных

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

+++Когда количество альтернатив и количество шагов принятия решений ограниченно (конечно)



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

+++Вариантные оптимизационные задачи с заданными критериями оптимальности, с определенными связями между переменными и целевой функцией, выраженными системой уравнений или неравенств.

+++Статические задачи, связанные с распределением ресурсов.
+++Задачи, связанные с динамикой процесса или системы.

Какое свойство является основным с точки зрения идеологии динамического программирования?
+++Последующее состояние, в котором оказывается система после выбора решения на k-м шаге, зависит только от данного решения и исходного состояния к началу k-го шага

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

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

Какие трудности связаны с вычислительными алгоритмами динамического программирования?
+++При наличии нескольких ограничений состояние управляемого объекта на каждом шаге характеризуется набором параметров и табулировать значения функций необходимо для многократно большего количества точек.

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

+++ J*(x, t) = max[I(x, u, t)Δt + {u(t)}
J*(x + Δx, t + Δt)].

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

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

Известно, что проверка решения задачи коммивояжёра:
+++Равна или больше самого решения

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

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

Что можно отнести к достоинствам комплекса методов динамического программирования?
+++Возможность упрощения процесса решения, за счет ограничения области и количества исследуемых при переходе к очередному этапу вариантов.

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

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

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

Что отображают узлы (вершины) дерева?
+++Состояния, в которых возникает необходимость выбора

Гамильтонов цикл – это:
+++Гамильтонов путь, начальная и конечная вершины которого совпадают

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

Что определяет направление решения задачи в алгоритмах динамического программирования?
+++Направление решения может быть выбрано произвольно

Какое свойство называют «отсутствием последействия»?
+++Последующее состояние, в котором оказывается система после выбора решения на k-м шаге, зависит только от данного решения и исходного состояния к началу k-го шага

Уравнение Беллмана имеет вид:
---((dJ*)/(dt)) = max[I(x, u, t) +
{u(t)}
((dJ*)/(dx))f(x, u, t)].