автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Теоретические и прикладные аспекты автоматизации технической подготовки производства цветных тканых узоров

БОРЗУНОВ ГЕОРГИЙ ИВАНОВИЧ

ТЕОРЕТИЧЕСКИЕ И ПРИКЛАДНЫЕ АСПЕКТЫ АВТОМАТИЗАЦИИ ТЕХНИЧЕСКОЙ ПОДГОТОВКИ ПРОИЗВОДСТВА ЦВЕТНЫХ ТКАНЫХ УЗОРОВ

004617993 Специальность:

05.13.06 - «Автоматизация и управление технологическими процессами и производствами (легкая промышленность)»,

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических наук

Москва-2010

1 6 ДЕК 2010

004617993

БОРЗУНОВ ГЕОРГИИ ИВАНОВИЧ

ТЕОРЕТИЧЕСКИЕ И ПРИКЛАДНЫЕ АСПЕКТЫ АВТОМАТИЗАЦИИ ТЕХНИЧЕСКОЙ ПОДГОТОВКИ ПРОИЗВОДСТВА ЦВЕТНЫХ ТКАНЫХ УЗОРОВ

Специальность:

05.13.06 - «Автоматизация и управление технологическими процессами и производствами (легкая промышленность)»,

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических наук

Москва-2010

Работа выполнена в Государственном образовательном учреждении высш профессионального образования «Московский государственный текстильн университет имени А.Н. Косыгина» на кафедре информационных технолог и компьютерного дизайна

Официальные оппоненты: доктор технических наук

Губин Виктор Владимирович

доктор технических наук, профессор Сапронов Михаил Иванович

доктор технических наук, профессор Юхин Сергей Семенович

Ведущая организация: ООО «МЕТРОТЕКС»

Защита состоится ц^РУ[! 2010 г. в^часов на заседании диссертационш совета Д 212.139.03 при Московском государственном текстильном унив^ ситете имени А.Н. Косыгина по адресу: 119071, Москва, М. Калужская ул.,

С диссертацией можно ознакомиться в библиотеке Государственного обра вательного учреждения высшего профессионального образования «Моею ский государственный текстильный университет имени А.Н. Косыгина»

Автореферат разослан « » XI_2010 г.

Ученый секретарь диссертационного совета доктор технических наук

Фирсов А. В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Опыт предприятий, устойчиво работающих в условиях современной рыночной экономики, свидетельствует о том, что для успешного расширения и быстрого обновления ассортимента выпускаемой продукции в современных условиях жесткой конкуренции текстильному предприятию необходимо выпускать ткани небольшими партиями при значительном разнообразии их художественного оформления (дизайна). Такая организация обновления и расширения ассортимента выпускаемых тканей требует значительных затрат на художественное проектирование, большого объёма технологических расчетов при технической подготовке производства и частых перезаправок ткацких станков. Единственный путь снижения указанных затрат - это широкое использование компьютерных технологий для автоматизации проектирования тканей и технической подготовки их производства. Таким образом, является актуальным исследование теоретических и прикладных аспектов проектирования тканых узоров, обеспечивающее разработку эффективных автоматизированных методов решения задач обновления ассортимента выпускаемых тканей.

Цель и задачи исследования.

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

Для достижения указанной цели решены следующие задачи:

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

- в соответствии с предложенной структурной схемой разработаны и исследованы алгоритмы выделения раппортов точечных изображений и понижения числа цветов в палитре изображения до заданного значения;

- разработана и исследована математическая модель структуры цветных точечных изображений и разработан алгоритм рационального преобразования точечных изображений;

- разработана и исследована математическая модель ткацких переплетений, которая, обеспечивает систематизацию и классификацию ткацких переплетений;

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

- разработаны теоретические основы расчета унифицированных сх проборок основ в ремиз;

- разработан алгоритм конструктивного перечисления вариантов р биения множества при монотонном возрастании числа подмножеств;

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

- разработана математическая модель, обеспечивающая количеств« ную оценку технологичности схем проборок основ в ремиз, и разработан ; горитм оптимизации сокращенных проборок;

- предложен метод построения моделей свойств тканей в условиях д< ствующего производства и вычислительная схема расчета рациональных I раметров строения ткани;

- предложен метод оптимального разделения графов на основе кон( руктивного перечисления разбиений множеств их вершин;

- подготовлено и осуществлено внедрение программных реализац основных теоретических результатов в Московском производственном ка вольного объединении «Октябрь».

Объектами исследования являются узоры многоцветных тканей, : правочные рисунки, а также цифровые изображения тканых узоров и р; пределённые вычисления.

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

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

Научная новизна работы заключается в следующих результатах:

- предложена структурная схема автоматизации рационального прое тирования и технической подготовки производства тканых узоров, воспро! водящих точечные изображения с помощью технологии ремизного ткачест)

- определены оценки временной сложности алгоритмов выделен раппортов в точечных изображениях;

- разработана методика понижения числа цветов в палитрах изобрая ний до заданных значений;

- разработана математическая модель структуры произвольных цве ных точечных изображений;

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

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

- предложена математическая модель ткацких переплетений ткачества, адекватно описывающая их структуру;

- разработаны теоретические основы расчета унифицированных заправок основ в ремиз;

- предложен метод оптимизации сокращенных проборок основ в ремиз

- предложен метод построения математических моделей в условиях действующего производства;

- разработан и исследован алгоритм генерации разбиений множества в порядке неубывания числа блоков (подмножеств);

- разработан алгоритм двоичного поиска минимального разбиения заданного множества и параллельный алгоритм поиска минимального разбиения заданного множества, получены оценки эффективности этих алгоритмов;

- впервые предложен метод расчёта оптимального числа процессоров, используемых для выполнения распределённых вычислений.

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

- разработаны алгоритмы выделения раппортов точечных изображений;

- предложена методика понижения числа цветов в палитрах изображений до заданных значений;

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

- разработана математическая модель ткацких переплетений, обеспечивающая отбор ткацких переплетений с заданными структурными признаками;

- предложен метод приведения сокращенных проборок к виду, обеспечивающему максимальную технологичность;

- разработан метод минимизации необходимого количества схем проборок основ в ремиз;

- предложен метод повышения эффективности распределённых вычислений за счёт использования оптимального числа процессоров.

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

Реализация результатов работы.

Разработанные алгоритмы реализованы в составе программного обеспечения САПР кареточных тканей "Логитрон 1002.СМ. Пакет прикладных программ для расчёта единых проборок основ в ремиз и оптимизации сокращенных проборок основ в ремиз внедрен в производство Московского производственного камвольного объединения «Октябрь». Внедрение и эффективность использования перечисленного выше программного обеспечения подтверждается актами и документами. Программный комплекс «Заправоч-

ный рисунок» используется в ГОУВПО «МГТУ им. А. Н. Косыгина» л разработки тканых узоров в курсовом и дипломном проектировании на i федре ткачества и при проведении лабораторных занятий по курсу «Компь терная обработка изображений» для студентов специальности № 23 004 ( Отдельные теоретические результаты работы и программные реализации е горитмов используются на кафедре информационных технологий и компь терного дизайна при подготовке и обновлении учебных курсов «Технолог программирования», «Компьютерная обработка изображений» и «Дискр( ная математика», а также в дипломном проектировании.

Апробация работы.

Основные результаты диссертационной работы докладывались и noi чили положительную оценку на международных и всероссийских научк технических конференциях: ТЕКСТИЛЬ - (Москва, 1995,1998, 1999, 20( 2002, 2004, 2008 гг., МГТУ им. А.Н. Косыгина), ПРОГРЕСС - (Ивано! 2005, 2008 гг., ИГТА), ПИКТЕЛ - (Иваново, 2003 г., ИГТА) на научных кс ференциях профессорско-преподавательского состава МГТУ им. А.Н. Кос гина, на Первой международной конференции «Трехмерная визуализац научной, технической и социальной реальности. Кластерные технологии и делирования» (Ижевск, 2009 г.).

Публикации.

Основные результаты работы отражены в 88 публикациях, в том чис 1 монография, 23 статьи в изданиях, рекомендованных ВАК РФ для публ кации. На программный комплекс «Заправочный рисунок» имеется свщ тельство о государственной регистрации №2006612092 в реестре програи для ЭВМ 16 июня 2006 г.

На защиту выносятся теоретические основы и результаты практик ской реализации перспективного направления применения компьютеры] технологий - автоматизации проектирования и технической подготовки пр изводства тканых узоров. Автор защищает:

- структурную схему автоматизированной проектирования и техни1 ской подготовки производства тканых узоров;

- результаты теоретического и экспериментального исследования ага ритмов выделения раппортов точечных изображений и понижения числа щ тов в палитрах изображений до заданных значений;

- математическую модель структуры произвольных цветных точечн] изображений и теоретические основы их преобразования в узоры, котор] могут быть выработаны с использованием однослойных ткацких перепле: ний;

- метод построения рационального заправочного рисунка;

- математическую модель ткацких переплетений и её применения д систематизации и классификации ткацких переплетений;

- теоретические основы расчета унифицированных заправок основ ремиз и метод минимизации необходимого числа заправок основ в ремиз;

- алгоритм генерации разбиений множества в порядке неубывания числа подмножеств;

- алгоритмы двоичного и параллельного поиска минимального разбиения;

- математическую модель и метод оптимизации сокращенных проборок основ в ремиз;

- метод определения оптимального числа процессоров при решении задач с использованием распределённых вычислений.

Структура и объём диссертации.

Диссертационная работа состоит из введения, семи глав, общих выводов по работе, списка использованной литературы, содержащего 196 наименований, и приложений на 32 листах. Основная часть изложена на 320 страницах, содержит 96 рисунков, 12 таблиц. Общий объём диссертации - 352 страницы.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Различные подходы к построению цветных тканых узоров были предложены Ф. Донатом, О. С. Кутеповым, Г.Л., Б. Лунд-Иверсен, О.С. А. А. Мартыновой, Г. Л. Слостина, С. В. Малецкой. В настоящее время автоматизированные методы проектирования узоров для ремизного ткачество объединяются в системы автоматизированного проектирования (САПР). Примерами отечественных разработок могут служить следующие системы: «Логи-трон 1002.СМ», «АРМ дессинатора» (МГТУ им. А.Н.Косыгина), «Дессина-тор 2.0» (ГП ЦНИИЖА), «Заправочный рисунок»). Среди зарубежных разработок наибольшее распространение получили системы: американская WeavePoint, канадская WeaveMaker Pro, испанская Fiberworks PCW Bronze, французская Lectra, NedGrhaphics. Современная тенденция развития САПР тканей заключается в том, что эти системы всё чаще ориентированы не только на проектирование (CAD - Computer-Aided Design - система автоматизированного проектирования), но и на генерацию управляющих программ управления ткацкими станками (САМ - Computer Aided Manufacturing - система автоматизированного производства). В другом направлении развивает интеграцию программного обеспечения своей системы фирма «Лектра». В 2009 году эта фирма представила на российском рынке инновационную версию своей системы Kaledo, которая представляет собой дизайн-платформу

для текстильной отрасли. Модуль Ка1ес1оТехШе позволяет имитировать ре листанное изображение тканых материалов. Кроме того этот программш модуль содержит инструменты для создания тканных и трикотажных мат риалов со сложным рисунком. В работе С. В. Малецкой предлагается ко плекс автоматизированных методов, совокупность которых может рассмг риваться как автоматизированная система проектирования пестроткан Функциональность этой системы обеспечивает автоматизированное пострс ние узоров однослойных и двусторонних тканей, а также выполнение запр вочных расчётов. Применение компьютеров позволило поставить и реши ряд новых задач, относящихся к различным аспектам проектирования ткане В работах С. Д. Николаева, С. С. Юхина, Г. Н. Муратовой, А. В. Фирсова б] ли предложены методы решения новых задач, реализация которых была б невозможна без использования компьютерных технологий. Применение ра пределённых вычислений открывает перед исследователями новые возмо; ности по расширению области применения автоматизированных. Однак аффективное применение распределённых вычислений требует специально планирования и управления вычислительным процессом. В предложенной 1 В. Малецкой САПР пестроткани системе, как в других рассмотренных си темах, отсутствуют средства предварительной обработки точечных изобр жений, необходимой для подготовки воспроизведения этих изображений использованием ремизного ткачества. Анализ доступных источников инфо мации показал, что практически отсутствуют работы по применению распр делённых вычислений в автоматизированных методах проектирования тк ных узоров. Теоретическим и практическим аспектам создания указаннь средств обработки точечных изображений, а также вопросам применеш распределённых вычислений при решении задач проектирования тканых уз ров посвящена данная диссертация.

Во второй главе рассмотрены алгоритмические основы предварител ной обработки точечных изображений.

В современной практике проектирования художественного оформл ния ремизных тканей исходные точечные изображения тканых рисунков ч ще всего создаются дессинаторами (художниками) в среде графического р дактора или получаются в результате либо цифрового фотографировани либо сканирования твердых копий рисунков. Для определения задач, реш ние которых требуется для технической подготовки таких изображений с и пользованием технологии ремизного ткачества структурная схема автомат; зированной системы (Рис. 1). Ниже описываются математические модели алгоритмы, обеспечивающие решение задач, определенных этой схемо Пусть точечное изображение представляется целочисленным двумерны массивом А[т][п], где п - ширина исходного рисунка, а т- высота.

АСПТ ТКАНЫХ УЗОРОВ

Предварительная обработка изображений

Заправочный расчет

Расчет параметров строения

Расчет заправочных параметров

Получение технологически " допустимого избражения

Расчет шаблона переплетения

Удаление

запрещенных фигур

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

Построение заправочного рисунка

Расчет рационального заправочного рисунка

Расчет унифицированных схем проборок основ в ремиз

Оптимизация сокращенных проборок основ в ремиз

Рис. 1. Структурная схема автоматизированной системы технической подготовки производства тканых узоров

Элементы массива А[т][п] могут принимать значения от 0 до 255, а раппорт представляется целочисленным массивом К[шг][пг], который получается из части массива А[т][п]: &>г(1=0; ¡<шг; ¡++) Вэг(]=0; ]<пг; ]++) {1а=(1ё+1)/%т; =0с1+])/%п; ЯЩИ = Р(А[1а][)а]);}, где БО - функция обра-

