WWW.KONF.X-PDF.RU
БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Авторефераты, диссертации, конференции
 

Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |

«Эффективные алгоритмы анализа закономерностей в строках ...»

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

Федеральное государственное автономное образовательное учреждение высшего профессионального образования

Уральский Федеральный Университет

имени первого Президента России Б.Н.Ельцина

На правах рукописи

Косолобов Дмитрий Александрович

Эффективные алгоритмы

анализа закономерностей в строках

Специальность 01.01.09 - дискретная математика и математическая кибернетика

Диссертация на соискание учёной степени

кандидата физико-математических наук



Научный руководитель

доктор физико-математических наук профессор Шур Арсений Михайлович Екатеринбург 2015 Оглавление 1 Введение

1.1 Структура диссертации и организация текста................... 4

1.2 Основные методы исследования........................... 6

1.3 Базовые определения................................. 6 1.3.1 Основные понятия............................... 7 1.3.2 Закономерности в строках.......................... 8

1.4 Модель RAM...................................... 10 1.4.1 Доступные инструкции и память...................... 10 1.4.2 Входные данные................................ 11 1.4.3 Время выполнения............................... 12

1.5 Модель решающего дерева.............................. 14

1.6 Обзор результатов................................... 15 1.6.1 Апробация и публикации........................... 15 1.6.2 Разложение Лемпеля–Зива.......................... 15 1.6.3 Повторы в

–  –  –

Глава 1 Введение Строка один из центральных объектов компьютерных наук. Любая последовательность, будь то последовательность байтов в файле или последовательность слов в тексте, это строка. В этом смысле каждый алгоритм работает со строкой битов, представляющих собой входные данные. Естественно, что такой общий взгляд на природу обрабатываемых данных оправдан не для всех проблем, но круг вопросов, оперирующих столь абстрагированным представлением, по-прежнему очень широк, ведь зачастую закономерности в исходных данных либо слишком сложны для формализации, либо вообще не известны. Как пример, можно привести задачи сжатия файлов, анализа последовательностей ДНК, поиска в тексте и многие другие. Алгоритмы, эффективно решающие подобные проблемы, почти всегда явно или неявно решают задачу выделения в строках определённых закономерностей, специфичных для данного конкретного вопроса. В настоящей работе исследуются как закономерности, играющие важную роль в ряде прикладных вопросов, так и закономерности, интересные с теоретической точки зрения и только нащупывающие возможности для применения.

Алгоритмы, имеющие дело с закономерностями в строках, помимо того, что активно используют существенную часть накопленного багажа знаний из области структур данных, вычислительной геометрии и алгоритмов на графах, также интенсивно применяют свой собственный обширный и постоянно совершенствующийся набор инструментов. Это позволило уже в 1985 году некоторым известным исследователям (на тот момент несколько претенциозно) утверждать, что изучение алгоритмов на строках можно считать отдельной областью, получившей название стрингология (англ. stringology от string строка) [42]. Эта динамически развивающаяся в настоящее время область уже успела обрасти множеством публикаций, рядом монографий [24, 28, 49, 82] и по меньшей мере двумя ежегодными специализированными конференциями с высоким уровнем цитируемости: SPIRE и CPM (не говоря о нескольких менее значимых специальных конференциях). Красноречивое свидетельство живого и активного интереса к рассматриваемым вопросам это список литературы к настоящей диссертации, в котором почти половина работ написана не ранее 2010-го года и в большинстве случаев опубликована в трудах наиболее цитируемых конференций по компьютерным наукам.

1.1 Структура диссертации и организация текста Прежде чем начинать непосредственно обсуждение результатов, в данной вводной главе читателю предоставляются некоторые дополнительные сведения, необходимые для понимания всего дальнейшего текста, и в концентрированном виде излагаются сами обсуждаемые результаты. В разделе 1.2 намечен применяемый нами метод исследований, который является по-существу стандартным при разработке алгоритмов. В разделе 1.3 даны, помимо некоторых базовых элементарных определений, определения основных объектов наших изысканий.





4 Разделы 1.4 и 1.5 содержат подробное описание алгоритмического инструментария, в контексте которого проводятся все дальнейшие рассуждения. Наконец, в разделе 1.6 кратко излагаются основные результаты.

Сами основные результаты распределены по трём главам. В главе 2 речь пойдёт о способах эффективного вычисления одной из самых распространённых на сегодняшний день конструкций, используемых для сжатия данных без потерь, разложения Лемпеля–Зива [68] (определение дано в разделе 1.3). Практическая важность этой техники, помимо применения в алгоритмах сжатия ZIP, 7z, PNG, GIF и других, подкрепляется включением разложения Лемпеля–Зива в (не столь длинный) список IEEE Milestones1, призванный увековечить ключевые вехи компьютерной революции и составленный IEEE (Institute of Electrical and Electronics Engineers) в настоящее время общепризнанно наиболее авторитетной ассоциацией в области стандартизации в компьютерной технике. С момента изобретения разложения Лемпеля–Зива постоянно возникают всё более и более эффективные методы его вычисления.

Особенно заметный бум наблюдается в последнее десятилетие [10, 21, 25, 38, 55, 75, 83, 86] в связи с развитием так называемых сжатых структур данных. В настоящей работе делается существенное теоретическое продвижение в вопросе вычисления разложения Лемпеля–Зива с эффективным использованием ресурсов машинного времени и памяти.

