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

УДК 004.07+004.2+519.683

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

МУРЗИН Федор Александрович

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

05.13.17 - Теоретические основы информатики

г 9 июп ш

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

Новосибирск 2015 005571034

005571034

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте систем информатики им. А.П. Ершова Сибирского отделения РАН

Официальные оппоненты:

Потатуркин Олег Иосифович

Доктор технических наук, профессор

Федеральное государственное бюджетное учреждении науки Институт автоматики и электрометрии Сибирского отделения РАН Заместитель директора по научной работе

Легалов Александр Иванович

Доктор технических наук, профессор Сибирский федеральный университет Заведующий кафедрой вычислительной техники

Тузовский Анатолий Федорович

Доктор технических наук, профессор

Томский политехнический университет

Профессор кафедры оптимизации систем управления

Ведущая организация: Федеральное государственное бюджетное учреждение науки Институт вычислительной математики и математической геофизики Сибирского отделения РАН

Защита состоится 29 октября в 15 ч. 00 мин. на заседании диссертационного совета Д 219.005.02 приФГОБУВПО "Сибирский государственный университет телекоммуникаций и информатики" по адресу: 630102, г. Новосибирск, ул. Кирова, 86, ауд. 625

С диссертацией можно ознакомиться в читальном зале ФГОБУ ВПО СибГУТИ

Автореферат разослан