ботки, (id, jd) - координаты левого верхнего угла области A[m][n], из кот рой образуется раппорт R[mr][nr], «%» - здесь и далее представляет co6i операцию деления для получения остатка. Ширина пг может меняться от 2,, п/2, а высота шг - от 2 до т/2. Покрытием изображения А[ш][п] точка! раппорта R[mr][nr] называется массив V[m][n], который образуется R[mr][nr] в результате следующих вычислений: for(i=0; i<m; i++) for(j=0; j<i ++) {if(i>id)ir=(i-id)%mr; else ir=mr-(id-i)°/omr; if(j>jd) jr=(j-jd)°/onr; else jr=r (jd-j)%nr; V[i][j]=R[ir][jr]}. Возможные раппорты будем оценивать по их п крытиям исходных изображений с помощью функции несовпадений W: i W(A [m][n], V[m][n]) {int s=0; for(int i=0;i<m;i++) for(int j=0;j<n;j+ {if(A[i][j]<V[i][j]) s+= V[i][j] - A[i][j]; else s+= A[i][j] - V[i][j];} return s;}. T перь задача выделения раппорта заключается в определении для заданно исходного изображения A[m][n] раппорта минимальных размеров R[mr][n такого что W(A[m][n],V[m][n]) —► min. Изображения, для которых существ ет R[mr][nr] такой что W(A[m][n],V[m][n])=0, будут называться изображ ниями класса 1. Второй класс изображений характеризуется тем, что знач ние функции несовпадений больше нуля: W(A [m][n],V[m][n])>0. Рассмотри определение раппортов изображений класса 1. Определим функцию несовп дений: int Wl(mr, nr, A [m][n]) { int ir, jr; for(int i= 0; i<m; i++) { ir = i%n for(int j=0; j<n; j++) {jr = j%nr; if (A[i][j] Ф A[ir][jr])return 1;}} return 0;}. Д. перечисления R[mr][nr] в порядке возрастания их размеров введём переме ную рг, значение которой равно «полупериметру массива R[mr][nr] pr=mr+nr. Тогда псевдокод алгоритма определения раппортов изображен! класса 1 будет иметь вид функции Rptl: int mr=0, nr=0; /* переменные mr, - глобальные */ void Rptl(A [m][n]) {int pr=0, prmax=m/2+n/2; for(pr= pr<prmax; pr++) {mr=2; nr=pr-mr; if(nr>n/2){nr=n/2; mr=pr-m while(mr<m/2&&nr>2) { if(Wl(mr, nr, A [m][n]) = 0) return; mr++; nr-; mr=nr=0; return;}. Если после завершения Rptl значения переменных mr, неравны нулю, то выполняется присваивание R[mr][nr] = A[mr][nr]. При р венстве нулю значений переменных mr, nr для данного A [m][n] не существ ет раппорта, точное повторение которого покрывает это изображение. Аси] птотическая оценка временной сложности алгоритма Rptl в худшем случ оказывается равной ТЗ(К)= 0(К4). Для выделения раппортов изображен! класса 2 был разработан Rpt2, который отличается от алгоритма Rptl те что в процессе его работы окно, выделяющее в качестве раппортов прям угольные фрагменты изображения, не только принимает все возможные ра меры, но размещается всеми возможными способами относительно изобр жения. Временная сложность алгоритма Rpt2 в худшем оказывается равнс Т5=0(К6). Оценки временной сложности Rptl, Rpt2 явились основанием д: разработки быстрых алгоритмов: Rpt3 - для выделения раппортов изображ ний класса 1 и Rpt4 - для выделения раппортов класса 2. Эти алгоритмы в о личии от простейших алгоритмов выполняют анализ изображения с пом щью окна, имеющего форму горизонтальной полосы. Данные вычислител ного эксперимента подтверждают результаты теоретического анализа: по»

раппорта с помощью алгоритма Яр14 значительно (на 3 порядка) быстрее стандартного поиска раппорта с помощью алгоритма Яр12.

Рис. 2. Пример применения алгоритма (^4.

Следующим этапом предварительной обработки изображений согласно предлагаемой структурной схеме является переход от недопустимо большой палитры цветов исходного изображения к палитре, содержащей меньшее число цветов (например, 10-20 цветов). Результаты исследования средств графических редакторов общего назначения свидетельствуют о том, при понижении числа цветов до 8 сохраняются основные цвета, определяющие колористическое решение и основные структурные особенности изображения. Экспериментальные исследования метода усечённого блочного кодирования показали, что этот метод может применяться для получения потенциально допустимых изображений в сочетании с другими методами редукции цвета. Понижение физической глубины цвета за счёт редукции разрядов 4-х разрядов в большинстве случаях несущественно изменяет восприятия изображения (см. рис. 3). Для эффективного понижения числа цветов изображений предлагается комплексный подход - методика, состоящая из следующих шагов:

1. Определяется, является ли исходное изображение тёмным или светлым. Для этого исходное изображение должно быть преобразовано, например, в формат ШВ, разделено на каналы Н, Б, В. Затем для канала В стоится гистограмма и определяется среднее значение. Если среднее значение меньше 128, то имеет место тёмное изображение; иначе исходное изображение является светлым.

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

3. Выполняется статистический анализ изображения, и строится гистограмма. В ходе такого анализа в памяти программы создается массив храня-

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

4. Выделяются п - наиболее часто встречающихся (основных) цвето которые после сортировки занимают первые позиции в отсортированнс массиве.

¿¿-.с-*-

а, 4 <и'- * ■'-> —■

И г

'.-ГЭ- .V Ь ¡■Г' ••' »¿1«, ...

Рис. 3. Исходные изображения (слева) и изображения после заполнения н} лями 4 младших разрядов

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

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

Ниже приводится пример матричного представления рисунка, которы невозможно выработать с помощью однослойного переплетения, т. е. он н является технологически допустимым изображением: "3 2 1

С,=

С другой стороны, один и тот же цветной узор Сг можно выработать с использованием различных комбинаций переплетений и цветных раппортов п< основе и утку. В таблицах 1, 2 приводятся варианта сочетаний раппорто переплетений и раппортов цвета по основе и утку, обеспечивающих выработку рисунка, заданного матрицей С2■

3 3 3 3 2 2 2 2 ' 1 1 1 1

Поставим в соответствие каждому элементу матрицы шц (здесь 1 - номер строки матрицы, j - номер её столбца), представляющей собой цветной узор, вершину графа ау. Соединим ребрами весом 1 все вершины, соответствующие неравным элементам одного и того же столбца указанной матрицы и весом 0 — все вершины, соответствующие неравным элементам одной и той же строки. Полученный граф назовем графом структуры точечного изображения. На рис. 4 приводится граф структуры цветного узора, заданного матрицей С].

Таблица 1 Таблица 2

3 3 3 3

3 3 3 3

2 2 2 2

2 2 2 2

1 1 1 1

1 1 1 1

Цвет утка Переплетение

3 0 0 0 0 1 1

3 0 0 0 0 1 1

2 0 0 1 1 0 0

2 0 0 1 1 0 0

1 1 1 0 0 0 0

1 1 1 0 0 0 0

Цвет 1 1 2 2 3 3

основы

Цвет утка Переплетение

3 0 0 1

г 0 0 1

2 0 1 0

2 0 1 0

1 1 0 0

1 1 0 0

Цвет основы 1 2 3

В терминах предложенной математической модели определяется необходимое условие существования сочетания однослойного ткацкого переплетения и раппортов цвета по основе и утку, обеспечивающее выработку заданного точечного изображения. Этим необходимым условием является возможность правильной раскраске вершин графа структуры заданного точечного изображения в два цвета, которые обозначим нулем и единицей при соблюдении следующих условий: 1) две вершины, соединенные ребром, имеющим вес О, не могут быть обе окрашены в цвет 0; 2) вершины, соединённые ребром с весом равным 1, не могут быть обе окрашены соответственно в цвет 1.

О

Будем называть суграфом часть графа, которая получается из исход» го графа после удаления некоторых рёбер при сохранении всех вершин и ходного графа. Для определения условий существования правильной ра краски выделим из графа структуры в изображения суграф вО, содержащг все ребра с весом 0 и только эти рёбра, а также суграф содержащий в< ребра с весом 1 и только эти рёбра. Рассмотрим объединение суграфов Со С/ и их композиции, вид которых определяется выражениями 1- 4:

Соо =(С0°С,) и((Со0С!)х(Оо°С1)) и..и((во°С!)°(Со0С1)°..°(Оо°С1)) (1)

С01 = О0и (С0° (С,° С0)) и., и (С0° (С,° С„) °... 0 (в,а С0)) (2)

С10 -С, V (С,0 (С0а С,)) V.. V (С,0 (С0° С,) °... 0 (С0° С,)) (3)

Си = (С1°Со) V ((С,°С0)°(С,°О0))и.. и ((С;°С0)°(С,°С0)а... ° (С,0 С0)) (4)

Построение графов С00, С01, Сю, Сц основано на использовании алг< ритма транзитивного замыкания Уоршелла. С учётом размерности матриц А А\ временная сложность алгоритма Уоршелла оценивается как Г4д=0(т3хп3 а при т=п Г4>2=0(тб). Для существования правильной раскраски графа стру] туры изображения необходимо выполнение следующих двух утверждений:

1. Любая вершина 1 структурного графа может быть окрашена в цвет тогда и только тогда, когда для любой вершины j того же графа справедлив! что дуга (у) не принадлежит одновременно бщ и £/ц-

2. Любая вершина 1 структурного графа может быть окрашена в цвет тогда и только тогда, когда для любой вершины j того же графа справедлив! что дуга 0не принадлежит одновременно (30о и С0\.

Пусть графы Сю, Си, Соо, Сл представляются в памяти компьютера в ввд матриц смежности вершин А10, А11, А00, А01, в которых наличие дуги (ц обозначается I на пересечении строки со столбцом соответствующей матрр цы. Все эти матрицы являются квадратными с числом строк и числом стол( цов равным пш= шхп, где т - число строк в матрице цветного изображени: а п - число столбцов в этой матрице. Следующий шаг анализа точечного изс

бражения состоит в определении матрицы эскиза переплетения D, размерность которой совпадает с размерностью матрицы, с помощью которой было определено исходное изображение. В этой матрице элементы могут принимать следующие значения: элементы равные 0, определяют позицию, которую в переплетении может занимать только уточное перекрытие; элементы равные 1 соответственно определяют позицию, в которой может размещаться только основное перекрытие; элементы равные Ei6 (шестнадцатиричное значение) определяют позицию, в которой могут располагаться уточное или основное перекрытия; наконец, элементы равные Fig определяют позицию коллизии, т. е. позицию в которой не может быть ни уточного, ни основного перекрытия. При наличии коллизий возникает задача рациональной коррекции исходного рисунка за счёт изменения цвета одной или нескольких точек этого рисунка. Справедливо следующее утверждение. В изображении имеет место коллизия, если в графе структуры изображения существует вершина i, для которой найдутся вершины j и к, соединённые с вершиной i с вершинами четырьмя маршрутами: ((i, Pi. 0), (рЬ р2, 1),... ,(Р2ш-2, Р2т-1,0), (р2т-1, Р2т, О, (Р2т, к,0)); (5)

((i, qi, 0), (qb q2, 1), ... ,(q2n-2, q2n-i,0), (q2n-b к , 1)); (6)

3) ((i, vb 1), (vb v2, 0),... , (v2s-2> v2s.i,l), (v2s-i, v2s, 0), (v2s, j, 1)); (7)

4) ((i, wb 1), (wb w2, 0),... ,(w2t.2, w2M, 1), (w2t.,, j, 0)). (8)

При наличии в графе маршрутов (5-6) можно выделить два цикла нечётной длины, один из которых начинается и заканчивается рёбрами с весом 0, а другой начинается и заканчивается рёбрами с весом 1:

((аз,1> аз,з, 0) (а33, а2-3, 1) (а2,3, а2>2, 0) (а2,2, а3>2, 1) (a3j2, а3>1, 0)); (7) ((а3,ь ai,i> 1) (ai.i, al2, 0) (а1>2, а2>2,1) (a2j2 a2jI, 0) (а2,ь а3,ь 1)). (8) Таким образом, для выполнения необходимого условия существования ткацкого переплетения, обеспечивающего выработку заданного рисунка необходимо отсутствие в графе структуры рисунка запрещённых фигур: циклов нечетной длины проходящих через оду и ту же вершину в соответствии с (7,6). На основании этого подхода разработаны алгоритмы Bsf и DelCycles, обеспечивающие устранение из графа структуры изображения всех запрещённых фигур при близком к минимальному количестве удаляемых рёбер. На рис. 5 приводится раппорт изображения, граф структуры которого содержит запрещённые фигуры, а на рис. 6 раппорт того же изображения после удаления запрещённых фигур с помощью алгоритмов Bsf и DelCycles. Сравнение рис. 5 и рис. 6 показывает, что изображения на этих рисунках практически совпадают. Вычислительный эксперимент подтвердил эффективность разработанных алгоритмов и одновременно их большую временную сложность: 0(тЗхпЗ). Для расширения диапазона практически решаемых задач такая временная сложность требует использования методов параллельного программирования.

Рис. 5. Исходное изображение Рис.6. Изображение без запрещенных фигур

Четвертая глава посвящена разработке математических основ моделирования ткацких переплетений и автоматизированного метода расчёта рациональных заправочных рисунков.

Пусть дан раппорт сатина 5/2, содержащий пять нитей основы и пять нитей утка. Поставим в соответствие каждой ¡-ой нити основы из раппорта переплетения вершину 01, а каждой ]-ой нити утка из того же раппорта вершину У^ где ¡=1,2, ...,5, а ]= 1,2,... ,5. Соединим звеньями (неориентированными рёбрами) каждую вершину 01 - с вершиной Ом (¡=1,2,... ,4) и каждую вершину Yj с вершиной У]+1 (] =1,2,.. .,4), а также 05 с О! и У5 с Уь Соединим дугой (ориентированным ребром) каждую вершину 01 с вершиной У, только в случае, когда ¡-ая нить основы перекрывает в пределах раппорта ]-ую нить утка. Полученный граф назовем графом структуры данного ткацкого переплетения или просто структурным графом (рис. 7). Любому представлению раппорта ткацкого переплетения однозначно соответствует некоторый граф структуры ткацкого переплетения. Разным представлениям одного и того же переплетения соответствуют изоморфные структурные графы. Пусть основным циклом называется минимальный по длине цикл, который не содержит повторяющихся вершин и проходит по неориентированному ребру (звену), соединяющему две смежные вершины из множества О, затем по ориентированному ребру, соединяющему вершину из множества О с вершиной из множества У, далее по неориентированным ребрам (звеньям), соединяющим вершины из множества Г и, наконец, по ориентированному ребру (против направления ребра), идущему из некоторой вершины, принадлежащей множеству У, в исходную вершину из множества О. Аналогично определяется уточный цикл.

Рис. 6. Граф структуры сатина 5/2.

Например, в графе, приведенном на рис. 6, цикл, проходящий по вершинам 0\, Оъ Уз, 5*2» У\, 0\, является основным. Уточный цикл в этом графе проходит по тем же вершинам, но в другой последовательности: Уъ Уз, Оъ Оъ, 0^,У2. Сравнение длины основных и уточных циклов структурных графов приводит к общепринятой классификации ткацких переплетений. Так, главным переплетениям соответствуют однородные структурные графы со степенью вершин, равной трем, и одинаковой длиной всех основных или уточных циклов. Назовем такие графы главными структурными графами. Главные структурные графы, имеющие основные и уточные циклы, равные четырем, соответствуют полотняным или саржевым переплетениям. При длине основных или уточных циклов более четырех главные структурные графы представляют сатиновые переплетения. Разницу в длине основного и уточного циклов в главных структурных графах, имеющих одинаковое число вершин, можно использовать для оценки равномерности размещения основных перекрытий в соответствующих ткацких переплетениях. Получаемый в результате анализа точечных изображений эскиз переплетения в сочетании с технологическими ограничениями на К[М][М], позволяет отсечь недостроенные варианты Я[М][Ы], завершение которых не приводит к желаемому результату. Это делает возможным для заданного тканого узора применение конструктивного перебора вариантов переплетений определяемых Я[М][М], с целью выбора переплетения, в максимальной степени удовлетворяющего технологическим требованиям. Для реализации этого подхода был предложен алгоритм 1УЕА УЕ, генерирующий матрицы II в два этапа: выполняется построение первого варианта матрицы К, удовлетворяющего заданным ограничениям; конструктивное перечисляются все последующие решения. При невозможности построить первый вариант матрицы Я, определяются неверно заданные ограничения. Функция \veave621 осуществляет проверку соответствия рабочих данных заданным ограничениям, \veave622 корректировку рабо-