Главы 3 и 4 описывают близкие по духу теоретические результаты, мотивация которых основывается главным образом на внутренних задачах математики. Часто техники, применяемые при работе со строками, требуют нетривиального математического аппарата. Этот аппарат стрингология черпает в комбинаторике слов относительно молодой, но уже достаточно состоявшейся области математики. Но не только это связывает две области. Многие задачи, решаемые в стрингологии, имеют происхождение непосредственно из комбинаторики слов и служат внутренним теоретическим нуждам последней. В то же время и сама комбинаторика слов нередко получает новые открытые вопросы и неожиданные результаты из стрингологии. Одна из центральных задач в комбинаторике слов описание природы закономерностей в повторяющихся структурах в строках; этому, например, посвящена бльшая часть известной монографии по комбинаторике слов [70]. Именно внутренние задао чи комбинаторики слов, связанные с повторяемостью в строках, являются нашей основной мотивацией при разработке алгоритмов поиска повторяющихся структур в главе 3. Эта тема традиционно является популярной в стрингологии, но, несмотря на это, по-прежнему богата открытыми проблемами и активно исследуется и в последнее время [6, 7, 27, 35, 37, 53, 61, 81].

В главе 3 представлены два результата. Первый из них посвящён так называемым максимальным повторам [71] (см. определение в разделе 1.3) конструкции, позволяющей описать все повторы в строке. Мы теоретически обосновываем возможность существования более эффективных алгоритмов поиска всех максимальных повторов, чем существующие на данный момент [60, 7]. Второй результат это алгоритм, позволяющий эффективно строить сколь угодно длинные строки без повторов задача, постоянно возникающая в комбинаторике слов [81], но имеющая также приложение в некоторых алгоритмах из области искусственного интеллекта [69]; по возможностям, скорости и объёмам потребляемой памяти наш алгоритм превосходит все существующие решения [5, 53, 54, 69, 81]. Исследуемые нами повторяющиеся структуры также представляют интерес с точки зрения биологии, где повторяющиеся участки ДНК могут нести определённый биологический смысл [49].

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

http://ethw.org/Milestones:List_of_IEEE_Milestones

оставалась открытой проблемой и которые даже одно время рассматривались как гипотетический контрпример к одной известной и важной в теории формальных языков гипотезе [57, 43, 67].

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

Объём диссертации составляет 100 страниц, библиография включает 93 наименования.

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

Главным мерилом эффективности рассматриваемых алгоритмов выступает характер скорости роста потребляемых алгоритмом ресурсов при росте размера входных данных решаемой задачи. В качестве ресурса нас интересует время выполнения и необходимая для работы память. Чтобы абстрагироваться от деталей реализации конкретных вычислителей, характер зависимости ресурсов от объёмов входных данных чаще всего измеряется асимптотически (хотя в некоторых ситуациях резонно измерять память точно, как это делается для одной из исследуемых нами задач). Например, будем говорить, что данный алгоритм работает за O(n2 ) времени и использует O(n n) памяти, если на входных данных размера n алгоритм выполняет O(n2 ) элементарных операций и потребляет O(n n) памяти. Что именно подразумевается под размером данных, зависит от конкретной задачи. Естественно, чтобы строго определить, какие элементарные операции допустимы и в каких единицах измеряется память, необходимо описать так называемую модель вычислений набор доступных программе инструкций и возможностей по использованию памяти. Применяемые нами модели подробно рассмотрены ниже, но, забегая вперёд, можно отметить, что почти все они являются незначительными модификациями RAM модели модели, наиболее полно отражающей особенности современных компьютеров.

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

1.3 Базовые определения Все определения разбиты на два подраздела. Подраздел 1.3.1 содержит основные элементарные понятия, которые будут использоваться на протяжении всего текста по многу раз.

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

1.3.1 Основные понятия это отображение {1, 2,..., n}, где Строки. Строка длины n некоторое конечное множество, называемое алфавитом. Элементы алфавита называются символами.

Длина строки w обозначается через |w|. Пустая строка (т.е. строка длины 0) обозначается.

Через w[1], w[2],..., w[n] обозначаются 1-й, 2-й,..., n-й символы w, соответственно. Для произвольных целых числе i и j обозначим w[i..j] = w[i]w[i+1] · · · w[j]; если i j, то полагаем w[i..j] =. Строка w = w[n] · · · w[2]w[1] называется строкой, обратной к w. Для произвольных чисел i и j множество {k Z : i k j} будем обозначать через [i..j]. Обозначим (i..j] = [i..j] \ {i}, [i..j) = [i..j] \ {j}, (i..j) = (i..j] [i..j). Везде в тексте для краткости логарифм по основанию 2 обозначается log.

Строка u называется подстрокой (или фактором) строки w, если u = w[i..j] для некоторых i и j. В этом случае пара чисел (i, j) не обязательно единственна; будем говорить, что i определяет вхождение u в w. Строка может иметь множество вхождений в другую строку. Строка вида w[1..i] [соответственно, w[i..n]] называется префиксом w [соответственно, суффиксом w]. Конкатенацией строк v и w называется строка vw = v[1]v[2]... v[|v|]w[1]w[2]... w[|w|]. Для k 1 k-й степенью строки w называется строка wk, являющаяся конкатенацией k копий w. Строка называется примитивной, если она не является степенью какой-то более короткой строки.

Произвольное множество строк (возможно бесконечное) над данным фиксированным алфавитом называется языком. Определим стандартные операции, позволяющие получать из языки. Обозначим L · M = {uv : u L, v M }.

простых языков сложные. Пусть L и M Произведение k копий языка L будем обозначать Lk. Договоримся считать, что L0 = { }.

Обозначим L = Lk. k=0 Пусть символы рассматриваемого алфавита линейно упорядочены. Строка x лексикографически меньше строки y (обозначается x y), если x является собственным префиксом y или для некоторого i [1..|x|] выполняется x[1..i1] = y[1..i1] и x[i] y[i]. Ясно, что отношение лексикографического порядка линейно упорядочивает множество строк над данным упорядоченным алфавитом. Естественным образом определяются отношения x y, x y, x y.