(Л^ОКХ 2015 г.

Ученый секретарь

диссертационного совета Д 219.005.02

к.т.н.

И.И. Резван

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

Актуальность проблемы

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

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

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

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

Тематика исследований соответствует паспорту специальности 05.13.17 — Теоретические основы информатики, пункты: 2, 3, 5, 9, 12.

Цель работы

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

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

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

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

• рассмотреть возможности отображения Р1С-метода на различные наиболее интересные архитектуры вычислительных систем;

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

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

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

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

Научная новизна

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

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

2. По заказу ОАО "Западно-Сибирская Корпорация Тюменьпромгеофизика" разработан и реализован ряд алгоритмов для обработки сигналов, получаемых в процессе радиоактивного каротажа нефтяных скважин. Создан ряд программных комплексов. Наиболее важный из них «Анализатор спектров» (SpectrumAnalyzer). Он предоставляет широкие возможности для обработки каротажных данных: загрузка, просмотр и обработка исходных амплитудных и временных спектров; расчет различных аналитических параметров; вычисление концентраций естественных радионуклидов; экспорт результатов обработки в формате LAS, применяемом в геофизике. Алгоритмы и программный комплекс используются при эксплуатации нефтяных месторождений и конкурентоспособны с мировыми аналогами. Таким образом, решена прикладная задача важная для народного хозяйства.

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

Практическая ценность

Результаты первой и второй глав диссертации были получены в процессе работы по теме «Мозаика», которая выполнялась в Институте теоретической и прикладной механики СО РАН совместно с НТО «Феникс», г. Омск для Инсги-

тута физики полупроводников СО РАН. Результаты также были использованы в Институте автоматики и электрометрии СО РАН.

Результаты 3-й главы имеют исследовательский характер, но в целом, они полезны специалистам по вычислительной математике, использующим в своей практике параллельные вычислительные системы.

Результаты 4-й главы получены в процессе работы по заказу ОАО «Западно-Сибирская Корпорация "Тюменьпромгеофизика"». Программный комплекс «Анализатор спектров» (SpectrumAnalyzer) внедрен в Интерпретационном центре ЗСК ТПГ, г. Мегион, Ханты-Мансийский Национальный Округ. Остальные работы были выполнены для заказчиков из Респ. Казахстан, там же внедрены соответствующие программные комплексы.

Результаты 5-й главы применены в системе интеллектуального поиска, реализованного в ИСИ СО РАН A.A. Перфильевым. Частично использовались A.B. Проскуряковым в работах по определению спам сообщений и рассыльши-ков спама. Работа выполнялась по заказу. Предполагается использовать результаты данной главы в программном комплексе анализа данных из социальных сетей также разработанным в ИСИ СО РАН, (комплекс реализован A.B. Проскуряковым). В настоящее время также ведутся работы применительно к тюркским языкам.

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

Результаты работы докладывались на следующих конференциях и семинарах: Совещание по системам аналит. вычислений на ЭВМ, Дубна, 1982; Школа-семинар соц. стран "Вычислительная аэрогидромеханика", Москва-Самарканд, 1985; Междунар. конф. по обработке изображений и дистанционным исследованиям, Новосибирск, 1990; Intern, conf. "Visual Analysis and Interface", Novosibirsk, 1991; Intern, conf. on the Methods of Aerophysical Research (ICMAR'96), Novosibirsk, 1996; Междунар. симп. "Математические модели и численные методы механики сплошной среды", Новосибирск, 1996; XVI Междунар. школа-семинар по численным методам механики вязкой жидкости, Новосибирск, 1998; IV Сибирский конгресс по прикладной и индустриальной математике (ИНПРИМ'2000), Новосибирск, 2000; Междунар. конф. "Портативные генераторы нейтронов и технологии на их основе", Москва 2004; 15th Intern, conf. on Computer Graphics and Applications (GraphiCon'05), 2005; V Российско-германская школа по параллельным вычислениям на высокопроизводительных вычислительных системах. Семинар "Распределенные и высоко-

производительные вычисления", Новосибирск, 2008; Росс, научно-техн. конф. "Информатика и проблемы телекоммуникаций", Новосибирск, 2011; Intern, conf. "Advanced Mathematics, Computations and Applications" (AMCA'2014), Novosibirsk 2014; V, VI, VII, VIII Международные конференции памяти академика А.П. Ершова "Перспективы систем информатики", рабочий семинар "Наукоемкое программное обеспечение", Новосибирск, 2003, 2006, 2009, 2011; Working Seminar of Univ. of Paris-Sud (Univ. of Paris XI), Lab. of Information Science and Technology, Paris, France, 2010; 3rd Global Congress on Intelligent Systems (GCIS'2012) and 3rd Word Congress on Software Engineering (WCSE'2012), Wuhan Univ. of Technology; Wuhan, China, 2012; Intern. Workshop on Enterprise Information Systems in Cloud Computing Envirionment, Beijing University of Posts and Telecommunications; Beijing, China, 2012; Working Seminar of State Key Laboratory Automation for Process Industries, Northeastern Univ. Shenyang, Shenyang, Liaoning, China, 2012; Working Seminar of Hebei Univ. of Science and Technology, School of Economics and Management, Dep. of Information Management, Shijiazhuang, Hebei, China, 2012; XIII Conf. of Intelligent Text Processing and Computational Linguistics (CICLing), Indian Inst, of Technology, Delhi, India, 2012.

Результаты диссертации также были представлены в виде докладов и/или стендов на научно-технических выставках: Российская научно-техн. выставка в Индии, Expo Centre EXPO XXI, Инновационная зона Нойда, Индия, 2008; Российская научно-техн. выставка в США, Exhibition Center McCormick Place, Чикаго, США, 2009; Российская научно-техн. выставка во Франции, Выставочный центр «Гранд Пале», Париж, Франция, 2010; Вторая междунар. инновационная ярмарка, Гуанчжоу, Китай, 2012; Неделя междунар. научно-техн. сотрудничества в 2013 году, Дунгуань, Китай, 2013.

Публикации

По теме диссертации опубликовано более 100 работ. Из них 5 монографий в соавторстве, 16 из списка ВАК, Scopus и Web of Science

Структура и объем работы

Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и одного приложения. Объем диссертации - 279 страниц. Список литературы содержит 221 наименование. Работа включает 69 рисунков и 8 таблиц.

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

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

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

Пусть nv...,nk - целые положительные числа. Множество

A(nl,...,nk) = {(il,..-.'i):Ay=i (0 ^ ij < >Tj)} назовем массивом. В действительности, в программировании под массивом размерности и, х...хпкпонимается отображение вида А' : /((/;,,) —W.

Далее вместо А(п{,...,пк) будем писать А, опуская круглые скобки вместе с их содержимым. Произвольное множество SczA будем называть сегментом.

Предположим, что в нашем распоряжении имеются N модулей памяти. Считаем, что емкость всех модулей одна и та же, и она равна К. Пространством памяти назовем массив Р = A{N,K). Для простоты можно считать, что по каждому адресу а, где 0 < а < К может храниться в точности один бит.

Пусть А,,...АГ — последовательность масстшов размерностей ki,...ks соответственно, G......Gt - семейства сегментов в А1,...As. Отображения f,,...fs

удовлетворяют условиям

1) dom f] = /1,,

2) range /] cz Р,

3) range/ глrange fj = 0.

4) ft инъективны.

Определение. Последовательность (/¡,.-./,) называется универсальной относительно (G^.-.jG,) в том и только в том случае, когда V / V S е Gl. V s0, е S(s0 Ф i, —> p/i_/j(s0) Ф /¡ (s,)), где pr\ - проекция пары на первую координату.

Пусть А = А(щ,...,пк) - массив, к>2. Определим сегменты:

Pj (О = Prj~\t) п A = {< г\, ....,г\ >eA:ij =t},

BL[Tx,....,Tk](jl....Jl) = {< .....ik > e A: A i'j ^ i, < + rj).

7=1

Рассматриваем следующие семейства сегментов:

Cutj= {P;<V):0<f<«,},

Cut = \JCutj, j