чих данных после определения очередного элемента R. Функция weave621 осуществляет проверку соответствия рабочих данных заданным ограничениям, weave622 - коррекцию рабочих данных при записи в W нового элемента, weave623 - коррекцию рабочих данных при обратном движении.

//Начало псевдокода алгоритма

weave620(); //Восстановление рабочих данных ////////////***** Построение первого решения *******///////////// for(J=l; J < = М; J++) { for(I=N; I > 0; I--) {If(D[I][J]=0xE) { // Проверка возможности присвоения R нулевого значения K=0;if(weave621()){R[I][J]=K;weave622();gotoetka2;} // Проверка возможности присвоения R единичного значения K=l; if(weave621()){ R [I][I]=K; weave622(); gotometka2;} ///////////**** Переход на новую ветвь***//// // поиск элемента R, который можно изменить for(J2=l; J2 < = J; J2++) { for(I2=N; 12 > 0; 12-) { If((D[I2][J2]==0xE)){ if(R[I2][J2]==0) { K=l; if(weave621()){R[I2][I2]=K; weave623(); go to metkal;}} // проверка возможности размещения нулевых значений else{ К=0; if(weave621()){ R[I2]tI2]=K;weave623(); go to metkal;}} //end else }// end of If((D[I2][J2]==0xE))

// Проверка возможности присвоения R нулевого значения

metkal: К=0; if(weave621()) { R[I][J]=K; weave622(); go to metka2;}

// Проверка возможности присвоения R единичного значения

K=l; if(weave621()) { R[I][I]=K; weave622(); gotometka2;}

if((J2=J)&&(I2=I)) stop; //неверны исходные данные

} } //evd of for(J2=l; J2 < = J; J2++)

stop; // неверны исходные данные

metka2:} } // end of for(I=N; I > 0; I--)

Use R; // Получено решение

///////////***** Конец построения первого решения *******////

//////***Начало генерации остальных решений**///////

flag = true; while(flag){flag = false; for(J=l; J2 < = M; J++) { for(I= N; I > 0; I--) {If(D [I] [J] ==OxE) {

// Проверка возможности присвоения R единичного значения

If(R[l][J]==0) {K=l; if(weave621()) { R[I][I]=K; weave623(); flag = true;

USE R; go to metka3;} // Получено решение

}//end of If(R[I][J]==0)

// Проверка возможности присвоения R нулевого значения

К=0; if(weave621()) { R[I][J]=K; weave623();}} //end of If(D[I][J]=0xE)

}} flag = false; metka3: } // end of while(flag)

///////////////******** Конец псевдокода алгоритма *******////////////

Для определения матриц, которым соответствуют однослойные переплетения, предлагается метод, основанный на анализе графов структуры переплетений:

1. Из графа структуры ткацкого переплетения G(0, Y, U), заданного множествами вершин О, Y и множеством рёбер U, удаляются неориентированные рёбра:£/, = £Л {{ О,, Oi+1 }, i = (1,2,..., и-1»\ { Оп, О, }\{{ Yj, Yi+I },j =1,2,..., т— 1}\{ Ym , Yj). При этом G(0, Y, U) граф U превращается в двудольный ориентированный граф G\(0, Y, U\), где множество рёбер состоит из дуг, соединяющие одну из вершин множества О с некоторой вершиной из множества Y: U\ = {(0¡, F¡)}.

2. Затем множество дуг U\ графа G\(0, Y, U\) пополняется дугами вида (Yj, 0¡), если в £/, нет дуги вида (Oí, 7¡): Е= U\ u{ (Y¡, 0¡) | (0¡, Y¡) e £/,}.

В результате пополнения множества рёбер граф G\(0, Y, U\) превращается в ориентированный граф Q(0, Y, Е. Такой граф Q здесь и ниже будем называть графом связности переплетения, соответствующего графу структуры переплетения G, из которого был получен граф Q. В памяти компьютера граф Q может быть представлен в виде модифицированной матрицы смежности, в которой элементы могут принимать следующие значения: элемент равный -1, стоящий на пересечении /-той строки и у'-того столбца(а^==-1), определяет наличие в графе <2(0, Г,Е) дуги, идущей из вершины 0-, в вершину Y¡, элемент равный +1, стоящий на пересечении г'-той строки и у'-того столбца (a¡¡==l), означает дугу, идущую из вершины Y¡ в вершину 0¡.

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

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

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

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

Минимальное число ремизок, необходимых для выработки к заданных тканей по единой проборке, равно числу классов эквивалентностей г= \Х1д\, где X. - множество нитей основы; д= ^Пс^П ^¡(¡=1, 2, ..., к) - эквива-

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

1. Положить .сгд\\

2. Положить ;=1;.

3. Выполнить д -дПд'ц

4.. Если [Х/д]>т, то единой проборки не существует, стоп.

5. Выполнить г++;.

6. Если 1<к, то перейти к п.З;

7. Единая проборка определяется эквивалентностью д, СТОП.

Как видно из приведенного описания алгоритма, в результате решение задачи по данному алгоритму либо получается единая проборка для выработки заданных тканей, либо доказывается, что такой проборки не существует. Если в результате применения рассмотренного выше алгоритма было установлено, что при заданных условиях унифицированная проборка не существует, возникает задача поиска разбиения заданного множества сопряжённых эквивалентности д\, дг, ..., д^ на минимальное число непересекающихся подмножеств при условии, для каждого подмножества существует унифицированная проборка. Ниже приводится псевдокод алгоритма решения этой задачи, в котором используются обозначения: э - число сопряженных эквивалентностей; п - число нитей основы в заправке; т - число доступных ремизок, Х={х1, Х2х„} - множество нитей основы в заправке; Е={е|, е2,..., е5} -множество сопряженных эквивалентностей, каждая из которых (еО разбивает множество X на непустые и непересекающиеся классы или подмножества X1!, Х'2, ..., Х'к (Х/^={Х'Ь Х'2, ..., Х'и}) т. о., что все нити основы одного класса Х^ (]=1, 2, ..., 1а) могут быть пробраны в одну ремизку; |Х/е;1 - число подмножеств в разбиении Х/е,- ; р^ - эквивалентность равная пересечению всех эквивалентностей, которые составляют подмножество Е'^. (¡=1, 2, ..., 1:1), принадлежащее разбиению ЕА}ь Любое разбиение q¡ называется допустимым; если оно разбивает множество Е на такие непустые и непересекающиеся

классы, что УЕ^ еЕ/д,:|Х/р'^<т. Допустимое разбиение q¡ еЦ, состоящее из минимального числа подмножеств множества Е, называется минимальным допустимым разбиением и обозначается qmin. Ниже приводится обобщенное описание алгоритма решения этой задачи;

1. Пусть допустимое разбиение qr есть разбиение множества Е на в классов (такое разбиение всегда является допустимьм), переменная г принимает значение равное числу классов в текущем допустимом разбиении г=з, а текущее разбиение qi множества Е состоит из единственного класса, и переменная п принимает значение равное числу классов в этом разбиении: п=1.

2. Если п< г, то с помощью функции проверяется, является ли разбиение допустимым. Если разбиение qi является допустимым (РС^)==1), то выполняется переход к п.З; иначе, т. е. при РС^)==0 - переход к п. 4.

3. Запоминаются новые значения и г=п.

4. Для получения нового варианта разбиения используется функция БС), которая возвращает в качестве своего значения либо число классов и описание нового разбиения, либо нуль, если все возможные варианты разбиения уже перечислены: п=Р<3^).

5. Если п=0, то выполняется переход к п.6; иначе - переход к п.2.

6. Поиск завершается и в качестве решения принимается разбиение qr, состоящее из г непересекающихся и непустых подмножеств:qmin=qr. Стоп.

В шестой главе рассматриваются методы повышения эффективности распределённых вычислений.

Естественной математической моделью, на основании которой решается задача балансировки вычислительной нагрузки является взвешенный граф. В этом графе вершины соответствуют подзадачам, вес вершин моделирует временную сложность подзадач, а вес рёбер моделирует объём передаваемой информации. Задача эффективного планирования вычислений состоит в разбиения вершин графа на непересекающиеся подмножества с максимально близкими значениями суммарных весов вершин подмножеств при минимальном значении суммы весов ребер, соединяющих вершины, принадлежащие разным подмножествам. При этом каждое подмножество вершин ставится в соответствие некоторому процессору. В данной работе анализируются спектральные, графические и многоуровневые методы разделения таких графов. Далее описывается разработка базовых алгоритмов конструктивного перечисления разбиений множеств создание на их основе метода оптимального разделения взвешенных графов. Алгоритм Ея2_1, последовательно генерирует варианты разбиения множества в порядке монотонного возрастания числа подмножеств, и для управления его работой используются два новых параметра: пэ и п£ Значение параметра ш определяет начальное (минимальное) значение числа подмножеств в генерируемых разбиениях, а значение параметра пТ - конечное (максимальное) значение числа подмножеств в генерируемых разбиениях. Использование алгоритма Ец2_1 обеспечивает возможность генерации разбиений не подряд, а выборочно, что позволяет использовать при поиске минимальных разбиений схему двоичного поиска.

Ниже приводится алгоритм двоичного поиска минимальных разбиений EQ3_1, в котором значение i-той координаты вектора pChi определяет номер класса, включающего в себя i-тый элемент разбиваемого множества.

1. Пусть исходное множество X содержит п элементов. Положить ns=l, nf=n, Р=(0,0Д.. .,0), где Р - характеристический вектор.

2. Положить np=nf. Используя алгоритм EQ2_1, выполнить поиск допустимого разбиения множества X на пр частей. Если найден характеристический вектор допустимого разбиения pChi, то выполнить: {Р= pChi; nf~;} иначе решения не существует, стоп.

3. Выполнить np= (nf + ns)/2. Здесь деление выполняется нацело, т. е. с отбрасыванием остатка. Используя алгоритм EQ2_1, выполнить поиск допустимого разбиения множества X на пр частей. Если найден характеристический вектор допустимого разбиения pChi, то выполнить: Р= pChi; иначе перейти к п.5.

4. Положить nf = пр; если ns < nf, то перейти к п. 3; иначе Р - характеристический вектор минимального разбиения множества X, стоп,

5. Если ns < nf, то выполнить ns= пр+1; иначе Р - характеристический вектор минимального разбиения множества X, стоп,

6. Выполнить np= (nf + ns)/2. Деление выполняется нацело. Используя алгоритм EQ2_1, выполнить поиск допустимого разбиения множества X н пр частей. Если найден характеристический вектор допустимого разбиени: pChi, то выполнить: { Р= pChi и перейти к п. 4;} иначе перейти к п. 5.

Использование алгоритма EQ3_1 обеспечивает уменьшение временно] сложности решения данной задачи в 2 -3 раза. На основе алгоритма EQ2_ впервые разработана вычислительная схема параллельного поиска мини мального разбиения (алгоритм EQ4_1).:

1. Пусть п - число элементов в исходном множестве X; р - число про цессоров, доступных для выполнения поиска; fp[n] -вектор активных про цессоров: nsp[i], nfp[i]- соответственно начальное (минимальное) и конечно! (максимальное) числа подмножеств в разбиениях при поиске, который реали зуется с использованием i - того процессора; pChi[i], np[i] - характеристиче ский вектор разбиения, удовлетворяющем заданным ограничениям, и теку щее число подмножеств в этом разбиении; icp - номер процессора, с исполь зованием которого найдено минимальное разбиение; i, ii, - управляющие па раметры циклов; к - рабочая переменная; ms[i] - сообщение i - того процес сора о завершении его работы; pChiMin, npMin - характеристический векто] минимального разбиения и число подмножеств в этом разбиении.

2. Центральный процессор определяет диапазоны поиска nsp[i], nfp[i для р процессоров, передает им эти значения и активизирует их работу icp =р; fp[]= (0, 0,..., 0); pChiMin =(1,2,..., n); k =n/p; nsp[0]=l; nfp[0]=k-l; for(i=l;i< p;i++) { nsp[i]+= к; nfp[i]+=k; передать nsp[i], nfp[i] процессор; P[i]; fp[i] =1; активизировать P[i]}

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

Parallel Start

for(ii=l;ii< p;ii++) { P[ii]: np[ii]= nsp[ii]; P[ii]: while (np[ii]<= nfp[ii]&& fp[ii] ==1) {Выполнить EQ2_1; if(pChi[ii] - удовлетворяет заданным ограничениям) {передать центральному процессору ms[ii]=l и pChi;} } P[ii]: if (fp[ii] ==1) { передать центральному процессору сообщение о завершении поиска ms[ii]=0; стоп [п];}} Parallel End

4. Центральный процессор, получив сообщение о завершении поиска от ii - того процессора выполняет действия:

while(fp[i]! =(0, 0,..., 0)) { Читать ms[ii]; if(ms[ii]=0) { for(i=0;i<=ii;i-H-) fp[i] =0;}else { Читать pChi[ii]; if(npMin > np[ii]) {icp=ii; npMin = np[ii]; pChiMin = pChifii];} if(ii<n-l){for(i=ii+l;i<n;i++) fp[i] =0;}} Стоп, в pChiMin размещается характеристический вектор минимального разбиения, а в npMin -число подмножеств в минимальном разбиении. Результаты экспериментальной оценки временной сложности алгоритма EQ4_1, что по сравнению с алгоритмом EQ3_1 в среднем он обеспечивает в среднем ускорение более чем в 2 раза.

В седьмой главе рассматриваются прикладные аспекты рассматриваются прикладные аспекты автоматизации технической подготовки производства тканых узоров.

На основе предложенных математической модели структуры цветных точечных изображений и алгоритмов расчета рационального заправочного рисунка были разработаны программы, эффективная работа которых в составе САПР тканей «Логитрон 1002М», подтвердила правильность теоретических результатов данной работы. Построенные с учетом производственных условий Московского производственного камвольного объединения «Октябрь» модели свойств тканей, обеспечили рациональный выбор параметров строения проектируемых тканей и расчет заправочных параметров тканей, вырабатываемых с использованием унифицированных схем проборок основ в ремиз. Использование унифицированных проборок в условиях производства Московского производственного камвольного объединения «Октябрь» позволило вырабатывать ткани, переходя от одного рисунка к другому без выполнения операции проборки новой основы в ремиз и заправки этой основы, осуществляя лишь её привязку. Построенные с учетом производственных условий Московского производственного камвольного объединения «Октябрь» модели свойств тканей, обеспечили рациональный выбор параметров строения проектируемых тканей и расчет заправочных параметров тканей, вырабатываемых с использованием унифицированных схем проборок основ в ремиз. Таким образом, практическое применение в производственных условиях программных реализаций основных теоретических результатов (математических моделей алгоритмов и основанных на них методов) полностью подтвердило правильность данной работы.

Основные результаты и выводы по работе:

1. Анализ работ в области автоматизированного проектирования тканей показал, что в известных САПР отсутствуют средства предварительной

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

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

3. Разработаны и исследованы алгоритмы, которые осуществляют выделение раппортов и понижение числа цветов в палитре.

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

5. Предложен метод автоматизированного построения рационального заправочного рисунка.

6. Разработаны теоретические основы расчета унифицированных заправок основ в ремиз.

7. Разработан алгоритм конструктивного перечисления вариантов разбиения множества при монотонном возрастании числа подмножеств.

8. Разработан алгоритм двоичного поиска минимального разбиени взвешенного графа, обеспечивающий ускорение в среднем равное 1,7.

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

10. Разработана математическая модель, обеспечивающая количествен ную оценку технологичности сокращённых схем проборок основ в ремиз.

11. Разработан метод оптимизации сокращённых схем проборок ochoi в ремиз.

12. Исследованы возможные подходы к повышению эффективност] распределённых вычислений.

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