Деревья и боры. Деревом называется обыкновенный связный граф без циклов. Дерево с одной выделенной корневой вершиной (корнем) называется корневым деревом. Фактически в тексте используются только корневые деревья, поэтому будем для краткости называть их просто деревьями, а корень всегда будет ясен из контекста. Листом дерева называется некорневая вершина степени 1; все остальные вершины называются внутренними. Иногда будут рассматриваться направленные деревья, в которых рёбра всегда направлены от вершин к листьям. Путь в графе это последовательность вершин v1, v2,..., vk такая, что vi и vi+1 соединены ребром для всех i [1..k). В деревьях будут рассматриваться только пути, идущие от корня к листьям без повторений вершин. Число k называется высотой данного дерева T, если самый длинный путь от корня до какого-либо листа T содержит k+1 вершину. Для краткости будем использовать запись v T для обозначения того факта, что v вершина T.

Бор 2 для конечного множества строк S это дерево, каждое ребро которого помечено непустой строкой так, что сумма длин меток минимальна и выполняются следующие свойства: каждая строка из S является префиксом строки, написанной на пути от корня до какого-либо листа, а каждая строка, написанная на пути от корня до листа, является строкой из S. Например, бор для множества строк Этот несколько странный термин устоялся в русскоязычной литературе по алгоритмам и программированию. Его английский аналог trie неологизм, полученный из tree и retrieval.

S = {a, aa, aaaaccccaaaac, aaaaccccaccc, aaaaccccaaac, aaacccc, aaaccaaca} изображён на рисунке 1.1. Ясно, что разные множества могут порождать одинаковый бор.

–  –  –

Наше определение бора незначительно отличается от общепринятого, в котором метками рёбер могут выступать не строки, а только символы. В контексте рассматриваемых в данной работе задач наше определение более удобно. Часто в бор входят строки, являющиеся подстроками какой-то одной основной в данной задаче строки s. В таком случае вместо того, чтобы указывать на каждом ребре строку-метку явно, можно просто задать позицию, в которой данная строка-метка встречается в s, и длину строки-метки. Полученное представление бора называют сжатым бором. Аналогично тому, как это было с деревьями, будем использовать запись v T для обозначения того факта, что v вершина данного [сжатого] бора T.

Асимптотические оценки. Для асимптотической оценки роста функций в работе обширно используются обозначения O,,, o,. Напомним их определение. Через F обозначим множество неотрицательных функций целочисленного аргумента. Пусть f F. Тогда O(f ) это множество всех g F таких, что g(n) cg f (n) для всех n Ng, где cg и Ng некоторые константы, зависящие от g. Обозначим (f ) = {g F : f O(g)} и (f ) = (f ) O(f ).

Через o(f ) обозначим множество всех g F таких, что g(n) = g (n)f (n) для всех n Ng, где Ng некоторое число, зависящее от g, а g (n) некоторая функция, зависящая от g, такая, что lim g (n) = 0. Обозначим (f ) = {g F : f = o(g)}. Вместо g O(f ), g (f ), n g (f ), g o(f ), g (f ) всегда пишут g = O(f ), g = (f ), g = (f ), g = o(f ), g = (f ), соответственно.

Также нам понадобятся аналоги введённых обозначений для случая неотрицательных функций с двумя и тремя параметрами. Например, для данной неотрицательной функции двух целочисленных аргументов f (m, n) через O(f (m, n)) будем обозначить множество неотрицательных функций g(m, n) таких, что g(m, n) cg f (m, n) для всех m Mg и n Ng, где cg, Mg, Ng некоторые константы, зависящие от g. Остальные определения аналогичны.

Дальнейшее описание способов работы с этими обозначениями можно найти, например, в учебнике [22].

1.3.2 Закономерности в строках Все исследуемые нами закономерности в строках так или иначе описывают некую повторяющуюся структуру и поэтому важную роль при их рассмотрении играет понятие периода. Целое число p (0..|w|] называется периодом строки w, если для каждой позиции i [1..|w|p] минимальный период строки w, то число |w|/p назывыполняется w[i] = w[i+p]. Если p вается экспонентой w. Строка u называется гранью w, если u одновременно и суффикс и префикс w. Будем говорить, что строка не имеет граней, если она имеет только тривиальные грани: саму строку целиком и пустую строку. Известна следующая связь между периодами и гранями.

Лемма 1.3.

1 (см. [28, раздел 1.7]). Строка w имеет период p 0 тогда и только тогда, когда w имеет грань длины |w| p.

Перейдём к определению главных объектов нашего исследования. Определения распределены по трём пунктам в соответствии с главами 2, 3, 4, в которых подробно обсуждаются соответствующие объекты.

Разложение Лемпеля–Зива Разложение Лемпеля–Зива [68] строки s это однозначное представление строки s в виде s = z1 z2 · · · zk такое, что каждая подстрока zi не пуста и представляет собой либо символ, не встречавшийся ранее в строке s, либо самую длинную подстроку в данной позиции, имеющую не менее двух вхождений в строке z1 z2 · · · zi. Строки zi будем называть факторами Лемпеля– Зива.

Удобно представлять себе, что разложение Лемпеля–Зива строки s строится жадно слева направо. Если уже найдены факторы Лемпеля–Зива z1, z2,..., zm1, то для построения zm нужно читать s с позиции i = |z1 z2 · · · zm1 |+1 до тех пор, пока строка s[i..i+z] имеет вхождение где-то левее в s. Нужно положить zm = s[i..i+z] для максимального такого z (или zm = s[i], если такая строка пуста).

Пример 1.3.

1. Строка ababcaba имеет разложение Лемпеля–Зива a · b · ab · c · aba. Строка abababaabbbaaba имеет разложение Лемпеля–Зива a · b · ababa · ab · bb · aab · a. В последнем случае обратите внимание на наложение на себя факторов Лемпеля–Зива ababa и bb.