3/(ri,...,ri) = |fi4r1,...,ri](f10,...>i°): л0</° <«,-Tj j,

Далее строятся некоторые функции X, р*, сг*, для которых доказываются следующие теоремы.

Теорема 1.1. Последовательность < X > является универсальной относительно (Cut).

Теорема 1.2. Последовательность (р*) является универсальной относительно ^О//, [_j3/(r,,..., r4

Теорема 1.3. Последовательность (а*) является универсальной относительно (о#/и<КЗ/(г,.....г^)).

Также доказывается следуюнцш результат.

Теорема 1.4. Пусть по крайней мере для двух j имеет место неравенство тj <п . Далее предположим, что имеют место следующие условия:

С1. д(и,// Tj) = О, С2. T^flinj/Tj). СЗ П^ = Л'.

j= 1 J=2 У=2

Тогда не существует /:у)(;;,,....и4)->Л, такое, что (/} - универсальная относительно {Cut (J 3/(г! ,...,гА)).

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

Основные функции системы являются следующие:

• преобразование светового потока в двумерную матрицу сигналов, подлежащую дальнейшей обработке;

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

• отслеживание объектов в режиме обратной связи;

• выдача полученных данных в удобном для человека виде.

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

а 5>

1 N

ЕРП—

V --

ТС — тактовый контроллер

НС - хост-компьютер,

Р — периферийные устройства,

О — шина данных,

А - адресная шина,

Я/Ж - шина сигнала чтения/записи.

А - фотоприемная матрица, 50,— стробирующие схемы, АС - генератор адресов, М1 — модули памяти, С — контроллеры, О — коммутаторная сеть, !] — процессоры,

Введем обозначения для массива данных, соответствующего фотоприемной матрице, и массива, соответствующего пространству памяти: А(М, М) = {{/, у): 0 < /, / < Л/}, Р(ЛГ, К) = {(/,_/): 0 <; < < у < Л^}.

Определим функцию р:А->А посредством соотношений:

Р(1,Л = (Р10,Л,Р20,Л) А(',7) = '

Рг('»У) = У©и*(то<ЗЛО, п*-п-[}Ип).

Введем функцшо е: А —> Р посредством соотношений:

с, = ¿V' + ] / Ы, Ы' = М / N г,(1,]) = ]// N.

Положим по определению р'(1,/) = ер "У'.УЛ Множество IV 0'°,у°) = {(/, /) е А: г'° < / < г° + п,<j< У° + «} будем называть квадратным окном размера п х п. Множество всех окон обозначим

\У = {щЛу0): 0 < ,у0 < Л/ - л}.

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

Теорема 2.1. Для любого iKeW функция р'21 W является инъектив-

ной.

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

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

В третьей главе исследуются вопросы, связанные с распараллеливанием метода частиц в ячейках (PIC-метода) на различных параллельных архитектурах. Рассматривается модельная задача — бесстолкновительная модель плазмы с частицами одного типа (электронами), электрическое поле описывается уравнением Пуассона.

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

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

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

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

и

фона, что полностью исключает субъективизм при обработке и повышает качество результатов;

2) полуавтоматическая энергетическая привязка загруженных данных энергетических спектров. Усовершенствования привязки заключаются в том, что программа производит учет нелинейности аппаратурных характеристик от энергии регистрируемых гамма-квантов, а также отслеживает температурный дрейф энергетической шкалы прибора от времени;

3) полуавтоматическая обработка временных спектров;

4) новые методы калибровок при расчете коэффициента нефтенасыщенно-сти: метод "Дельта С/О" и метод "Кросс-плот";

5) некоторые методы кластеризации каротажных данных.

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

Link Grammar Parser - это синтаксический анализатор английского языка, разработанный в 1990-е гг. в университете Корнеги-Мелона, базирующийся на некоторой теории. Отметим, что данная теория, вообще говоря, отличается от классической теории синтаксиса. Получив предложение, система приписывает к нему синтаксическую структуру, которая состоит из множества помеченных связей (коннекторов), соединяющих пары слов. В настоящее время имеются варианты системы Link Grammar Parser для ряда других языков, в том числе, для русского.

В диссертации рассматриваются логические методы отождествления предложений, конструкции языка REFAL. Методика определения тем текстов, обобщающая исследования индийских ученых (Нирадж Кумар и др.), в том числе вариант, использующий размытую логику Заде.

Вкратце остановимся на логических методах. Считаем, что L -множество слов некоторого естественного языка. Для любого слова xeL обозначим Norm{x) его нормализованную форму. Запись Syn{x,y) обозначает, что х, v — синонимы.

Возникают два вида эквивалентностей:

1) .г, ~х2 <-> jr, = л\ vijnfip-v,), т.е. слова являются синонимами;