16. Практическое применение в производственных условиях про граммных реализаций основных теоретических результатов (математически; моделей алгоритмов и основанных на них методов) полностью подтвердил! правильность данной работы.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Борзунов Г. И., Фирсов А. В. Повышение эффективности распределённые вычислений при решении задач текстильной технологии и дизайна (моно графия). - М.: ГОУВПО «МГТУ им. А. Н. Косыгина», 2010. - 124 с.

2. Борзунов Г. И., Власов П. В. Анализ и алгоритмы построения проборки i ремиз при производстве семейства тканей с различными переплетениями/ Изв. вузов. Технология текстильной промышленности. - 1979. - №1.-с.4; ..45.

3. Борзунов Г. И. Язык конструирования ткацких переплетений // Опыт функционирования и создания АСУ в легкой промышленности. Материалы всесоюзного науч.-техн. совещания. - М.: ЦНИИТЭИлегпром, 1980. - с. 140 ..141.

4. Борзунов Г. И. Алгоритм перечисления ткацких переплетений по заданному эскизу переплетений// Развитие научных исследований и их влияние на теоретическую и профессиональную подготовку молодых инженерных кадров: Тез. докл. науч.-метод. конф. 30-31 октября 1980 г. - Иваново: ИвТИ имени М.В.Фрунзе, 1980. -С. 119..121.

5. Борзунов Г. И. Расчёты проборок, снижающих число перезаправок основы в ремиз //Деп. В ЦНИИТЭИлегпром 19.09.1980, № 379-80. - М.: ЦНИИТЭИлегпром, 1980. - 13 с.

6. Борзунов Г. И. Алгоритм коррекции параметров ткацкого переплетения и проверки соответствия этих параметров при расчёте на ЭВМ ткацких переплетений //Деп. В ЦНИИТЭИлегпром, № 446-81. - М.: ЦНИИТЭИлегпром, 1981.-17 с.

7. Борзунов Г. И., Гаврилов В. Л. Выбор математического метода улучшения сокращенных проборок основы в ремиз //Деп. В ЦНИИТЭИлегпром, № 53181. - М.: ЦНИИТЭИлегпром, 1981. - 25 с.

8. Борзунов Г. И. Исследование возможности выработки камвольных тканей по единым проборкам основы в ремиз //Текстильная промышленность. Научно -техн. реф. сборник,- М.: ЦНИИТЭИЛегпром, 1981,- №3. - с. 19..2.

9. Борзунов Г. И. Синтез ткацкого переплетения по заданному рисунку // Изв. вузов. Технология текстильной промышленности. - 1981. - № 5. - с. 42 .. 45.

10. Проскуряков С. А., Борзунов Г. И. Автоматизированная система подготовки к производству семейства видорисунков одного артикула.// 1. Сборник научно - исследовательских работ МТИ-ЛМТИ. -М.: МТИ, 1981. - с. 253..259.

11. Борзунов Г. И. Возможности программного комплекса для расчёта ткацких переплетений по заданным технологическим ограничениям //Текстильная промышленность. Научно - техн. реф. сборник.- М.: ЦНИИТЭИЛегпром, 1982,- №2.-с. И..13.

12. Борзунов Г.И. Классификация и группировка ткацких переплетений на основе теоретико-графовой модели // Изв. вузов. Технология текстильной промышленности. - 1982. - №5. - с. 36 .. 39.

13. Борзунов Г. И.Лабутина О. Н., Оганесян К. А. Расширение возможности использования единых проборок основ в ремиз//Текстильная промышленность. - 1982. №12. -31..32 с.

14. Борзунов Г.И., Гаврилов В.Л. Программная реализация алгоритмов оптимизации сокращенных проборок основы в ремиз // Изв. вузов. Технология текстильной промышленности. - 1982. - № 6. - С 11..13.

15. Борзунов Г.И. Применение ЭВМ при подготовке к производству тканей мелкоузорчатых переплетений // Автореферат дисс. на соиск. уч. ст. канд. техн. наук. - М.:МТИ, 1982. - 18 с.

16. Борзунов Г. И. Комплекс программ для анализа цветных рисунков//Деп. В ЦНИИТЭИлегпром 05.12.83, № 760ЛП-Д83. - М.: ЦНИИТЭИлегпром, 198: -8 с.

17. Борзунов Г. И. Новые методы проектирования структур мелкоузорчаты тканей// Шерстяная промышленность. Выпуск 3. Обзорная информация. - М ЦНИИТЭИлегпром, 1983. - 48 с.

18. Борзунов Г. И. Основные принципы разработки и реализации языка прс граммирования задач ткацкого рисования// Изв. вузов. Технология текстшп ной промышленности. - 1984. - № 1. - с. 71 .. 74.

19. Борзунов Г.И., Серов Е. Ю. Диалоговый режим обучения работе с интер претатором для решения задач ткацкого рисования // Изв. вузов. Технологи текстильной промышленности. - 1985. - № 1. - С 76..78.

20. Борзунов Г.И., Гаврилов В.Л., Соболев С. Разработка математических мс делей для расчета свойств тканей в условиях действующего производства , Изв. вузов. Технология текстильной промышленности. - 1985. - № 6. - < 36..39.

21. Борзунов Г.И., Оганесян С. К., Стрельников Б. А. Информационная баз автоматизированного проектирования тканей и технической подготовки и проихзводства. // Изв. вузов. Технология текстильной промышленности.

1986.-№ 1.-С 3..6.

22. Фирсов A.B., Борзунов Г.И. Разработка программы для анализа цветны ткацких рисунков, не использующей явного представления матрицы смежнс сти структурного графа // Разработка высокоэффективных технологически процессов и оборудования, систем управления и автоматизированного прс ектирования в текстильной промышленности: Тез. докл. Межреспуб. нау^ студ. конф. 23-24 апреля 1986 г.- М.: МТИ, 1986. -С.105-108.

23. Борзунов Г.И., Гаврилов В.Л. Расчет с помощью ЭВМ рациональных зна чений параметров строения проектируемых тканей // Изв. вузов. Технологи текстильной промышленности. - 1987. - № 4. - С 42..45.

24. Ахматова Н.И., Борзунов Г.И., Фирсов A.B. Возможности программ! анализа цветных ткацких рисунков, выполняемой в вычислительной сред системы коллективного доступа // Технический прогресс в развитии ас сортимента и качества изделий легкой промышленности: Тез. докл. всес науч.-техн. конф. 13-15 мая 1987 г. - Иваново: ИвТИ имени М.В.Фрунзе

1987.-С. 55.

25. Борзунов Г.И., Стрельников Б.А., Степанова О.П. Автоматизация выбор переплетений для жаккардовых тканей. //Тез. докл. Всесоюз. научно.- техг конф. Автоматизированные системы управления в легкой промышленности условиях нового хозяйственного механизма и использования ноых средст вычислительной техники и связи. -Иваново. 14-15 апреля1988 г. - : ВНИИ ПИАСУ, 1988.

26. Фирсов A.B., Капустина Н.И., Борзунов Г.И. Программа корректировю результатов анализа цветных ткацких узоров / XXXII студенческая научно техническая конференция вузов Прибалтийских республик, Белорусско]

ССР и Молдавской ССР. 19-21 апреля 1988 г. Тезисы докладов. -Рига: РПИ, 1988. часть 1,-с. 131.

27. Борзунов Г.И., Степанова О.П., Стрельников Б.А., Фирсов A.B. Автоматизация оформления результатов предпроектных исследований при создании САПР тканей. Деп. в ЦНИИТЭИлегпром. 79 8777й нд. 1988.

28. Данилевич А.Е., Фирсов A.B., Борзунов Г.И. Структура программного комплекса для анализа цветных узоров // Разработка новых технологических процессов, оборудования и материалов для текстильной и легкой промышленности: Межвузовский сборник научных трудов. -М.: МТИ, 1989. -С. 80-82.

29. Маслов М.А., Фирсов A.B., Пушкарев А.Г., Борзунов Г.И. Исследование возможностей рационального выбора ткацких переплетений для реализации цветных рисунков, разработанных на базе орнаментально-пространственных структур // Прогрессивная техника и технология, системы управления и автоматизированного проектирования в текстильной и легкой промышленности: Межвузовский сборник научных трудов. -М.: МТИ, 1990. - с. 65-66.

30. Слостина Г.Л., Сумарукова Р.И., Борзунов Г.И., Фирсов A.B. Использование ЭВМ для построения рисунков переплетения пестротканей на базе неправильных сатинов // Теория и практика бесчелночного ткачества. Тез. докл. Рос. респ. науч.-техн. конф. 24-26 ноября 1992 г. -М.: МГТА, 1992. - 35 с.

31. Борзунов Г.И., Фирсов A.B., Палаткин М.В. Визуализация цветных ткацких рисунков //Доклад на науч. конф. проф.-преп. сост., науч. сотр. и асп. МГТА имени А.Н. Косыгина.3-5 февраля 1992 г. -М.: МГТА, 1992 -С..

32. Борзунов Г.И., Фирсов A.B. Программирование графических представлений ткацких рисунков средствами языка СИ //Доклад на науч. конф. проф.-преп. сост., науч. сотр. и асп. МТИ имени А.Н. Косыгина.5-7 февраля 1991 г. -М.: МТИ, 1992-С..

33. Борзунов Г.И., Фирсов A.B. Возможности узорообразования на установке с беззевным способом образования ткани // Бесчелночное ткачество. Строение и проектирование ткани: Межвузовский сборник научных трудов. -М.: МГТА, 1993. -С. 50-54.

34. Козлова Т.В.,Борзунов Г.И.,Заболотская Е.А. Моделирование активности зрительного образа текстильного рисунка средствами машинной графики. // Проблемы разработки, производства и реализации детских изделий: сб.докладов и тезисов международного семинара, 1-2 ноября 1994 г.-М.: Рослегпром, 1994 г. - ,с.37..47.

35. Борзунов Г.И.,Журавлева Т.А.,Заболотская Е.А. Автоматизированное проектирование рисунков для мелкоузорчатых тканей с эффектами иллюзий// Машиностроение, приборостроение, энергетика.-М.: Изд-во Моск. ун-та, 1994. - с.278.,285.

36. Борзунов Г.И., Фирсов A.B. Моделирование ткацких узоров на ПЭВМ // Известия вузов. Технология текстильной промышленности.- 1994. - № 6. -С. 40-42.

37. Слостина Г.Л., Сумарукова Р.И., Борзунов Г.И., Фирсов A.B. Компьютер ное проектирование пеетротканей на базе сатинов с переменным сдвигом Известия вузов. Технология текстильной промышленности. - 1995. - № 2. -С 37-40.

38. Слостина Г.Л., Сумарукова Р.И., Борзунов Г.И., Фирсов A.B. Компьк терное проектирование и построение рисунков тканей с мелкоузорчатым э4 фектом // «Современные технологии текстильной промышленности» (TEE СТИЛЬ-95). Тез. докл. всерос. науч.-техн. конф. 28-29 ноября 1995 г. -М.: МГТА, 1995. С.66.

39. Слостина Г.Л., Сумарукова Р.И., Борзунов Г.И., Фирсов A.B. Автомата зированное проектирование рисунков мелкоузорчатых переплетений на баз смещенных сарж // Системы автоматизированного проектирования те* стильных материалов, технологических процессов и оборудования, АСУ текстильной промышленности. Межвузовский сборник научных трудов. М.: РИО МГТА, 1996. -С. 20-27.

40. Борзунов Г.И., Палаткин М.В. Интерфейс дессинатора для решения зада ткацкого рисования. И Системы автоматизированного проектирования тек стильных материалов, технологических процессов и оборудования, АСУ текстильной промышленности. Межвузовский сборник научных трудов. М.: РИО МГТА, 1996. - ,с.63..66.

41. Борзунов Г. И. Расчет на ПЭВМ заправок основ по заданным цветньп узорам// Современные технологии текстильной промышленности: тез. док; всерос. науч.-техн. конф. 26-27 ноября 1996 г. (ТЕКСТИЛЬ-96). - М.: МГТЛ 1996. - с. 110..111.

42. Слостина Г.Л., Сумарукова Р.И., Борзунов Г.И., Фирсов A.B. Построени теневых переходов от цвета основы к цвету утка // Известия вузов. Технолс гия текстильной промышленности. - 1996. - № 2. - с. 52-55.

43. Борзунов Г.И., Фирсов A.B. Автоматизация построения полутораслойны и двухслойных переплетений // Материалы науч. конф. проф.-преп. составг науч. сотр. и асп. МГТА имени А.Н.Косыгина. -М.: РИО МГТА, 1996. С. 84 85.

44. Борзунов Г.И., Фирсов A.B. Использование трехмерной графики для ви зуализации текстильных материалов в интерьере. Тез. докл. науч.-техн. конф проф.-преп. состава, науч. сотрудников и аспирантов. -М.: МГТА, 1997. С..

45. Борзунов Г.И., Палаткин М.В. Использование объектной модели для ав томатизации технологических расчетов. // Современные наукоемкие техно логии и перспективные материалы текстильной и легкой промышленности тез. докл. международной науч.-техн. конф. (ПРОГРЕСС-98). -Иваново РИО ИГТА, 1998,. - с. 108.

46. Борзунов Г.И., Палаткин М.В. Расчет рациональных параметров графи ческой системы при автоматизированном проектированиии тканых узоров. / Современные технологии и оборудование текстильной промышленности Тез. докл. всерос. науч.-техн. конф. 24-25 ноября 1998 г. (ТЕКСТИЛЬ-98). М.: МГТА, 1998.

47. Борзунов Г. И., Палаткин М.В. Построение раппорта ткацкого переплетения минимальных размеров для выработки заданного цветного рисунка тезисов Всероссийской научно-технической конференции-«ТЕКСТИЛЬ 1999»., 23-24 ноября1999, г. Москва, с 175-176.

48. Борзунов Г.И., Севостьянов П.А., Федотова Е.А. Разработка электронных учебных пособий и их применение в системах дистанционного обучения // Изв. вузов. Технология текстильной промышленности.-1999,N6.-c.40..42.

49. Борзунов Г.И., Фирсов A.B., Яковлева Н.Б. Использование графического редактора для построения канвовых рисунков // «Современные технологии и оборудование текстильной промышленности» (ТЕКСТИЛЬ-2001): тез. докл. всерос. науч.-техн. конф. 27-28 ноября 2001 г. -М.: МГТУ им. А.Н. Косыгина, 2002. - с.175-176.

50. Авдеев И. В., Борзунов Г. И. Графическая база данных для определения перспективных цветовых решений художественного оформления текстильных изделий // Компьютерные технологии в образовании и научной деятельности: сборник научных трудов. - М.: ИГТУ им А. Н. Косыгина, 2001. - с. 14-17.

51. Борзунов Г. И., Войнов А.Е. Проектирование и выбор средств реализации интерфейса графической среды для ткацкого рисования // Современные технологии и оборудование текстильной промышленности: тез. докл. Всероссийской научно-технической конференции (ТЕКСТИЛЬ 2002)., 26-27 ноября 2002, г-М.: МГТУ им. А.Н. Косыгина, 2002. - с 173-174.