Повторы Зафиксируем рациональное число e 1. Строки с экспонентами большими или равными e будем называть e-повторами; если e в обсуждаемом контексте не важно, то будем говорить просто о повторах. Например, строка abab это 2-повтор, aaa 3-повтор, abbcab 1.5повтор. Из определения следует, что если w e-повтор, то w также является e -повтором для всех e таких, что 1 e e. Например, aaa это 3-повтор и в то же время 1.7-повтор и, например, 2-повтор. Повторы вида xx, где x непустая строка, называются квадратами.

Загрузка...

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

Подстрока w[i..j] строки w называется максимальным повтором, если w[i..j] это 2повтор, а подстроки w[i1..j] и w[i..j+1] (если определены) не являются 2-повторами.

Палиндромы Палиндром это строка w такая, что w = w. Подстроку v [соответственно, суффикс v, префикс v] данной строки будем называть подпалиндромом [соответственно, суффикспалиндромом, префикс-палиндромом], если v является палиндромом. Например, строка ababa содержит 5 различных подпалиндромов: b, bab,, a, aba, ababa; четыре последних подпалиндрома имеют вхождения, являющиеся суффикс-палиндромами и префикс-палиндромами исходной строки. Обозначим через Pal язык всех непустых палиндромов над рассматриваемым алфавитом (о каком алфавите идёт речь будет всегда понятно из контекста).

1.4 Модель RAM это RAM модель (от Базовая модель, используемая нами для построения алгоритмов, англ. Random Access Machine или Random Access Model). В подразделе 1.4.1 сформулировано, какие именно инструкции являются допустимыми в RAM алгоритме и рассмотрены некоторые совсем неочевидные особенности модели памяти RAM машины, которые будут играть существенную роль в обсуждаемых впоследствии алгоритмических построениях. В подразделе 1.4.2 явно определено, в каком виде RAM алгоритм взаимодействует с входными данными, а также вводится важное понятие онлайнового алгоритма. Подраздел 1.4.3 посвящён описанию способа оценки времени выполнения RAM алгоритмов в различных моделях входных данных и здесь же определяется в дальнейшем очень часто применяемое понятие структуры данных.

1.4.1 Доступные инструкции и память В модели RAM алгоритму доступны все базовые арифметические операции: сложение, вычитание, умножение, деление, а также побитовые операции: побитовый сдвиг, побитовые и, или, отрицание, но самое главное, что есть возможность использовать массивы, индексируемые целыми числами, это память с произвольным доступом (Random Access Memory).

Для простоты можно полагать, что элементами массивов выступают только целые числа.

Известно, что с помощью таких массивов можно имитировать массивы, состоящие из структур произвольного фиксированного размера (см. [22, раздел 10.3]). Чтение и запись в ячейку массива, равно как и каждая арифметическая или побитовая операция, выполняются за фиксированное константное время. Входными данными для всех рассматриваемых в тексте алгоритмов является строка и длина этой строки всегда обозначается через n. Относительно n и оценивается время работы алгоритма, т.е. число операций, которые алгоритм затрачивает на решение задачи.

Часто алгоритмы или фрагменты алгоритмов для RAM машины будут кодироваться псевдокодом, похожим на традиционные императивные языки, такие как C или Pascal. В псевдокоде, помимо стандартных конструкций присваивания, циклов и ветвлений, присутствует трёхоперандный цикл for, как в языке C. Запись для массивов аналогична записи для строк, но нам будет удобно всякий раз явно оговаривать, с какой позиции начинается индексация в массиве. Например, в псевдокоде ниже используется массив b[0..n1]. Дальнейшие расширения языка псевдокода будут вводиться по мере надобности.

1: алгоритм обрабатывает строку w длины n 2: for (i 1; i n; i i + 1) do тернарный цикл for b[i1] 0; присвоить 0 в ячейку массива b 3:

if w[i] = a then 4:

b[i1] 1;

5:

while i n and w[i+1] = a do 6:

i i + 1;

7:

Данный алгоритм отмечает в b позиции начала блоков, состоящих из символов a, во входной строке. Если не вдаваться в детали, то можно заключить, что этот алгоритм использует O(n) памяти. Хотя вопрос оценки памяти стоит обсудить отдельно.

С RAM моделью связана одна на первый взгляд неочевидная тонкость. Алгоритм почти наверняка на входной строке длины n будет оперировать целыми числами порядка n, хотя бы просто чтобы иметь доступ к символам строки. И операции над числами, принимающими значение от 0 до n, выполняются за константное время, конечно. Таким образом, одно целое число, с которым алгоритм может совершать операции за константное время, содержит (log n) битов. Такая элементарная целочисленная ячейка, содержащая (log n) битов, называется машинным словом. Поэтому RAM модель иногда называют RAM моделью с константными операциями над словами. Эта особенность RAM модели отражает реальный факт: компьютер для выполнения операции сложения, например, использует схему, которая работает параллельно и вычисляет результат за константное время. Таким образом, RAM машина имеет толику параллелизма внутри себя. И это немаловажно для нас, так как в некоторых случаях позволяет улучшать асимптотическое время работы алгоритмов, оперируя за константное время блоками данных, состоящими из O(log n) битов. Этот трюк часто называют методом четырёх русских (см. [1]). В свете этого стоит уточнить, что RAM алгоритмы используют массивы не произвольных целых чисел, а целых чисел, помещающихся в машинное слово.

