БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

НАУЧНО-ПРАКТИЧЕСКИЕ КОНФЕРЕНЦИИ

<< ГЛАВНАЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ



Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 28 |

«ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ И СИСТЕМЫ Труды Третьей международной научной конференции Банное, Россия, 26 февраля — 2 марта 2014 года Научное электронное издание Челябинск ...»

-- [ Страница 5 ] --

ничное условие: f (x) = exp(ikx3), x G. Волновые чи- По результатам экспериментов можно сделать высла k1 = 1, k2 = 4, k3 = 7, k4 = 14, k5 = 21, k6 = 30. вод, что применение мозаично-скелетонного метода Количество точек дискретизации варьируется от при численном решении трехмерных задач Дирихле 1000 до 32 000. Каждая СЛАУ решается дважды: без для уравнения Гельмгольца, сформулированных в использования мозаично-скелетонного метода и с его виде граничных интегральных уравнений, сокращает использованием. В дальнейшем результаты вычисле- требования к ресурсам компьютера и позволяет суний, относящиеся к этим двум способам решения, щественно снизить общее время решения рассматриотмечены на рисунках выражениями «initial method» ваемых задач без потери точности. Это свидетельсти «mosaic method» соответственно. вует об эффективности предлагаемого подхода.

Блоки «дальней» зоны аппроксимируются с применением мозаично-скелетонного метода, = 104, блоки «ближней» зоны считаются по формулам исходного метода. На рис. 1 приведены графики зависимости времени решения СЛАУ в секундах от порядка матриц для разных волновых чисел.

Сравнивая результаты экспериментов, можно заметить, что применение мозаично-скелетонного метода дает существенное ускорение во времени. При этом исходный метод имеет второй порядок сложности, тогда как мозаично-скелетонный метод имеет почти линейную сложность, и при удвоении порядка СЛАУ время возрастает лишь в 2,5 раза.

Правильность работы метода проверялась с использованием известных аналитических решений интегральных уравнений и задач Дирихле [2]. ЭксА. А. Каширин, М. Ю. Талтыкина Использование мозаично-скелетонного метода при численном решении трехмерных задач Дирихле...

ЗАДАНИЕ ТРЕХМЕРНЫХ ОБЪЕКТОВ

В ПАМЯТИ КОМПЬЮТЕРА

Исследование поддержано грантами РФФИ 12-01-00748, НШ-1015.2014 и УрО РАН № 12-С-1-1018- Описывается экономный способ задания трехмерных объектов в памяти компьютера. Основная идея состоит в представлении многообразия в виде клеточного комплекса весьма специального вида и числовом кодировании этого комплекса. При этом кодирование является естественным, то есть позволяет работать с объектами без раскодирования.

Удобнее всего дать определение двумерного клеточного комплекса в несколько шагов.

1. 0-мерный клеточный комплекс X 0 — это конечное множество точек, называемых вершинами.

2. 1-мерный клеточный комплекс X 1 получается из 0-мерного приклеиванием нескольких 1-мерных клеток (т. е. дуг), причем концы дуг должны приклеиваться к вершинам, а дуги не должны иметь других общих точек. Другими словами, 1-мерный клеточный комплекс является графом, даже мультиграфом, поскольку петли и кратные ребра допускаются.

3. 2-мерный клеточный комплекс X 2 получается из 1-одномерного комплекса X 1 приклеиванием нескольких 2-мерных клеток. Каждая 2-клетка представляет собой двумерный диск, который приклеивается к X 1 по некотоОтметим, что информации о графе X1, ориентациях его ребер и порядке, в котором граничные окружно- Спайн называется специальным, если каждая его сти 2-клеток проходят по ребрам, вполне достаточно точка имеет окрестность одного из трех типов, изодля восстановления комплекса X2. Требуемые данные браженных на рис. 3.