2) л, = х2 <-> Xorm(x,) = Norm(x2), т.е. нормализованные формы слов совпадают.

Предложение рассматриваем, как вектор с компонентами из слов х =<х„...,хп >. Функция Norm может быть естественно распространена на предложения Xorm{x)=<Norm(xl\...,Norm(xn)>. Текст Т =<> есть последовательность предложений.

Пусть запись ,х|= Д.т,,*,) обозначает, что в схеме разбора предложения х =<х}....,хп > посредством анализатора Link Grammar Parser имеется коннектор типа Р, идущий от слова х, к слову xj. Знак |= означает, что фактически мы имеем дело с моделью. Основным множеством модели является множество пар (<1,х, >,...,<п,хп >}. Так как одно и то же слово может входить в предложение два и более раз, то это приводит к необходимости рассмотрения именно пар, а не отдельных слов. Ввиду сказанного выше, корректным является даже обозначение х\=<р, где /р — формула, например, исчисления предикатов первого порядка. Фактически х одновременно является обозначением и для вектора, и для модели.

Предположим, что даны два предложения х =<х^...,хп >, у =<у\,...,ут >■ Интерес представляют функции / такие, что

dom{f) с (1,..., n), range(f) с {1,..., т) с дополнительными свойствами типа: Л0 = у'-»*, ~ 3',, /(0 = J х, - У, и другие подобные.

При сопоставлении двух предложений, точнее, при анализе их на близость осуществляется проверка ряда логических свойств. Например, пусть /('i) = /г f02) = J2- Теперь приведены примеры такого рода свойств.

1. Инвариантность коннектора

х\= P(xh,xJ->y\= Р(У1ГУИ).

2. Замена коннектора на дизъюнкцию других

л|= л=у а О-Л.з-Л) ■

3. Расщепление коннектора на два коннектора

.х 1= P(x,t, Л-,г) -> Эк (у |= 0(yJt, Л ) a R{yt. yj;)).

4. Расщепление коннектора на два коннектора с инверсией

* 1= Р(-х,.> ) Эк {у |= 0(уи, ук) Л R{yk о )).

Принимая во внимание, что у является обозначением для соответствующей модели, формула из третьего пункта может быть переписана в виде х |= Р(хч,х,г) у |= ЭуО,(уи,у) л Я(у,уи). В аналогичном виде может быть записана формула из четвертого пункта.

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

+-----os----+

+-D3-+—3s-+ +—"j 4 u- -I I ! I !

the fox.n ate.v the rabbit.p

+---Js—+

+—B*u-+—Ss—+—Pv—+-KVD-+ +-DS-+

I I ! Ill I

the rabbit.p was.v eaten.v by the fox.n

x, = The xz = fox x¡ = ate x4 = the x¡ = rabbit

v, = the v, = radon уъ = vas у, - eaten у, = by ys = the j>, = fox

Результаты работы анализатора Link Grammar Parser и действие функции /

Таким образом, имеем /(1) = 6, /(2) = 7, /(3) = 4, /(4) = I, /(5) = 2. При этом отображении получаем:

1) Norm(ate) = Norm(ealen) ИЛИ, ЧТО ТО же самое ate = eaten ;

2) коннекторы Ds и D*u сохраняются, т.е. они инвариантны;

3) х 1= Ss(fox,ate) -> у |= MVpfeaten.by) л Js(by, fox), Т.е. имеет Место расщепление коннектора Ss с инверсией;

4) X |= Os(ate, rabbit) —> у |= Ss (rabbit, иш) a Pv(woî, fax), Т.е. аналогично имеет место расщепление с инверсией, но другого коннектора Os.

Резюмируя можно сказать, что в нашем распоряжении имеются правила вида R, : х |= <p¡ (.г,, ) у \= у/,. (у„у2).

Далее строится функция /, и проводится анализ, встречаются ли индексы ¡i> ;2> Л = /('Д J2 = f(h) такие, что на конкретных словах из предложений х,у

выполнено правило Д,, т.е. x\=<p,(xt■i,.*/l)->;H=V/tVj1 Для простоты можно говорить, что правило выполняется на паре < /,, /2 >.

Рассмотрим множество всех таких пар < /,, i2 >, на которых выполнено одно из правил. Обозначим это множество I, и пусть его мощность | /1 = п. Отметим, что анализатор Link Grammar Parser допускает между двумя словами наличие только одного коннектора.

Далее пусть и,, и2 — количество коннекторов, получающихся в результате анализа предложений х,у соответственно. В качестве меры похожести двух предложений можно ввести /jjx,y) = л/пи^и,,^) или //Д^у) = 2n!(ni + п2). В заключении перечислены основные результаты работы.

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

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

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

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

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

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

О ЛИЧНОМ ВКЛАДЕ АВТОРА