52. Борзунов Г. И., Войнов А. Е. Система автоматизированного построения заправочных рисунков ремизных тканей // Перспективы использования компьютерных технологий в текстильной и легкой промышленности»: сб. материалов международной научно-технической конференции (ПИКТЕЛ-2003), 27-29 мая 2003 г. - Иваново.. - с. 62 - 63

53. Борзунов Г. И., Пронин А. К. Базовые алгоритмы поиска экстремальных разбиений множеств // Безопасность информационных технологий, 2004, № 4.-С. 58-60.

54. Борзунов Г. И., Войнов А. Е. Построение заправочных рисунков в графической среде ткацкого рисования // Информационные технологии в образовательной, научной и управленческой деятельности: тез. докл. всерос. науч. конф. 27,28 января 2004 г. (ИНФОТЕКСТИЛЬ-2004). -М.: МГТУ им. А.Н. Косыгина, 2004. - с. 57.

55. Борзунов Г. И., Войнов А. Е. Использование графических редакторов для создания изображений с ограниченным числом цветов // Современные технологии и оборудование текстильной промышленности: тез. всероссийской научно-технической конференции (ТЕКСТИЛЬ 2004), 24 ноября 2004 г. -Москва: МГТУ им. А.Н. Косыгина. - с. 207 -208.

56. Борзунов Г.И., Буцких Е.В., Войнов А.Е., Фирсов A.B. Компьютерная обработка изображений для подготовки их воспроизведения средствами текстильных технологий // Труды Российского науч.-техн. общества радиотехники, электроники и связи имени A.C. Попова. Серия: Научная сессия, посвященная Дню радио. Выпуск LX. Т.2. -М.: 2005. - С.53-54.

57. Борзунов Г.И., Войнов А.Е., Ульянов А.А. Отбор операций компьютерно обработки изображений для понижения глубины цвета заданных рисунков Современные наукоемкие технологии и перспективные материалы текстил; ной и легкой промышленности (Прогресс - 2005): материалы международно научно-технической конференции, часть 2. - Иваново: ИГТА, 2005. с. 61-63.

58. Борзунов Г.И., Фирсов А.В. Методы воспроизведения точечных рисункс средствами текстильных технологий // Текстильная промышленность. Hay ный альманах - 2006. - № 1-2, - С. 23 .. 26.

59. Борзунов Г. И., Пронин А. К. Алгоритмы поиска экстремальных разби< ний множеств большой мощности // Безопасность информационных технол< гий, 2006, № 1.-е. 52..54.

60. Борзунов Г.И., Фирсов А.В. Необходимое и достаточное условия сущес вования однослойного ткацкого переплетения // Известия вузов. Технолога текстильной промышленности. - 2006, №3, - с 40..42.

61. Борзунов Г. И. Математическая модель коррекции цветных точечных pi сунков // Известия вузов. Технология текстильной промышленности. - 200i №5,-с. 121 .. 123.

62. Борзунов Г. И., Войнов А. Е. Алгоритм изменения цвета точек рисую при его преобразовании в технологически допустимое изображен» //Известия вузов. Технология текстильной промышленности. - 2006, №6, -' 129.. 131.

63. Борзунов Г. И., Войнов А. Е. Расчет заправочного рисунка по заданном технологически допустимому точечному изображению // Известия вузо] Технология текстильной промышленности. - 2007, №1, - с. 117.. 119.

64. Борзунов Г. И., Войнов А. Е. Разработка автоматизированной систем подготовки заправочных рисугеов для ремизного ткачества // Известия вузо: Технология текстильной промышленности. - 2007, №2, - с. 138 .. 140.

65. Борзунов Г. И., Войнов А. Е. Вычислительный эксперимент по примеш нию алгоритма изменения цвета точек рисунка при его преобразовании технологически допустимое изображение // Известия вузов. Технология Tei стильной промышленности. - 2007, №ЗС, - с. 124 .. 127.

66. Боначёв А. Н., Махов С. А., Борзунов Г. И., Новиков А. Н., Фирсов А. I Вопросы контроля качества нетканых полотен в процессе производства Швейная промышленность. - 2007, №6, - с. 43 .. 44.

67. Борзунов И. И., Новиков А. Н., Фирсов А. В. Современные технологии дизайн-образовании // Материалы 6-ой Всероссийской научно-практическо конференции (6 - 13 октября 2007). - Сочи, 2007, с. 85 - 89.

68. Борзунов Г. И. Совершенствование базового алгоритма минимизации ко личества необходимых проборок основ в ремиз // Известия вузов. Технологи текстильной промышленности. - 2008, №5, - с. 102 .. 104.