можно записывать так. Сначала мы нумеруем вершины и кодируем ребра парами вида (i1, j1),..., (im, jm), где (ik, jk)$ — номера вершин, соединенных ребром с номером k, причем вершина ik является его началом, а вершина jk — его концом. Затем, для каждой 2-клетки регулярная точка тройная линия истинная величина мы выписываем последовательность ненулевых це- Рис. 3. К определению специального спайна лых чисел, которые показывают как граничная кривая рассматриваемой 2-клетки проходит по ребрам. Например, двумерный тор можно задать следующими строчками: ребра — (1,1), (1,1);

2-клетки — (1 2 –1 –2) и (1 –1 2 –2)$ (рис. 1). На самом деле, эта информация избыточна, поскольку строчка для ребер полностью восстанавливается по строчкам для 2-клеток.

2. Спайны трехмерных многообразий Определение. Компактный 2-мерный клеточный зия можно связать конечной цепочкой локальных преокомплекс P, лежащий внутри трехмерного многоо- бразований T и T –1, изображенных на рис. 4. Поскольку эти преобразования легко реализуются на уровне коди- ности 13, что намного превосходит зарубежные аналорующих строчек, то не только построение спайнов, но ги (около 100 тыс. многообразий против 12 тыс.).

и распознавание гомеоморфности отвечающих им мно- Все это можно прочитать в книге С. В. Матвеева гообразий можно выполнять с помощью компьютера. «Алгоритмическая топология и классификация трехИспользование этих моментов позволило коллек- мерных многообразий», которая является перевотиву кафедры компьютерной топологии и алгебры дом на русский язык книги S. Matveevа «Algorithmic Челябинского государственного университета соста- Topology and Classification of 3-manifolds», изданной в вить таблицу всех трехмерных многообразий до слож- Шпрингере в 2003 г. и переизданной там же в 2007 г.

С. В. Матвеев Задание трехмерных объектов в памяти компьютера

ОПТИМАЛЬНОЕ РАЗМЕЩЕНИЕ ДЕРЕВА

Рассмотрены два класса задач размещения дерева в конечном множестве: задача Вебера и квадратичная задача о назначении. Для решения задачи Вебера известен полиномиальный в сильном смысле алгоритм. Рассматриваемый частный случай квадратичной задачи о назначении остается NP-трудным в сильном смысле. Для ее решения построен псевдополиномиальный алгоритм, использующий алгоритм для задачи Вебера. Данный факт является доказательством совпадения классов NP и P. Показано, что сложность задачи «Гамильтонова цепь» в графе (V,E) не превосходит величины O(|V|6 log2|V|).

Рассматривается экстремальная задача (G,V,b,c,) представляет задачу Вебера, а внешняя — задачу выC() = jJ c( j,( j)) + [i, j]Eb([i, j]), пуклого программирования. Предложен алгоритм редля данных дерева G = (J,E), конечного множества V, отображения c: E V Z, отображения b: E V2 Z и множества допустимых размещений элементов множества J в точках множества V.

В случае = W = {: J V} (т. е. представляет все однозначные отображения) задача = W известна как задача Вебера для древовидной связывающей сети. Для ее решения известен [1;

2] полиномиальный алгоритм с вычислительной сложностью O(|J||V|2).

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

Если в (1) имеет место = Q = {: J V | (i, jJ)((i j)((i) ( j)))}, т. е. все инъективные однозначные отображения, то задача = Q представляет квадратичную задачу о назначении [3] с древовидной связывающей сетью.

Дана постановка задачи Q в виде задачи целочисленного линейного программирования. Доказано, что соответствующая релаксированная задача имеет целочисленное оптимальное решение. Для его поиска может быть использована схема декомпозиции по ограничениям [4], в которой внутренняя задача

О ПОСТРОЕНИИ МАРШРУТА ДВИЖЕНИЯ

РЕЖУЩЕГО ИНСТРУМЕНТА ПРИ УСЛОВИИ ВЫРЕЗАНИЯ

ТОЛЬКО СОСЕДНИХ ДЕТАЛЕЙ

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