Исследуемые вопросы являются довольно трудоемкими, и в ряде случаев очень высока их степень неопределенности ввиду отсутствия формализованных постановок. В основном работа выполнялась совместно с учениками: сотрудниками института, аспирантами и студентами. Среди них: Батура Т.В., Лобив И.В., Перфильев A.A., Половинко О.Н., Проскуряков A.B., Семич Д.Ф., Шманина Т.В. и др. Наибольший вклад автором диссертации внесен в теоретические исследования и разработку алгоритмов. Разработка больших программных комплексов, в основном, выполнялась коллективно с учениками.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Монографии

1. Батура Т.В., Мурзин Ф.А., Перфильев A.A., Шманина Т.В. Методы повышения эффективности поиска информации на основе синтаксического анализа // Моногр. / Институт систем информатики им. А.П. Ершова СО РАН. - Новосибирск: Изд-во СО РАН, 2014. ISBN 978-5-7692-13984. - 76 с.

2. Батура Т.В., Белогубова М.В., Братцев С.Г., Копылова Н.С., Мурзин Ф.А. Мультиагентные модели социодинамических процессов // Моногр. / Институт систем информатики им. А.П. Ершова СО РАН. — Новосибирск: Изд-во СО РАН, 2014. ISBN 978-5-7692-1404-2. - 119 с.

3. Ануреев И.С., Батура Т.В., Боровикова О.И., Загорулько Ю.А., Коно-ненко И.С., Марчук А.Г., Марчук П.А., Мурзин Ф.А., Сидорова Е.А., Шилов Н.В. Модели и методы построения информационных систем, основанных на формальных, логических и лингвистических подходах // Моногр. / Институт систем информатики им. А.П. Ершова СО РАН. — Новосибирск: Изд-во СО РАН, 2009. ISBN 978-5-7692-1113-3. - 330 с.

4. Батура Т.В., Мурзин Ф.А. Машинно-ориентированные логические методы отображения семантики текста на естественном языке // Моногр. / Институт систем информатики им. А.П. Ершова СО РАН. — Новосибирск: Изд. НГТУ, 2008. ISBN 978-5-7782-1138-4. - 248 с.

5. Братцев С.Г., Мурзин Ф.А., Нартов Б.К. Пунтус A.A. Конфликт сложных систем. Модели и управление // Моногр. / Изд. Моск. авиац. ин-та. ISBN 5-7035-0554-2, 1995. - 118 с.

Публикации из списка ВАК, Scopus и Web of Science

1. Батура Т.В., Мурзин Ф.А., Семич Д.Ф. Облачные технологии: основные модели, приложения, концепции и тенденции развития // Программные продукты и системы. - Тверь, 2014. — №. 3. — С. 64-72.

2. Батура Т.В., Копылова Н.С., Мурзин Ф.А., Проскуряков A.B. Методы анализа данных из социальных сетей // Вестник ЛГУ. Серия: Информационные технологии. - Новосибисрк, 2013. - Том 11, Вып. 3. — С. 5-21.

3. Копылова Н.С., Мурзин Ф.А., И.А. Курков И.А. Моделирование социальных процессов и мультиагентный подход // Программные продукты и системы. 2013. № 3. С. 120-126.

4. Перфильев A.A., Мурзин Ф.А., Шманина Т.В. Методы синтаксического анализа и сопоставления конструкций естественного языка, ориентированные на применение в информационно-поисковых системах // Вестник НГУ. Серия: Информационные технологии. Том 9, Вып. 4, 2011. - С 50-59.

5. Мурзин Ф.А., Поплевина Н.В., Семич Д.Ф. Алгоритмы и программное обеспечение для определения нефтенасыщенных пластов на основе данных радиоактивного каротажа // Автометрия. - Том 47, № 4, 2011, -С. 91-103.

6. Murzin, F.A., Poplevina, N.V., Semich, D.F. Algorithms and software for detecting oil reservoirs from nuclear logging data // Optoelectronics, Instrumentation and Data Processing. — 2011 — Vol. 47, — Iss. 4. — P. 395-405. (Scopus, перевод на англ. 5-й работы)

7. Мурзин Ф.А., Поплевина Н.В., Семич Д.Ф. Методы выделения нефтенасыщенных пластов на основе данных радиоактивного каротажа // Вестник НГУ. Серия: Информационные технологии. - Новосибисрк, 2009. -Том 7, Вып. 2. - С. 88-103..

8. Андреева Т.А., Ануреев И.С., Бодин Е.В., Городняя JI.B., Марчук А.Г., Мурзин Ф.А., Шилов Н.В. Образовательное значение классификации компьютерных языков // Прикладная информатика. - 2009. №6 - С. 1828.