Везде в тексте потребляемая память измеряется в машинных словах; если же память измеряется в битах (как это часто происходит в разделе 2.3), это каждый раз оговаривается явно. Таким образом, будем говорить, что, например, алгоритм потребляет O(n2 ) памяти, если на любой входной строке длины n алгоритм использует O(n2 ) машинных слов, что фактически равно O(n2 log n) битам. Будем говорить, что алгоритм использует линейную память, если он потребляет O(n) памяти (как в примере выше). Линейная память зачастую воспринимается как наилучшая возможная асимптотическая оценка, потому что как минимум O(n) памяти требуется для хранения входной строки. Тем не менее для некоторых задач естественно предполагать, что входная строка расположена в некоем внешнем хранилище или же, что входная строка занимает o(n log n) битов памяти. В этом случае будем говорить не о памяти, а о дополнительной памяти, чтобы подчеркнуть, что речь идёт о памяти помимо входной строки. Лучшее на что можно надеяться при решении задачи с такими ограничениями это O(1) дополнительной памяти (константная память).

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

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

Итак, в работе применяются следующие модели алфавита.

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

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

–  –  –

• Алфавит целочисленный. Алфавит состоит из целых чисел, умещающихся в константное число машинных слов. Размер алфавита является дополнительным параметром входных данных. Входная строка над целочисленным алфавитом [0..) кодируется непрерывным блоком в памяти, занимающим n log битов.

• Алфавит константный. Число различных символов во входной строке фиксировано и никак не зависит от длины этой строки.

Для удобства здесь и далее вместо общий упорядоченный алфавит будем говорить просто упорядоченный алфавит. Аналогично вместо общий неупорядоченный алфавит будем говорить неупорядоченный алфавит.

Ясно, что целочисленный алфавит частный случай упорядоченного алфавита, а упорядоченный частный случай неупорядоченного. Несложным рассуждением покажем, что, не ограничивая общности, константный алфавит можно считаться состоящим из чисел 0, 1,..., c, где c некоторая константа (таким образом, константный алфавит частный случай целочисленного): при работе алгоритма нужно фиксировать все встречавшиеся символы алфавита и последовательно присваивать им номера 0, 1,...; тогда, чтобы определить номер очередного символа, достаточно сравнить его со всеми уже фиксированными символами, а так как алфавит константный, таких символов всего константное число, и, значит, сравнение занимает константу времени.

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

Пример 1.4.

1. Онлайновый алгоритм, проверяющий строку на наличие 2-повторов, читает строку слева направо посимвольно и сразу после окончания чтения очередного префикса определяет, присутствуют ли в нём подстроки, являющиеся 2-повторами.

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

1.4.3 Время выполнения Как уже упоминалось выше, во всех рассматриваемых нами алгоритмах входные данные это строка длины n. Пусть f (n) некоторая неотрицательная функция. Будем говорить, что алгоритм работает за O(f (n)), если он выполняет O(f (n)) операций для решения данной задачи на любой строке длины n. Алгоритмы, работающие за O(n), называются линейными.

Линейный алгоритм для большинства адекватных задач на строках это асимптотически самый быстрый алгоритм, потому что O(n) времени требуется как минимум для того, чтобы прочитать всю входную строку. Часто будет удобно производить более тонкие оценки времени выполнения, включая помимо параметра n какой-либо естественный дополнительный параметр. Например, если число различных символов входной строке, то будем говорить, что алгоритм работает за O(f (n, )), где f (n, ) некоторая функция, если на любой строке длины n, содержащей различных символов, данный алгоритм выполняет O(f (n, )) операций. Подобным же образом определяются оценки времени, зависящие от любых других дополнительных параметров.

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

На целочисленном алфавите с символами, принимающими значение от 0 до n, задачу можно решить за линейное время: нужно создать массив с ячейками, индексируемыми числами от 0 до n, и отметить присутствующие в строке символы. Для упорядоченного алфавита задачу можно решить за O(n log n) с помощью какого-нибудь сбалансированного дерева (красночёрного, например; см. [22, глава 13]). Оказывается, что быстрее этого сделать нельзя.

Теорема 1.4.

1 (см. [15, теорема 1.3]). Любой алгоритм, определяющий все ли символы в строке длины n над упорядоченным алфавитом различны, выполняет (n log n) сравнений в худшем случае.

Для неупорядоченного алфавита ситуация ещё хуже.

Теорема 1.4.

2 (см. [15, теорема 1.1]). Любой алгоритм, определяющий все ли символы в строке длины n над неупорядоченным алфавитом различны, выполняет (n2 ) сравнений в худшем случае.

Говорят, что алгоритм распознаёт язык L или алгоритм является распознавателем L или язык L распознаваем данным алгоритмом, если этот алгоритм принимает на вход строку и определяет принадлежит ли она L или нет. Распознаватель языка L называется онлайновым (или говорят, что язык L онлайново распознаваем), если данный алгоритм читает входную строку слева направо и сразу после считывания каждого префикса определяет принадлежит ли этот префикс языку L. Пусть f (n) и g(n) некоторые функции целочисленного аргумента. Будем говорить, что данный [онлайновый] распознаватель работает за время O(f (n)) и O(g(n)) памяти, если на любой строке длины n он [онлайново] определяет принадлежит ли эта строка L за время O(f (n)) и O(g(n)) памяти.

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

Время работы операций структуры данных измеряется относительно размера поддерживаемого структурой набора данных. Причём то, что подразумевается под набором данных определяется отдельно для каждой задачи. Например, будем говорить, что операция добавления в словарь работает за O(log n), если добавление нового символа в словарь, содержащий n различных символов, требует выполнения O(log n) элементарных инструкций.

Будем говорить, что данная операция в рассматриваемой структуре данных выполняется за амортизированное время O(f (n)), где f (n) некоторая функция, если время работы любой последовательности из m данных операций, выполняющихся на только что созданной структуре, равно O(mf (n)), где n максимальный размер поддерживаемых данных на протяжении работы данной последовательности из m операций.

Пример 1.4.2. Рассмотрим простую структуру расширяющийся массив. Эта структура поддерживает массив машинных слов b[1..n] (изначально пустой) с двумя операциями:

read(i), которая читает ячейку i массива, и extend(x), которая увеличивает длину массива на единицу, присоединяя справа к массиву машинное слово x. Структура поддерживает память размера 2k под массив b. Если при выполнении extend в выделенной памяти размера 2k не хватает места для расширения, структура выделяет память размера 2k+1 и за O(2k ) копирует старое содержимое в новое место. Несложно понять, что extend работает за O(n), но в то же время амортизированное время работы extend равно O(1).

1.5 Модель решающего дерева Модель решающего дерева стоит особняком от RAM моделей. Она используется для доказательства нижних границ на время работы алгоритмов. Нижней границей называют утверждение о том, что та или иная задача на определённой машине не может быть решена быстрее чем за определённое число операций. Примеры нижних границ приведены в теоремах 1.4.1 и 1.4.2.

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

Решающее дерево, анализирующее строки длины n над упорядоченным алфавитом, это корневое направленное тернарное дерево, в котором каждая внутренняя вершина помечена некоторой упорядоченной парой целых чисел (i, j) таких, что i, j [1..n], а исходящие рёбра помечены символами, =, (см. рис. 1.2). Будем говорить, что некая вершина v решающего дерева достижима по строке t или строка t достигает вершину v, если для каждой вершины u на пути от корня к v и ребра e, исходящего из u по тому же пути, выполняется: t[i] t[j] [соответственно, t[i] t[j], t[i] = t[j]] тогда и только тогда, когда ребро e помечено символом [соответственно,, = ], где (i, j) пара чисел в вершине u. Отметим, что каждая строка достигает в точности одного определённого листа данного дерева.

Рис. 1.2: Решающее дерево высоты 2, анализирующее строки длины 3. Строки aaa и bbb достигают закрашенной вершины.

Чтобы лучше освоиться с решающими деревьями, рассмотрим классическое доказательство (n log n) нижней границы для задачи сортировки. Итак, дана строка длины n над упорядоченным алфавитом: требуется найти перестановку позиций строки, сортирующую все символы по возрастанию. Что значит, что данное решающее дерево решает задачу сортировки? Это значит, что каждому листу дерева сопоставлена некая перестановка и если взять входную строку t длины n, то листу, которого достигает t, сопоставлена перестановка, сортирующая символы t. Не ограничивая общности, можно допустить, что все листья нашего дерева достижимы. Всего есть n! перестановок и, очевидно, каждая из этих перестановок должна присутствовать в каком-то листе. Но тернарное дерево с n! листья обязательно имеет высоту никак не меньше log3 n! = (log n!) = (n log n). Значит, существует плохая строка t, на которой решающее дерево выполняет (n log n) сравнений.

Отметим, что каждому n сопоставлено своё отдельное решающее дерево. В этом решающие деревья сильно отличаются от RAM моделей. Тем не менее из нашего доказательства следует, что никакой RAM алгоритм не может решать задачу сортировки на упорядоченном алфавите менее, чем за (n log n) операций. Чтобы это понять, можно естественным образом сопоставить данному RAM алгоритму и данному числу n решающее дерево, решающее задачу сортировки для строк длины n. Из представленных выше рассуждений сразу следует, что найдётся строка, на которой решающее дерево, а значит и исходный RAM алгоритм, выполняют (n log n) сравнений символов. Вообще, решающие деревья это основной инструмент для доказательства нижних границ на RAM алгоритмы, работающие с общими алфавитами.

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

1.6 Обзор результатов Все полученные в работе результаты тематически поделены по трём главам 2, 3, 4. Обзор результатов из этих глав дан, соответственно, в подразделах 1.6.2, 1.6.3, 1.6.4 настоящего раздела. Прежде чем переходить непосредственно к описанию результатов, в начале каждого подраздела коротко указываются области возникновения рассматриваемых задач и мотивация. Более развёрнутое описание существующих результатов, а также подробная мотивация исследований приводятся во вводных частях соответствующих глав и разделов этих глав.

1.6.1 Апробация и публикации Все представленные результаты опубликованы в статьях автора [92, 93, 89, 90, 88] (две из них в соавторстве с Рубинчиком Михаилом Валентиновичем и Шуром Арсением Михайловичем) в сборниках трудов следующих международных конференций: 40-й международный симпозиум по математическим основам компьютерных наук (MFCS 2015, Милан, Италия), 26-й ежегодный симпозиум по комбинаторному поиску шаблонов (CPM 2015, о.

Искья, Италия), 32-й симпозиум по теоретическим аспектам компьютерных наук (STACS 2015, Мюнхен, Германия), 41-я международная конференция по текущим направлениям в теории и практике компьютерных наук (SOFSEM 2015, Пец-под-Снежкой, Чехия), Пражская конференция по стрингологии (PSC 2013, Прага, Чехия). Все названные сборники удовлетворяют достаточному условию ВАК для опубликования результатов диссертации. Часть результатов опубликована в тезисах [91, 87] (один из них в соавторстве с Рубинчиком М. В.) в трудах международных школ-конференций CSEdays 2013 и CSEdays 2014 в Екатеринбурге. Автор выступал с докладами на всех перечисленных конференциях. Результаты также докладывались на семинаре Алгебраические системы (УрФУ, рук. Шеврин Л. Н., 2014–2015). В нижеследующем описании после краткого изложения каждого результата указывается, в какой именно статье он опубликован.