При технологической подготовке процесса рас- тория движения режущего инструмента, Int(Ci) — откроя возникают различные ограничения на траекто- резанная от листа часть при прохождении режущим рию движения режущего инструмента. Так, в ранних инструментом части траектории. Тогда условие упоряработах автора [1] была рассмотрена задача постро- доченности охватывания означает, что отрезанная от ения маршрута, при котором отрезанная часть листа листа часть не требует дополнительных разрезаний.

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

ности на порядок вырезания деталей: будем продолжать вырезание только по примыкающему контуру.

Формальная постановка задачи может быть сделана в терминах теории графов. Положим, что на плоскости S задан плоский граф G = (V,E), и пусть f 0 — XT(G) — заданная система переходов, j = i – 1 или j = i + 1.

внешняя (бесконечная) грань графа G. Для любого Другими словами, в A-цепи возможен переход тольподмножества НG обозначим через Int(H) подмноже- ко на соседнее ребро, получающееся при вращении тество S, являющееся объединением всех связных ком- кущего ребра против часовой стрелки (либо по часовой понент множества S\H, не содержащих внешней грани стрелке). Например, для графа, приведенного на рис. 1, f 0. Множества вершин, ребер и граней графа G будем последовательность ребер v1e1v3e3v2e2v1e4v3e5v2e6v1 не обозначать через V(G), E(G) и F(G) соответственно, а является A-цепью, т. к. переход e2v1e4 осуществляется |S| — число элементов (мощность) множества S. не на соседнее ребро в циклическом порядке. ПослеОпределение 1 [1]. Будем говорить, что цикл C = довательность v1e4v2e5v3e6v1e1v3e3v2e2v1 будет A-цепью.

v1e1v2e2 … vk в эйлеровом графе G имеет упорядочен- Данная последовательность удовлетворяет и условию ное охватывание, если для любой его начальной ча- упорядоченного охватывания.

сти Ci = v1e1v2e2... ei, l (|E(G)|) выполнено условие В общем случае задача построения A-цепи являНапример, для плоского эйлерова графа, приведенного на рис. 1., цикл v1e1v3e3v2e2v1e4v3e5v2e6v1 удовлетворяет условию упорядоченного охватывания, а цикл v1e4v2e5v3e6v1e1v3e3v2e2v1 — не удовлетворяет, т. к.

ния интерпретируются следующим образом: S — раскраиваемый лист, G — раскройный план, C — траекТ. А. Панюкова О построении маршрута движения режущего инструмента при условии вырезания только соседних деталей формируют множество ребер Ek, имеющих ранг k для внешней грани графа G. Всем ребрам этого циисходного графа G, т. е. (eEk)(rank(e) = k). кла присвоить пометку k (таким образом, e Ck, Предложение. В плоском 4-регулярном графе су- kmark(e) k). Положить k = k + 1.

ществует A-цепь с упорядоченным охватыванием.

Доказательство. Рассмотрим систему переходов не помеченные ребра, перейти на шаг 2. В противном XT(G), соответствующую некоторой A-цепи в графе G. случае перейти на шаг 4.

Выберем произвольную вершину v0 f0 и построим из нее цикл C( f0) из ребер, смежных внешней грани (име- Выбрать первое ребро e1, инцидентное v0 и имеющее ющих ранг 1). Удалив все ребра eC( f0), получим k ранг 2. Положим, что v0 = v1(e1), в противном случае компонент связности, ребра которых имеют ранг боль- необходимо поменять индексы кодирующих функше 1. Причем, любая пара ребер ранга 2 будет иметь хотя бы одну общую вершину второй степени (этой вершине были инцидентны два ребра el,eC( f0)).