9. Винокуров A.A., Ильин И.В., Мурзин Ф.А., Семич Д.Ф. Расчет коэффициента нефтенасыщенности по данным, полученным аппаратурой ИНГК-С-ЗСК «ТюменьПромГеофизика» // Каротажник. - 2004. № 12-13 (125-126).-С. 41-46.

lO.Murzin F.A., Sluev V.A. A Memoiy Organization for Parallel Computers // New Generation Computing J. Vol. 6, № 1, 1988. - P. 3 - 18. (Scopus, Web of Science)

1 l.Murzin F.A. Syntactic properties of the REFAL language // Int. J. Computer Math. - 1985. - №17. - P. 123 - 139. (Scopus, Web of Science)

12.Murzin F.A., Murzina T.S., Shlishevsky V.B. New Grills for Girard Spectrometers // Applied Optics, vol.24, no.21, - 1985, - P.3625 - 3630. (Scopus, Web of Science)

13.Валиуллин A.H., Ганжа В.Г., Ильин В.П., Мурзин Ф.А., Шапеев В.П., Яненко Н.Н. Задача автоматического построения и исследования на ЭВМ разностных схем в аналитическом виде // Доклады Академии Наук СССР, Т. 275, №3, - 1984. - С. 528.

14.Ганжа В.Г., Мелешко С.В., Мурзин Ф.А., Шапеев В.П., Яненко Н.Н. Реализация на ЭВМ алгоритма исследования на совместность систем дифференциальных уравнений в частных производных // Доклады Академии Наук СССР, Т. 261, №5, - 1981. - С. 1044-1046.

15.Batura Т., Murzin F. Logical Methods for Representing Meaning of Natural Language Texts // Proc. 4th Intern. Conf. on Computational Science (ICCS 2004), Krak6w, Poland, June 6-9, 2004. Part III, LNCS 3038. P. 545-551. (Web of Science)

16.Sizikov V.P., Murzin F.A., Razumov V.I. On the Qualitative Models // Proc. of Conf. on Artificial Intelligence, Research Announcements. — Helsinki, Finland, 1997. - P.294-297. (Web of Science)

Избранные прочие публикации

17.Мурзин Ф.А., Слуев В.А. Организация памяти параллельных компьютеров, ориентированных на вычислительные методы механики и методы обработки изображений // Школа-семинар соц. стран "Вычислительная аэрогидромеханика". - Москва - Самарканд, 1985. - С. 313-316.

18.Мурзин Ф.А., Слуев В.А. Некоторые методы организации памяти параллельных компьютеров // Препринт ИТ11М СО АН №19-85, Новосибирск. — 19 с.

19.Мурзин Ф.А. Высокопроизводительные ЭВМ // Препринт ИТПМ СО АН №13-86, Новосибирск. - 52 с.

20.Мурзин Ф.А. Инструментальные средства пакетов прикладных программ // Препринт ИТТТМ СО АН №14-86, Новосибирск. - 47 с.

21.Братцев С.Г., Мурзин Ф.А., Нартов Б.К. Исследования по обработке динамических изображений // Тезисы Междунар. конф. по обработке изображений и дистанционным исследованиям. — Новосибирск, 1990, — С. 41 -43.

22.Bratsev S.G., Murzin F.A., Nartov В.К. The Optimum Search of Targets and the Processing of Dynamical Images // Visual Analysis and Interface, Novosibirsk, 1991.-P. 17.

23.Bratsev S.G., Murzin F.A., Nartov B.K. A Parallel Automatic System for Image Processing // Computer Algebra and its Application in Mechanics, 1992. Nova Science Publishers, Inc. - P. 129-133.

24.Bratsev S.G., Murzin F.A., Nartov B.K. Optimum targets search and dynamic image processing // Modelling & Analysis, Vol. 26, № 4,1993. - P. 1-11.

25.Voyevodin A.F., Murzin F.A., Ponomarev M.Yu. The Parallel Algorithm of Computing the Hydraulic Systems with Elastic Pipes // Proc. Intern. Conf. on the Methods of Aerophysical Research, ICMAR'96. - Novosibirsk, 1996. -Vol.1. -P.228-233.

26.Лобив И.В., Мурзин, Ф. А. О распараллеливании PIC - метода // Проблемы систем информатики и программирования. — Новосибирск, 1999. - С. 146-155.

27.Вшивков В.А., Лобив И.В., Мурзин Ф.А. Параллельный алгоритм решения задачи о взаимодействии потоков разреженной плазмы // Поддержка супервычисленнй и Интернет-ориентированные технологии, ИСИ СО РАН, 2001,-С. 68-81.

