|
||||||||||||||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[171] мы
25.5-3 Может ли в графе ограничений кратчайший путь из vq в какую-то вершину иметь положительный вес? 25.5-4 Сведите задачу о кратчайшем пути между парой вершин к задаче линейного программирования. 25.5-5 Модифицируйте алгоритм Беллмана-Форда таким образом, чтобы при решении системы т ограничений на разности с п неизвестными он работал за время О (inn). 25.5-6 Как с помощью алгоритма, аналогичного алгоритму Беллмана-Форда, решить систему ограничений на разности, пользуясь графом ограничений без дополнительной вершины vq! 25.5-7* Покажите, что решение системы разностных ограничений с п неизвестными, находимое алгоритмом Беллмана-Форда, имеет (среди всех решений этой системы, в которых все переменные неположительны) максимальное значение суммы х\-\-х2-\-.. .+ хп. 25.5-8* Покажите, что решение системы разностных ограничений Ах Ь с п неизвестными, находимое алгоритмом Беллмана-Форда, имеет минимально возможное значение величины тах{жг} - тт{жг} среди всех оещений этой системы. Чем полезно это обстоятельство при планировании строительства? 25.5-9 Рассмотрим систему неравенств, в которой каждое неравенство является либо ограничением на разности, либо неравенством вида Xi а, либо неравенством вида Xj а. Модифицируйте алгоритм Беллмана-Форда таким образом, чтобы он находил хотя бы одно решение или устанавливал несовместность таких систем. 25.5-10 Пусть к системе ограничений на разности добавлено некоторое количество уравнений вида жг- = Xj + b. Модифицируйте алгоритм Беллмана-Форда таким образом, чтобы он мог находить решения таких систем. 25.5-11 Разработайте эффективный алгоритм для нахождения решения системы ограничений на разности, в котором все неизвестные являются целыми числами (константы в ограничениях не обязаны быть целыми, но их можно заменить на их целые части). 25.5-12* Разработайте эффективный алгоритм для нахождения решения системы ограничений на разности, если все переменные разбиты на две группы: целые (для которых допустимы только целые значения) и вещественные (для которых такого ограничения нет). Задачи 25-1 Модификация алгоритма Беллмана-Форда по Иену Выберем порядок, в котором обрабатываются рёбра в алгоритме Беллмана-Форда, следующим образом. Пронумеруем каким-либо образом вершины графа и разобьем множество Е вершин графа на два подмножества: Ef, состоящее из стрелок, идущих из вершины с меньшим номером в вершину с большим номером, и Еь, состоящее из стрелок, идущих из вершины с большим номером в вершину с меньшим номером. Пусть Gf = (V,Ef) и Gj, = (V, Еь) (через V обозначено множество вершин графа). Начнём с такого очевидного наблюдения: (а)Покажите, что графы Gf и Gb ацикличны, причём расположение вершин в порядке возрастания (убывания) номеров задает топологическое упорядочение на графе Gf (Gb)- Будем теперь проводить релаксацию ребер при каждой итерации цикла в алгоритме Беллмана-Форда в следующем порядке: сначала перебираем вершины в порядке возрастания номеров и для каждой вершины подвергаем релаксации все выходящие из нее ребра графа Ef, затем перебираем все вершины в порядке убывания номеров и для каждой вершины подвергаем релаксации все выходящие из нее ребра графа Еь- (б)Пусть G не содержит циклов отрицательного веса, достижимых из вершины s; докажите, что после [~У/2] итераций цикла равенства d[v] = S(s, v) будут выполняться для всех v £ V. (в)Оцените время работы описанной модификации алгоритма Беллмана-Форда. 25-2 Вложенные ящики Будем говорить, что d-мерный ящик размеров (х\, х2, , x,i) вкладывается (nests) в ящик размеров (у\,у2, -,y<l), если у множества { 1, 2,..., d } существует такая перестановка тг, что хж < уъжтг(2) < У2, - ,2(0 < Ув,- (а)Покажите, что отношение «вкладываться» транзитивно. (б)Опишите эффективный способ проверить, вкладывается ли один d-мерный ящик в другой. (в)Даны п различных d-мерных ящиков. Требуется узнать, какое максимальное число из них можно последовательно вложить друг в друга (первый во второй, второй в третий и т.д.). Укажите эффективный алгоритм для решения этой задачи и оцените время его работы. 25-3 Арбитражные операции Арбитражными операциями (arbitrage) называется следующий способ извлекать прибыль из несогласованности курсов обмена валют. Предположим, что один доллар можно обменять на 0,7 фунта стерлингов, один фунт стерлингов - на 9,5 франков, и один франк - на 0,16 доллара. Тогда, обменивая 1 доллар в указанной последовательности, в результате можно получить 1,064 доллара и тем самым остаться с прибылью 6,4%. Пусть имеются га валют (пронумерованных от 1 до га) и массив R[l..n, 1..га], в котором записаны курсы обмена (единицу валюты г можно обменять на R[i,j] единиц валюты j). (а)Разработайте эффективный алгоритм, позволяющий выяснить, существует ли такая последовательность (ii, г2, , гк), что R[ii, i2\ R[i2, гз]R[ik-i, h] R[ik, ч] > 1- Оцените время работы вашего алгоритма. (б)Разработайте эффективный алгоритм, печатающий такую последовательность, если она существует. Оцените время его работы. 25-4 Алгоритм Габоу нахождения кратчайших путей с помощью масштабирования Пусть нам дан взвешенный ориентированный граф G = (V,E), в котором веса всех ребер являются целыми неотрицательными числами, не превосходящими W. Покажем, как можно найти кратчайшие пути из одной вершины за время O(ElgW). Пусть к = \lg(W + 1)1 - количество битов в двоичном представлении числа W. Для г = 1,2,..., к положим Wi(u,v) = \w(u,v)/2к~г\ (иными словами, Wi(u,v) получается из w(u, v) отбрасыванием к - г младших битов в двоичном представлении числа w(u,v)). Например, если к = 5 и w(u,v) = 25 = (11001), то ws(u,v) = (НО) = 6. В частности, w\ принимает только значения 0 и 1, определяемые старшим разрядом, a wk = w. Пусть Si(u,v) - вес кратчайшего пути из и в v относительно весовой функции иц (в частности, 5k(u,v) = S(u,v)). Алгоритм, о котором пойдёт речь в этой задаче, найдёт сначала все Si (s, v) (s - исходная вершина), затем все (s, и), и так далее, пока не дойдёт до Sk(s,v) = S(s,v). Далее мы полагаем, что \Е\ \V\ - 1; как мы увидим, стоимость нахождения Si при известном <S4- i есть О(Е), так что алгоритм будет работать за время О(кЕ) = O(ElgW). Такой план решения задачи - замена исходных данных их двоичными приближениями с последовательным уточнением - называется масштабированием (scaling) (а)Пусть S(s,v) \Е\ для всех вершин v £ V (предполагается, что \Е\ \V\ - 1 и веса являются целыми неотрицательными числами). Покажите, что можно найти S(s, v) для всех v £ V за время О(Е). (б)Покажите, что можно подсчитать Si(s,v) для всех v £ V за время 0(E). |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||||||||||||||||||||||||||||||||||||