1.6.2 Разложение Лемпеля–Зива Разложение Лемпеля–Зива, впервые описанное в [68], и некоторые его незначительные модификации в настоящее время является наиболее распространённой эффективной техникой сжатия данных, используемой в стандартах ZIP, 7z, PNG, GIF и других. На основе этого разложения реализуется простая идея сжатия без потерь: если есть подстрока z, встречавшаяся в строке ранее, то при сжатии всей строки нет необходимости записывать z целиком, а достаточно лишь указать длину z и в какой позиции встречалась z. Таким образом, если каждый неодносимвольный фактор Лемпеля–Зива кодировать парой чисел (p, l), где p позиция в строке, где ранее встречался этот фактор (таких позиций может быть несколько и достаточно взять любую), а l длина фактора, то строка с разложением Лемпеля–Зива a · b · ababa · ab · bb · aab · a может быть закодирована так: ab(1, 5)(5, 2)(9, 2)(7, 3)a. Нетрудно понять, что исходная строка легко восстанавливается по этой кодировке. Конечно, формат хранения пар чисел и символов зависит от реализации, но общая идея остаётся неизменной.

–  –  –

Таблица 1.1: Лучшие алгоритмы поиска разложения Лемпеля–Зива, использующие O(n log ) битов.

Стандартные алгоритмы, вычисляющие разложение Лемпеля–Зива на упорядоченном алфавите, работают за O(n log ) времени, где число различных символов во входной строке длины n [23, 78, 34]. Первый вопрос, который исследуется в настоящей работе: можно ли на упорядоченном алфавите вычислять разложение Лемпеля–Зива за o(n log )?

Так как основное применение разложения Лемпеля–Зива сжатие данных, которые сами по себе часто очень велики и оставляют мало места для работы самого алгоритма сжатия, естественным образом встаёт задача вычисления разложения Лемпеля–Зива в условиях крайних ограничений на используемую память. Для наиболее важного случая целочисленного алфавита [0..) (для простоты будем полагать, что это степень двойки) существует несколько линейных алгоритмов, потребляющих O(n log n) битов памяти (здесь представляется целесообразным измерять память в битах); лучшие из таких алгоритмов описаны в [2, 4, 21, 25, 38, 46, 56]. Но когда мало, выделять O(n log n) битов памяти в дополнение к n log битам, занимаемым самой входной строкой, становится обременительно. Для решения этой проблемы было разработано множество алгоритмов, использующих O(n log ) битов [10, 55, 63, 66, 75, 76, 83, 86]. В таблице 1.1 приведены время и память, потребляемые лучшими существующими решениями, вычисляющими разложение Лемпеля–Зива в рамках O(n log ) битов.

• В разделе 2.2 доказывается, что на упорядоченном алфавите любой алгоритм, вычисляющий разложение Лемпеля–Зива на строке длины n, содержащей различных символов, работает за (n log ) в худшем случае. Этот результат показывает, что известные алгоритмы, вычисляющие разложение Лемпеля–Зива за O(n log ), являются оптимальными, а значит, случай упорядоченного алфавита можно считать закрытым.

Результат опубликован в [89]

• В разделе 2.3 рассматривается важнейший для практики случай вычисления разложения Лемпеля–Зива на целочисленном алфавите в условиях ограниченной памяти. Конструируется алгоритм, позволяющий найти разложение Лемпеля–Зива строки длины n с символами из диапазона [0..) за время O(n(log + log log n)) и n log + n битов памяти, где произвольная положительная константа, а n log битов в оценке памяти сама анализируемая строка, доступная только для чтения. В настоящее время это самый быстрый алгоритм, использующий O(n) битов дополнительной памяти.

Результат опубликован в [88] 1.6.3 Повторы в строках Приложение алгоритмов поиска повторов для внутренних исследований в комбинаторике слов является нашей основной мотивацией. Хотя стоит отметить, что поиск 2-повторов имеет отдельный интерес с точки зрения биоинформатики, где участки строк ДНК, являющиеся 2-повторами, могут нести определённый биологический смысл [49].

В [60, 7] доказано, что любая строка длины n содержит не больше n максимальных повторов. Таким образом, множество всех максимальных повторов в компактной форме определяет все 2-повторы в строке и, значит, в некотором смысле охватывает всю периодическую структуру строки. Задача поиска максимальных повторов на неупорядоченном алфавите давно решена: доказана нижняя граница (n log n) [72] и приведён алгоритм, работающий за O(n log n) [71]. Колпаков и Кучеров [60] описали алгоритм поиска всех максимальных повторов, работающий за O(n) при условии, что разложение Лемпеля–Зива строки уже найдено (а на упорядоченном алфавите, как доказывается в разделе 2.2, поиск разложения Лемпеля–Зива требует (n log ) времени). Максимальным повторам посвящено немало работ [6, 26, 27, 61, 80], но вплоть до последней работы Баннаи и др. [7] все эффективные алгоритмы поиска максимальных повторов основывались на разложении Лемпеля–Зива. (В [7] используется иной подход, но, к сожалению, тоже работающий за (n log ) в худшем случае на упорядоченном алфавите.) Естественно возникает вопрос: можно ли найти все максимальные повторы за линейное время на упорядоченном алфавите? Или может быть можно доказать нижнюю границу (n)?

Другая рассматриваемая нами задача онлайновый поиск e-повторов. Существует целая серия онлайновых алгоритмов, проверяющих строку на наличие e-повторов [5, 53, 54, 69, 81].

На неупорядоченном алфавите для e = 2 самый быстрый из них алгоритм Апостолико и Бреслауэра [5], работающий за O(n log n) времени и O(n) памяти. В [72] доказано, что для неупорядоченного алфавита это время оптимально. Возникает вопрос: можно ли на неупорядоченном алфавите получить онлайновый алгоритм, работающий за оптимальное время O(n log n) и O(n) памяти для произвольной рациональной константы e 1?

Наш интерес к онлайновым алгоритмам проверки на наличие e-повторов обусловлен популярной в комбинаторике слов задачей построения длинных случайных строк без e-повторов [81]. В связи с этим мы рассматриваем также операцию отката, позволяющую на любом шаге работы онлайнового алгоритма отбрасывать последний символ прочитанной строки (подробнее см. в разделе 3.4). Также полученные алгоритмы интересны для некоторых приложений в области искусственного интеллекта [69].

