Cтраница 2
Заданы начальное и конечное состояния. Задача заключается в нахождении последовательности перемещений фишек из начального положения в конечное. Любую фишку можно передвинуть по горизонтали или вертикали, если рядом есть свободное место, но двигаться по диагонали запрещено. [16]
Эти задачи по своей сущности являются распределительными, и. Модель такого типа может быть использована для задач нахождения последовательности выполнения переходов обработки поверхностей детали на многошпиндельных токарных полуавтоматах, прутковых автоматах и др. Пусть имеющуюся совокупность переходов необходимо распределить по / позициям станка. [17]
Прямые пути выполнения пункта 1 будут рассмотрены в следующем разделе. Существует два принципиально различных метода выполнения пункта 2, а именно: одновременный расчет рециркуляционной последовательности и нахождение последовательности вычислений внутри рециркуляционной последовательности. Оба метода обычно требуют выполнения повторяющихся вычислений ( итераций) до тех пор, пока переменные потоков не достигнут значений, которые удовлетворяют предварительно точно определенному критерию ошибки или изменения которых при каждом шаге итерации не превышают заранее установленной величины. [18]
В общем блоки, которые остаются после вычеркивания разомкнутых последовательностей, начинающих и заканчивающих процесс, могут быть частью рециркуляционной последовательности или разомкнутой последовательности, соединяющей две рециркуляционные последовательности. Матрица процесса может быть использована для определения того, какой блок принадлежит какой рециркуляционной последовательности, а также для нахождения последовательности вычислений для этих блоков. Эти вопросы обсуждаются в разд. [19]
Преобразование представляет собой метод исследования линейных цифровых систем с постоянными параметрами. С точки зрения анализа желательнее иметь сами выходные последовательности, а не их z - преобразования. Процесс нахождения последовательности по соответствующей функции переменной z называется обратным z - преобразованием. [20]
Определим на графе G маршрут L как такую последовательность ребер, что каждые два соседних ребра имеют общую концевую точку. В случае ориентированного графа маршрут называют путем. Очевидно, что решение задачи методом поиска в пространстве состояний ( т.е. нахождение последовательности операторов, преобразующей начальное состояние в конечное) сводится к задаче поиска пути L на графе G. Часто бывает удобно приписывать дугам графа веса, отражающие стоимость применения соответствующих операторов. Стоимость пути между двумя вершинами определяется как сумма стоимостей всех дуг, образующих этот путь. В ряде приложений возникает задача нахождения путей ( пути), имеющих минимальную стоимость, между любыми элементами из множества Х0 и любыми элементами из множества Xf. Отметим, что граф G может быть задан как в явном виде, так и неявно. Неявное задание графа G состоит в определении множества Х0 и множества операторов, которые будучи применимы к некоторой вершине графа, дают все ее дочерние вершины. [21]
Несмотря на то что диаграммы состояний полностью описывают кодер, по сути, их нельзя использовать для легкого отслеживания переходов кодера в зависимости от времени, поскольку диаграмма не представляет динамики изменений. Древовидная диаграмма ( tree diagram) прибавляет к диаграмме состояния временное измерение. Древовидная диаграмма сверточного кодера, показанного на рис. 7.3, изображена на рис. 7.6. В каждый последующий момент прохождения входного бита процедура кодирования может быть описана с помощью перемещения по диаграмме слева направо, причем каждая ветвь дерева описывает кодовое слово на выходе. Правило ветвления для нахождения последовательности кодовых слов следующее: если входным битом является нуль, то он связывается со словом, которое находится путем перемещения в следующую ( по направлению вверх) правую ветвь; если входной бит - это единица, то кодовое слово находится путем перемещения в следующую ( по направлению вниз) правую ветвь. Предполагается, что первоначально кодер содержал одни нули. [22]
В системе GSM требуется обеспечить подавление искажений, вызванных дисперсией сигнала, имеющего разброс задержек порядка 15 - 20 мкс. Поскольку в GSM длительность бита составляет 3 69 мкс, Ь0 можно выразить в единицах битовых интервалов. Следовательно, эквалайзер Витерби, применяемый в системе GSM, обладает памятью от 4 до 6 битовых интервалов. На каждом интервале Д, бит задача эквалайзера Витерби состоит в нахождении наиболее правдоподобной последовательности, длиной L0 бит, среди 1L возможных, которые могли быть переданы. Определение наиболее правдоподобной / - - битовой последовательности, которая могла быть передана, требует создания 2L значащих опорных сигналов путем модификации ( или искажения) 2L идеальных сигналов ( генерируемых приемником) таким образом, как канал искажает передаваемый слот. Следовательно, 1L опорных сигналов сворачиваются с усеченной оценкой импульсной характеристики канала h t с целью генерации искаженных или своего рода подогнанных под канал опорных сигналов. Затем подкорректированные сигналы сравниваются с принятыми информационными сигналами для расчета метрик. Отметим, что перед сравниванием принятые данные сворачиваются с известной усеченной автокорреляционной функцией w ( t) Rs ( t), преобразовывая ее подобно опорным сигналам. [23]
Y (), для которых последовательность tpCcp ограничена. Возникает деликатный вопрос - а существуют ли такие последовательности. Мовяо переформулировать задачу минимакса для семейства - г как задачу о нахождении минимаксной последовательности, такой что последовательность точек ( К3), где Л [ Z4l - / se ] t ограничена. [24]
Анализ модели обычно производится с помощью методов и алгоритмов решения условных экстремальных задач или посредством статистич. К числу наиболее широко применяемых в И. Модели, приводящие к задачам линейного программирования, глубоко изучены, имеются эффективные алгоритмы и стандартные программы для ЭВМ, позволяющие решать задачи, содержащие тысячи ограничений и десятки тысяч переменных. Эти выводы базируются на теории двойственности ( объективно-обусловленные оценки) и принципах декомпозиции. Если целевая функция или ограничения модели исследуемой операции не могут быть достаточно точно описаны с помощью линейных функций, для ее анализа используются др. методы математического программирования. Модели, в к-рых по смыслу операции все переменные или их часть могут принимать лишь конечное число различных значений, изучаются методами целочисленного или дискретного программирования, в частности, сюда относится большое число нла-ново-производств. Это задачи, связанные с нахождением последовательности обработки определ. При этом должны быть соблюдены опродел. Задачи теории расписаний часто встречаются во внутризаводском планировании, особенно на мапшностроит. [25]