Построение A-цепи с упорядоченным охватыванием вершины v1(e) в вершину v2(e). В противном случае необследующим образом. Из вершины v0 f0, выбранной ходимо изменить направление прохода по ребру заменой в качестве начальной пройти по ребру e1: rank(e1) = 2. индексов задающих его функций на противоположные, В силу 4-регулярности графа, ребра, инцидентные начальной вершине, не могут иметь больший ранг. А ребра, инцидентные ребру e: rank(e) = k, не могут иметь полнение алгоритма A-цепь с упорядоченным охватываранг, отличающийся от k более чем на единицу. Далее, нием найдена, в противном случае, перейти на шаг 6.

используя рекурсивный алгоритм A1 [4], построим эйлерову цепь с упорядоченным охватыванием. Снова, в силу 4-регулярности графа G, на всех уровнях рекур- мальный возможный ранг и не пройденное ранее (не сии переход будет осуществляться на соседнее ребро большего ранга (если это возможно). Последнее ребро цепи, e|E|, будет смежно внешней грани, а следующим – e = l2(e), если kmark(r2(e)) kmark(l2(e));

для него в циклическом порядке будет начальное ребро – если kmark(r2(e)) = kmark(l2(e)) продолжить обe1. Таким образом, построенный эйлеров цикл с упоря- ход по любому из ребер, по возможности не повышая доченным охватыванием является и A-цепью. Предло- связности непройденного подграфа.

Рассмотрим алгоритм построения A-цепи с упорядоченным охватыванием для плоского 4-регулярного Рассмотрим вопрос сложности представленного Рис. 2. Представление ребер графа Входные данные: Граф G(V,E), представленный шестью функциями для каждого ребра (рис. 2):

– v1(e), v2(e) — вершины, инцидентные ребру e;

– l1(e), l2(e) — ребра, инцидентные вершинам vk(e) и получающиеся при вращении ребра e против часовой стрелки;

– r1(e), r2(e) — ребра, инцидентные вершинам vk(e), и получающиеся при вращении ребра e по часовой стрелке.

Выходные данные: A-цепь C с упорядоченным охватыванием.

Шаг 1. Положить k = 1 и G = G(V,E).

Шаг 2. Определить цикл Ck из ребер, смежных

ИСПОЛЬЗОВАНИЕ АЛГОРИТМА ПОИСКА В ШИРИНУ

ДЛЯ ОПРЕДЕЛЕНИЯ УРОВНЕЙ ВЛОЖЕННОСТИ

РЕБЕР ПЛОСКОГО ГРАФА

Формализована с точки зрения теории графов задача раскроя плоских материалов, определены понятия уровня вложенности ребер графа и условия упорядоченного охватывания. Был рассмотрен подход к определению уровней вложенности при помощи поиска в ширину в двойственном графе, а также скорректирован алгоритм определения маршрута режущего инструмента в соответствии с этим подходом.

В процессе технологической подготовки раскроя листовых материалов при подготовке маршрута вырезания важно обеспечить соответствие маршрута условию упорядоченного охватывания: каждая отделенная от заготовки часть не должна требовать дополнительной резки. В терминах теории графов раскройный план мо- ции rank(e), определяемой рекурсивно:

жет быть представлен плоским графом, грани которого соответствуют вырезаемым деталям, а ребра обозначают линии реза. Введем некоторые обозначения и определения, чтобы формализовать задачу раскроя. Вос- – ребра с уровнем вложенности 1 в графе Моделью раскройного листа будем считать плоскость S, моделью раскройного плана — плоский граф G с внешней гранью f0 на плоскости S. Для любой части графа J G (части траектории движения режущего инструмента) обозначим через Int(J) теоретико-множественное объединение его внутренних граней (объединение всех связных компонент множества S \ J, не содержащих внешней грани). Тогда Int(J) можно интерпретировать как отрезанную от листа часть. Множества вершин, ребер и граней графа J будем обозначать через V(J), E(J) и F(J) соответственно, а число элементов множества M — через |M|. При этом требуется, чтобы отрезанная от листа часть не требовала дополнительных разрезаний. В общем случае раскройный план представляет многосвязный граф, состоящий из вложенных компонент связности. Задача состоит в построении покрытия графа ребрами, учитывающего ограничения, наложенные практической задачей.

В соответствии с [2] будем говорить, что цепь ченное охватывание, если для любой его начальной Int(Cl) E =.

Также будем говорить, что последовательность C 0 = v0e0 v0 e0... e0 v0, C 1 = v1e1 v1 e1... e0 v0, Рис. 1 Функции, кодирующие ребра графа с упорядоченным охватыванием, покрывающая граф G и такая, что является покрытием с упорядоченным охватыванием.

Минимальную по мощности последовательность реберно-непересекающихся цепей с упорядоченЕ. А. Савицкий Использование алгоритма поиска в ширину для определения уровней вложенности ребер плоского графа Рис. 2. Уровни вложенности плоского графа Уровень вложенности ребра определяет его удаленность от внешней грани и показывает, какое минимальное число граней необходимо пересечь, чтобы добраться до заданного ребра. То есть уровень вложенности ребра можно определить как номер шага, на котором будет помечено ребро при поиске в ширину на двойственном графе (рис. 3). Поиск начинается с вершины, соответствующей внешней грани. Мосты в двойственном графе будут представлены как петли.

Рис. 3. Уровни вложенности ребер Алгоритмическая сложность предложенного метода не превысит O(|E|log|E|), т. к. используется ал- смежных ребер.



Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 28 |
 


Похожие материалы:

«МАТЕРИАЛЫ ВОСЬМОЙ НАУЧНО-ПРАКТИЧЕСКОЙ КОНФЕРЕНЦИИ Перспективные системы и задачи управления Таганрог 2013 Конференция “Перспективные системы и задачи управления” УДК 681.51 Материалы Восьмой Всероссийской научно-практической конференции Перспективные системы и задачи управления. – Таганрог: Изд-во ТТИ ЮФУ, 2013. – 378 с. Издание осуществлено при поддержке Российского фонда фундаментальных исследований, грант № 13-08-06015. ОРГАНИЗАТОРЫ Министерство обороны РФ; Министерство внутренних дел РФ; ...»

«3 Генеральный секретариат IRU 14 Организации-партнеры IRU 18 Автомобильный транспорт 19 Приоритетные задачи IRU: устойчивое развитие 20 Безопасность дорожного движения 20 Инновации 21 Академия IRU 26 Система стимулирования 30 Инфраструктура 32 Приоритетные задачи IRU: содействие развитию торговли, туризма и автотранспорта 34 Общий контекст и вопросы, связанные с торговлей 34 Содействие автомобильным перевозкам и вопросы безопасности 38 4-я Конференция IRU по автотранспортным перевозкам ...»

«08 основные операции 09 Агентство по распределению номеров Интернета 10 Группа DNS 10 Информационные технологии 10 Группа обеспечения безопасности 12 инициативы 13 Новые gTLD 13 Обзор Утверждения обязательств 15 Глобальное сотрудничество 15 Многоязычные доменные имена 16 Оценка строки IDN ccTLD 17 Программа грантов 17 Общественные конференции ICANN 18 Участие и привлечение 18 Программа для новичков ФотограФия на обложкЕ 19 консультативные советы и вспомогательные организации Члены совета ...»

«ИНТЕРВЬЮ с. 6–7 Дик Ватика: Расизм сдерживает развитие СОЦИАЛЬНЫЕ ПРЕОБРАЗОВАНИЯ с. 26 Новый этап в программе ЮНЕСКО МОСТ ДОСЬЕ с. 12–23 Молодежь создает завтрашний мир www.unesco.org/shs/views 2 Июнь/сентябрь 2007 ОТ РЕДАКЦИИ 17 Повышение роли молодежи – путь к устойчивому развитию Жить и видеть ту зарю – блаженство, но быть молодым – это ...»






 
© 2013 www.kon.libed.ru - «Бесплатная библиотека научно-практических конференций»