• В разделе 3.2 обсуждается возможное существование нижних границ на задачу поиска всех максимальных повторов в строке на упорядоченном алфавите. Показано, что на решающем дереве подобной нижней границы не существует, а именно, в модели решающего дерева построен линейный алгоритм поиска всех максимальных повторов (дальнейшие разъяснения см. в разделе 3.2). Можно смотреть на этот результат как на указание на то, что, по-видимому, существует линейный RAM алгоритм поиска максимальных повторов на упорядоченном алфавите. Это открывает возможности для дальнейшего улучшения существующих алгоритмов. Результат опубликован в [89].

(В разделе 3.3 в подтверждение высказанной гипотезы конструируется RAM алгоритм поиска всех максимальных повторов в строке над упорядоченным алфавитом, работающий за O(n log 3 n). Все другие известные на данный момент решения работают за (n log n), когда в строке много различных символов. Соответствующая статья принята к печати в журнале Information Processing Letters, но ещё не опубликована, и поэтому этот результат не заявлен как один из основных в диссертации; см. [64].)

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

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

Результат опубликован в [90].



Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |
 
Похожие работы:

«ВОРОНЦОВА ЕВГЕНИЯ АЛЕКСЕЕВНА МЕТОД ОТДЕЛЯЮЩИХ ПЛОСКОСТЕЙ С ДОПОЛНИТЕЛЬНЫМИ ОТСЕЧЕНИЯМИ И ЕГО ПРИМЕНЕНИЕ В ЗАДАЧАХ АНАЛИЗА ДАННЫХ С НЕОПРЕДЕЛЕННОСТЯМИ Специальность 05.13.18 – Математическое моделирование, численные методы и комплексы программ Диссертация на соискание учёной степени кандидата физико-математических наук Научный...»

«ГУРИН Григорий Владимирович СПЕКТРАЛЬНАЯ ХАРАКТЕРИСТИКА ВЫЗВАННОЙ ПОЛЯРИЗАЦИИ ВКРАПЛЕННЫХ РУД Специальность 25.00.10 – Геофизика, геофизические методы поисков полезных ископаемых Диссертация на соискание ученой степени кандидата геолого-минералогических наук Научный руководитель: д.г.-м.н., проф. К.В. Титов Санкт-Петербург –...»

«Семиков Сергей Александрович Методы экспериментальной проверки баллистической теории света 01.04.03 – Радиофизика ДИССЕРТАЦИЯ на соискание учёной степени кандидата физико-математических наук Научный руководитель д. ф.-м. н., проф. Бакунов Михаил Иванович Нижний Новгород – 2015 Содержание ВВЕДЕНИЕ ГЛАВА 1....»

«КУДАШОВ Егор Сергеевич ИНЖЕНЕРНО-ГЕОЛОГИЧЕСКОЕ ОБОСНОВАНИЕ УСТОЙЧИВОСТИ НАМЫВНЫХ ГИПСОНАКОПИТЕЛЕЙ Специальность 25.00.16 – Горнопромышленная и нефтегазопромысловая геология, геофизика, маркшейдерское дело и геометрия недр Диссертация на соискание ученой степени...»

«Шахсинов Гаджи Шабанович НЕСТАЦИОНАРНЫЕ КИНЕТИЧЕСКИЕ ПРОЦЕССЫ С УЧАСТИЕМ МЕТАСТАБИЛЬНЫХ АТОМОВ ИНЕРТНЫХ ГАЗОВ В ПЛАЗМЕННЫХ ВОЛНОВОДАХ 01.04.04 – физическая электроника ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук Научный руководитель: д. ф.-м. н., профессор Ашурбеков Назир Ашурбекович Научный консультант: д. ф.-м. н., профессор Иминов Кади Османович Махачкала – 2015 Оглавление ВВЕДЕНИЕ...»

«Черемхина Анастасия Петровна ОЦЕНКА ЗАКОНОМЕРНОСТЕЙ ИЗМЕНЕНИЯ ИНЖЕНЕРНОГЕОЛОГИЧЕСКИХ УСЛОВИЙ УСТОЙЧИВОСТИ ГИДРООТВАЛОВ ВСКРЫШНЫХ ПОРОД В ЗАВИСИМОСТИ ОТ ЭТАПА ЭКСПЛУАТАЦИИ Специальность 25.00.16 Горнопромышленная и нефтегазопромысловая геология, геофизика,...»

«Чирская Наталья Павловна Математическое моделирование взаимодействия космических излучений с гетерогенными микроструктурами Специальность: 01.04.20 – физика пучков заряженных частиц и ускорительная техника 01.04.16 – физика атомного ядра и элементарных частиц диссертация на соискание ученой степени кандидата физико-математических наук Научный руководитель: доктор...»

«ЕМЕЛЬЯНОВ НИКИТА АЛЕКСАНДРОВИЧ Структура и диэлектрические свойства наночастиц BaTiO3 c модифицированной поверхностью и композитного материала на их основе Специальность 01.04.07 – физика конденсированного состояния ДИССЕРТАЦИЯ на соискание учёной степени кандидата физико-математических наук Научный руководитель: доктор технических наук, профессор, Заслуженный деятель науки РФ Сизов А.С. Курск – 2015...»

«ПАНЧЕНКО Алексей Викторович МАРКШЕЙДЕРСКАЯ ОЦЕНКА УСТОЙЧИВОСТИ КРИВОЛИНЕЙНОГО В ПЛАНЕ БОРТА КАРЬЕРА Специальность 25.00.16 – Горнопромышленная и нефтегазопромысловая геология, геофизика, маркшейдерское дело и геометрия недр Научный руководитель: доктор технических...»









 
2016 www.konf.x-pdf.ru - «Бесплатная электронная библиотека - Авторефераты, диссертации, конференции»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.