69. Борзунов Г. И., Войнов А. Е. Анализ временной сложности выделени раппортов точечных рисунков, содержащих точное повторение раппорта Современные проблемы текстильной и легкой промышленности (14 - 15 ма; 2008): тез. международной научно-технической конференции. - М.: Госуда{ ственное образовательное учреждение высшего профессионального образо

вания «Российский заочный институт текстильной и легкой промышленности», 2008.

70. Борзунов И. Г., Войнов А. Е., Моисеев К. А. Разработка математической модели выделения раппортов точечных рисунков // Современные технологии и перспективные материалы текстильной и легкой промышленности» (ПРОГРЕСС 2008): сборник материалов международной научно-техническая конференции. - Иваново: ИГТА, 2008.

71. Борзунов Г. И. Исследование распараллеливания алгоритма выделения раппортов точечных изображений // Применение многопроцессорных суперкомпьютеров в исследованиях, наукоемких технологиях и учебной работе: вторая региональная научно-техническая конференция. - Иваново: ИГТА, 2008.

72. Борзунов Г. И., Моисеев К. А. Быстрое выделение раппорта точечного рисунка без учёта возможных помех // Современные технологии и оборудование текстильной промышленности (ТЕКСТИЛЬ 2008): тез. всероссийской научно-технической конференции. -М.: МГТУ им. А.Н. Косыгина, 2008.

73. Борзунов Г. И. Совершенствование математической модели поиска экстремальных разбиений множеств // Безопасность информационных технологий, 2008, №3.-С. 58 ..61.

74. Борзунов Г. И. Двоичный поиск и параллельное программирование при минимизации количества необходимых проборок основ в ремиз. // Известия вузов. Технология текстильной промышленности. - 2009, № 2. - с. 99 .. 101.

75. Борзунов Г. И. Исследование алгоритмов выделения раппортов точечных изображений // Известия вузов. Технология текстильной промышленности. -2009, №ЗС.- с. 101 .. 103.

76. Борзунов Г. И., Войнов А. Е., Петрова Т. В. Анализ методов повышения эффективности распределённых вычислений при решении задач безопасности информационных технологий // Безопасность информационных технологий.-2009, №4. - с. 57 ..60.

77. Борзунов Г. И. Исследование возможности повышения эффективности параллельного алгоритма выделения повторяющихся фрагментов текстур // Трехмерная визуализация научной, технической и социальной реальности. Кластерные технологии моделирования: труды первой международной конференции Том 1. Пленарные доклады. Секции 1, 2. - Ижевск: Ижевский государственный технический университет, 2009. - с. 128 .. 132.

78. Борзунов Г.И., Стрельников Б.А., Степанова О.П., Фирсов A.B. Методическая разработка к лабораторным работам по курсу "Системное программирование" -М.: РИО МГТА, 1993. - 41 с.

79. Слостина Г.Л., Сумарукова Р.И., Борзунов Г.И., Фирсов A.B. Методическая разработка. Моделирование цветных узоров, полученных с использованием сатиновых переплетений с двумя переменными сдвигами или комбинированных саржевых переплетений. - М.: РИО МГТА 1993 г..42с.

80. Борзунов Г.И., Фирсов A.B. МЕТОДИЧЕСКИЕ УКАЗАНИЯ к выполнению лабораторных работ по курсу "АППАРАТНО-ПРОГРАММНЫЕ СРЕДСТВА ИСАУ", - М.: РИО МГТА 1994. - 15 с.

81. Борзунов Г.И., Фирсов A.B. МЕТОДИЧЕСКИЕ УКАЗАНИЯ к выполнению лабораторных работ по курсу "Программные средства визуализаци данных", -М.: РИО МГТА 1994.

82. Борзунов Г.И., Журавлева Т.А., Заболотская Е.А. Методические указани к проектированию рисунков тканей на ПЭВМ при выполнении практически заданий по дисциплине АМХП. / Часть I. - М., МТИ, 1995. - 47с.

83. Борзунов Г.И., Фирсов A.B. Методические указания к выполнению лабс раторных работ по курсу "Системное программное обеспечение". Разде "Архитектура ПЭВМ и основные средства ассемблера", -М.: РИО МГТ, 1996.-28 с.

84. Слостина Г.Л., Борзунов Г.И., Фирсов A.B. Построение мелкоузорчаты переплетений на ЭВМ. Учебное пособие-М.: РИО МГТУ, 1999,-24 с.

85. Борзунов Г.И., Заболотская Е.А., Палаткин М.В., Фирсов A.B. Лаборг торный практикум по дисциплине «Математика и информатика». 4.1 Опр< деление направлений моды -М.: РИО МГТУ, 2001. - 45 с.

86. Борзунов Г.И., Заболотская Е.А., Палаткин М.В., Фирсов A.B. Лаборг торный практикум по дисциплине «Математика и информатика». 4.2 Введ« ние в компьютерную графику. Основные средства графического редактора М.: РИО МГТУ, 2001 -36 с.

87. Борзунов Г. И., Аксёнова А.Н, Незнанова Н.И. Практикум по дисциплине "Математика и информатика "Часть 3. Использование дополнительных средств графического редактора для создания орнаментальных композиций" (учебное пособие). - М.: РИО МГТУ им. А.Н. Косыгина, 2007. - 52 с.

88. Борзунов Г. И. Автоматизация работы в среде графического редактора (учебное пособие). - М.: РИО МГТУ им. А.Н. Косыгина, 2007. - 52 с.

Подписано в печать 27.09.10 Формат бумаги 60x84/16 Бумага множ. Усл.печ.л. 2,0 Заказ 300 Тираж 100 ГОУВПО «МГТУ им. А.Н. Косыгина», 119071, Москва, ул. Малая Калужская, 1

ВВЕДЕНИЕ.

ГЛАВА 1. ОБЗОР И АНАЛИЗ СОСТОЯНИЯ НАУЧНЫХ РАБОТ ПО АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ И ТЕХНИЧЕСКОЙ ПОДГОТОВКИ ПРОИЗВОДСТВА ЦВЕТНЫХ ТКАНЫХ УЗОРОВ.

1.1. Основные методы и математические модели проектирования цветных узоров.

1.2. Системы автоматизированного проектирования (САПР) тканей.

1.3. Использование современных компьютерных технологий для автоматизации проектирования и технической подготовки производства тканых узоров.

1.4. Определение цели и постановка задач разработки методов автоматизации технической подготовки производства цветных тканых узоров.

ГЛАВА 2. ПРЕДВАРИТЕЛЬНАЯ ОБРАБОТКА ТОЧЕЧНЫХ ИЗОБРАЖЕНИЙ И ПОЛУЧЕНИЕ ПОТЕНЦИАЛЬНО ДОПУСТИМЫХ ИЗОБРАЖЕНИЙ.

2.1. Структурная схема автоматизированной системы технической подготовки производства тканых узоров и объектная модель расчёта заправочных рисунков.

2.2. Анализ простейших алгоритмов выделения раппортов в точечных изображениях.

2.3. Разработка быстрых алгоритмов выделения раппортов в точечных изображениях.

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

2.5. Исследование возможностей параллельного программирования для решения задачи выделения раппортов в точечных изображениях класса 1.

2.6. Повышение эффективности параллельного алгоритма выделения раппортов с учётом случайных помех в точечных изображениях класса 2.

2.7. Использование графических редакторов общего назначения для получения из произвольного точечного изображения потенциально допустимого изображения.

2.8. Исследование метода усечённого блочного кодирования (УБК).

2.9. Понижение физической глубины цвета.

2.10. Комплексный подход к получению потенциально допустимых изображений

2.11. Выводы.

ГЛАВА 3. АНАЛИЗ ЦВЕТНЫХ РИСУНКОВ И ПОЛУЧЕНИЕ ТЕХНОЛОГИЧЕСКИ ДОПУСТИМЫХ ИЗОБРАЖЕНИЙ.

3.1. Постановка задачи анализа точечных изображений.

3.2. Математическая модель структуры точечных изображений.

3.3. Анализ точечных изображений с помощью графов их структуры.

3.4. Программная реализация анализа точечных изображений и вычислительный эксперимент.

3.5. Развитие математической модели структуры точечных изображений

3.6. Получение технологически допустимого изображения.

3.7. Вычислительный эксперимент применения разработанного метода преобразования точечных изображений в потенциально допустимые изображения.

3.8 Выводы.

ГЛАВА 4. МАТЕМАТИЧЕСКИЕ ОСНОВЫ МОДЕЛИРОВАНИЯ ТКАЦКИХ ПЕРЕПЛЕТЕНИЙ И АВТОМАТИЗИРОВАННОГО МЕТОДА РАСЧЁТА РАЦИОНАЛЬНЫХ ЗАПРАВОЧНЫХ РИСУНКОВ.

4.1. Автоматизация проектирования ткацких переплетений - важнейшая задача САПР тканей.

4.2. Математическая модель ткацких переплетений.

4.3. Генерация ткацких переплетений в виде матриц, состоящих из нулей и единиц.

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

4.5. Алгоритм синтеза рациональных заправочных рисунков.

4.6. Выводы.

ГЛАВА 5. МИНИМИЗАЦИЯ ЧИСЛА НЕОБХОДИМЫХ СХЕМ ПРОБОРОК ПРИ ВЫРАБОТКЕ ТКАНЕЙ С ИСПОЛЬЗОВАНИЕМ ОДИНАКОВОЙ ЗАПРАВКИ ОСНОВЫ.

5.1 .Постановка задачи и математическая модель.

5.2. Алгоритм расчёта унифицированных схем проборок основ в ремиз.

5.3. Минимизация количества необходимых проборок основ в ремиз.

5.4. Алгоритмы поиска экстремальных разбиений множеств большой мощности

5.5. Совершенствование базового алгоритма минимизации количества необходимых проборок основ в ремиз.

5.6. Выводы.

ГЛАВА 6. ИССЛЕДОВАНИЕ ВОЗМОЖНОСТЕЙ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ РАСПРЕДЕЛЁННЫХ ВЫЧИСЛЕНИЙ ПРИ РЕШЕНИИ ЗАДАЧ ПРОЕКТИРОВАНИЯ ЦВЕТНЫХ ТКАНЫХ УЗОРОВ.

6.1. Задача оптимального разбиения графов как математическая модель повышения эффективности распределённых вычислений.

6.2. Алгоритмический анализ методов оптимального разделения графов и оценка их временной сложности.

6.3. Экспериментальная оценка временной сложности базового алгоритма генерации разбиений множеств ЕС>

6.4. Определение целевой функции и экспериментальная проверка монотонности её роста с увеличением числа блоков в разбиении.

6.5. Разработка метода оптимального разделения взвешенных графов на основе конструктивного перечисления разбиений множеств их вершин

6.6. Выводы.

ГЛАВА 7. ПРИКЛАДНЫЕ АСПЕКТЫ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ И ТЕХНИЧЕСКОЙ ПОДГОТОВКИ ПРОИЗВОДСТВА ТКАНЫХ УЗОРОВ.

7.1. Реализация разработанных автоматизированных методов технической подготовки производства тканых узоров.

7.2. Производственная апробация автоматизированного метода минимизации необходимого числа заправок основ в ремиз при выработке камвольных тканей.

7.3. Оптимизация сокращенных схем проборок основ в ремиз.

7.4. Программная реализация алгоритма оптимизации сокращённых схем проборок и вычислительный эксперимент.

7.5. Расширение возможности использования единых проборок основы в ремиз.

7.6. Практическое применение математической модели структуры цветных точечных изображений в составе САПР кареточных тканей «Логи-трон 1002.СМ»

7.7. Использование теоретических результатов в учебном процессе

7.8. Выводы.

Анализ состояния развития текстильной промышленности показывает, что к настоящему времени сформировался круг устойчиво работающих предприятий, которые доминируют в производстве и на рынке товаров среди отечественных производителей. Так, 70,3% готовых хлопчатобумажных тканей выпускается тринадцатью предприятиями из 102, работающих в отрасли, 62,3% шелковых готовых тканей выпускается тремя предприятиями из 13 предприятий [137]. Покупателям хорошо известна продукция ОАО ХКБ «Шуйские ситцы», ЗАО «Московский шелк», ОАО «Донецкая мануфактура М», ЗАО «Славянка» и др. Показательно, что лидерство этих предприятий достигнуто благодаря их адаптации к современным условиям рынка, обоснованности стратегических решений по развитию производства, обновлению ассортимента продукции, повышению её качества и потребительских характеристик. Это позволило увеличить объёмы производства и продаж продукции по рыночным конкурентным ценам. Опыт этих и других предприятий свидетельствует о том, что для успешного расширения и быстрого обновления ассортимента выпускаемой продукции в современных условиях жесткой конкуренции текстильному предприятию необходимо выпускать ткани небольшими партиями при значительном разнообразии их художественного оформления (дизайна). Такая организация обновления и расширения ассортимента выпускаемых тканей требует значительных затрат на художественное проектирование, большого объёма технологических расчетов при технической подготовке производства и частых перезаправок ткацких станков [112]. Единственный путь снижения указанных затрат - это использование компьютерных, технологий для автоматизации проектирования тканей и технической подготовки их производства. Для широкого внедрения компьютерных технологий в ткацкое производство требуется разработка эффективных автоматизированных методов, обеспечивающих решение инновационных задач проектирования тканей и технической подготовки их производства.

Специалисты агентства 1БЮ, оценившие перспективы развития текстильной отрасли промышленности по заказу Минпромэнерго, поставили ее на третье место по привлекательности инвестирования после ТЭК и торговли [137]. С 2008 года существенно расширяются меры поддержки предприятий отрасли. Так субсидии по кредитам на закупку сырья законодательно увеличены в 2 раза (200 млн. рублей ежегодно). При этом основной проблемой отрасли остаётся решение задачи повышения конкурентоспособности её продукции. В современных условиях повышение конкурентоспособности продукции текстильной отрасли неразрывно связано с переводом производства на инновационный путь развития. Активное внедрение инноваций в промышленность не может быть реализовано без научного сопровождения. В этих целях в ноябре 2007 году образован Национальный инновационный центр текстиля и одежды, основным предназначением которого является укрепление взаимосвязей науки и производства, а также активизация инновационной деятельности в отрасли [137]. В настоящее время в Центре сформирован пакет научно-исследовательских разработок в области технологии, маркетинга и менеджмента, который предложен к внедрению отраслевыми предприятиями и учебными заведениями.

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

Цель и задачи исследования.

Для достижения указанной цели решены следующие задачи:

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

- в соответствии с предложенной структурной схемой разработаны и исследованы алгоритмы выделения раппортов точечных изображений и понижения числа цветов в палитре изображения до заданного значения;

- разработана и исследована математическая модель структуры цветных точечных изображений и разработан алгоритм рационального преобразования точечных изображений;

- разработана и исследована математическая модель ткацких переплетений, которая, обеспечивает систематизацию и классификацию ткацких переплетений;

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

- разработаны теоретические основы расчета унифицированных схем проборок основ в ремиз;

- разработан алгоритм конструктивного перечисления вариантов разбиения множества при монотонном возрастании числа подмножеств;

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

- разработана математическая модель, обеспечивающая количественную оценку технологичности схем проборок основ в ремиз, и разработан алгоритм оптимизации сокращенных проборок;

- предложен метод построения моделей свойств тканей в условиях действующего производства и вычислительная схема расчета рациональных параметров строения ткани;

- предложен метод оптимального разделения графов на основе конструктивного перечисления разбиений множеств их вершин;

- подготовлено и осуществлено внедрение программных реализаций основных теоретических результатов в Московском производственном камвольного объединении «Октябрь».

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

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

Методы исследования.

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

Научная новизна работы заключается в следующих результатах:

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

- определены оценки временной сложности алгоритмов выделения раппортов в точечных изображениях;

- разработана методика понижения числа цветов в палитрах изображений до заданных значений;

- разработана математическая модель структуры произвольных цветных точечных изображений;

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

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

- предложена математическая модель ткацких переплетений ткачества, адекватно описывающая их структуру;

- разработаны теоретические основы расчета унифицированных заправок основ в ремиз;

- предложен метод оптимизации сокращенных проборок основ в ремиз

- предложен метод построения математических моделей в условиях действующего производства;

- разработан и исследован алгоритм генерации разбиений множества в порядке неубывания числа блоков (подмножеств);

- разработан алгоритм двоичного поиска минимального разбиения заданного множества и параллельный алгоритм поиска минимального разбиения заданного множества, получены оценки эффективности этих алгоритмов;

- впервые предложен метод расчёта оптимального числа процессоров, используемых для выполнения распределённых вычислений.

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

- разработаны алгоритмы выделения раппортов точечных изображений;

- предложена методика понижения числа цветов в палитрах изображений до заданных значений;

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

- разработана' математическая модель ткацких переплетений, обеспечивающая отбор ткацких переплетений с заданными структурными признаками;

- предложен метод приведения сокращенных проборок к виду, обеспечивающему максимальную технологичность;

- разработан метод минимизации необходимого количества схем проборок основ в ремиз;

- предложен метод повышения эффективности распределённых вычислений за счёт использования оптимального числа процессоров.

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

Реализация результатов работы.

Разработанные алгоритмы реализованы в составе программного обеспечения САПР кареточных тканей "Логитрон 1002.СМ. Пакет прикладных программ для расчёта единых проборок основ в ремиз и оптимизации сокращенных проборок основ в ремиз внедрен в производство Московского производственного камвольного объединения «Октябрь». Внедрение и эффективность использования перечисленного выше программного обеспечения подтверждается актами и документами. Программный комплекс «Заправочный рисунок» используется в ГОУВПО «МГТУ им. А. Н. Косыгина» для разработки тканых узоров в курсовом и дипломном проектировании на кафедре ткачества и при проведении лабораторных занятий по курсу «Компьютерная обработка изображений» для студентов специальности № 230400. Отдельные теоретические результаты работы и программные реализации алгоритмов используются на кафедре информационных технологий и компьютерного дизайна при подготовке и обновлении учебных курсов «Технологии программирования», «Компьютерная обработка изображений» и «Дискретная математика», а также в дипломном проектировании.

Апробация работы.

Основные результаты диссертационной работы докладывались и получили положительную оценку на международных и всероссийских научно-технических конференциях: ТЕКСТИЛЬ - (Москва, 1995, 1998, 1999, 2001, 2002, 2004, 2008 гг., МГТУ им. А.Н. Косыгина), ПРОГРЕСС - (Иваново, 2005, 2008 гг., ИГТА), ПИКТЕЛ - (Иваново, 2003 г., ИГТА) на научных конференциях профессорско-преподавательского состава МГТУ им. А.Н. Косыгина, на Первой международной конференции «Трехмерная визуализация научной, технической и социальной реальности. Кластерные технологии моделирования» (Ижевск, 2009 г.).

Публикации.

Основные результаты работы отражены в 88 публикациях, в том числе 1 монография, 23 статьи в изданиях, рекомендованных ВАК РФ для публикации. На программный комплекс «Заправочный рисунок» имеется свидетельство о государственной регистрации №2006612092 в реестре программ для ЭВМ 16 июня 2006 г.

Структура и объём диссертации.

Диссертационная работа состоит из введения, семи глав, общих выводов по работе, списка использованной литературы, содержащего 196 наименований, и приложений на 32 листах. Основная часть изложена на 320 страницах, содержит 96 рисунков, 12 таблиц. Общий объём диссертации - 352 страницы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

1. Анализ работ в области автоматизированного проектирования тканей показал, что в известных САПР отсутствуют средства предварительной обработки точечных изображений, а также практически отсутствуют работы по применению распределённых вычислений в решении задач проектирования тканых узоров.

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

3. Разработаны и исследованы алгоритмы, которые осуществляют выделение раппортов и понижение числа цветов в палитре.

Для выделения раппортов в реальных изображениях, как правило, необходимо использовать быстрые алгоритмы 1^3, 11р14. Алгоритм 1^3 обеспечивает коэффициент ускорения О(К) при выделении раппортов изображений, не содержащих случайных искажений, а алгоритм 1^4 -коэффициент ускорения при выделении раппортов изображений, в которых имеют место искажения цвета некоторых точек. Дальнейшее снижение временной сложности выделение раппортов достигается с использованием средств параллельного программирования. Эффективность параллельных вычислений зависит от баланса вычислительной нагрузки процессоров. При обеспечении равномерной вычислительной нагрузки процессоров ускорение и эффективность алгоритма параллельного выделения раппортов увеличиваются: для изображений класса 1 в худшем случае на 18,7% и в среднем случае на 13,2%, а для изображений класса 2 в худшем случае на 87,3% и в среднем случае на 32,5%.

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

Применение методов теории графов позволило свести задачу синтеза ткацкого переплетения по заданному цветному рисунку, к задаче раскраски вершин графа специального вида (графа структуры заданного рисунка). Для решения задачи раскраски вершин графа структуры изображения разработаны эффективные алгоритмы, основанные на анализе объединений суграфов графа структуры рисунка и их композиций. Программная реализация этих алгоритмов подтвердила эффективность предложенных алгоритмов и одновременно большую временную сложность: Т4>2= 0(ш3хп3). Такая временная сложность для расширения диапазона практически решаемых задач требует использования методов параллельного программирования.

5. Представление ткацких переплетений графами структуры ткацких переплетений позволяет свести группировку подобных переплетений (например, сатинов, которые можно совместить одиночными перекрытиями посредством поворота на 90° или на изнанку) к сравнению длины основных и уточных циклов в соответствующих структурных графах.

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

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

6. Разработаны теоретические основы расчета унифицированных заправок основ в ремиз: на основе теории отношений разработана математическая модель схем проборок основ в ремиз, которая обеспечивает их адекватное представление, а также является основой для разработки алгоритма расчёта унифицированных схем проборок основ в ремиз; алгоритм минимизации необходимого числа схем проборок основ в ремиз для выработки определённого множества тканей, который базируется на поиске минимальных разбиений заданного множества.

7. Поиск минимальных разбиений заданного множества является важной составной частью оптимизационных алгоритмов, применяемых в различных предметных областях. Его реализация оказывается задачей большой временной сложности. Для его реализации разработан алгоритм конструктивного перечисления вариантов разбиения множества при монотонном возрастании числа подмножеств ЕС>21.

8. Разработанный автором алгоритм Е<^31 реализует двоичный поиск минимальных разбиений заданных множеств, что обеспечивает уменьшение временной сложности решения данной задачи в 2 -3 раза. Для дальнейшего уменьшения временной сложности задачи следует использовать при её решении параллельный алгоритм Е(241.

9. Эффективное выполнение многих параллельных алгоритмов обычно требует решения проблемы разделения взвешенного графа, где веса вершин представляют собой временные сложности подзадач, а веса ребер моделируют затраты на межзадачный обмен данными. Проблема разделения графа ИР-полна. Однако разработано много приближенных алгоритмов для поиска хорошего разделения за приемлемое время. Эти алгоритмы можно разделить на три класса. Первый класс методов использует для нахождения хорошего разделителя геометрическую информацию о графе. Геометрические алгоритмы разделения оказываются быстрыми, но часто приводят к разделениям, низкого качества. Спектральные методы разделения производят хорошие разделения для широкого класса проблем, но работаю слишком медленно. Третий класс алгоритмов разделения графа уменьшает размер графа до приемлемой величины, огрубляя граф путем стягивания его узлов и ребер, делит меньший граф, и затем уточняет разделитель, чтобы построить разделение для первоначального графа. Эти методы имеют средние показатели по сравнению с геометрическими и спектральными методами. Наилучшие результаты могут быть получены с помощью комбинаторных методов.

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

11. Монотонность функции' Б (6.4) позволила использовать базовый алгоритм Eq2l как в вычислительной схеме последовательного поиска (будем отождествлять её с алгоритмом Eq2l) так в вычислительной схеме двоичного поиска минимального разбиения взвешенного графа, при котором обеспечивается коэффициент ускорения в среднем равный 1,665766. Разработанный метод оптимального разделения взвешенных графов, основанный на использовании алгоритма ЕцЗ1, обеспечивает эффективное решение задачи определения минимального числа процессоров, необходимых для реализации параллельных вычислений с заданным ускорением относительно последовательных вычислений.

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

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

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

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

16. Высвободившийся при внедрении в объединении «Октябрь» единых проборок фонд рабочего времени позволил сократить простои ткацких станков, расширить ассортимент выпускаемых тканей. Таким образом, внедрение станков СТБ, оснащенных ремизоподъемной кареткой на 18 и более ремизок, в сочетании с использованием единых проборок основы в ремиз, рассчитанных по предложенной методике, позволяет существенно повысить эффективность работы ткацких производств.

17. Программная реализация расчёта рациональных заправочных рисунков, разработанная на основе рассмотренных в главах 3, 4 математической модели структуры цветных точечных изображений, алгоритма преобразования точечных изображений в технологически допустимые изображения, была включена в виде пакета программ для имитационного моделирования ткацких переплетений в состав САПР кареточных тканей «Логитрон 1002.СМ». Пакет программ для имитационного моделирования ткацких переплетений в составе САПР кареточных тканей «Логитрон 1002.СМ» прошел приёмочные испытания и был рекомендован к серийному производству и поставке на предприятия системы Минлегпрома СССР.

18. Теоретические результаты данной работы успешно используются автором в учебном процессе.

1. Алгоритм 76. Алгоритм Евклида для нахождения общего наибольшее делителя чисел// В кн. Библиотека алгоритмов 16 - 506. - М.: Советское радио, 1975.-с. 20 .21.

2. Ахо A.B., Хопкрофт Дж., Ульман Дж.Д. Структуры данных и алгоритмы. -М.: Издательский дом «Вильяме», 2003. 384 с.

3. Бавструк Н.Ф. Курс ткацких переплетений. М: Искусство, 1951.

4. Бачев Ц.З. Аналитический метод проектирования тканей полотняного переплетения. Дис. . канд. техн. наук. -М., 1970. 184 с.

5. Боначев А. Н., Махов С. А., Борзунов Г.И., Новиков А. Н., Фирсов А. В. Вопросы контроля качества нетканых полотен в процессе производства // Швейная промышленность. 2007. №6. - с. 43. 44.

6. Борзунов Г. И. Алгоритм коррекции параметров ткацкого переплетения и проверки соответствия этих параметров при расчёте на ЭВМ ткацких переплетений //Деп. В ЦНИИТЭИлегпром, № 446-81. М.: ЦНИИТЭИлегпром,1981.-17 с.

7. Борзунов Г. И. Возможности программного комплекса для расчёта ткацких переплетений по заданным технологическим ограничениям //Текстильная промышленность. Научно техн. реф. сборник.- М.: ЦНИИТЭИЛегпром,1982.-№2.-с. 11.13.

8. Борзунов Г. И. Оптимизация сокращенных проборок нитей основы в ре-миз//Текстильная промышленность. Научно техн. реф. сборник.- М.: ЦНИИТЭИЛегпром, 1982.- №4. - с. 25.26.

9. Борзунов Г. И. Расчёты проборок, снижающих число перезаправок основы в ремиз //Деп. В ЦНИИТЭИлегпром 19.09.1980, № 379-80. М.: ЦНИИ1. ТЭИлегпром, 1980. 13 с.

10. Борзунов Г. И., Гаврилов В. JI. Выбор математического метода улучшения сокращенных проборок основы в ремиз //Деп. В ЦНИИТЭИлегпром, № 531-81. М.: ЦНИИТЭИлегпром, 1981. - 25 с.

11. Борзунов Г. И., Фирсов Ач. В. Методы воспроизведения точечных рисунков средствами текстильных технологий // Текстильная промышленность. Научный альманах.- 2006. № 1-2. - с. 23.26.

12. Борзунов Г. И. Использование единых проборок основы в ремиз для выработки камвольных тканей на станках СТБ. // Текстильная промышленность. Экспресс- информация. 1982. - № 19. - с. 10 . 19.

13. Борзунов Г. И. Исследование алгоритмов выделения раппортов точечных изображений // Изв. вузов. Технология текстильной промышленности. -2009.- № ЗС. с. 101 . 103.

14. Борзунов Г. И. Комплекс программ для анализа цветных рисунков//Деп. В ЦНИИТЭИлегпром 05.12.83, № 760ЛП-Д83. М.: ЦНИИТЭИлегпром, 1982.-8 с.

15. Борзунов Г. И. Новые методы проектирования структур мелкоузорчатых тканей// Шерстяная промышленность. Выпуск 3. Обзорная информация. -М.: ЦНИИТЭИлегпром, 1983. 48 с.

16. Борзунов Г. И. Параллельные алгоритмы в моделях и методах криптографической защиты //Безопасность информационных технологий. 2005. - №4.

17. Борзунов Г. И. Синтез ткацкого переплетения по заданному рисунку // Изв. вузов. Технология текстильной промышленности. 1981. - № 5. - с. 42 . 45.

18. Борзунов Г. И., Власов П. В. Анализ и алгоритмы построения проборки в ремиз при производстве семейства тканей с различными переплетениями// Изв. вузов. Технология текстильной промышленности. 1979. - № 1. - с. 42

19. Борзунов Г. И., Фирсов А. В. Повышение эффективности распределённых вычислений при решении задач текстильной технологии и дизайна. М.: ГОУВПО «МГТУ им. А. Н. Косыгина, 2010. - 124 с.

20. Борзунов Г. И.Лабутина О. Н., Оганесян К. А. Расширение возможности использования единых проборок основ в ремиз//Текстильная промышленность. 1982. №12. - 31.32 с.

21. Борзунов Г.И. Анализ цветных ткацких рисунков при помощи ЭВМ // Изв. вузов. Технология текстильной промышленности.-1985. №5. -c.35.-38.

22. Борзунов Г.И. Быстрые алгоритмы выделения раппортов точечных изображений // Изв. вузов. Технология текстильной промышленности. -2009. № 5.

23. Борзунов Г.И. Двоичный поиск и параллельное программирование при минимизации количества необходимых проборок основ в ремиз // Изв. вузов. Технология текстильной промышленности. 2009. - №2. - с. 99 .101.

24. Борзунов Г.И. Классификация и группировка ткацких переплетений на основе теоретико-графовой модели // Изв. вузов. Технология текстильной промышленности. 1982. - №5. - с. 36 . 39.

25. Борзунов Г.И. Математическая модель коррекции цветных точечных рисунков // Изв. вузов. Технология текстильной промышленности. 2006. - №5. -с. 121 .23.

26. Борзунов Г.И. Новые методы автоматизированного проектирования и художественного оформления тканей. Выпуск 5: -М., ЦНИИТЭИлегмаш. Шерстяная промышленность: обзорная информация. 1988. 34 с.

27. Борзунов Г.И. Применение ЭВМ при подготовке к производству тканей мелкоузорчатых переплетений // Дисс. канд. техн. наук. М.:МТИ, 1982.

28. Борзунов Г.И. Разработка объектно-ориентированных программ с использованием CASE технологий (учебное пособие). -М.: РИО, ГОУВПО «МГТУ им. А. И. Косыгина», 2008

29. Борзунов Г.И. Совершенствование базового алгоритма минимизации количества необходимых проборок основ в ремиз // Изв. вузов. Технология текстильной промышленности. 2008. - № 5. - с. 102 . 104.

30. Борзунов Г.И., Фирсов A.B. Возможности узорообразования на установке с беззевным способом образования ткани // Бесчелночное ткачество. Строение и проектирование ткани: Межвузовский сборник научных трудов. -М.: МГТА, 1993. -С. 50-54.

31. Борзунов Г.И., Аксёнова А.Н, Незнанова Н.И. Практикум по дисциплине "Математика и информатика ".Часть 3. Использование дополнительных средств графического редактора для создания орнаментальных композиций.-М.: РИО МГТУ им. А.Н. Косыгина, 2010.

32. Борзунов Г.И., Войнов А.Е. Алгоритм изменения цвета точек рисунка при его преобразовании в технологически допустимое изображение // Изв. вузов. Технология текстильной промышленности. 2006. - №6. - с. 129.131.

33. Борзунов Г.И., Войнов А.Е. Выделение раппорта точечного рисунка // Современные технологии и оборудование текстильной промышленности: тез. докл. всероссийской научно-технической конференции «ТЕКСТИЛЬ-2007». М.: МГТУ, 2007.

34. Борзунов Г.И., Войнов А.Е. Расчет заправочного рисунка по заданному технологически допустимому точечному изображению // Изв. вузов. Технология текстильной промышленности. 2007. - №1. - с. 117 .119.

35. Борзунов Г.И., Гаврилов B.JI. Программная реализация алгоритма оптимизации сокращенных проборок основы в ремиз проектируемых тканей // Изв. вузов. Технология текстильной промышленности. 1982. - № 6. - С 11.13.

36. Борзунов Г.И., Гаврилов B.JI. Расчет с помощью ЭВМ рациональных значений параметров строения проектируемых тканей // Изв. вузов. Технология текстильной промышленности. 1987. - № 4. - С 42.45.

37. Борзунов Г.И., Гаврилов В.Л., Соболев С. Разработка математических моделей для расчета свойств тканей в условиях действующего производства // Изв. вузов. Технология текстильной промышленности. 1985. - № 6. - с. 36.39.

38. Борзунов Г.И., Заболотская Е.А., Палаткин М.В., Фирсов A.B. Лабораторный практикум по дисциплине «Математика и информатика». Раздел «Определение направлений моды». М.: РИО МГТУ, 2001. - 45 с.

39. Борзунов Г.И., Заболотская Е.А., Палаткин М.В., Фирсов A.B. Лабораторный практикум по дисциплине «Математика и информатика». Введение в компьютерную графику. Основные средства графического редактора. М.: РИО МГТУ, 2001. - 36 с.

40. Борзунов Г.И., Моисеев К. А. Быстрое выделение раппорта точечного рисунка без учёта возможных помех// Современные технологии и оборудование текстильной промышленности (ТЕКСТИЛЬ 2008), 11-12 ноября, 2008. Г. Москва, ГОУВПО «МГТУ им. А. Н. Косыгина».

41. Борзунов Г.И., Новиков А. Н., Фирсов А. В. Подготовка специалистов по компьютерному дизайну. Современные технологии в дизайн-образовании. Материалы 6-ой Всероссийской научно-практической конференции (6-13 октября 2007). Сочи, 2007, с. 85 - 89.

42. Борзунов Г.И., Пронин А. К. Алгоритмы поиска экстремальных разбиениймножеств большой мощности // Безопасность информационных технологий. 2006,- № 1.-е. 52.54.

43. Борзунов Г.И., Пронин А. К. Базовые алгоритмы поиска экстремальных разбиений множеств // Безопасность информационных технологий. 2004. - № 4. - С. 58.60.

44. Борзунов Г.И., Степанова О.П., Стрельников Б.А., Фирсов A.B. Автоматизация оформления результатов предпроектных исследований при создании САПР тканей. Деп. в ЦНИИТЭИлегпром. 7987/7а нд. 1988.

45. Борзунов Г.И., Стрельников Б.А., Степанова О.П., Фирсов A.B. Методическая разработка к лабораторным работам по курсу "Системное программирование". -М.: РИО МГТА, 1993. 41 с.

46. Борзунов Г.И., Фирсов А. В. Необходимые и достаточные условия существования однослойного ткацкого переплетения // Изв. вузов. Технология текстильной промышленности. 2007. - № 3. - 123 . 126.

47. Борзунов Г.И., Фирсов A.B. Автоматизация построения полутораслойных и двухслойных переплетений // Материалы науч. конф. проф.-преп. состава, науч. сотр. и асп. МГТА имени А.Н.Косыгина. М.: РИО МГТА, 1996.-С. 84.85.

48. Борзунов Г.И., Фирсов A.B. Возможности узорообразования на установке с беззевным способом образования ткани // Бесчелночное ткачество. Строение и проектирование ткани: Межвузовский сборник научных трудов. М.: МГТА, 1993. - С. 50.54.

49. Борзунов Г.И., Фирсов A.B. Использование трехмерной графики для визуализации текстильных материалов в интерьере. Тез. докл. науч.-техн конф. проф.-преп. состава, науч. сотрудников и аспирантов. М.: МГТА 1998.-С. 71.72.

50. Борзунов Г.И., Фирсов A.B. Методические указания к выполнении: лабораторных работ по курсу 'Аппаратно-программные средства ИСАУ". -М.: РИО МГТА, 1994. 15 с.

51. Борзунов Г.И., Фирсов A.B. Методические указания к выполнении: лабораторных работ по курсу "Программные средства визуализации данных". М.: РИО МГТА, 1994. - 16 с.

52. Борзунов Г.И., Фнрсов A.B. Методические указания к выполнении: лабораторных работ по курсу "Системное программное обеспечение". Раздел "Архитектура ПЭВМ и основные средства ассемблера". М.: РИО МГТА. 1996.28 с.

53. Борзунов Г.И., Фирсов A.B. Моделирование ткацких узоров на ПЭВМ // Известия вузов. Технология текстильной промышленности. 1994. -№6.-С. 40.42.

54. Борзунов Г.И., Фирсов A.B. Необходимое и достаточное условия существования однослойного ткацкого переплетения // Известия вузов. Технология текстильной промышленности. 2006. - №3, - С.40.42.

55. Борзунов Г.И., Фирсов A.B. Программирование графических представлений ткацких рисунков средствами языка СИ //Доклад на науч. конф. проф.-преп. сост., науч. сотр. и асп. МТИ имени ATI. Косыгина.5-7 февраля 1991 г. М.: МТИ, 1992 -С. 38.

56. Борзунов Г.И., Фирсов A.B., Палаткин М.В. Визуализация цветных ткацких рисунков //Доклад на науч. конф. проф.-преп. сост., науч. сотр. и асп. МГТА имени А.Н. Косыгина.3-5 февраля 1992 г. М.: МГТА, 1992 -С. 57.

57. Борзунов Г .И., Журавлева Т. А.,Заболотская Е.А. Автоматизированное проектирование рисунков для мелкоузорчатых тканей с эффектами иллюзий// Машиностроение, приборостроение, энергетика. -М.: Изд-во Моск. ун-та, 1994. С.278.285.

58. Бреус В. Информация управляет качеством, а следовательно и конкурентоспособностью. 24.12.2004. TEXTILMARKET.RU.

59. Бувайло Д.П., Толок В.А. Быстрый высокопроизводительный алгоритм для разделения нерегулярных графов.// BicroiK Запор1зького державного ушверситету. 2002. - № 2. - с. 1 . 10.

60. Вендров A.M. Проектирование программного обеспечения экономическихинформационных систем: Учебник М.: Финансы и статистика, 2005. - 352 с.

61. Виноградов И. М. Основы теории чисел. М.: Наука, 1972. - 167 с.

62. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. -СПб.: БХВ-Петербург, 2002. 606 с.

63. Воинов А. Е Автоматизация подготовки точечных рисунков для их воспроизведения с использованием технологии ремизного ткачества. Дис. . канд. техн. наук. М.: МГТУ им А.Н. Косыгина, 2003. - 165 с.

64. Горбатов В.А. Основы дискретной математики: Учебное пособие для студентов вузов. -М.: Высш. шк., 1986.

65. Дамянов Г.Б., Бачев Ц.З., Сурнина Н.Ф. Строение ткани и современные методы ее проектирования. -М: Легкая и пищевая промышленность. 1984 -240 с.

66. Заборовский Ю.А., Морозов Г. К., Петренко А. И. и др. Автоматическое программирование жаккардовых ткацких рисунков. -Киев: Техника, 1978, -198 с.

67. Информационно аналитический портал "Ивановский текстиль" Электронный ресурс. - Режим доступа: http://www.ivtextile.ru/

68. Калистратова С.Н. Матричный метод построения креповых переплетений //

69. Изв. вузов. Технология текстильной промышленности. 1968. - №4.

70. Кальченко А.И., Муратова Г.И. Автоматизированная технология проектирования хлопчатобумажных тканей. -М.: ЦНИИТЭИлегпром, 1991, 27 с.

71. Карпов Б., Баранова Т. С++: специальный справочник. СПб.: Питер, 2001. - 480 с.

72. Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. М.: Мир, 1977. - 724 с.

73. Ковтанюк Ю. С. CorelDRAW для дизайнера. CorelDRAW для дизайнера. Под Windows Vista + приложение. МК-Пресс, 2008. - 1648 с.

74. Козлов В. Н. Основы художественного оформления текстильных изделий: Учебник для вузов. М.: Легкая и пищевая промышленность, 1981. -264 с.

75. Крапоткина Т.И. Система генерации ткацких переплетений на ЭВМ // Сб. науч. трудов ЦНИИЛВ. -М.:ЦНИИТЭИлегпром, 1990.

76. Крылов Г.А. Автоматизированная система проектирования тканей «Авто-дессинатор»// Текстильная промышленность. 1979. - № 3. С. 42 . 44.

77. Кутепов О.С. Строение и проектирование тканей. -М.: Легпромбыт издат. 1988.-224 с.

78. Лазишвили Д.Г. Исследование возможности выработки различного ассортимента камвольных тканей по единому заправочному расчету // Дисс. . канд. техн. наук. -М.:МТИ, 1979.

79. Лацис А. Как построить суперкомпьютер. -М.: Бестселлер, 2003. -240 с.

80. Липский В. Комбинаторика для программистов.-М.: Мир, 1988. 213 с.

81. Лунд-Иверсен Б. Ткацкие переплетения. Перевод с норвежского. -М.: Лег-промбытиздат, 1987.- 103 с.99; Макконелл Дж. Основы современных алгоритмов. 2-е дополненное издание. М:: Техносфера, 2004. - 368 с.

82. Малецкая С. В. Разработка автоматизированных методов проектирования узоров многоцветных тканей. Дис. докт. техн. наук. -М.: МГТУ им А.Н. Косыгина. 2003 . — 363 с.

83. Мальгунова H.A., Сафьянников Н.М., Буренева H.A. Построение заправочных рисунков ремизного ткачества с помощью компьютера // Материалы юбилейной науч.-техн. межвуз. конф. Ч.З. -СПб.:СПГУТД, 2000.

84. Мансуров Ф.К., Уразов Н.Х. О целенаправленном поиске ткацкого переплетений с использованием ЭВМ // Изв.вузов. Технология текстильная промышленности. 1989. - N 1. - с. 47.50.

85. Мариева Н. Г., Мариев В. А., Блинов И. П. Программа построения переплетений на основе четырёхэлементного заправочного рисунка// Текстильная промышленность, 1999. №1. - с. 12.

86. Мартынова А. А., Слостина Г. Л., Власова Н. А. Строение и проектирование тканей. — М.: РИО МГТА, 1999. -434 с.

87. Мартынова A.A., Власова H.A. Использование ЭВМ в проектировании тканей // Текстильная промышленность. 1987. - №8. -С.38.39.

88. Милашюс В.М. Матричный метод построения саржевых переплетений // Изв. вузов. Технология текстильной промышленности. 1980.- №1.

89. Морозов Г.К., Осиповская М.Е., Андреев А.Ф., Каган В.М. Система подбора переплетений для однослойных тканей. Программа для ЭВМ. Базы данных. Топология интегральных микросхем.// Инф. бюллетень официальной регистрации РОСПАТЕНТа. Вып. №1, 1994.

90. Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных систем. -Спб.: БХВ-Петербург, 2002.-400 с.

91. Никитин М.Н. Теория ткацких переплетений на математической основе. -М.: Легкая индустрия, 1971.

92. Николаев С. Д., Малецкая С. В. Пестроткани. Особенности строения и технологии выработки.-М.: МГТУ им. А. Н. Косыгина,2005.-248 с.

93. Новиков Ф. А. Дискретная математика для программистов. СПб.: Питер, 2008 г.- 384 с.

94. Основы компьютерной стеганографии: Учебное пособие для вузов./А.В. Аграновский, П.Н. Девякин, P.A. Хади, A.B. Черёмушкин. -М.: Радио и связь, 2003. 152 с.

95. Плюханова Т.Ю. Разработка и проектирование тканей новой структуры. Авто-реф. дис. канд. техн. наук. -Иваново.: Ивановская государственная текстильная академия. 2000. 19 с.

96. Пономаренко С. И. Adobe Photoshop CS3 Extended. СПб.: БХВ - Петербург, 2008. -1072 с.

97. Провести НИР. Разработать ТЭО и выдать исходные требования на АРМ дес-синатора для САПР тканей. Исследование процессов проектирования тканей: Отчет о НИР (заключительный) / ЦНИИШерсти, Моск.текст.ин-т -№ ГР 81051797-М., 1986. Т. 1,-84 с.

98. Проскуряков С. А., Борзунов Г. И. Автоматизированная система подготовки к производству семейства видорисунков одного артикула.// 1. Сборник научно исследовательских работ МТИ-ЛМТИ. -М.: МТИ, 1981. - с. 253.259.

99. Разработка базы данных регулярных переплетений для автоматизированного проектирования тканей: Отчет о НИР (заключительный) / Моск.текст.ин-т; Руководитель темы Г. И. Борзунов. -№ ГР 0187.0080148. -М., 1987. 80 с.

100. Раченкова О.М. Разработка метода расчета рациональных параметров строения тканей различного переплетения с учетом технологии их изготовления. Дис. канд. техн. наук. -М.: МГТУ им А.Н. Косыгина, 2000. 239 с.

101. Розанов Ф.М., Кутенков О.С., Жупикова Д.М., Молчанов С. В. Строение и проектирование тканей. М.: Гизлегпром, 1953. - 471 с.

102. Романовский И. В. Алгоритмы решения экстремальных задач. М.: Наука, 1977. - 352 с.

103. Селиванов Г. И. Строение однослойных элементов тканей//Науч. тр. МТИ.— 1954, № 12. С. 15.

104. Сидоров В.Ю., Алексеева H.H., Розанов А.Ф. Зарубежное ткацкое оборудование. Текстильная промышленность. № 3, 1989, с.43.

105. Склянников В.П. Оптимизация строения и механических свойств тканей и химических волокон. М., 1974.

106. Скоков П.И., Казарновская Г.В. Применение ЭВМ для проектирования цветных рисунков // Известия вузов. Технология текстильной промышленности, 1989, №6, с. 97-98.

107. Слостина Г.Л., Борзунов Г.И., Фирсов A.B. Построение мелкоузорчатых переплетений на ЭВМ. Учебное пособие. М.: РИО МГТУ, 1999. -24 с.

108. Страуструп Б. Язык программирования С++. СПб.; М.: «Невский диалект» - «Издательство БИНОМ», 1999.-991 с.

109. Суркова В. М., Могильный А. Н. МЕТОДИЧЕСКИЕ УКАЗАНИЯ и задания к контрольным работам по дисциплине «САПР тканей» для студентов специальности 260704 «Технология ткачества» заочной формы обучения. СПб.: ГОУВПО СПГУТД, 2007.- 37 с.

110. Сурнина Н.Ф., Крапоткина Т.И., Попилина Г.П., Желенкова Л.Г Автоматизация проектирования тканей. // Текстильная промышленность. № 6, 1989, с.60.

111. Фирсов А. В. Разработка метода проектирования рисунков мелко -узорчатых переплетений и его реализация на ПЭВМ// Дис. канд. техн. наук. М.:1. МГТА .-1995.-117 с.

112. Фирсов А. В. Теоретические и прикладные аспекты разработки автоматизированных систем управления проектированием тканых полотен// Дисс. .докт. техн. наук. -М.: МГТУ им. А.Н. Косыгина. 2007. - 351 с.

113. Фирсов A.B., Страшнов А.Ю. Модульная система многовариантного проектирования тканей // Химические волокна. 2005. - № 2. - С.32.34.

114. Фомин Б. М. Состояние и перспективы развития российского рынка продукции текстильной и легкой промышленности // Мир текстиля. Весна 2008. - С. 6.9.

115. Хавкин В.П., Живетин В.В., Ребарбар Я. М., Карпинский В.В. Системы автоматизированного проектирования изделий легкой промышленности Текстильная промышленность. № 2, 1989, с.22.

116. Хлопкоткачество. Справочник / Букаев П.Т., Оников Э.А., Малько JI.A. и др. -М.:Легпромбытиздат, 1987.

117. Художественное оформление текстильных изделий/С. А. Малахова, Т. А. Журавлева, В. Н. Козлов и др. М.: Легпромбытиздат, 1988. -304 с.

118. Хьюоз К., Хьюоз Т, Параллельное и распределенное программирование с использованием С++. -М.: Издательский дом «Вильяме». 2004. -672 с.

119. Чугин В.В. Определение рельефа ткани по заправочному рисунку // Изв.вузов.Технология текстильной промышленности. № 3,1989, с. 54.

120. Шерстоткачество. Справочник / Разумовский СИ., Петрова И.Н Зыбина Л.А. и др. -М.: Легпромбытиздат, 1988.

121. Шиханович Ю. А. Введение в современную математику. М.: Наука, 1965.- 376 с.

122. Якобовский М.В. Обработка сеточных данных на распределенных вычислительных системах. // Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов. 2004. Вып.2. - . с. 40-53.

123. Яншин В. В., Калинин Г. А. Обработка изображений на языке СИ для IBM PC: Алгоритмы м программы. М.: Мир, 1994. - 241 с.

124. Alex Pothen, Horst D. Simon, and Kang-Pu Liou. Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal of Matrix Analysis and Applications, 11(3):430.452, 1990.

125. Andrews G. R. Foundations of Multithreading, Parallel Distributed Programming. -N. Y.: AddisonWeslley, 2000.

126. B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 1970.

127. Baechinger Th., Krause H.W. Computer aided Textile Design and Elec tronic Dobby Motion Control// Computers in the World of Design. -1984. P.513.633.

128. Barker M. (Ed.) Cluster Computing. Whitepaper at http://www.dcs.port.ac.uk/~mab/tfcc/WhitePaper/. 2000.

129. Barker M. (Ed.) Cluster Computing. Whitepaper at http://www.dcs.port.ac.uk/~mab/tfcc/WhitePaper/. 2000.

130. Bradford L. Chamberlain. Graph Partitioning Algorithms for Distributing Workloads of Parallel Computations. 1998.

131. Bruce Hendrickson and Robert Leland. An improved spectral graph par-titioning algorithm for mapping parallel computations. Technical Report SAND92-1460, Sandia National Laboratories, 1992.

132. С. C. Paige and M. A. Saunders. Solution to sparse indefinite systems of linear equations. SIAM Journal on Numerical Ananlysis, N12:617.629, 1974.

133. С. M. Fiduccia and R. M. Mattheyses. A linear time heuristic for improving network partitions. In In Proceedings 19th IEEE Design Automation Conference, pages 175.181, 1982.

134. Clark D/ Breaking the TERRAFLOPS barrier//Computer, 1997, v. 30, №2, p. 1214.

135. D. M. Nicol, «Rectilinear partitioning of irregular data parallel computations,»

136. Tech. Rep. 91-55, ICASE, NASA Langley Res. Ctr., Jul. 1991.

137. Delp E. J.,Mitchel O.R. Image compression using block truncation coding.IEEE Trans.Commun.,v. COM-27, #9, 1979, pp.1335 1342.

138. Dobrzanski E. Owczarz R. Proektowanie wzorow kolorystycznychtkanin wspomagane komputerem // Przglad wlokienniczy. 1980. - № 1. - s. 29.32.

139. Donat F. Bindungs-Lexikon for Schaftweberei. Wien. Pest. Leipzig: A. Hartlebens Verlag, 1903.

140. Donat F. Die farbige Gewebemusterung. Wien und Leipzig: A. Hartlebens Verlag, 1907.

141. Donat F. Methodik der Bindungslehre, Dekomposition u. Kalkulation for Schaftweberei. Wien und Leipzig: A. Hartlebens Verlag, 1908

142. Fiberworks PCW . Электронный ресурс. Режим доступа: http://www.fiberworks-pcw.com/

143. Fujita Т. Warp Lifting Plan of weaving Calculated with Matrices // J. Text. Mach. Soc. Japan (Eng. Ed.). 1962. №1.

144. G. L. Miller, S.-H. Teng, W. Thurston, and S. A. Vavasis. Automatic mesh partitioning. In A. George, J. R. Gilbert, and J. W. H. Liu, eds., Graph Theory and Sparse Matrix Computation, Springer-Verlag, 1993.

145. Galuszynski S., Hepworth K. Komputerowa symulacja procesu firmava nia tkaniny // Przglad Wlokiermczy. 1979, № 6.

146. Gary L. Miller, Shang-Hua Teng, and Stephen A. Vavasis. A unified geometric approach to graph separators. In Proceedings of 31st Annual Symposium on Foundations of Computer Science, pages 538.547, 1991.

147. George. Nested dissection of a regular finite-element mesh. SIAM Journal on Numerical Ananlysis, N10:345.363, 1973.

148. H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, NY, 1987.

149. Hendricson В., Leland R. Multidemensional spectral load balancing. Rep. SAND93-0074, Sandia National Laboratories, Albuquerque, NM, January 1993.

150. Herrmann A. CAD/CAM-System fur Webereien. Textil betrieb. N : 1986.

151. Hollstein H. Symbolik der Gewebebindungen for die Direkteingabe in den Computer// Sbornik vedeckych. Praci/ Visoke skoly strojni a textilni v Libereci. 1980. №12.

152. Hoskins I.A., King M.W. An Interactive Database for Woven Texstil Design // Annual World Conference. «Computers of the World of Textile», Honj Kong, -September 26-29, 1984. -Manchester, England. The Textile Institute, 1984. -P.32.46.

153. J. P. Singh, Parallel Hierarchical N-iBody Methods and their Implications for Multiprocessors. PhD thesis, Stanford Univ., Dept. of Electrical Engineering, Feb. 1993.

154. J. P. Singh, Parallel Hierarchical NbBody Methods and their Implications for Multiprocessors. PhD thesis, Stanford Univ., Dept. of Electrical Engineering, Feb. 1993.

155. John R. Gilbert, Gary L. Miller, and Shang-Hua Teng. Geometric mesh partitioning: Implementation and experiments. In Proceedings of International Parallel Processing Symposium, 1995.

156. John R. Gilbert, Gary L. Miller, Shang-Hua Teng. Geometric Mesh Partitioning: Implementation and Experiments, 1994.

157. Lectra Systemes Home. Электронный ресурс. Режим доступа: www.lectra.com

158. Moravec V. Anwendung elektronischer Datenverarbeitung fur die Gewebebindung //Textiltechnik. 1981. № 1.

159. NedGraphics Home. Электронный ресурс. Режим доступа: www.nedgraphics.com

160. Ou С., Ranka S., Fox G «Fast and parallel mapping algorithms for irregular and adaptive problems» Journal of Supercomputing. 1996. 10. P. 119 140

161. Patra A., Kim D Efficient mesh partitioning for adaptive hp finite element methods International Conference on Domain Decomposition Methods. 1998

162. Pilkington J., Baden S Partitioning with space filling curves Technical Report CS94-349, Dept. of Computer Science and Engineering, Univ. of California. 1994

163. Pothen A «Graph partitioning algorithms with applications to scientific computing» Kluwer Academic Press, 1996

164. R. J. Upton and R. E. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, N36:177.189, 1979.

165. Rozelle W. N. Don't give up weaving training //Textile world. 1979. - #9. - p. 61,71.

166. Rudloff E., Muhlmann R. Neuer Standart Gewebebindungen mit Darstel-lung in Matrixform // Textiltechnik. 1983. № 6.

167. T. Bui and C. Jones. A heuristic for reducing fill in sparse matrix factorization. In 6th SIAM Conf. Parallel Processing for Scientific Computing, pages 445.452, 1993.

168. T. N. Bui, S. Chaudhuri, F. T. Leighton, and M. Sipser. Graph bisection algorithms with good average case behavior. Combinatorica, N7:171.191, 1987.

169. Weavelt A Handweaving design software Program. Электронны. ресурс]. -Режим доступа: http://www.weaveit.com/demos.aspx

170. WeaveMaker Home. Электронный ресурс. Режим доступа: http://www. weavemaker.com/1 /index.php

171. WeavePoint Home. Электронный ресурс. Режим доступа: http ://weavepoint.com/

172. Weaving short warps // Textile industries. 1978. - #5. - с/ 90.92.Jederan M., Csaszi F. Szott kelmeszerkezetek tipizalasi es a tipizalas elmeleti alapjai// Magyar textiltechnika. - 1980. - #1.- s. 1.3.

173. Whimsical Weaver Электронный ресурс. Режим доступа: http://historicweaving.eom/ww/weaving.htm#Assumptions).

174. Xiaogang Chen. Characteristics of Cloth Formation in Weaving and Their Influence on Fabric Parameters // Textile Research Journal, Apr 2005; 75: P 281.287.