28.Дунаев А.А., Лобив И.В., Мехонцев Д.Ю., Мурзин Ф.А., Половинко О.Н., Семич Д.Ф., Чепель А.В., Ярков К.А. Алгоритмы быстрого поиска фрагментов фотографических изображений // Современные проблемы конструирования программ. — Новосибирск, 2002. — С. 88 — 109.

29.Винокуров А.А., Ильин И.В., Лобив И.В., Мурзин Ф.А., Половинко О.Н., Семич Д.Ф. Программное обеспечение для поддержки процесса ядерного каротажа нефтяных скважин // Пятая междунар. конф. памяти акад. А.П. Ершова, "Перспективы систем информатики", Рабочий семинар "Наукоемкое программное обеспечение", Новосибирск 2003, -С. 40-42.

30.Dunaev A.A., Lobiv I.V., Mekhontsev D.Yu., Polovinko O.N., Semich D.F., Yarkov K.A. Algorithms of fast search of rotated and scaled patterns inside the given image // Пятая междунар. конф. памяти акад. А.П. Ершова, "Перспективы систем информатики", Рабочий семинар "Наукоемкое программное обеспечение", Новосибирск 2003, -С. 50-52.

31.Батура Т.В., Мурзин Ф.А. Логические методы представления смысла текста на естественном языке // "Новые информационные технологии в науке и образовании", ИСИ СО РАН, Новосибирск 2003, -С. 59-111.

32.Винокуров A.A., Ильин И.В., Лобив И.В., Мурзин Ф.А., Половинко О.Н., Семич Д.Ф. О некоторых задачах, связанных с автоматизацией процесса ядерного каротажа нефтяных скважин // "Новые информационные технологии в науке и образовании", ИСИ СО РАН, Новосибирск 2003,-С. 112-123.

33.Винокуров A.A., Ильин И.В., Мурзин Ф.А., Семич Д.Ф. Опыт применения аппаратуры ИНГК-С (С/О-каротажа) в ЗАО ПГО «Тюменьпромгео-физика», оптимизация режимов измерения // Материалы междунар. конф. " Портативные генераторы нейтронов и технологии на их основе ", Москва 2004, - С. 25.

34.Винокуров A.A., Ильин И.В., Мурзин Ф.А., Семич Д.Ф. Расчет коэффициента нефтенасыщенности по результатам ядерного каротажа // Методы и инструменты конструирования и оптимизации программ, Новосибирск, ИСИ СО РАН, 2005; С. 28 - 54.

35.Батура Т.В., Мурзин Ф.А. Обработка поисковых запросов на естественном языке с помощью REFAL-подобных конструкций. // Проблемы интеллектуализации и качества систем информатики, Новосибирск, ИСИ СО РАН, 2006; С. 24-33.

36.Батура Т.В., Мурзин Ф.А. Машинно-ориентированные методы анализа текста на естественном языке // Шестая междунар. конф. памяти акад. А.П. Ершова, "Перспективы систем информатики", Рабочий семинар "Наукоемкое программное обеспечение", Новосибирск 2006. — С. 33—34.

37.Винокуров A.A., Ильин И.В., Лобив И.В., Мурзин Ф.А., Семич Д.Ф. Алгоритмы и программные системы для интерпретации данных радиоактивного каротажа нефтянных скважин // Шестая междунар. конф. памяти акад. А.П. Ершова, "Перспективы систем информатики", Рабочий

семинар "Наукоемкое программное обеспечение", Новосибирск 2006. — С. 45—41.

38.Batura Tatyana, Murzin Feodor Logical Analysis of Texts in a Natural Language and a Sense Representation // Bull, of NCC. Ser.: Comput. Sci. - Iss. 26.-2007.-P. 141-158.

39.Мурзин Ф.А., Поплевина H.B., Семич Д.Ф. Обработка данных радиоактивного каротажа и выделение нефтенасьнценных пластов на основе кластеризации // Междунар. научно-практическая конф. "Казахстан на этапе социально-политического и экономического развития в условиях глобализации", том 1, г. Тараз, Унивеситет "Аулие-Ата", Респ. Казахстан, 2008. - С. 268-271.

40.Бах Т.А., Калинников П.А., Мурзин Ф.А. О распараллеливании некоторых алгоритмов обработки изображений с ориентацией на многоядерный процессор CELL // V Российско-германская школа по параллельным вычислениям на высокопроизводительных вычислительных системах. Семинар "Распределенные и высокопроизводительные вычисления". Новосибирск, 2008. - С. 4-7.

41.Валиулин Р.Г., Мурзин Ф.А. Параллельный вариант Р1С-метода, ориентированный на вычислительные системы с топологией гиперкуба // V Российско-германская школа по параллельным вычислениям на высокопроизводительных вычислительных системах. Семинар "Распределенные и высокопроизводительные вычисления". Новосибирск, 2008. — С. 9-11.

