close

Вход

Забыли?

вход по аккаунту

?

Методы анализа и разработки параметризированных алгоритмов

код для вставкиСкачать
ФИО соискателя: Быкова Валентина Владимировна Шифр научной специальности: 05.13.17 - теоретические основы информатики Шифр диссертационного совета: Д 212.099.11 Название организации: Сибирский федеральный университет - ФГАОУ ВПО Адрес организации: 6
?а правах рукописи
?ыкова ?алентина ?ладимировна
??Т??Ы ??????? ? Р??Р???Т??
П?Р???ТР???Р?????ЫХ ????Р?Т???
???????? ? теоретические основы информатики
??Т?Р?Ф?Р?Т
диссертации на соискание ученой степени
доктора физико?математических наук
?расноярск ? ????
Работа выполнена на базовой кафедре вычислительных и информацион?
ных технологий Ф???У ?П? ?Сибирский федеральный университет?
?аучный консультант?
доктор технических наук? профессор
Потапов ?иктор ?льич
?фициальные оппоненты
доктор физико?математических наук? профессор
?олоколов ?лександр ?лександрович?
?мский филиал Ф??У? ?нститута математики
им? С??? Соболева С? Р??? лаборатория дискрет?
ной оптимизации? заведующий лабораторией
доктор технических наук? профессор
?гибалов ?еннадий Петрович?
Ф???У ?П? ??ациональный исследовательский
Томский государственный университет??
кафедра защиты информации и криптографии?
заведующий кафедрой
доктор физико?математических наук? профессор
Сафонов ?онстантин ?ладимирович?
Ф???У ?П? ?Сибирский государственный аэро?
космический университет им? академика
??Ф? Решетнева?? кафедра прикладной математики?
заведующий кафедрой
?едущая организация?
Ф???У ?П? ??ациональный исследовательский
Томский политехнический университет?
?ащита состоится ? ноября ???? г? в ?? часов на заседании диссертаци?
онного совета ? ?????????? при Сибирском федеральном университете по
адресу? г? ?расноярск? ул? ?иренского? ??? ауд? У?? ????
С диссертацией можно ознакомиться в библиотеке Сибирского федераль?
ного университета?
?втореферат разослан ?
Ученый секретарь
диссертационного совета
?
???? года?
Покидышева ?юдмила ?вановна
??Щ?Я Х?Р??Т?Р?СТ??? Р???ТЫ
?ктуальность темы? Понятие алгоритма является не только одним
из важнейших понятий математики? но одним из основных понятий совре?
менной науки? Чтобы ориентироваться в сегодняшнем мире алгоритмов?
необходимо уметь сравнивать различные алгоритмы решения одних и тех
же задач? причем не только по качеству выдаваемого решения? но и по
характеристикам самих алгоритмов? Точный язык для обсуждения этих
вопросов дает теория сложности вычислений? ?е результаты составляют
теоретическую основу современной информатики и программной инжене?
рии? ?лгоритм как звено триады ?задача ? алгоритм ? программа?? с одной
стороны? предопределяет производительность реализующей его програм?
мы? а? с другой стороны? способствует глубокому проникновению в реша?
емую задачу и нахождению эффективных методов ее решения?
? теории сложности вычислений выделяют два специальных раздела?
Это собственно сложность вычислений ? раздел? включающий в себя ана?
лиз сложности задач ?нахождение нижних оценок времени решение за?
дач?? классическую дихотомию задач ?классы сложности P? ?P??
теорию ?P?полноты? ?нализ алгоритмов ? раздел? направленный на изу?
чение сложности алгоритмов с различных точек зрения? но главным об?
разом с точки зрения ресурсов? необходимых для их выполнения? ?нализ
алгоритмов предполагает поиск критериев сравнения алгоритмов? нахож?
дение асимптотических оценок сложности? классификацию алгоритмов по
сложности и выработку рекомендаций по построению эффективных алго?
ритмов? При этом под сложностью алгоритма традиционно понимают вре?
мя осуществления вычислительного процесса? порождаемого алгоритмом?
то есть ресурсную или вычислительную сложность алгоритма? Типичный
уровень анализа ? установление класса сложности и асимптотических оце?
нок функции временной сложности исследуемого алгоритма с ориентацией
на худший случай? Такие функции формально задают время выполнения
алгоритма на равнодоступной адресной машине ?Р??? в зависимости от
длины исходных данных ?длины входа алгоритма?? Полученные в резуль?
тате анализа асимптотические оценки сложности алгоритма служат верх?
ними оценками сложности решаемой задачи и согласно ??СТ ????????
определяют производительность программы? реализующей этот алгоритм?
?еобходимость исследований в области анализа и разработки эффек?
тивных ?с точки зрения потребляемых ресурсов? алгоритмов обусловлена?
прежде всего? тенденциями развития современных информационных тех?
нологий и особенностями подлежащих решению вычислительных задач?
?адачи? возникающие в системах принятия решений? распознавания обра?
зов? компьютерной безопасности? искусственного интеллекта и биоинжене?
рии? при создании и эксплуатации крупномасштабных информационных и
?
телекоммуникационных систем? характеризуются? как правило? большой
размерностью и высокой вычислительной сложностью? Сложность вычис?
лений порой настолько высока? что с ней не могут справиться мощности
современных компьютеров? ?ктуальность разработки теоретических основ
создания программных систем для решения подобных задач отражена в
приоритетных направлениях развития науки? технологий и техники ?при?
каз президента РФ от ? июля ???? г? ? ?????
Широкий класс задач? возникающих в рамках современных информа?
ционных технологий? составляют задачи выбора? ?тличительная особен?
ность этих задач ? поиск решения в конечной области? ? них требуется
найти одно из допустимых решений ?в задачах удовлетворения ограниче?
ний? или оптимальное решение ?в задачах комбинаторной оптимизации??
?ля ?P?трудных задач выбора характерен стремительный рост числа до?
пустимых решений с увеличением размерности задачи? что делает поиск
решения полным перебором? алгоритмически неэффективным? ?ногие за?
дачи выбора могут быть математически сформулированы как задачи на
графах и гиперграфах? ?менно ?P?трудные задачи выбора? допускающие
графовое и гиперграфовое представление? составляют класс рассматри?
ваемых в диссертации задач?
Теория сложности вычислений сформировала фактический стандарт
эффективной вычислимости задачи? ?адачу считают эффективно ?полино?
миально? вычислимой? если существует алгоритм? время выполнения кото?
рого ограничено полиномом от длины входа? ? то же время имеется боль?
шое число ?P?трудных задач? для которых пока не получено эффектив?
ных алгоритмов? Справедливость гипотезы P = ?P означает? что таких
алгоритмов вообще не существует? ?ыполнение этого неравенства предпо?
лагается в рамках всей диссертационной работы? ? развитие классических
основ теории сложности вычислений и анализа алгоритмов значительный
вклад внесли ???? ?олмогоров? ???? ?арков? ???? ?агорный? ???? ?аль?
цев? ??С? Цейтин? Ю??? Янов? ???? ?евин? Ю??? ?ршов? ???? Разборов?
???? Семенов? ???? Успенский? ???? Трахтенброт? Э??? Пост? ???? Тью?
ринг? ?? Черч? Р? ?арп? С? ?ук? ?? ?эри? ?? ?жонсон? ?? ?нут? Р? Тарьян?
Х? Пападимитриу? ?? Стайглиц и многие другие российские и зарубежные
ученые?
?а сегодняшний день основными подходами к решению ?P?трудных за?
дач выбора являются? сужение задачи с целью выделения легких частных
случаев? сокращение перебора за счет ?разумной? организации стратегии
поиска решения? нахождение приближенных решений с гарантированной
ошибкой? применение эвристик и метаэвристик? параметризация задачи?
Параметризированный подход ? сравнительно новый подход ?борьбы? с
трудноразрешимостью задач выбора? ?сновная идея параметризированно?
го подхода состоит в том? чтобы с помощью некоторого числового пара?
?
метра структурировать и измерить конечное пространство поиска? ? Роль
параметра ? выделить основной источник неполиномиальной сложности
?P?трудной задачи и показать? ?комбинаторный взрыв? какой величины
можно ожидать при ее решении на тех или иных исходных данных? ?оз?
никающие при этом алгоритмы называются параметризированными? Па?
раметризированный алгоритм ? основной объект исследования диссер?
тационной работы?
Параметризированный алгоритм ? это алгоритм? осуществляющий по?
иск точного решения задачи путем просмотра всего или некоторой части
конечного отструктурированного пространства поиска? ?ремя его выпол?
нения представляется функцией? зависящей от двух переменных? n ? дли?
ны входа алгоритма и k ? числового параметра задачи? ?еобходимо отме?
тить? что для одной и той же задачи возможны разные параметризации
относительно различных параметров? ?ногда возникают параметризации
с несколькими параметрами? ?аибольший интерес представляют парамет?
ризации ?P?трудных задач? приводящие к алгоритмам? время выполне?
ния которых полиномиально зависит от длины входа и неполиномиаль?
ным образом ? от значения параметра? ?сли такой параметр для рас?
сматриваемой задачи существует? то задача называется ?P??разрешимой
?
? относительно этого параметра? а соответству?
ющий алгоритм ? ?P??алгоритмом? С помощью ?P??алгоритмов можно
решать задачи выбора большой размерности при малых фиксированных
значениях параметра?
Параметризированный подход к оценке сложности вычислений был
сформулирован в конце прошлого столетия Р? ?ауни и ?? Феллови? ? ?о?
нечно? алгоритмы с функциями сложности от двух и более переменных
встречались всегда? Параметризированный подход к сложности вычисле?
ний использован еще в теории графовых миноров ?? Робертсона и П? Сей?
мура? ? ?днако только Р? ?ауни и ?? Феллови четко определили роль па?
раметра и ввели понятие ?P??разрешимости задачи? ? российской науч?
ной среде параметризированный подход также известен и востребован? ?го
идеи и воплощения можно найти в публикациях российских ученых? рабо?
тающих в области дискретной оптимизации и целочисленного программи?
рования? Ю??? ?уравлева? ???? Сергиенко? ???? ?меличева? ???? ?овале?
ва? ???? ?равцова? ???? ?еонтьева? ???? ?ереснева? Э?Х? ?имати? ???? ?и?
зинга? С??? Севастьянова? ???? ?олоколова? ???? Романовского? Ю??? ?о?
четова? ??Х? Сигала? ???? Пяткина? ???? Серваха? ??П? ?льева? ???? ?лек?
??????P?r???t?r ?r??t????
? ???? ??? ?r??? ?? P?r???t?r???? ????????t? t???r?? ? ??r???? ????????r?? ??r????r?
??r???? ?????
? ?????? ??? ??????s ?? P?r???t?r???? ????????t?? ? ??? ??r?? ??r????r???r???? ?????
? ????rts?? ??? ??????r P??? ?r??? ????rs? ??? ????r?t???? ?s???ts ?? tr?????t? ?? ??
????r?t??s? ? ????? ? ?? ?? ? P? ????????
?
сеева? ???? ?ондаренко? ???? Щербины и многих других?
? настоящее время параметризированный подход к оценке сложности
вычислений развивается в нескольких направлениях? определение иерар?
хии классов сложности параметризированных задач? установление условий
?P??разрешимости? выявление взаимосвязи между параметризированной
сложностью и полностью полиномиальными схемами приближений? созда?
ние теоретических основ параметризированной алгоритмики ?методов ана?
лиза и разработки параметризированных алгоритмов??
Существующие на сегодняшний день открытые проблемы параметри?
зированной алгоритмики составляют предмет исследования диссерта?
ции? Укажем наиболее существенные из них? решению которых в работе
уделено основное внимание?
?? ? многочисленных работах по параметризированному подходу к ана?
лизу сложности вычислений традиционно применяются методы клас?
сической ?одномерной? систематизации? ?ежду тем классическая од?
номерность ограничивает глубину анализа параметризированных ал?
горитмов с функциями сложности двух и более переменных? ?ля ис?
следования таких функций сложности нужны специальные инстру?
менты анализа?
?? ?ля одномерного случая ?когда функция сложности алгоритма зави?
сит только от длины входа? также есть нерешенные проблемы? Суть
одной из них состоит в отсутствии простых и удобных для практи?
ки математических средств распознавания современных сложност?
ных классов алгоритмов? Сегодняшняя алгоритмическая практика
уже давно вышла за рамки классической дихотомии ?с классами по?
линомиальных и экспоненциальных алгоритмов? и оперирует пятью
сложностными классами алгоритмов? ?ыделены субполиномиальные
?быстрые? алгоритмы из полиномиального класса? субэкспоненци?
альные и гиперэкспоненциальные алгоритмы из экспоненциального
класса? ?спользование непосредственного асимптотического оцени?
вания в этих условиях? как правило? приводит к громоздким вычис?
лениям? ?звестны попытки введения классификационного признака?
позволяющего распознавать современные сложностные классы алго?
ритмов? Так? ???? ?оловешкин и ???? Ульянов предложили в качестве
такого признака употреблять угловую меру асимптотического роста
функций сложности? ? ?днако применение этой меры на практике за?
частую ограничено трудностями вычислительного характера ?она не
просто находится для некоторых логарифмически?экспоненциальных
? ?оловешкин ????? Ульянов ???? ?етод классификации вычислительных алгоритмов
по сложности на основе угловой меры асимптотического роста функций ?? ?ычисли?
тельные технологии? ? ????? ? Т? ??? ? ??? ? С? ??????
?
функций? и сложностью ее обобщения на функции многих перемен?
ных? ?ругая проблема связана с анализом рекурсивных алгоритмов?
? настоящее время основным инструментом анализа рекурсивных ал?
горитмов является метод рекуррентных соотношений? ?дея этого ме?
тода состоит в построении и решении рекуррентного соотношения?
которому удовлетворяет функция сложности анализируемого алго?
ритма? ?ак известно? общих правил решения рекуррентных соотно?
шений пока не найдено? Поэтому всякий математический результат?
дающий какой?либо общий подход к решению данной проблемы? инте?
ресен как теоретически? так и практически? ? подобным результатам
относятся методы решения линейных рекуррентных соотношений с
постоянными коэффициентами? а также оценки ?ж? ?ентли? ?? Ха?
кена? ?ж? Сакса? полученные для времени выполнения рекурсивного
алгоритма? организованного по принципу ?разделяй и властвуй?? ?
?ктуальны подобные оценки и для других широко употребляемых
принципов организации рекурсии? ?апример? для принципа ?умень?
шай и властвуй?? характерного для метода динамического програм?
мирования? ? этом случае на каждом шаге рекурсии размерность
задачи понижается на некоторую константу?
?? Параметризированный подход позволяет исследовать различные па?
раметризации одной и той же задачи? каждая из которых может
приводить или не приводить к ?P??алгоритмам? ? настоящее вре?
мя уже известны некоторые специальные методы конструиро?
вания ?P??алгоритмов? ?аиболее универсальный метод разра?
ботки ?P??алгоритмов для задач выбора? представимых графами и
гиперграфами? ? метод динамического программирования по дере?
ву декомпозиции? автором которого считается ?? ?одлаендер? ? Про?
странство поиска здесь структурируется на основе специальной де?
композиции входного графа или гиперграфа и измеряется через чис?
ловой параметр? отражающий ширину этой декомпозиции? При всей
теоретической привлекательности данного метода практическое его
применение ограничивается двумя серьезными проблемами? Первая
проблема связана с высокими потребностями в памяти получаемых
?P??алгоритмов? а вторая ? с решением ?P?трудной задачи ? с вы?
числением древовидной ширины графа?
Целью диссертации является разработка теоретических основ и
практических решений проблем анализа параметиризированных алгорит?
? ???t??? ????? ????? ??? ???? ???? ? ????r?? ??t??? ??r s?????? ??????????????q??r
r???rr????s ?? ?????? ???s? ? ????? ??? ???? ? P? ??????
? ?????????r ???? ?r?????t?? ????r?t???? t?????q??s ??? r?s??ts ?? Pr??? ???? ?????
??r????r???r??? ???? ????? ? ????? ? P? ??????
?
мов? а также проблем создания ?P??алгоритмов для решения ?P?трудных
задач выбора на графах и гиперграфах ограниченной древовидной шири?
ны?
?адачи исследования?
?? ?зучение вопросов систематизации алгоритмов по вычислительной
сложности и параметризированного подхода к оценке сложности вы?
числений? Разработка удобных для широкой алгоритмической прак?
тики математических инструментов анализа параметризированных
алгоритмов?
?? ?сследование проблемы анализа рекурсивных процессов и ее решение
для класса рекурсивных алгоритмов? организованных по принципу
?уменьшай и властвуй??
?? ?сследование проблем создания ?P??алгоритмов и практической
применимости метода динамического программирования по дере?
ву декомпозиции? Разработка методов решения этих проблем для
?P?трудных задач выбора? представимых графами и гиперграфами?
?спользуемые в диссертации методы исследования опираются на
аппарат математического анализа? теории графов? дискретной оптимиза?
ции и теории реляционных баз данных?
?аучная новизна и выносимые на защиту положения? ?се ре?
зультаты диссертации являются новыми? Укажем наиболее существенные?
?? Разработаны математические инструменты анализа вычислительной
сложности параметризированных алгоритмов?
? метод распознавания классов субполиномиальных? полиноми?
альных? субэкспоненциальных? экспоненциальных и гиперэкспо?
ненциальных алгоритмов? базирующийся на асимптотике пове?
дения эластичности функций сложности ?одной переменной??
? метод двумерной классификации параметризированных алго?
ритмов на основе частных эластичностей?
?? ?ведены и изучены новые понятия? эластичность алгоритма? неэла?
стичные? эластичные и суперэластичные алгоритмы?
?? Получены верхние и нижние оценки времени выполнения рекурсив?
ных алгоритмов? построенных путем аддитивного уменьшения раз?
мерности задачи на некоторую константу?
?? Разработаны теоретические положения и алгоритмические решения
проблем? возникающих при построении ?P??алгоритмов методом ди?
намического программирования по дереву декомпозиции? ? их число
входят?
?
? теоретические и алгоритмические аспекты применения бинарно?
го сепараторного дерева в решении проблемы памяти?
? два рекуррентных и полиномиальных по времени метода вычис?
ления верхних и нижних оценок древовидной ширины графа и
гиперграфа?
?остоверность и обоснованность результатов диссертации под?
тверждаются строгими математическими доказательствами и аргумента?
циями?
Теоретическая ценность диссертации? ?сновные результаты рабо?
ты имеют преимущественно теоретический характер?
?? Предложен и изучен простой и удобный для алгоритмической прак?
тики математический аппарат исследования вычислительной слож?
ности параметризированных алгоритмов на основе эластичности? ко?
торый не зависит от числа учитываемых параметров? Эластичность?
являясь математически точно определяемой величиной? легко вычис?
ляется для логарифмически?экспоненциальных функций? имеет нуж?
ную для анализа алгоритмов интерпретацию? позволяет сравнивать
между собой алгоритмы и выявлять степень влияния параметра на
время выполнения алгоритма?
?? Решена проблема анализа класса рекурсивных алгоритмов? органи?
зованных по принципу ?уменьшай и властвуй??
?? Разработаны и математически обоснованы методы? способствующие
развитию и практическому применению специального метода кон?
струирования ?P??алгоритмов ?метода динамического программиро?
вания по дереву декомпозиции??
?? Совокупность представленных в диссертации математических мето?
дов составляет теоретическую основу параметризированной алгорит?
мики и позволяет исследовать и создавать ?P??алгоритмы для ре?
шения широкого спектра ?P?трудных задач выбора? возникающих в
рамках новых информационных технологий?
Практическая ценность диссертации? ?сновные предложенные
в работе методы доведены до методик? рекомендаций? алгоритмов и про?
грамм? что подтверждается свидетельствами о регистрации программных
разработок в фонде электронных ресурсов ??аука и образование? Р???
? широкой алгоритмической практике и программной инженерии могут
быть использованы следующие результаты диссертации?
?? ?етодика сравнения алгоритмов по асимптотике поведения эластич?
ностей функций сложности?
?
?? ?етодика установления степени воздействия параметра на слож?
ность параметризированного алгоритма через коэффициент замеще?
ния одного аргумента функции другим аргументом? Такой анализ да?
ет возможность исследовать вычислительные возможности парамет?
ризированного алгоритма на входах большой длины и регулировать
эти возможности путем изменения значения параметра?
?? ?ерхние и нижние оценки времени выполнения рекурсивных алго?
ритмов? построенных путем аддитивного уменьшения размерности
задачи на некоторую константу? ?анные оценки могут служить ре?
комендациями к эффективной организации соответствующих рекур?
сивных вычислений?
?? ?етоды? алгоритмы и программы? касающиеся метода динамическо?
го программирования по дереву декомпозиции? Это математическое
и программное обеспечение поможет решать задачи выбора большой
размерности на графах и гиперграфах ограниченной древовидной
ширины?
?спользование результатов диссертации? Результаты диссертаци?
онной работы переданы и используются? в ?нституте вычислительного
моделирования С? Р?? ?г? ?расноярск? при выполнении проекта ?Раз?
работка интеллектуальных вычислительных комплексов для поддержки
принятия решений при конструировании и эксплуатации сложных техни?
ческих систем и объектов? в рамках Программы Президиума Р??? а также
темы ?Разработка и исследование методов компьютерного моделирования
и обработки данных для информационно?управляющих систем поддерж?
ки принятия решений по повышению уровня пожарной безопасности зда?
ний? в рамках междисциплинарного интеграционного проекта С? Р???
в филиале ??? ?Р??? ?г? ?расноярск? для управления терминально?
складской и транспортно?экспедиционной логистикой грузоперевозок? в
??? ?РУС????чинск? для разработки программ и мероприятий? направ?
ленных на совершенствование управления производством и повышение ин?
формационной безопасности компьютерных систем предприятия? Резуль?
таты диссертации применяются в учебном процессе ?нститута математики
Сибирского федерального университета ?г? ?расноярск? для подготовки
бакалавров и магистров направления ??атематика? ?омпьютерные нау?
ки?? а также ?нститута информатики и телекоммуникаций Сибирского
государственного аэрокосмического университета им? академика ??Ф? Ре?
шетнева ?г? ?расноярск? для подготовки бакалавров направления ?При?
кладная математика? и магистров направления ?Теоретическая информа?
тика?? ?меются акты об использовании?
?пробация работы? ?сновные результаты исследования докладыва?
лись и обсуждались на следующих конференциях и семинарах междуна?
??
родного? всероссийского и региональных уровней? ?сероссийских конфе?
ренциях ?Проблемы оптимизации и экономические приложения? ??мск?
Россия? ????? ?????? ?????? ?сероссийских конференциях по финансово?
актуарной математике и смежным вопросам ??расноярск? Россия? ?????
?????? ???? ?сесибирских конгрессах женщин?математиков ??расно?
ярск? Россия? ????? ?????? ???? Сибирских научных школах?семинарах
с международным участием ??омпьютерная безопасность и криптогра?
фия? ?Тюмень? Россия? ????? Томск? Россия? ????? ?ркутск? Россия?
?????? ??? ?еждународной конференции по эвентологической матема?
тике и смежным вопросам ??расноярск? Россия? ?????? ??? ?сероссий?
ской научно?практической конференции ?Проблемы информатизации ре?
гиона? ??расноярск? Россия? ?????? ???? ?еждународных конференци?
ях по финансово?актуарной математике и эвентоконвергенции техноло?
гий ??расноярск? Россия? ????? ?????? ??? ???r? ??t?r??t????? ?????r????
?Pr?????s ?? ????r??t??s ??? ????r??t??s? ?????? ???r??????? ?????? ???
???r? ?????? ??t?r??t????? ???t???????r???? ?? ??t???t???? ???tr??? ???
????r??t??? ??????????? ???????????? ?????s???rs?? ??ss??? ?????? ???
?????r???? ????t?? t? ?? ??????rs?r? ?? ???????????? ?? t?? ????????
??????st?? ?????r? ??t????t??s Pr?????s? ???rs??? ??????st??? ?????? ???
??t? ??????? ?t????st?? ?????s ??? ??t? ?????s?s ??t?r??t????? ?????r?????
????????? ?????? ?t???? ??????
Публикации? По материалам диссертации автором опубликовано ??
работ? включая монографию ???? ?? печатных работ в журналах и сбор?
никах ?из них ?? статей в ведущих рецензируемых журналах и журналах
из перечня ??? ???????? ? свидетельства о государственной регистрации
комплексов программ ????????
?ичный вклад автора? Результаты диссертации получены соискате?
лем самостоятельно? ? соавторстве выполнены работы ???? ??? ??? ??? ???
??????? в которых вклады авторов равнозначны?
Структура и объем работы? ?иссертация состоит из введения? ше?
сти глав? заключения? библиографического списка и трех приложений? ?з?
ложение иллюстрируется ?? рисунком и двумя таблицами? ?иблиографи?
ческий список включает ??? наименования? ?бщее число страниц диссер?
тации ? ???? в том числе приложения ? ?? страниц?
??Щ?Я Х?Р??Т?Р?СТ??? Р???ТЫ
?о введении обосновывается актуальность темы исследования? фор?
мулируются цель и задачи диссертационной работы? отмечаются новизна?
теоретическая и практическая ценность полученных результатов? кратко
излагается содержание работы?
? первой главе даны основные понятия? обозначения и соглашения?
??
Приведены концептуальные основы анализа алгоритмов? на которых бази?
руются результаты работы?
? диссертации под словом ?задача? подразумевается массовая зада?
ча ?? Там? где речь идет об индивидуальной задаче I ? применяются сло?
восочетания ?экземпляр I задачи ??? ?I ? вход алгоритма? решающего
задачу ?? и т?п? Следуя классическим традициям и позициям парамет?
ризированной теории сложности вычислений? функция вычислительной
сложности алгоритма поставлена в центр внимания исследования? вначале
в главах ? и ? как функция t(n) одной переменной n? а затем в главах
??? как функция t(n, k) двух аргументов n и k ? Эта функция представляет
время выполнения алгоритма ?в худшем случае применительно к Р??? в
зависимости от длины входа n = |I| и значения числового параметра k
?если он учитывается?? Сравнение алгоритмов осуществляется по поряд?
ку роста их функций сложности? При этом используются традиционные
асимптотические обозначения?
? t1 (n) ? t2 (n)? или t1 (n) = o[t2 (n)]? Функция t1 (n) меньше функции
t2 (n) по порядку роста?
? t2 (n) t1 (n)? или t1 (n) = ?[t2 (n)]? Функция t1 (n) не меньше функции
t2 (n) по порядку роста?
? t1 (n) t2 (n)? или t1 (n) = O[t2 (n)]? Функция t1 (n) не больше функции
t2 (n) по порядку роста?
? t1 (n)
t2 (n)? или t1 (n) = ?[t2 (n)]? Функция t1 (n) равна функции
t2 (n) по порядку роста?
?а функции сложности накладываются отдельные ограничения?
?о?первых? полагается? что областью значений этих функций выступает
множество неотрицательных действительных чисел R+ ? а областью опре?
деления ? множество целых положительных чисел Z+ ?или Z+ Ч N?? где
N ? множество натуральных чисел? ?о?вторых? при необходимости дис?
кретные n и k формально заменяются непрерывными x и y ? а нужные
значения вычисляются в целочисленных точках x = n и y = k ? ? этом
случае вместо t(n) или t(n, k) используется запись z(x) или z(x, y) соответ?
ственно? ??третьих? предполагается? что функции сложности принадлежат
семейству L ? рекурсивно определяемому множеству монотонно неубыва?
ющих? ?по существу положительных? логарифмически?экспоненциальных
функций?
Функция z(x) считается ?по существу положительной?? если существу?
ет x0 такое? что z(x) > 0 для всех x > x0 ? ?звестно? что каждая функция
из L ?далее просто L?функция? непрерывна и дифференцируема в той об?
ласти? где она определена? ?роме того? если z1 (x)? z2 (x) ? L? то при x ? ?
??
либо z1 (x) ? z2 (x)? либо z2 (x) ? z1 (x)? либо z1 (x)
z2 (x)? ? Поэтому лю?
бые две L?функции асимптотически сравнимы между собой по порядку
роста? а значит? сравнимы между собой по сложности соответствующие им
алгоритмы?
Сделанные в работе предположения относительно функций сложности
являются естественными и выполнимыми для большинства реальных ал?
горитмов?
?торая глава состоит из восьми параграфов и посвящена класси?
фикации алгоритмов по вычислительной сложности? Установление клас?
са сложности алгоритма ? один из этапов анализа алгоритма? ? данной
главе предложен новый метод систематизации алгоритмов? базирующий?
ся на асимптотике поведения эластичности функций сложности? Теорети?
ческое обоснование метода ? теорема ????? ?десь анализ ограничивается
одномерным случаем ?когда функция сложности z(x) зависит только от
непрерывного аргумента x ? длины входа алгоритма??
? параграфе ??? исследована классическая систематизация алгоритмов?
?тмечено? что данная систематизация ? это дихотомия? которая выделя?
ет низкозатратные ?полиномиальные? и высокозатратные ?экспоненциаль?
ные? алгоритмы? Причем эти классы определены с точностью до полиноми?
альных преобразований длины входов алгоритмов и традиционно устанав?
ливаются путем непосредственного асимптотического оценивания поряд?
ка роста функций сложности алгоритмов? ?лассическая систематизация
алгоритмов лежит в основе классификации задач по сложности? Соответ?
ственно выделены классы полиномиально разрешимых и трудноразреши?
мых задач? а для задач разрешения определены классы P? ?P и класс
?P?полных задач? ? современной алгоритмической практике используют
пять сложностных классов алгоритмов ?с субполиномиальным? полиноми?
альным? субэкспоненциальным? экспоненциальным и гиперэкспоненциаль?
ным порядком роста функций сложности?? ? диссертации доказано? что
все эти пять классов математически точно и достаточно просто устанав?
ливаются исходя из такой дифференциальной характеристики функций
сложности алгоритмов? как эластичность?
? параграфах ??? и ??? исследуются свойства эластичности L?функций?
Под эластичностью Ex (z) функции z = z(x) принято понимать предел
отношения относительного приращения этой функции к относительному
приращению аргумента?
Ex (z) = lim
?x?0
?z ?x
:
z
x
=
x
?z
x
lim
= z = x(ln z) .
z ?x?0 ?x
z
???
Согласно ??? эластичности присущи свойства? сходные со свойствами
? ?рэхем Р?? ?нут ??? Паташник ?? ?онкретная математика? ?снование информатики?
? ??? ?ир? ?????
??
операций логарифмирования и дифференцирования? поэтому она легко
определяется для всякой L?функции? ?роме того? при малых ?x спра?
ведливо приближение
?x
?z
? Ex (z)
,
z
x
которое задает подходящую для анализа алгоритмов интерпретацию эла?
стичности? Ex (z) ? коэффициент пропорциональности между темпами ро?
ста величин z и x? Справедливо
?ля любой L?функции z = z(x) всегда существу?
ет эластичность? и Ex(z) ? 0? Ex(z) = o(z/ ln x)? ?симптотическое по?
ведение эластичности L?функции z = z(x) при x ? ? инвариантно от?
носительно полиномиального преобразования? заключающегося в умноже?
нии этой функции на константу c > 0 и возведении в положительную и
отделенную от нуля степень m > 0? то есть Ex(czm) = ?[Ex(z)]?
Утверждение ????
? параграфе ??? формально выделены шесть классов L?функций с
принципиально различным порядком роста? С использованием асимпто?
тических обозначений эти классы определены следующим образом?
?? CONST = {z(x) | z(x) = ?(1)} ? асимптотические константы?
?? SUBPOLY = z(x) | 1 ? z(x) ? e?(ln x) ? функции субполиномиаль?
ного порядка роста?
?? POLY = z(x) | z(x)
ка роста?
e?(ln x) ? функции полиномиального поряд?
?? SUBEXP = z(x) | e?(ln x) ? z(x) ? e?(x)
циального порядка роста?
?? EXP = z(x) | z(x)
роста?
? функции субэкспонен?
e?(x) ? функции экспоненциального порядка
?? HYPEREXP = z(x) | e?(x) ? z(x) ? функции гиперэкспоненциаль?
ного порядка роста?
? параграфе ??? доказана теорема ???? о классификации L?функций
на основе эластичностей? ?оказательство базируется на утверждении ???
и леммах ???????? справедливость которых математически обоснована в
диссертации? Согласно этим леммам разным ?по порядку роста? классам
L?функций свойственно принципиально различное поведение эластичности
и? наоборот? по асимптотике поведения эластичности можно определить
класс? к которому относится эта функция? При этом данное соответствие
однозначно? если объединить CONST? SUBPOLY в один класс SUBPOLY?
??
Разбиение семейства монотонно неубывающих? ?по
существу положительных? L?функций на классы SUBPOLY? POLY?
SUBEXP? EXP? HYPEREXP в соответствии с порядком их роста экви?
валентно надлежащему разбиению по асимптотике эластичности этих
функций на бесконечности?
Теорема ?????
SUBPOLY = z(x) | z(x) ? e?(ln x) ? {z(x) | Ex (z) = o(1)} ;
POLY = z(x) | z(x)
e?(ln x) ? {z(x) | Ex (z)
1} ;
???
???
SUBEXP = z(x) | e?(ln x) ? z(x) ? e?(x) ? {z(x) | 1 ? Ex (z) ? x} ; ???
EXP = z(x) | z(x)
e?(x) ? {z(x) | Ex (z)
x} ;
HYPEREXP = z(x) | e?(x) ? z(x) ? {z(x) | x ? Ex (z)} .
???
???
?анное разбиение инвариантно относительно полиномиального преобра?
зования? заключающегося в умножении L?функции на константу и воз?
ведении в положительную и отделенную от нуля степень?
?з теоремы ???? и свойств эластичности вытекают важные следствия?
Разбиение L?функций на указанные в теореме ????
классы инвариантно относительно следующего полиномиального преобра?
зования? если u(x) ? POLY и z(x) ? K ? K ? { SUBPOLY? POLY? SUBEXP?
EXP? HYPEREXP}? то u(z(x)) ? K ?
?ласс SUBPOLY замкнут относительно суперпози?
ции ?композиции ? L?функций? если z(x)? u(x) ? SUBPOLY? то u(z(x)) ?
SUBPOLY?
?ласс POLY замкнут относительно суперпозиции
L?функций? если z(x), u(x) ? POLY? то u(z(x)) ? POLY?
?ласс HYPEREXP замкнут относительно су?
перпозиции L?функций? если z(x), u(x) ? HYPEREXP? то u(z(x)) ?
HYPEREXP?
Следствие ?????
Следствие ?????
Следствие ?????
Следствие
?????
? параграфах ??? и ??? определены классы сложности алгоритмов че?
рез соответствующие классы L?функций и описана методика сравнения
алгоритмов по асимптотике поведения эластичностей их функций слож?
ности? ?сли z(x) ? время выполнения алгоритма при длине входа x? то
Ex (z) ? эластичность этого алгоритма? Эластичность алгоритма ? это ко?
эффициент пропорциональности между темпом роста времени выполнения
алгоритма и темпом роста его длины входа? С учетом этой интерпретации
??
полученные в теореме ???? эквивалентности ??????? порождают пять соот?
ветствующих сложностных классов? которые полностью отвечают совре?
менной детальной классификации алгоритмов? ?ласс субполиномиальных
?быстрых? алгоритмов образуют алгоритмы? которым свойственна тожде?
ственно нулевая или бесконечно малая эластичность? ?ласс полиномиаль?
ных алгоритмов ? это множество алгоритмов? для которых эластичность
есть асимптотически постоянная величина? ?ласс субэкспоненциальных
алгоритмов ? алгоритмы? для которых эластичность есть бесконечно боль?
шая величина с порядком роста ниже линейной функции? ?ласс экспонен?
циальных алгоритмов состоит из алгоритмов? для которых эластичность ?
бесконечно большая величина? асимптотически равная ?по порядку роста?
линейной функции? ?ласс гиперэкспоненциальных алгоритмов образуют
алгоритмы? для которых эластичность есть бесконечно большая величина
с порядком роста выше линейной функции?
? параграфе ??? предложено более крупное разбиение алгоритмов на
классы? выделены и определены неэластичные? эластичные? суперэластич?
ные алгоритмы ? алгоритмы с бесконечно малой? асимптотически посто?
янной и бесконечно большой эластичностью соответственно? ?еэластичные
и эластичные алгоритмы практически значимые? так как эффективные?
Суперэластичные алгоритмы очень чутко реагируют на изменение длины
входа и с этой точки зрения хорошо управляемые по сложности через эту
величину?
? выводах к главе ? указаны следующие достоинства предложенного
метода систематизации алгоритмов? Эластичности достаточно легко вы?
числяются и представляются более простыми по виду функциями? чем
отвечающие им логарифмически?экспоненциальные функции сложности
алгоритмов? Поэтому их применение на практике обеспечивает ?прозрач?
ность? сложностных классов и облегчает анализ алгоритмов? Прежняя
традиционная классификация с полиномиальными и экспоненциальными
алгоритмами не разрушается? а лишь дополняется и уточняется? ?опусти?
мо обобщение данного метода на функции сложности многих переменных?
Третья глава диссертации состоит из четырех параграфов и посвяще?
на анализу сложности рекурсивных алгоритмов? ? этой главе установлены
и теоретически обоснованы верхние и нижние оценки времени выполнения
рекурсивного алгоритма? построенного на основе принципа ?уменьшай и
властвуй?? то есть путем аддитивного уменьшения размера задачи на неко?
торую константу ?теорема ????? ?десь анализируются функции сложности
t(n) от одного дискретного аргумента n ? длины входа алгоритма?
? параграфе ??? раскрыты проблемы анализа рекурсивных алгоритмов?
? параграфе ??? представлены рекуррентные соотношения? которые харак?
терны для прямой рекурсии? организованной по принципам ?разделяй и
властвуй? и ?уменьшай и властвуй?? Указаны наиболее распространен?
??
ные случаи? когда эти соотношения могут быть решены? постоянное число
подзадач? создаваемых на каждом шаге рекурсии? и полиномиальная тру?
доемкость рекурсивного перехода?
? параграфе ??? исследованы оценки ?ж? ?ентли? ?? Хакена? ?ж? Сак?
са? полученные ими для времени выполнения рекурсивного алгоритма?
организованного по принципу ?разделяй и властвуй?? Этот широко из?
вестный результат уже давно применяется при анализе и разработке эф?
фективных алгоритмов? Согласно нему рекурсивная реализация принципа
?разделяй и властвуй? всегда приводит к быстрым и полиномиальным ал?
горитмам?
? параграфе ??? сформулирована и доказана теорема ???? ?анная теоре?
ма позволяет находить верхние и нижние асимптотические оценки време?
ни выполнения рекурсивного алгоритма? построенного путем аддитивного
уменьшения размера задачи на некоторую константу k ? N? Такие алгорит?
мы? например? порождает рекурсивная реализация метода динамического
программирования?
Теорема ????
Пусть дано рекуррентное соотношение
если 0 ? n ? k ? 1,
???
?
at(n ? k) + bn? , если n ? k,
где a > 0? k ? 1 ? целые константы? b ? 0? c ? 0? ? ? 0 ? вещественные
константы? Тогда при n = km? m ? Z+ и n ? ? верны оценки
t(n) =
?
? c,
t(n) = ?(n),
t(n) = ?(an/k ),
t(n) = O n? +1 ,
a = 1, b > 0;
t(n) = O n? an/k ,
t(n) = ?(1),
a > 1, b > 0;
a = 1, b = 0;
t(n) = ? an/k ,
a > 1, b = 0.
???
???
????
????
? рекуррентном соотношении ??? константа a трактуется как число под?
задач? порождаемых рекурсивной ветвью алгоритма? а степенная функция
bn? определяет трудоемкость рекурсивного перехода? ?ценки ???? и ????
отвечают случаю ?бесплатного? рекурсивного перехода? ? работе установ?
лены другие частные случаи? когда из ???? ??? вытекают ??оценки? ?ни
отражены в следствиях ????????
??
? предположениях теоремы ??? при ? = 0 решением
рекуррентного соотношения ??? является функция
Следствие ????
t(n) =
?
b
?
?
c + n,
?
?
k
если a = 1,
?
n/k
?
?1
?
? an/k c + b a
,
a?1
если a > 1.
При ? = 0? любых значениях b > 0? c ? 0 и n ? ? для
решения рекуррентного соотношения ??? верны оценки
?
если a = 1, b > 0,
? ?(n),
t(n) =
?
? an/k , если a > 1, b > 0.
Следствие ????
?ля решения рекуррентного соотношения ??? при
? целых положительных ? и n ? ? справедлива оценка
Следствие ????
?
?
a=1 c?0 b>0
t(n) = ? n? +1 .
?ля решения рекуррентного соотношения ??? при
и целых положительных ? верна оценка
Следствие ????
?
?
a>1 c?0 b>0
t(n) = ? n? an/k .
?з оценок теоремы ??? и следствий ??????? вытекают важные для
практики положения? рекурсивные алгоритмы? образованные аддитивным
уменьшением размера задачи на некоторую константу? могут быть быст?
рыми? полиномиальными и экспоненциальными? ?ыстрый алгоритм возмо?
жен только в тривиальной ситуации ?при одной подзадаче и нулевых за?
тратах на рекурсивный переход?? Полиномиальные алгоритмы возникают
лишь в случае? когда исходная задача сводится к одной подзадаче меньше?
го размера? При числе подзадач a > 1 рекурсивный алгоритм? построенный
путем аддитивного уменьшения размера задачи на некоторую константу?
всегда экспоненциальный по времени и никакие усовершенствования про?
цедуры разбиения и объединения подзадач не способны изменить класс
его сложности? Причина этого кроется в возникновении на каждом шаге
рекурсии перекрывающихся подзадач? ?анные положения служат матема?
тическим обоснованием тому факту? что метод динамического программи?
рования для большинства задач выбора реализуется итерационно ?с помо?
щью табличной техники?? для него перекрытия подзадач обязательны? но
??
именно эти перекрытия ? источник экспоненциальной сложности рекур?
сивной реализации метода?
? выводах к главе ? отмечено? что результат ?ж? ?ентли? ?? Хаке?
на и ?ж? Сакса и доказанная в диссертации теорема ??? предоставляют
разработчикам алгоритмов и программ средства асимптотической оценки
сложности рекурсивных алгоритмов? построенных определенным образом?
?х применение не требует особых математических знаний? и потому они
могут быть использованы в широкой алгоритмической практике для по?
строения эффективных алгоритмов?
Четвертая глава содержит шесть параграфов? ?сновной результат
этой главы ? метод двумерной классификации параметризированных ал?
горитмов на основе частных эластичностей? ?етод позволяет сравнивать
между собой параметризированные алгоритмы по времени выполнения и
легко распространяется на параметризации задач с несколькими парамет?
рами?
? параграфе ??? кратко обсуждаются традиционные классы сложности
задач? концепция ?P?полноты и современные подходы к решению трудно?
разрешимых задач? ? параграфах ??? и ??? диссертации исследуется пара?
метризированный подход к оценке сложности вычислений? вводится необ?
ходимый понятийный аппарат?
Параметризованная задача ? ?в распознавательной формулировке? ?
язык? определяемый как L(?) ? ?? Ч N? где ? ? некоторый конечный
алфавит? ?? ? множество всех слов в данном алфавите? N ? множество
натуральных чисел? ?аждая пара значений (I, k) ? L(?) выступает в ка?
честве экземпляра параметризированной задачи ? и входа алгоритма? ре?
шающего данную задачу? При этом величина n = |I| задает длину входа
алгоритма? k ? значение параметра? ?сли параметризированная задача ?
может быть решена некоторым алгоритмом за время? не более чем
nO(1) · f (k),
????
то ее называют ?P??разрешимой относительно параметра k ? а соответству?
ющий алгоритм ? ?P??алгоритмом? ? Примечательно? что в ???? функция
f (k) зависит только от k ? Соотношение ???? определяет верхнюю асимпто?
тическую оценку времени выполнения ?P??алгоритма и свидетельствует о
том? что при каждом фиксированном k данный алгоритм полиномиальный
относительно n? ? этом смысле t(n, k) = O nO(1) · f (k) ?
? параграфе ??? излагается метод двумерной классификации парамет?
ризированных алгоритмов на основе частных эластичностей? ?десь вновь
формально дискретные n и k заменяются на непрерывные x и y соответ?
ственно? и вместо t(n, k) используется запись z(x, y)?
? ?????r????r ?? ????t?t??? t? ???????r???t?r ????r?t??s? ????r? ???t?r? s?r??s ??
??t????t??s ??? ?ts ???????t???s? ?? ??? ? ????r? ?????rs?t? Pr?ss? ?????
??
Частная эластичность Ex (z) функции z = z(x, y) по аргументу x ?
эластичность переменной z ? которая рассматривается как функция только
от x и при постоянных значениях y ? ?налогичным образом определяется
частная эластичность Ey (z) функции z = z(x, y) по аргументу y ?
?сли функция z(x, y) отражает время работы параметризированного
алгоритма при длине входа x и значении параметра y ? то Ex (z) ? коэф?
фициент пропорциональности между темпом роста времени выполнения
этого алгоритма и темпом роста длины входа ?при постоянном значении
параметра?? ?налогично Ey (z) ? коэффициент пропорциональности меж?
ду темпом роста времени выполнения параметризированного алгоритма и
темпом роста параметра y ?при постоянной длине входа??
? общем случае частные эластичности Ex (z)? Ey (z) являются функци?
ями? зависящими от x и y ? ?днако ситуация значительно упрощается? если
время работы параметризированного алгоритма описывается L?функцией?
имеющей мультипликативную форму записи? z(x, y) = q(x) · f (y)? где
q(x) ? L ? количественная компонента? а f (y) ? L ? параметрическая
компонента функции z(x, y)? Так? условие ?P??разрешимости ???? тра?
диционно определяется именно через мультипликативную форму записи
функции сложности параметризированного алгоритма?
? параграфе ??? в условиях мультипликативной формы записи функ?
ций сложности и в границах семейства L?функций разработан метод дву?
мерной классификации параметризированных алгоритмов на основе част?
ных эластичностей? Суть метода состоит в следующем?
Рассмотрим функцию z(x, y) = q(x) · f (y) ? L? Согласно свойствам эла?
стичностей величины Ex (z) и Ey (z) вырождаются в обычные эластичности
функции одного аргумента?
Ex (z) = Ex [q(x) · f (y)] = Ex [q(x)] + Ex [f (y)] = Ex [q(x)],
????
Ey (z) = Ey [q(x) · f (y)] = Ey [q(x)] + Ey [f (y)] = Ey [f (y)].
????
Теперь Ex (z) зависит лишь от x? а Ey (z) зависит только от y ? По теореме
???? каждая из функций q(x)? f (y) принадлежит только одному сложност?
ному классу ?по надлежащему аргументу? из множества
K = {SUBPOLY, POLY, SUBEXP, EXP, HYPEREXP} .
Пусть Kx ? класс сложности функции q(x) по аргументу x? и Ky ?
класс сложности функции f (y) по аргументу y ? Пусть эти классы опреде?
лены исходя из теоремы ???? и соответствующих частных эластичностей
?????????? Тогда всякому параметризированному алгоритму с функцией
сложности z(x, y) = q(x)·f (y) ? L отвечает пара (Kx , Ky ) ? KЧK? Эта пара
характеризует сложность данного алгоритма по длине входа x и значению
параметра y ? Таким образом? мы приходим к двумерной классификации
??
параметризированных алгоритмов по вычислительной сложности? ?чевид?
но? что при наличии нескольких параметров возможно введение подобным
образом многомерной классификации параметризированных алгоритмов?
При двумерном подходе отчетливую формулировку получает опреде?
ление ?P??алгоритма? Параметризированный алгоритм является ?P??
алгоритмом? если время его работы задается функцией z(x, y) = q(x) · f (y)?
для которой
(Kx , Ky ) ? {SUBPOLY, POLY} Ч K.
? параграфе ??? диссертации ?P??алгоритмы систематизированы по
сложности относительно параметра y ? ?лгоритмы? вычислительная слож?
ность которых соответствует парам
(Kx , Ky ) ? {SUBPOLY, POLY} Ч {SUBPOLY, POLY} ,
(Kx , Ky ) ? {SUBPOLY, POLY} Ч {SUBEXP} ,
(Kx , Ky ) ? {SUBPOLY, POLY} Ч {EXP} ,
(Kx , Ky ) ? {SUBPOLY, POLY} Ч {HYPEREXP} ,
определены как полиномиальные? субэкспоненциальные? экспоненци?
альные и гиперэкспоненциальные
?P??алгоритмы соответственно?
Субэкспоненциальные? экспоненциальные и гиперэкспоненциальные
?P??алгоритмы присущи ?P?трудным задачам? ?ни суперэластичные по
параметру ?при постоянной длине входа??
?нализ параметризированных алгоритмов предполагает не только
определение класса сложности алгоритма? но и установление степени вли?
яния параметра на время выполнения алгоритма? ? параграфе ??? дис?
сертации разработана методика? позволяющая проводить такие исследова?
ния? ?на основана на коэффициенте замещения одного аргумента функции
другим аргументом? Этот коэффициент определяется и интерпретируется
следующим образом? Пусть z(x, y) ? L? Тогда величина
?
xEy (z)
dx
=
=M
dy
yEx (z)
????
есть коэффициент замещения одного аргумента функции другим? при
условии? что значения функции постоянные ?отвечают некоторой линии
уровня?? Формулу ???? можно записать так?
?dx =
xEy (z)
= M dy.
yEx (z)
????
Соотношение ???? дает следующее толкование коэффициенту замеще?
ния? при некотором постоянном значении z ?реально осуществимой нор?
мы времени исполнения алгоритма? уменьшение значения параметра y на
??
?y = 1 позволяет увеличить x ? длину входа алгоритма ? примерно на M ?
то есть регулировать вычислительные возможности алгоритма на входах
большой длины?
?ля определения ?P??алгоритма традиционно применяется мульти?
пликативная форма представления функции сложности алгоритма? ? па?
раграфе ??? диссертации предложены аддитивная и смешанная формы
представления? доказана их эквивалентность мультипликативной форме
в смысле ?P?? Этот результат отражает
Пусть задана задача ?? параметризированная от?
носительно параметра ??Следующие высказывания эквивалентны?
?? ?ля задачи ? существует ?P??алгоритм со временем работы
O[q(x) · f (y)]? где q(x) ? функция полиномиального или субполи?
номиального порядка роста от длины входа x?
?? ?ля задачи ? существует ?P??алгоритм со временем работы
O[u(x) + w(y)]? где u(x) ? функция полиномиального или субполи?
номиального порядка роста от длины входа x?
?? ?ля задачи ? существует ?P??алгоритм со временем работы
O[q1 (x) · f1 (y) + q2 (x) · f2 (y)]? где q1 (x)? q2 (x) ? функции полиноми?
ального или субполиномиального порядка роста от длины входа x?
Утверждение ????
Утверждение ??? расширяет область применимости разработанных в
главе ? математических средств анализа параметризированных алгорит?
мов?
Пятая и шестая главы диссертации посвящены алгоритмическим
аспектам развития метода динамического программирования по дереву
декомпозиции? ?бсуждаются две проблемы? сдерживающие практическое
применение этого метода при решении задач выбора большой размерности?
проблема памяти и проблема вычисления древовидной ширины? ? пятой
главе разработаны и математически обоснованы средства решения первой
из указанных проблем? ?етодам и алгоритмам решения второй проблемы
отведена шестая глава диссертации?
? параграфе ??? дан краткий обзор основных методов разработ?
ки ?P??алгоритмов? ?тмечено? что в настоящее время уже предложе?
ны и апробированы несколько специальных методов конструирования
?P??алгоритмов? наиболее универсальный из них ? метод динамического
программирования по дереву декомпозиции? Этот метод ориентирован на
параметризированные задачи выбора? представимые графами и гипергра?
фами ограниченной древовидной ширины? ?менно по древовидной ширине
должна быть осуществлена параметризация решаемой задачи?
??
? параграфе ??? приводятся определения и известные свойства дерева
декомпозиции и древовидной ширины графа? ? Пусть G = (V, E) ? связный
неориентированный граф? |V | ? 1 и |E| ? 1? ?ерево декомпозиции графа
G = (V, E) представляет собой пару (MG , TG )? задающую разбиение множе?
ства вершин и множества ребер графа G? где MG = {Xi | i ? IG } ? семей?
ство подмножеств множества V ? называемых ?мешками?? а TG = (IG , W ) ?
дерево? узлам которого сопоставлены эти ?мешки?? ?ершины дерева TG
принято называть узлами? чтобы избежать путаницы с вершинами графа
G? Семейство MG и множество W ребер дерева TG такие? что справедливы
условия?
?? объединение множеств вершин? образующих ?мешки? Xi ? i ? IG ? дает
множество V ?
?? для всякого ребра графа G обязательно имеется хотя бы один ?ме?
шок?? содержащий обе вершины этого ребра?
?? для любой вершины v графа G множество узлов {i ? IG | v ? Xi }?
?мешки? которых содержат эту вершину? индуцирует связный под?
граф? являющийся поддеревом дерева TG ?
Ширина дерева декомпозиции (MG , TG ) равна наибольшей вместимости
его ?мешка?? уменьшенной на единицу?
max {|Xi | ? 1} .
i?IG
tr?????t?
?ревовидная ширина ?
? графа G определяется как наименьшая
ширина всех допустимых его деревьев декомпозиции и обозначается через
tw(G)? ?ерево декомпозиции (MG , TG ) ширины tw(G) называется опти?
мальным? а без кратных и вложенных ?мешков? ? фундаментальным? ?ля
tw(G) верны естественные границы? 1 ? tw(G) ? |V |?1? Пусть k ? некото?
рая заданная целая положительная константа? и k < |V |? ?сли tw(G) ? k ?
то говорят? что граф G обладает ограниченной ?значением k ? древовидной
шириной?
Структуру многих задач выбора удобно представлять и интерпретиро?
вать в терминах гиперграфов? ? параграфе ??? понятия дерева декомпо?
зиции и древовидной ширины обобщены применительно к гиперграфам и
доказано
?сякое дерево декомпозиции (MH , TH ) связного ги?
перграфа H есть дерево декомпозиции графа L(2)(H) и наоборот? любое
Утверждение ????
? ?????????r ???? ??s????r??? tr?????t? ?? Pr??? ?? t?? ??st ?????r???? ?????? ?????
??r????r???r??? ???? ????? ? ????? ? P? ?????
??
дерево декомпозиции графа L(2)(H) задает дерево декомпозиции гипергра?
фа H ? ?роме того?
древовидная ширина гиперграфа H равна древовидной
ширине графа L(2)(H)?
Таким образом? с точки зрения древовидной ширины граф L(2) (H)? от?
ражающий отношение смежности вершин гиперграфа H ? полностью опре?
деляет этот гиперграф? Поэтому гиперграфовое описание задач выбора?
хотя и не вносит ничего существенного в метод динамического програм?
мирования по дереву декомпозиции в сравнении с представлением таких
задач графами? зато позволяет привлекать для его реализации свойства
ациклических гиперграфов? ?граниченная древовидная ширина исходно?
го графа и гиперграфа ? это условие применимости данного метода? Чем
меньше древовидная ширина? тем меньше вычислительных ресурсов нуж?
но ?P??алгоритму? реализующему динамическое программирование по де?
реву декомпозиции?
? параграфе ??? дано описание метода динамического програм?
мирования по дереву декомпозиции? Указаны рекурсивные правила вы?
деления подзадач? ? параграфе ??? исследованы достаточные усло?
вия ?P??разрешимости задач выбора относительно древовидной ширины?
устанавливаемые теоремой ?урселя?? ? Согласно теореме ?урселя? данный
метод приводит к ?P??алгоритму со временем работы O(|V | · f (k))? если
решаемая задача может быть сформулирована в виде конечной формулы
монадической логики второго порядка и входной граф G = (V, E) имеет
tw(G) ? k ?
?инамическое программирование по дереву декомпозиции по своей су?
ти ? рекурсивный метод? Число подзадач? возникающих на каждом шаге
рекурсии? определяется арностью дерева? которая в общем случае боль?
ше единицы? По теореме ??? рекурсивная реализация метода неминуемо
приводит к неполиномиальному времени вычислений относительно длины
входа? ?ля получения ?P??алгоритма требуется этот метод реализовывать
с помощью табличной техники? ?днако данная техника порождает пробле?
му памяти для размещения создаваемых таблиц динамического програм?
мирования? сколько узлов содержит дерево декомпозиции? столько таблиц
возникает? размер всякой таблицы экспоненциально зависит от арности и
ширины применяемого дерева декомпозиции? ? частности? если в методе
динамического программирования исходить из бинарного дерева декомпо?
зиции графа G = (V, E) ширины k и с O(|V |) узлами? то общая потребность
соответствующего алгоритма в памяти и времени составит O(|V | · k · q 3k )?
где q ? число состояний? в которых может находиться вершина графа к
допустимому решению? Таким образом? проблема памяти ? серьезное пре?
?? ???r????? ?? ??? ??????? s???????r??r ????? ?? ?r???s? ???? ?r?? ???????s?t???s? ????rs
??? ????????t? ?ss??s ?? ????? ????r?? ????r? ????? ? ????? ? ?????? ? P? ????????
??
пятствие применимости этого метода на практике?
?ля решения проблемы памяти применяют различные преобразования
дерева декомпозиции?? ? ?аиболее известное в этом отношении ? ????s?
дерево?? ? ?анное дерево дает возможность удерживать размер всякой таб?
лицы динамического программирования в пределах оценки O(k · q k )? ?еж?
ду тем это достигается за счет увеличения числа таблиц примерно в k раз?
? параграфе ??? предложено бинарное сепараторное дерево декомпозиции
?????дерево?? которое обеспечивает компромисс между размером и числом
таблиц динамического программирования?
? диссертации ????дерево определено следующим образом? ?орневое
дерево декомпозиции (MG , TG )? MG = {Xi | i ? IG }? TG = (IG , W )? связного
графа G = (V, E) называется ????деревом? если в нем каждый узел имеет
не более двух прямых потомков и относится к одному из четырех типов
узлов?
?? узел?лист ? узел? у которого нет потомков?
?? узел?сепаратор ? узел s с одним прямым потомком j и узлом i в роли
родителя? ?сегда Xs ? сепаратор ?разделяющее множество вершин?
графа G и Xs = Xi ? Xj = ? Xs ? Xi ? Xs ? Xj ?
?? узел?расширение ? узел i с одним прямым потомком s? ? данном
случае Xs ? Xi ?
?? узел?соединение ? узел i с двумя прямыми потомками l и j ? ?десь
Xl ? Xj ? Xi ?
? параграфе ??? доказано
?сякое фундаментальное дерево декомпозиции
графа G = (V, E)? где MG = {Xi | i ? IG}? TG = (IG, W )? имеющее
ширину и O(|V |) узлов? может быть преобразовано за время O(|V |) в
? ??дерево? которое обладает той же шириной и O(|V |) узлами?
Утверждение ?????
(MG , TG )
k
&
Показаны и теоретически
обоснованы следующие
достоинства
?&??дерева? Переход от бинарного корневого дерева декомпози?
ции к ????дереву увеличивает число таблиц не более чем в два раза ?за
счет добавления узлов?сепараторов?? ????дерево удерживает размер вся?
кой таблицы динамического программирования в тех же пределах? что и
????s?дерево? ?ля вычисления таблиц динамического программирования
по ????дереву возможно привлечение аппарата реляционной алгебры и
?? ?s????? ??? Pr?s??r??s?? ??? ????? ???? ????r? r?q??r????ts ??r t???? ?????t?t???s ??
??rt??? ??tr?? ????r?t??s ?? ????r?t?????? ? ????? ? ?????? ? P? ????????
?? ????s ?? ?r?????t?? ?????t?t???s ??? ???r?????t???s? ? ??r????r???r??? ???? ????
?????
??
свойств ациклических баз данных? Это способствует алгоритмической кон?
кретизации метода и сокращению числа строк в промежуточных таблицах
?за счет применения монотонного плана соединения и программы полусо?
единений таблиц??
? параграфе ??? показано применение метода динамического програм?
мирования по ????дереву при решении оптимизационных задач ?на при?
мере задачи о вершинном покрытии? и задач удовлетворения ограничений
?на примере задачи ????
?? ?ля задач удовлетворения ограни?
чений употреблено гиперграфовое описание?
? выводах к главе ? отмечено? что реляционный взгляд на процесс ди?
намического программирования ?как процесс соединения таблиц? находя?
щихся в разных узлах дерева декомпозиции? позволяет при решении задач
выбора применять свойства ациклических баз данных и выполнять поиск
решения в режиме распределенных вычислений? ?спользование при этом
????дерева дает возможность существенно снижать теоретические и ре?
альные потребности в вычислительных ресурсах ?P??алгоритмов? реали?
зующих метод динамического программирования на графах и гиперграфах
ограниченной древовидной ширины?
?ля практического применения метода динамического программирова?
ния по дереву декомпозиции необходимо убедиться? что входной граф име?
ет ограниченную ?значением k ? древовидную ширину и при положитель?
ном ответе построить дерево декомпозиции такой ширины? ?ежду тем? са?
ма задача вычисления древовидной ширины является ?P?трудной? Хотя на
сегодняшний день известен широкий спектр точных? приближенных и эв?
ристических алгоритмов решения этой задачи? вопрос ее алгоритмического
обеспечения нельзя считать закрытым? ?еобходимость практического ре?
шения данной задачи в условиях большой размерности для произвольных
видов графов и гиперграфов требует новых алгоритмов и подходов?
? шестой главе диссертации разработаны и теоретически обоснова?
ны два рекуррентных метода? позволяющие снижать размерность задачи
вычисления древовидной ширины и вычислять нижние и верхние оценки
древовидной ширины входного графа и гиперграфа?
? параграфе ??? представлен краткий обзор популярных на сегодняш?
ний день методов вычисления древовидной ширины графа? ? параграфе
??? приведены известные нижние границы значений древовидной ширины
графа G = (V, E)? связывающие tw(G) с другими числовыми параметрами
этого графа? ?тмечено? что наиболее существенные из этих оценок труд?
новычисляемые и потому актуальны различные способы предобработки?
снижающие размерность задачи вычисления древовидной ширины? ? па?
раграфе ??? разработан и теоретически обоснован рекуррентный метод?
позволяющий редуцировать входной граф и гиперграф и вычислять ниж?
ние оценки его древовидной ширины? ?анный метод реализует принцип
??t?s??????t?
??
?уменьшай и властвуй? и опирается на свойства хордальных графов и
ациклических гиперграфов? ?боснованием метода служат доказанные в
диссертации следующие положения?
?сли v ? V ? симплициальная вершина графа G = (V, E)
степени deg(v)? то
?емма ????
tw(G) = max{deg(v), tw(G ? v)}.
????
?сякая висячая вершина гиперграфа H = (X, U ) ? сим?
плициальная вершина графа L(2)(H)?
Пусть x ? X является висячей вершиной ги?
перграфа
H = (X, U ) степени d ?для нее в обозначениях теории гипер?
графов??? x ? X(u)? U (x) = {u} и d = |X(u)| ? 1?? Пусть гиперграф
H = Hµ (X ? x) получен из H слабым удалением вершины x с последу?
ющей минимизацией ?удалением кратных и вложенных ребер?? Тогда
?емма ????
Утверждение ????
tw(H) = max{d, tw(H )}.
????
Рекуррентные формулы ????? ???? дают способ вычисления древовид?
ной ширины путем последовательного удаления симплициальных вершин в
графе и висячих вершин в гиперграфе? ? работе представлен рекурсивный
алгоритм? реализующий данный метод? ?сли входной граф хордальный
?или гиперграф ациклический?? то алгоритм вырождается в рекурсивный
процесс вычисления древовидной ширины этого графа ?или гиперграфа??
По теореме ??? алгоритм имеет полиномиальную временную сложность от?
носительно числа входящих в граф ?или гиперграф? вершин?
? параграфах ??????? изложен и теоретически обоснован рекуррент?
ный метод верхнего оценивания древовидной ширины? Этот метод основан
на свойствах сепараторов? ?н воплощает принцип ?разделяй и властвуй?
?разбивая исходный граф или гиперграф на части? и потому всегда име?
ет полиномиальную относительно числа вершин рекурсивную реализацию
при условии? что применяемые сепараторы полиномиально вычисляемые?
?зложим суть данного метода применительно к графам?
?оворят? что множество вершин S ? V разделяет несмежные верши?
ны a и b связного графа G = (V, E)? если в графе G(V \ S) вершины a
и b принадлежат различным компонентам связности? ?ножество S при
этом называется (a, b)?сепаратором и минимальным (a, b)?сепаратором? ес?
ли S есть (a, b)?сепаратор? и в нем нет собственного подмножества? явля?
ющегося (a, b)?сепаратором? Сепаратор S называется минимальным? если
?? ?ыков ???? ?иперграфы ?? У??? ? ????? ? Т? ??? ? ?ып? ?? ? С? ???????
??
в графе G существует такая пара вершин a и b? что S ? минимальный
(a, b)?сепаратор?
Пусть ?(G) ? множество сепараторов связного графа G = (V, E)
и S ? ?(G)? ?бозначим через Y1 ? Y2 ? . . . ? Y? области связности графа
G(V \ S)? Части G1 ? G2 ? . . . ? G? графа G? выделенные в результате его
разделения сепаратором S ? определим следующим образом?
Gi = G(Yi ? S) ? K(S),
где K(S) ? полный граф на множестве вершин S ? i ? IS = {1, 2, . . . , ? }?
? частности? если S ? точка сочленения графа G? то G1 ? G2 ? . . . ? G? ?
блоки этого графа? Сепаратор S графа G назовем целесообразным отно?
сительно tw(G)? если справедливо равенство
tw(G) = max{tw(Gi ) | i ? IS }.
????
?анное равенство определяет рекуррентное соотношение для вычисления
древовидной ширины графа через его части? полученные разделением G
сепаратором S ? ? параграфе ??? доказаны утверждения ???? ????? согласно
которым кликовые сепараторы и минимальные почти кликовые сепарато?
ры гарантируют справедливость ????? ?ликовый сепаратор ? сепаратор
графа G? образующий в G клику? Сепаратор S графа G считается почти
кликовым? если существует вершина v ? S такая? что множество S \ {v} ?
клика графа G?
? параграфе ??? исследуются минимальные кликовые и минимальные
почти кликовые сепараторы? Показано? что такие сепараторы всегда мож?
но извлечь за полиномиальное время из минимальной триангуляции графа?
?апомним? что триангуляцией графа G = (V, E) называется хордальный
граф G = (V, E )? который содержит граф G в качестве остовного подгра?
фа (E ? E )? Триангуляция G минимальная? если для G не существует
другой триангуляции? которая образует собственный подграф графа G ?
?звестно? что всякий минимальный сепаратор S минимальной триангуля?
ции G = (V, E ) ? минимальный сепаратор исходного графа G = (V, E)?
E ? E ? а для вычисления минимальной триангуляции G = (V, E ) доста?
точно O(|V |3 ) времени?? ?
? параграфе ??? также дано описание рекурсивного алгоритма раз?
ложения заданного графа на части минимальными кликовыми и мини?
мальными почти кликовыми сепараторами и вычисления верхней оцен?
ки древовидной ширины этого графа с использованием формулы ?????
?ерхние оценки для частей графа вычисляются на основе неравенств
tw(Gi ) ? tw(Gi )? где Gi ? соответствующие минимальные триангуляции?
?? ??rr? ??? ??r??t ??P?? ?????r??s P?? ??????t ??? ????????r ?? ? ???? r???? ????r?t?? ??r
??????? tr???????t??? ?r?? ?? ?r??tr?r? ?r??r??? ?? ?? ????r?t??s? ? ????? ?????? ? P? ??????
??
? параграфе ??? предложенный метод обобщен на гиперграфы ?лемма ?????
утверждение ?????? Указаны правила формирования частей разложения?
Результат разложения графа и гиперграфа на части минимальными
кликовыми и минимальными почти кликовыми сепараторами зависит от
порядка выбора этих сепараторов? поскольку допустимы разделяющие
друг друга сепараторы? ?ежду тем? если для разложения использовать
только минимальные кликовые сепараторы? то результат уникален? Уни?
кальность такого разложения применительно к графам была установлена
?? ?аймером?? в ???? г? ? параграфе ??? диссертации доказано утвержде?
ние ????? согласно которому уникальность сохраняется и для гиперграфов?
Пусть H = (X, U ) ? связный гиперграф без кратных и вложенных ре?
бер и Y ? X ? это максимальное по включению подмножество вершин
такое? что гиперграф H(Y ) связен и не содержит минимальных кликовых
сепараторов? ?иперграф H(Y ) назовем атомом гиперграфа H ? ?аметим?
что H(Y ) ? часть гиперграфа H = (X, U )? индуцированная множеством
Y ? X ? Пусть ?(H) ? множество минимальных кликовых сепараторов?
?(H) ? множество частей гиперграфа H ? полученных рекурсивным разло?
жением этого гиперграфа сепараторами из ?(H)? при этом каждая часть ?
некоторый гиперграф H(Yi ) с областью связности Yi (i ? IH )?
? Разложение ?(H) = {H(Yi ) | i ? IH } определяет
уникальное для заданного гиперграфа H множество атомов?
Утверждение ????
Эта уникальность означает следующее? Результат разложения не зави?
сит от порядка выбора минимальных кликовых сепараторов? ?аждый из
гиперграфов H(Yi ) ? ?(H) ? атом гиперграфа H ? и никакой из атомов
этого гиперграфа не утерян при разложении? Состав атомов? образующих
?(H)? не зависит от минимальных триангуляций? используемых для на?
хождения минимальных кликовых сепараторов?
? выводах к главе ? отмечено? что разработанные в диссертации ме?
тоды нижнего и верхнего оценивания древовидной ширины имеют поли?
номиальную сложность относительно числа вершин входного графа ?или
гиперграфа? и потому представляют ценность для практического приме?
нения метода динамического программирования по дереву декомпозиции
при решении задач выбора? возникающих в рамках новых информацион?
ных технологий? ?онечно? существуют графы и гиперграфы? для которых
использование данных методов не приводит к желаемому эффекту ?в них
нет симплициальных и висячих вершин? отсутствуют минимальные клико?
вые и минимальные почти кликовые сепараторы?? Поэтому перспективны
дальнейшие исследования? направленные на разработку других методов
?? ?????r ???? ??t???? ???????s?t??? ?? ???q?? s???r?t?rs ?? ??s?r?t? ??t????t??s? ?????
? ???? ? P? ???????
??
вычисления и оценивания древовидной ширины? Утверждение ???? откры?
вает дополнительные вычислительные возможности приложений гипергра?
фовых моделей систем? поскольку атомарное разложение гиперграфа мо?
жет быть использовано не только в аспекте древовидной ширины? но в
других задачах? базирующихся на отношениях смежности вершин?
? заключении сформулированы основные результаты диссертацион?
ной работы? ? приложениях ? и ? приведены свойства хордальных гра?
фов и ациклических гиперграфов? алгоритмы построения минимальных
триангуляций и тесты на ацикличность? цитируемые в главах ? и ? диссер?
тации? ? приложении ? дано описание комплексов программ? в которых
реализованы основные алгоритмы диссертации?
?С????Ы? Р??У?ЬТ?ТЫ
?? Предложен метод распознавания классов субполиномиальных?
полиномиальных? субэкспоненциальных? экспоненциальных и ги?
перэкспоненциальных алгоритмов? ?оказано? что все эти пять
современных сложностных классов устанавливаются математически
точно по асимптотике поведения эластичности функций сложности
алгоритмов ?теорема ??????
?? Разработаны математические инструменты анализа параметри?
зированных алгоритмов? метод двумерной классификации пара?
метризированных алгоритмов по сложности на основе частных
эластичностей? методика установления степени воздействия пара?
метра на сложность параметризированного алгоритма с помощью
коэффициента замещения одного аргумента функции другим? две
альтернативные формы представления функции сложности ?P??
алгоритма ?утверждение ?????
?? Получены верхние и нижние оценки времени выполнения рекур?
сивных алгоритмов? построенных путем аддитивного уменьшения
размера задачи на некоторую константу ?теорема ??? и следствия
?????????
?? ?оказано? что проблему высоких потребностей в памяти ?P??
алгоритмов? образующихся при применении метода динамического
программирования по дереву декомпозиции? можно решать с
помощью бинарного сепараторного дерева декомпозиции ?утвержде?
ние ??????
?? Разработаны и математически обоснованы два рекуррентных и
полиномиальных по времени метода вычисления верхних и нижних
оценок древовидной ширины графа и гиперграфа ?леммы ???? ??? и
утверждение ???? лемма ???? и утверждения ???? ????? ??????
?? ?оказано? что гиперграф уникальным образом разлагается на части
минимальными кликовыми сепараторами ?утверждение ??????
??
Представленные в диссертации теоретические результаты и практиче?
ские решения расширяют и углубляют научные основы современных ин?
формационных технологий на базе использования средств вычислитель?
ной техники? ?х применение в алгоритмической практике и программной
инженерии будет способствовать созданию эффективных ?с точки зрения
объема потребляемых вычислительных ресурсов? программных и инфор?
мационных систем различного назначения?
ПУ?????Ц?? ??Т?Р? П? Т??? ??СС?РТ?Ц??
?онография
?? ?ыкова ???? Теоретические основы анализа параметризированных
алгоритмов? монография? ? ?расноярск? СФУ? ????? ? ??? с?
Статьи в журналах? рекомендованных ??? РФ
?? ?ыкова ???? ?P??алгоритмы на графах ограниченной древовидной
ширины ?? Прикладная дискретная математика? ? ????? ? ? ?????? ?
С? ??????
?? ?ыкова ???? ? разложении гиперграфа кликовыми минимальными
сепараторами ?? ?урнал СФУ? ?атематика и физика? ? ????? ?
? ????? ? С? ??????
?? ?ыкова ???? ?нализ воздействия параметра на вычислительную
сложность параметризированного алгоритма ?? ?мский научный
вестник? Приборы? машины и технологии? ? ????? ? ? ??????? ?
С? ????????
?? ?ыкова ???? Рекуррентные методы вычисления древовидной шири?
ны гиперграфа ?? ?звестия Томского политехнического университе?
та? Управление? вычислительная техника и информатика? ? ????? ?
Т? ???? ? ? ?? ? С? ?????
?? ?ыкова ???? Программирование задач на графах ограниченной дре?
вовидной ширины ?? Программные продукты и системы? ? ????? ?
? ?????? ? С? ????????
?? ?ыкова ???? ?ычислительные аспекты древовидной ширины гра?
фа ?? Прикладная дискретная математика? ? ????? ? ? ?????? ?
С? ??????
?? ?ыкова ???? ?P??алгоритмы и их классификация на основе эластич?
ности ?? Прикладная дискретная математика? ? ????? ? ? ?????? ?
С? ??????
??
?? ?ыкова ???? ?лгоритм построения дерева декомпозиции гипергра?
фа на основе ацикличности ?? Программные продукты и системы? ?
????? ? ? ?????? ? С? ??????
??? ?ыкова ???? Сложность и эластичность вычислений ?? ?мский на?
учный вестник? Приборы? машины и технологии? ? ????? ? ? ?????? ?
С? ??????
??? ?ыкова ???? ?симптотические свойства решений специального типа
рекуррентных соотношений ?? ?мский научный вестник? Приборы?
машины и технологии? ? ????? ? ? ?????? ? С? ????????
??? ?ыкова ???? ??ациклические и древовидные гиперграфы ?? ?зве?
стия Томского политехнического университета? ?атематика и меха?
ника? Физика? ? ????? ? Том ???? ? ? ?? ? С? ??????
??? ?ыкова ???? Эластичность алгоритмов ?? Прикладная дискретная
математика? ? ????? ? ? ????? ? С? ??????
??? ?ыкова ???? ?етод распознавания классов алгоритмов на основе
асимптотики эластичности функций сложности ?? ?урнал СФУ? ?а?
тематика и физика? ? ????? ? ? ????? ? С? ??????
??? ?ыкова ???? Полиномиальные достаточные условия реализуемости
гиперграфа на плоскости ?? ?звестия Томского политехнического
университета? ?атематика и механика? Физика? ? ????? ? Т? ???? ?
? ?? ? С? ??????
??? ?ыкова ???? ?атематические методы анализа рекурсивных алго?
ритмов ?? ?урнал СФУ? ?атематика и физика? ? ????? ? ? ????? ?
С? ????????
??? ?ыкова ???? Полиномиальные достаточные условия бихроматично?
сти гиперграфа ?? ?естник ?рас?У? Серия физ??мат? науки? ? ?????
? ? ? ? С? ???????
??? ?????? ???? ?????s?s ??r???t?r???? ????r?t??s ?? t?? ??s?s ?? ???st???t?
t? ????t???s ????????t? ?? ???r??? ?? ????r??? ????r?? ?????rs?t??
??t????t??s P??s??s? ? ????? ? ? ????? ? P? ????????
?атериалы конференций? статьи в сборниках
??? ?ыкова ???? ?P??алгоритмы и их классификация на основе эла?
стичности ?? ?атериалы ?? Сибирской научной школы?семинара
??омпьютерная безопасность и криптография? ????????P??????
???? сентября ???? г?? Томск? ? Прикладная дискретная математика? ?
????? ? Приложение ? ?? ? С? ??????
??
??? ?ыкова ???? ?ычислительные аспекты древовидной ширины графа
?? ?атериалы ?? Сибирской научной школы?семинара ??омпьютер?
ная безопасность и криптография? ????????P?????? ???? сентября
???? г?? Томск? ? Прикладная дискретная математика? ? ????? ? При?
ложение ? ?? ? С? ??????
??? ?ыкова ???? ?омбинаторно?геометрическое моделирование задач вы?
бора ?? ?атериалы ??? ?сероссийской научно?практической конфе?
ренции ?Проблемы информатизации региона? ?П?Р??????? ????? но?
ября ???? г?? ?расноярск? ? ?расноярск? СФУ? ????? ? С? ??????
??? ?ыкова ???? Подходы и проблемы нахождения точных решений ?P?
трудных задач? обзор ?? Труды ?есятой ?еждународной конферен?
ции по финансово?актуарной математике и эвентоконвергенции тех?
нологий ?Ф??Э? ?????? ????? апреля ???? г?? ?расноярск? ? ?расно?
ярск? ???ПП?? СФУ? ??ТЭ?? ????? ? С? ??????
??? ?ыкова ????? ?икульская ???? Сравнительный анализ эвристик по?
строения триангуляций графа для древовидной ширины ?? Труды
?есятой ?еждународной конференции по финансово?актуарной ма?
тематике и эвентоконвергенции технологий ?Ф??Э? ?????? ????? ап?
реля ???? г?? ?расноярск? ? ?расноярск? ???ПП?? СФУ? ??ТЭ??
????? ? С? ??????
??? ?ыкова ???? ?рафоаналитический метод анализа сложности алго?
ритмов ?? ?атериалы ?? ?сесибирского конгресса женщин?
математиков ?в день рождения Софьи ?асильевны ?овалевской??
????? января ???? г? ? ?расноярск? Р?Ц Сиб?ТУ? ????? ? С? ??????
??? ?ыкова ???? ?омбинаторно?геометрический анализ задачи динами?
ческого программирования ?? Труды ?? ?еждународной конферен?
ции по финансово?актуарной математике и эвентоконвергенции тех?
нологий ?Ф??ЭТ ?????? ????? апреля ???? г?? ?расноярск? ? ?расно?
ярск? ??ТЭ?? СФУ? ????? ? С? ??????
??? ?ыкова ???? Эластичность алгоритмов ?? ?атериалы ? Сибирской
научной школы?семинара ??омпьютерная безопасность и криптогра?
фия? ????????P?????? ???? сентября ???? г?? Тюмень? ? Прикладная
дискретная математика? ? ????? ? Приложение ? ?? ? С? ??????
??? ?ыкова ????? ?икульская ???? ?лгоритмические аспекты минималь?
ных триангуляций графа ?? Труды ??? ?еждународной кон?
ференции по эвентологической математике и смежным вопросам
?Э???????? ????? декабря ???? г?? ?расноярск? ? ?расноярск?
??ТЭ?? СФУ? ????? ? С? ??????
??
??? ?ыкова ????? Трубникова ??С? ?лгоритмы построения оптимального
дерева декомпозиции ациклического гиперграфа ?? Труды ??? ?еж?
дународной конференции по эвентологической математике и смеж?
ным вопросам ?Э???????? ????? декабря ???? г?? ?расноярск? ? ?рас?
ноярск? ??ТЭ?? СФУ? ????? ? С? ??????
??? ?ыкова ???? ?атематические методы анализа рекурсивных алгорит?
мов ?? ?атериалы ? ?сесибирского конгресса женщин?математиков
?в день рождения С??? ?овалевской?? ????? января ???? г?? ?расно?
ярск? ? ?расноярск? Р?? СФУ? ????? ? С? ??????
??? ?ыкова ????? Портнягина Т?П? ?сследование угловой меры асимп?
тотического роста функций сложности алгоритмов ?? Труды ???
?сероссийской конференции по финансово?актуарной математике и
смежным вопросам ?Ф????????? ?? февраля?? марта ???? г?? ?рас?
ноярск? Ч??? ? ?расноярск? ?П? СФУ? ????? ? С? ??????
??? ?ыкова ???? ?симптотическая оценка сложности рекурсивных алго?
ритмов с аддитивным уменьшением размерности задачи ?? Труды
?? ?сероссийской конференции по финансово?актуарной математи?
ке и смежным вопросам ?Ф???????? ??? марта ???? г?? ?расноярск?
Ч? ?? ? ?расноярск? ??? С? Р??? СФУ? ??ТЭ?? С??УП? ?зд?во
??ротеск?? ????? ? С? ??????
??? ?ыкова ????? ?уприянова Т??? Сравнительный анализ ??
ациклических и комплектных гиперграфов ?? Проблемы оптимиза?
ции и экономические приложения? Тезисы доклада ?еждународной
конференции? ? ?мск? ?м?У? ????? ? С? ???
??? ?????? ???? P?r???t?r???? ????????t? ??? ???st???t? ?? t?? ????r?t??s
?? ??? ??t? ??????? ?t????st?? ?????s ??? ??t? ?????s?s ??t?r??t?????
?????r???? ???????????? ????? ?t???? ???? ???? ????? P? ????????
??? ?????? ???? ?? t?? ????? ?????t ?? ??r???t?r ?? t?? t??? ?????t??? ??
??r???t?r???? ????r?t??s ?? ??? ?????r???? ????t?? t? ?? ??????rs?r?
?? ???????????? ?? t?? ???????? ??????st?? ?????r? ??t????t??s
Pr?????s? ???P??????? ??rs???
??????st??? ????? ??r?? ?????
P? ????????
??? ?????? ???? ????????t? ??? ???st???t? ?? t?? ?????t?t??? ?? Pr???
?? t?? ???r? ?????? ??t?r??t????? ???t???????r???? ?? ??t???t????
???tr??? ??? ????r??t??? ?????????? ????????? ????? ?? ?????r?t???
??t? t?? ??ss??? ??????? ?? ???????s? ????? ???? ????? ????s???rs??
??ss??? ???? Pr?ss ??????? ? ?????r? ? ??r???? P? ????????
??
??? ?????? ???? ?s???t?t?? ?r???rt??s ?? s???t???s ?? ? s?????? t??? ??
r???rr???? r???t???s ?? ??? ???r? ??t?r??t????? ?????r???? ?Pr?????s
?? ????r??t??s ??? ????r??t??s? ?P????????? ??? ???t????r ????? ?????
???r??????? P? ????????
Свидетельства о регистрации программных комплексов
??? ?ыкова ????? ?икульская ???? ?омплекс программ ?r????? для на?
хождения дерева декомпозиции и вычисления верхней оценки древо?
видной ширины графа? Свидетельство о государственной регистра?
ции ? ????? от ?????????? ????? Р??? ?Ф?Р?и?? ? ?нв? номер
??Т?Ц ??????????? от ???????????
??? ?ыкова ????? ?олховец ???? ?омплекс программ ??????? для безопас?
ного разложения графа минимальными сепараторами? Свидетель?
ство о государственной регистрации ? ????? от ?????????? ?????
Р??? ?Ф?Р?и?? ? ?нв? номер ??Т?Ц ??????????? от ???????????
??? ?ыкова ????? Свинцов Ю??? ?омплекс программ ????r?? для пре?
образования дерева декомпозиции в бинарное сепараторное дерево?
Свидетельство о государственной регистрации ? ????? от ??????????
????П? Р??? ?Ф?Р?и?? ? ?нв? номер ??Т?Ц ??????????? от
???????????
??
Документ
Категория
Физико-математические науки
Просмотров
118
Размер файла
343 Кб
Теги
Докторская
1/--страниц
Пожаловаться на содержимое документа