42.Kalinnikov Р.А., Murzin F.A., Pletneva Т.А. Some algorithms of image processing and their reflection onto multiprocessor systems // Bull, of NCC. Ser.: Comput. Sci. - 2008. - Iss. 28. - P. 67-78.

43.Мурзин Ф.А., Поплевина H.B., Семич Д.Ф. Алгоритмы определения нефтенасьнценных пластов на основе данных радиоактивного каротажа // Седьмая междунар. конф. памяти акад. А.П. Ершова, "Перспективы систем информатики", Рабочий семинар "Наукоемкое программное обеспечение", Новосибирск 2009. - С. 199-206.

44.Перфильев А.А., Мурзин Ф.А. Поисковая система с элементами лингвистического анализа // Седьмая междунар. конф. памяти акад. А.П. Ершова, "Перспективы систем информатики", Рабочий семинар

"Наукоемкое программное обеспечение", Новосибирск 2009. — С. 221— 227.

45.Zverev N.B., Murzin F.A., Poletaev S.A. On the realization of algorithm of claster analysis on GPU by means of CUDA technology. // Bull, of NCC. Ser.: Comput. Sci. -2009. -Iss. 29. - P. 139-150.

46.Batura Tatiana, Murzin Feodor, Proskuryakov Alexey, Trelevich Jennifer Models and Algorithms for the Detection of Spam and Senders of Spam // Bull, of NCC. Ser.: Comput. Sci. -2010. - Iss. 30. - P. 29^3.

47.Perffliev A.A., Murzin F.A., Shmanina T.V. Methods of syntactic analysis and comparison of constructions of a natural language oriented onto using in search systems // Bull, of NCC. Ser.: Comput. Sci. - 2010. - Iss. 30. - P. 91109.

48.Alina Glodowski, Feodor Murzin, Tatiana Murzina Memory Organization with Parallel Access to Information and Its Application for Image Processing // Bull, of NCC. Ser.: Comput. Sci. -2011. - Iss. 32. - P. 77-92.

49.Литвиненко Г.Г., Мурзин Ф.А., Немченко М.Ю., Поплевина Н.В., Семич Д.Ф. Определение нефтенасыщенных пластов на основе данных радиоактивного каротажа методом "Кросс-плот" и посредством кластеризации. Доклады HAH РК, №6, 2011. — С. 5-16.

50.Кальменов Т.Ш., Мурзин Ф.А., Поплевина Н.В. Анализ данных радиоактивного каротажа на основе метода И.Б. Мучника. Доклады HAH РК, №6, 2011. - С. 17-23.

51.Перфильев А.А., Мурзин Ф.А., Шмашша Т.В. Методы синтаксического анализа и сопоставления конструкций естественного языка и их использование в поисковых системах // Восьмая междунар. конф. памяти акад. А.П. Ершова, "Перспективы систем информатики", Рабочий семинар "Наукоемкое программное обеспечение", Новосибирск 2011. — С. 200207.

52.Глодовски А.В., Калинников П.А., Мурзин Ф.А., Мурзина Т.С., Плетнева Т.А. О распараллеливании некоторых алгоритмов обработки изображений с ориентацией на процессор CELL // Материалы Росс. Научно-техн. Конф. «Информатика и проблемы телекоммуникаций». — Новосибирск, 2011. — С. 28-31.

53.Batura T.V., Kopylova N.S., Murzin F.A., Proskuiyakov A.V. Methods for analysis of data from social networks // Bull, of NCC. Ser.: Comput. Sci. -2013.-Iss. 34.-P. 1-22.

54.Батура T.B., Мурзин Ф.А., Семич Д.Ф. Облачные технологии: основные понятия, задачи и тенденции развития // Программные продукты, системы и алгоритмы. - Вып. 1 от 07.03.2014. http://swsys-web.ru/cloud-computing-basic-concepts-problems.html

55.Batura T.V., Murzin F.A., Bakiyeva A.M., Yerimbetova A.S. The methods of estimation of the degree of similarity of sentences in a natural language based on the link grammar // Bull, of NCC. Ser.: Comput. Sci. - 2014. - Iss. 37. -P. 55-70.

56.Батура T.B., Мурзин Ф.А., Еримбетова A.C., Бакиева A.M. Методы определения степени близости предложений на естественном языке на основе грамматики связей // Наука и мир, 2015. — Т.2. — № 3(19). — С. 61-

Мурзин Ф.А.

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

Автореферат

Подписано в печать Объем 1,5 уч.-изд. л.

Формат бумаги 60 х 90 1/16_Тираж 100 экз.

Отпечатано в ЗАО РИЦ «Прайс-курьер» 630128, г. Новосибирск, ул. Кутателадзе, 4г, 310 к., Тел. (383)330-72-02

Заказ №135