Организация и анализ многомерных и неоднородных данных в задачах обработки изображений, вычислительной математике, геофизике и лингвистике тема диссертации и автореферата по ВАК РФ 05.13.17, доктор наук Мурзин Федор Александрович

• Мурзин Федор Александрович
• доктор наук
• 2015

Оглавление диссертации доктор наук Мурзин Федор Александрович

ВВЕДЕНИЕ

ГЛАВА 1. ОРГАНИЗАЦИЯ ПАМЯТИ С ПАРАЛЛЕЛЬНЫМ ДОСТУПОМ

§ 1.1. Принципы организации памяти с параллельным доступом

§ 1.2. Некоторые перестановки и их свойства

§ 1.3. Адресация данных

§ 1.4. Параллельный доступ к сегментам многомерных массивов

§ 1.5. Выводы

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

§ 2.1. Основные цели и принципы построения системы

§ 2.2. Некоторые отображения и их свойства

§ 2.3. Адресация данных и стробирование

§ 2.4. Взаимодействие процессоров с памятью

§ 2.5 Процессорные элементы

§ 2.6. Отслеживание протяженных объектов

§ 2.7. Выводы

ГЛАВА 3. РАСПАРАЛЛЕЛИВАНИЕ PIC-МЕТОДА

§.3.1. Бесстолкновительная модель частиц в ячейках

§.3.2. Отображение алгоритма на систему с коммутатором

§ 3.3. Отображение PIC-метода на гиперкуб

§ 3.4. Отображение PIC-метода, на гибридную вычислительную систему

§ 3.5. Распараллеливание задачи о взаимодействии потоков плазмы

§ 3.6. Выводы

ГЛАВА 4. ОБРАБОТКА ДАННЫХ РАДИОАКТИВНОГО КАРОТАЖА

§ 4.1. Анализ энергетических спектров

§ 4.2. Обработка временных спектров и вычисление чистых спектров

§ 4.3. Алгоритмы для расчёта нефтенасыщенности методом "Кросс-плот"

§ 4.4. Расчёт по методу Дельта C/O

§ 4.5. Кластеризация

§ 4.6. Выводы

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

§ 5.1. Основные задачи

§ 5.2. Программная система Link Grammar Parser

§5.3. Алгоритмы отождествления предложений

§ 5.4. Конструкции языка REFAL и его применение

§ 5.5. Определение тем текстов

§ 5.6. Результаты тестирования поисковой системы

§ 5.7. Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Организация и анализ многомерных и неоднородных данных в задачах обработки изображений, вычислительной математике, геофизике и лингвистике»

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результаты работы докладывались на следующих конференциях и семинарах: Совещание по системам аналит. вычислений на ЭВМ, Дубна, 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.

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

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

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

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

A(n1,...,nk) = {i1,...,ik):лk=1 (0 < ij < nj)} назовем массивом. В действительности, в программировании под массивом размерности n х ...х nпонимается отображение вида A : A(n1 ,...,nk) ^ W.

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

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

Пусть A^...As - последовательность массивов размерностей kx,...ks соответственно, Gv...,GS - семейства сегментов в Alt... As. Отображения fx,... f удовлетворяют условиям

1) domf = A.,

2) rangef с P,

3) i Ф j ^ rangef n range f = 0.

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

Определение. Последовательность (fi,--- fs) называется универсальной относительно {G\,•••, G) в том и только в том случае,

когда V i V S е Gi V s е S(s0 ф s ^ prifi(s0) ф prifiOJX где pri - проекция пары на первую координату.

Пусть A = A(ni,-,nk) - массив, k > 2. Определим сегменты:

Pj (t) = prj ~\t) n A = {< ii,....,ik > е A: i. = t},

к

BL[Ti,....,Tk](if,....,i°°) = {<ii,....,ik >е A: л (i0 <i. <i0 + t.).

j=i

Рассматриваем следующие семейства сегментов: Cut j. = р (t): 0 < t < nj }

Cut = у Cut j,

j

3/fo,...,Tk)=]BL[ri,...,Tk](ii0,...,ik): Л0<ij <п. -т.

j=i

Я3/(Ti,...,Tk)={BLTi,...Tk](ii0,...,ik):е3/fa,..,): ii0 //Ti = 0}

тт 1 Л * * *

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

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

Теорема 1.2. Последовательность (р *) является универсальной относительно (Си^ у тк ^.

Теорема 1.3. Последовательность (а *) является универсальной относительно (СиУ^/(^.

Также доказывается следующий результат.

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

к к k С1. Л Щ // Tj ) = 0, С2. т1 =П(щ / Tj ). С3 Пn = N-

j=1 j=2 J=2

Тогда не существует f : АЩ,..., щ P,, такое, что (/) - универсальная относительно (CutУ3/(г1,...,тк).

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

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

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

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

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

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

широкое использование параллелизма на всех этапах: восприятия,

А - фотоприемная матрица, 50, 51 - стробирующие

ТС - тактовый контроллер НС - хост-компьютер, Р - периферийные устройства, Б - шина данных,

схемы,

АО - генератор адресов, М1 - модули памяти,

С - контроллеры, О - коммутаторная сеть, Рг - процессоры,

А - адресная шина, Я / Ж - шина чтения/записи.

шина сигнала

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

А(М,М) = {(г,/): 0 < г,/ < М}, Р(N К) = {{г, у: 0 < г < К,0 < / < N}.

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

у) = (Pl(г', у ^(Л У)) Р<Л у) =г

р (г, У) = / ® п *(тоёМ), п* = п • (г // п).

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

в(г,/) = (В1(г,У),В 2 В (\,/) = + //N, N' = М/N в 2 (г,/) = ///М.

Положим по определению р * (г,/) = вр~х(1,/). Множество Ж (г0, /0) = {{г, / е А: г0 < г < г0 + п, /0 < / < /0 + п} будем называть

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

= {Ж(г0,/0): 0 < г0,/0 < М - п}.

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

Теорема 2.1. Для любого W е W функция р* | W является инъективной.

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

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

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

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

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

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

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

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

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

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

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

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

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

семантико-синтаксические отношения между словами предложения, получаемые на выходе программной системы Link Grammar Parser.

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

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

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

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

1) x1 « x2 ^ x1 = x2 vSyn(x1,x2), т.е. слова являются синонимами;

2) x1 = x2 ^ Norm(xY) = Norm(x2), т.е. нормализованные формы слов совпадают.

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

Пусть запись x |= P(xt, x]) обозначает, что в схеме разбора предложения

x =<xj,...,xn > посредством анализатора Link Grammar Parser имеется

коннектор типа Р, идущий от слова хг к слову х. . Знак |= означает, что

фактически мы имеем дело с моделью. Основным множеством модели является множество пар {< 1,х >,...,<п,хп >}. Так как одно и то же слово может входить в предложение два и более раз, то это приводит к необходимости рассмотрения именно пар, а не отдельных слов. Ввиду сказанного выше, корректным является даже обозначение х |=р, где р -формула, например, исчисления предикатов первого порядка. Фактически х одновременно является обозначением и для вектора, и для модели.

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

ёот(/)^{1,.,п}, га^в(/)^{1,.,т} с дополнительными свойствами типа: / (г) = у ^ Хг « у у, /(г) = / ^ Хг = у у и другие подобные.

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

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

Х |= Р(х4, х^ ) ^ у |= Р(уА, уу1) .

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

х |= Р(х,, х^ ) ^ у |= V & (ул, ул ) .

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

х |= Р(х4 , х^ ) ^зк (у |= £(уА, у^ ) а Я(у^, уУ2)).

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

х |= Р(х4 , х^ ) ^зк (у |= £(уя, ук ) а Я(ук, у/. )).

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

может быть записана формула из четвертого пункта.

Ниже показан пример анализа двух предложений, одно из которых является перефразированным вариантом другого, т.е. показаны результаты работы анализатора Link Grammar Parser и действие функции f.

+-----05----+

+-DS-+—Ss-+ +—D*u-+

I I I I I

the fox.n ate.v the rabbit.p

+---Js—+

+—D*u-+—Ss— +—Pv—+-MVp-+ +-DS-+

I I I I I I I

the rabbit.p was.v eaten.v by the fox.n Xj = the x2 = fox x3 = ate x4 = the x5 = rabbit

= the y2 = rabbit y3 = was yA = eaten y5 = by y6 = the y7 = fox

Таким образом, имеем f (1) = 6, f (2) = 7, f (3) = 4, f (4) = 1, f (5) = 2.

При этом отображении получаем:

1) Norm(ate) = Norm(eaten) или, что то же самое ate = eaten ;

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

3) x |= Ss(fox,ate) ^ y |= MVp(eaten,by) л Js(by, fox), т.е. имеет место расщепление коннектора Ss с инверсией;

4) X |= Os(ate,rabbit) ^ y |= Ss(rabbit, was) лPv(was, fox), т.е. аналогично имеет место расщепление с инверсией, но другого коннектора Os .

Резюмируя можно сказать, что в нашем распоряжении имеются правила вида R, :x |= <р,(x1,x2) ^ y |= щг(y^y2).

Далее строится функция f, и проводится анализ, встречаются ли индексы ix, i2, j = f (ij), j = f (i2) такие, что на конкретных словах из предложений x,y выполнено правило R, т.е. x |= (x4,xh) ^ y |= (уЛ,ул).

Для простоты можно говорить, что правило выполняется на паре < ^, /2 >.

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

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

В заключении перечислены основные результаты работы.

ГЛАВА 1. ОРГАНИЗАЦИЯ ПАМЯТИ С ПАРАЛЛЕЛЬНЫМ ДОСТУПОМ

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

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

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

Из отечественных авторов наиболее близкие по содержанию исследования проводили А.И. Панарин [1] и Б.Я. Штейнберг [2]. Некоторые вопросы рассматривали также В.П. Гергель [3] , В.В. Воеводин и Вл.В. Воеводин [4]. Результаты автора, описанные в данной главе, представляют собой обобщения на многомерный случай результатов Д. Ван Воорхиса и Т. Моррина. [5-9].

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

(рафинированный) вид, что облегчает их решение. Кроме того, этот случай является основным при создании компьютеров, ориентированных на численные методы и обработку изображений. Можно указать еще некоторые менее очевидные сферы применения такого рода памяти. Это компьютеры, ориентированные на базы данных [10-13], в которых аппаратно поддерживается реляционный подход, и робототехнические системы.

§ 1.1. Принципы организации памяти с параллельным доступом

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

Л(щ,...щк) = {1х,...,1к):Ак= (0 < г] < п])}.

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

ЛЛ : Л(п1,...,пк) ^ Ж,

где Ж - множество чисел определенного вида (целых, вещественных, комплексных,...) или множество слов в некотором алфавите. Вместо Л(п15...,пк) часто будем писать Л, опуская круглые скобки вместе с их содержимым. Произвольное множество 5 с Л будем называть сегментом.

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

Пусть Л15...Л5 - последовательность массивов размерностей к1,^к8

соответственно, G1,.,Gs - семейства сегментов вД,...As. Отображения f,. fs удовлетворяют условиям:

1) domf = Ai,

2) range f с P,

3) i ф j ^ rangef n rangef . =0.

Здесь dom - область определения, range - область значений функций. Таким образом последовательность (fi,...fs) задает распределение массивов AA 6 памяти. Примем еще естественное предположение, что f инъективны, то есть для любых a, b е f если a ф b , то f (a) ф f (b).

Определение. Последовательность (f1,. fs) называется универсальной относительно {G\,.,G) в том и только в том случае, когда

V i V S е Gi V s0, si е S(s0 ф si ^ prif (s0) ф (si)), где pri - проекция пары на первую координату.

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

(0 < i < K,0 < j < N) в естественном порядке, т.е. в модуле j по адресу i находится элемент aj. В этом случае за один такт можно извлечь строку

i = Const. Для этого нужно сразу во все модули заслать один и тот же адрес а = i. Извлечение столбца j = Const затруднительно. Оно требует время пропорциональное числу K. Аналогичная проблема возникает если в памяти разместить трехмерный массив, используя какой-нибудь стандартный метод и пытаться осуществить доступ к двумерным сечениям или трехмерным под-массивам небольшого объема.

Универсальность (fi,...fs) относительно (Gi,.,Gs) обозначает, что

любой сегмент 5 е О (1 < I < £) хорошо распределен в памяти. В том смысле, что любые его элементы хранятся а различных модулях памяти. Именно это обстоятельство позволяет извлечь (или записать) сегмент 5 целиком, параллельно в один прием. При этом в модули {рг1 fi (£): £ е 5}

записываются адреса {рг2(£) : £ е 5}.

Естественно, что универсальная последовательность относительно {0\ О) может не существовать. В этом случае находятся семейства

О\ (1 < ^ < т), такие, что с О-, и = О- и относительно каждого кортежа

G1Í, ..., О^ универсальная последовательность существует.

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

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

Здесь М. - модули памяти, /. - логические устройства. По горизонтальным шинам поступают пары {fi (£): £ е 5}. При этом, если мы хотим получить элементы сегмента 5 в фиксированном порядке £Т, то по первой шине передается ^(£1), по второй ^ (£2) и т.д. Шины содержат в себе также линии чтения/записи.

Пусть (£) = (у{ ,аг). Логическое устройство /т подключает линию передачи адреса и линию чтения/записи данных в том случае, когда т = у(. То есть в том случае, когда уг совпадает с номером модуля, к

Список литературы диссертационного исследования доктор наук Мурзин Федор Александрович, 2015 год

СПИСОК ЛИТЕРАТУРЫ

1. Панарин А.И. Структуры данных высокопроизводительных ЭВМ и многомерные матрицы // Научный совет по комплексной проблеме «Кибернетика». - 1984, 66 с..

2. Штейнберг Б.Я. Оптимизация размещения данных в параллельной памяти. - Ростов н/Д., Изд-во ЮФУ, 2010. - 256 с.

3. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. - Н.Новгород, ННГУ, 2001.

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

5. Van Voorhis D.C., Morrin T.H. Memory Systems for Image Processing // IEEE Trans. on Computers, - 1978. - Vol. C-27. - No.2. - p.113-125.

6. Van Voorhis D.C., Morrin T.H. Memory Systems for Image Processing // Working Paper 15/3 45 / IBM System Communication Division. - Los Catos, CA, August 1975.

7. Van Voorhis D.C., Morrin T.H. United States Patent N3, 995, 253, November 30, 1976.

8. Van Voorhis D.C., Morrin T.H. United States Patent N3, 996, 559, December 7, 1976.

9. Van Voorhis D.C., Morrin T.H. United States Patent N3, 938, 102, February 10, 1976.

10.0зкарахан Э. Машины баз данных и управление базами данных. - М.: Мир, 1989.

11.Kitsuregawa M., Tanaka H., Moto-oka T. Application of Hash to Data Base Machine and Its Architecture // New Generation Computing J. - 1983. -Vol.1. - N1. - P.63-74.

12.Kitsuregawa M., Tanaka H., Moto-oka T. GRACE: Relational Algebra Machine Based on Hash and Sort - Its Design Concepts // J. of Information Processing. - 1983. - Vol.6. - N3. - P.148-155.

13.Kitsuregawa M. et al. Relational Algebra Machine Based on Hash and Sort // IECEJ Technical Group Meeting EC81-35. - 1981. (in Japanese).

14.Yalamanchili S., Martin W.N., Aggarwal J.K. Extractin of Moving Objects Descriptions via Differencing // Computer Graphics and Image Processing -1982. - N 18. - P. 188-201.

15.Aggarwal J.K, Martin W.N. Analysis Dynamic Scenes Containing Multiple

Moving Objects // Tech Rep. 125 / Dep. of Computer Sciences. The Univ. of Texas at Austin, 1980.- P.1-44.

16.Fu K.S., Fan T.I. Tree Translation and Its Application to a Time-Varying Image Analysis Problem // IEEE Trans. on Systems, Man and Cybernetics. -1982. - Vol. SMC - 12. - N6.- P. 856-867.

17.Shi Q.Y., Fu K.S. Parsing and Translation of (Attributed) Expansive Graph Languages for Scene Analysis // IEEE Trans. on Pattern Analysis and Machine Intelligence. - 1983. - Vol.PAMI - 5. - N5.- P.472-485.

18.Nagel H.H. Analysis Techniques for Image Sequences // Proc. of tbe 4th IJCPR. - Kyoto, Japan, 1978. - P.186-211.

19.Danielsson Per-Erik, Levialdi Sfefano. Computer Architectures for Pictorial Information Systems // Computer. - 1981. - N11. - P.53-67.

20.Системы технического зрения / Писаревский А.Н. и др. - М.: Машиностроение, 1988.

21.Vorozhtsov E.V., Yanenko N.N. Methods for the Localization of Singularities in Numerical Solutions of Gas Dynamics Problems. - Berlin, Heidelberg: Springer Verlag, 1990.

22.Прэтт У. Цифровая обработка изображений. - М: Мир, 1982. Т. 1 - 2.

23.Обработка изображений // Под ред. Хуанга. - М.: Мир, 1979.

24.Грицык В.В., Распараллеливание алгоритмов обработки информации в системах реального времени. - Киев: Наумова думка, 1981.!

25.Intelligent and Optimal Normalized Correlation for High- Speed Pattern Matching, Datacube, Inc., February 2000

26.H. Z. Sun, T. Feng and T. N. Tan, "Robust extraction of moving objects from video sequences", Proc. of the Fourth Asian Conference on Computer Vision, Vol.2, Jan. 2000, pp. 961-963.

27.Харлоу Ф.Х. Численный метод частиц в ячейках для задач гидродинамики // Вычислительные методы в гидродинамике. - Изд. Мир, 1967.

28. Бабенко К.И. Теоретические основы и конструирование численных алгоритмов задач математической физики. - Изд. Наука, 1979. - С.235-253.

29. Анучина Н.Н., Петренко В.Е., Шокин Ю.И., Яненко Н.Н. О методах расчета задач газовой динамики с большими деформациями. // Численные методы механики сплошной среды (Информ. бюллетень). -1970, 1, 1. - С. 40-63.

30.Белоцерковский О.М., Давыдов Ю.М., Исследование схем метода

"крупных частиц" с помощью дифференциальных приближений, в кн.: Проблемы прикладной математики и механики, М., 1971, с. 145-55.

31.Хокни Р., Иствуд Дж. Численное моделирование методом частиц. - М.: Мир, 1987. - 638 с.

32.Поттер Д. Вычислительные методы в физике. - М.: Мир, 1975. - 392 с.

33.Малышкин В.Э., Вшивков В.А., Краева М.А. О реализации метода частиц на мультипроцессорах.-- Новосибирск, 1995. - 37 с. - (Препр. / СО РАН. ВЦ; N 1052).

34. Omer Egecioglu. A Recursive Doubling Algorithm for Solution of tridiagonal Systems on Hypercube Multiprocessors. - Department of Computer Science University of California Santa Barbara, 1989. - 15 с.

35.Sanjay Ranka, Sartaj Sahni. Hypercube algorithm for image transformation. University of Minnesota - 15 c.

36. Antonio González, Miguel Valero-García and Luis Díaz de Cerio. Executing Algorithms with Hypercube Topology on Torus Multicomputers. Universitat Politécnica de Catalunya Departament d'Arquitectura de Computadors - 28 c.

37.Вшивков В.А. , Снытников А.В. Особенности проведения экзафлопс-расчетов в физике плазмы // Вычислительные методы и программирование. - 2012. - Т. 13, № 1. - С. 44-48.

38.Боресков А., Харламов А., Марковский Н. Параллельные вычисления на GPU. Архитектура и программная модель CUDA. - М.:Издательство МГУ, 2012.

39. Электронный ресурс CUDA Programming guide http://docs.nvidia.com/cuda/cuda-c-programming-guide

40. Радиоактивные методы разведки / Новиков Г.Ф., Копков Ю.Н. - М.: «Недра», 1965. - 755 с.

41. Геофизические методы контроля разработки нефтяных пластов / Хуснуллин М.Х. - М.: «Недра», 1989. - 188 с.

42. Радиоактивные и другие неэлектрические методы исследования скважин / Резванов Р.А. - М.: «Недра», 1982. - 367 с.

43.Ядерная геофизика при исследовании нефтяных месторождений / Алексеев Ф.А., Головацкая И.В., Гулин Ю.А. - М.: «Недра», 1978. -359 с.

44.Фертл В.Х. Спектрометрия естественного гамма-излучения в скважине // Нефть, газ и нефтехимия за рубежом., №3, 1986. - С. 11 - 12.

45.Kozhevnikov D.A., Shagin V.L. A method of treating the spectral response

of a tool in open and cased boreholes to determine the natural radioactivity of rocks, Nucl. Geophys. -1989.Vol.3, - N. 1, - P.17—29.

46.Xu Jinwu, Zhang Zongjian. Improved Carbon/Oxigen Log Interpretation Techniques under Variable Formation Water Salinity, Shengli Well Logging Co., December 1999, 12p.

47.Новый прибор малого диаметра с высокими характеристиками для мониторинга продуктивных пластов / Джекобсон Л.А., Этридж Р., Симпсон Дж. - Hulliburton Energy Services, 1994. - 14 с.

48.Винокуров А.А., Серебрянский В.В., Ильин И.В., Фисенко А.Н., Пенязь К.Г. Применение новых технологий в аппаратуре спектрометрического каротажа // Научно технический журнал "Технологии ТЭК" №2(15), Апрель 2004 г. Москва, пр-т Вернадского д. 53, Бизнес-центр "Дружба". С. 7-11

49.Винокуров А.А., Ильин И.В. Оптимизация режимов измерений аппаратурой ИНГК-С (С/О-каротаж) Научно-технический журнал "Каротажник", Выпуск 12-13 (125-126), 2004 г. Издательство "АИС", г. Тверь. Стр. 46-48

50.Хаматдинов Р.Т., Велижанин В.А., Черменский В.Г. С/О-каротаж -перспективная основа современного геофизического мониторинга нефтяных месторождений // НТВ "Каротажник", вып. 12-13 (125-126). - Тверь, 2004. - С. 3 - 24.

51.Боголюбов Е.П., Бортасевич В.С., Велижанин В.А., Глебов А.П., Еникеева Ф.Х., Журавлёв Б.К., Хаматдинов Р.Т., Хасаев Т.О., Черменский В.Г. Спектрометрическая аппаратура импульсного нейтронного гамма-каротажа для элементного анализа горных пород (С/О каротаж - реальность для российской геофизики) // НТВ "Каротажник", Выпуск 22. - Тверь, 1996. - С. 28 -36.

52.Тропин А.Н., Велижанин В.А., Еникеева Ф.Х., Журавлёв Б.К., Саранцев С.Н., Хаматдинов Р.Т., Черменский В.Г., Бубеев А.В., Бортасевич В.С., Таухутдинов Р.К. Опыт применения углерод-кислородного (C/O) каротажа для изучения текущей и остаточной нефтенасыщенности пород // НТВ "Каротажник", вып. 55. - Тверь, 1999. - С. 11 - 16.

53.Хаматдинов Р.Т., Тропин А.Н., Тихонов А.Г., Глебочева Н.К. Сравнительные испытания аппаратурно-методического комплекса углеродно-кислородного каротажа АИМС-С производства НПЦ "Тверьгеофизика" с аппаратурой PSGT (Halliburton) на месторождениях ОАО "Сургутнефтегаз" // НТВ "Каротажник", вып. 99. - Тверь, 2002. -С. 47 - 53.

54.Jacobson A., Ethridge R. and Simpson G. A New Small-Diameter, HighPerformance Reservior Monitoring Tool // SPWLA 39th Annual Logging Symposium, May 26-29, 1998.

55.Roscoe B.A., Stoller C., Adolph R.A., Boutemy Y., Cheeseborough J.C., Hall J.S., McKeon D.C., Pittman D., Seeman B., Thomas S.R. A New Through-Tubing Oil-Saturation Measurement System // Paper SPE 21413, presented at then SPE Middle East Oil Show. Bahrain. November 16-19, 1991.

56.Велижанин В.А., Лобода Н.Г., Меженская Т.Е., Хаматдинов Р.Т., Черменский В.Г., Глебочева Н.К., Теленков В.М. Некоторые вопросы методического обеспечения аппаратуры АИМС при решении задачи опделения текущей нефтенасыщенности коллектров // Геофизический вестник. М. 2003. № 12.

57.Кучурин Е.С., Гайнетдинов Р.Г., Рыскаль О.Е., Коротченко А.Г., Огнев А.Н. Оценка коэффициента нефтенасыщенности коллекторов по данным углеродно-кислородного каротажа // НТВ "Каротажник", вып. 12-13 (125-126). - Тверь, 2004. - С. 24 - 35.

58.Jerame A.T., Jacobson L.A., Simpson G.A., Durbin D.P. Field experience and results obtained with an improved carbon/oxygen logging system and reservoir optimization // SPWLA 42nd Annual Logging Symposium, June 17-21 2001.

59.Кучурин Е.С., Глухов В.Л., Огнев А.Н., Метелев В.П. Состояние, эффективность применения и перспективы развития углеродно-кислородного каротажа для оценки нефтенасыщенности пластов разрабатываемых месторождений // НТВ "Каротажник", вып. 1 (114). -Тверь, 2004. - С. 25 - 34.

60.Еникеева Ф.Х., Жуков А.М., Журавлёв Б.К., Тропин А.Н. Определение текущей нефтенасыщенности терригенных коллекторов со сложным флюидальным составом по данным ядерно-физической спектрометрии // НТВ "Каротажник", вып. 110. - Тверь, 2003. - С. 115 - 123.

61.Винокуров А.А., Серебрянский В.В., Ильин И.В., Фисенко А.Н., Пенязь К.Г. Применение новых технологий в аппаратуре спектрометрического каротажа // НТВ "Каротажник", вып. 2 (115). -Тверь, 2004. - С. 75 - 84.

62.Винокуров А.А., Серебрянский В.В., Ильин И.В., Фисенко А.Н., Пенязь К.Г. Анализ основных параметров, полученных аппаратурой ИНГК-С-95 // НТВ "Каротажник", вып. 7 (120). - Тверь, 2004. - С. 15 -21.

63.Jacobson L.A., Beals R., Wyatt D.F., Hrametz A. Response characterization

of and induced gamma spectrometry tool using bismuth germinate scintillator // The Log Analyst. - 1993. vol. 34, № 4. - P. 14-23.

64.Ахметов К.Р. О Возможностях и ограничениях углеродно-кислородного каротажа // НТВ "Каротажник", вып. 12-13 (125-126). -Тверь, 2004. - С. 77 - 81.

65. Геофизический мониторинг разработки нефтяных пластов обсаженных стеклопластиковыми трубами / В.И. Дворкин. - Уфа, 2001. - 198 С.

66.Телеков В.М. Технология определения текущей нефтенасыщенности коллекторов при контроле разработки нефтегазовых месторождений Нижневартовского района // НТВ "Каротажник", вып. 98. - Тверь, 2002.

- С. 72 - 94.

67.Поздеев Ж.А. О достоверности определения текущей нефтенасыщенности по данным С/О-каротажа // НТВ "Каротажник", вып. 12-13 (125-126). - Тверь, 2004. - С. 81 - 89

68.Воронков Л.Н., Баженов В.В., Нуретдинов Я.К., Кормильцев Ю.В., Юсупов Р.И. Опыт применения углеродно-кислородного каротажа на нефтяных месторождениях Татарстана. // НТВ "Каротажник", вып. 1213 (125-126). - Тверь, 2004. - С. 89 - 93.

69.Громобоев Ю.В. Применение статистического анализа для повышения надежности литологического расчленения скважины по данным ГИС и ГТИ // НТВ "Каротажник", вып. 101. - Тверь, 2002. - С. 75 - 84.

70. Фридман М.Я. Разработка технологии комплексного изучения сложно построенных продуктивных разрезов в подсолевых отложениях восточного борта прикаспийской впадины / Дис. канд. геол.-минер. наук (НПП "ГЕРС"), - 1992.

71.Драцов В.Г., Абдухаликов Я.Н., Трунин В.Ю. Литологическое расчленение разреза по данным геофизических исследований скважин / Геофизика. 2001. № 1

72.Hilton B.E. Some Application of Methods Used in Electrofacies Identification // The Log Analyst. - 1994.

73.Громобоев Ю.В., Нестерова Т.Н., Кудрявцев Д.А. Система хранения, обработки и интерпретации геолого-технологической и геофизической информации (WellBase) // Свидетельство об официальной регистрации программы № 2001610876 от 24.07.2001.

74.Хаматдинов Р.Т., Черменский В.Г., Велижанин В.А. Проблемы и перспективы современного состояния приборостроения в радиоактивном каротаже // НТВ "Каротажник", вып. 101. - Тверь, 2002.

- С. 26 - 33.

75.Таужнянский Г.В., Соколовская О.А., Румак Н.П., Селиванова Е.Е. Петрофизическое обоснование определения коэффициента нафтегазонасыщенности коллекторов месторождений западной Сибири // НТВ "Каротажник", вып. 101. - Тверь, 2002. - С. 36 - 42.

76. Радиометрия скважин / В.В. Ларионов. - М.: "Недра", 1969. - 327 С.

77.Ларионов В.В., Нефедова Н.И. Естественная радиоактивность полимиктовых песчано-глинистых отложений юрского возраста полуострова Мангашлак // Труды МИНХ и ГП, вып. 89 - М., "Недра", 1969. - С. 47 - 56.

78.Юдин В.А., Горбунов В.Ф., Кантор С.А. О возможности использования двухзондовой модификации ИНГМ для расчленения геологического разреза по водородосодержанию // Ядерная геофизика. - М.: "Недра", 1971. - С. 35-46.

79.Гулин Ю.А. О характере зависимости показаний нейтронного каротажа от пористости пород // Прикладная геофизика. - М.: "Недра", вып. 72,

1973. - С. 204.

80.Нейтронные характеристики горных пород и их использование в нефтегазопромысловой геологии / Кожевников Д.А. - М.: "Недра",

1974. - 184 С.

81.Юдин В.А., Лутфирахманова Л.Б., Цойтлин В.Г. О возможности применения двухзондовой модификации ИННК для расчленения геологического разреза по водородосодержанию // Вопросы ядерной геофизики и нефтегазопоисковой геохимии. - М. 1972. - С. 14-20.

82.Salton G. Automatic Information Organization and Retrieval. - 1968, - 514 p.

83.Захаров В.П. Информационно-поисковые системы: Учеб.-метод. пособие. - СПб., 2005. - 48 с.

84.Лезин Г.В., Тузов В.А. Семантический анализ текста на русском языке: семантико-синтаксическая модель предложения // Экономико-математические исследования: математические модели и информационные технологии. - СПб.: Наука, 2003. - Вып. 3. - C. 282303.

85.Temperley D., Sleator D., Lafferty J. Link Grammar Documentation - 1998. -URL: http://www.link.cs.cmu.edu/link/dict/index.html (accessed: 15 November 2012)

86.Sleator D., Temperley D. Parsing English with a Link Grammar. Pittsburgh: School of Computer Science Carnegie Mellon University, 1991. - 93 p.

87. Grinberg D., Lafferty J., Sleator D. A robust parsing algorithm for link

grammars. Carnegie Mellon Univ. Comp. Sci. Tech. Rep. CMU-CS-95-125. - 1995.

88.Лбов Г.С. Методы обработки разнотипных экспериментальных данных: - Новосибирск:Сиб. отд-ние, Наука. 1981. - 160 с.

89.Викентьев А.А., Викентьев Р.А. О метриках для формул от разнотипных переменных и мерах опровержимости // Труды Второй междунар. молодежной школы-конференции «Теория и численные методы решения обратных и некорректных задач». 2011. - Ч. 1. - С. 192-209. - URL: http://semr.math.nsc.ru/v8/c182-410.pdf (дата обращения: 11.08.2014)

90.Tukeyev U.A., Melby A.K., Zhumanov Zh.M. Models and algorithms of translation of the Kazakh language sentences into English language with use of link grammar and the statistical approach // Proc. of IV Congress of the Turkic World Math. Society, 1-3 July, Baku, 2011. - P.474.

91.Eryigit G., Oflazer K. Statistical Dependency Parsing of Turkish // Proc. of EACL 2006, 11th Conf. of the European Chapter of the Association for Comp. Linguistics, Trento, Italy, 2006. - P. 89-96.

92.Istek O, Cicekli I. A Link Grammar for an Agglutinative Language // Proc. of Recent Advances in Natural Language Processing (RANLP 2007), Borovets, Bulgaria, 2007. - P. 285-290.

93.Index of /downloads/link-grammar/4.7.12. [Electronic resource]. - Mode of access: http://www.abisource.com/downloads/link-grammar/4.7.12/

(accessed: 7 December 2014)

94.Kumar N., Srinathan K., Varma V. Using graph based mapping of co-occurring words and closeness centrality score for summarization evaluation // CICLing Proceedings of the 13th International Conference on Computational Linguistics and Intelligent Text Processing. 2012. Vol. 2. -P. 353-365.

95. Заде Л.А. Понятие лингвистической переменной и его применение к принятию приближенных решений. - М.: Мир, 1976. - 165 с.

96.Кейслер Г.Дж., Чэн Чень-чунь. Теория непрерывных моделей. - М.: Мир, 1971. - 184 с.

97.Пивкин В.Я., Бакулин Е.П., Кореньков Д.И. Нечеткие множества в системах управления: Учебное пособие.- Новосибирск: НГУ, 1997. - 52 с.

98. Иерархическая кластеризация. - URL:

http: //ru.wikipedia.org/wiki/Графовые_алгоритмы_кластеризации (дата обращения: 20.12.2012)

99. Ward's method. - URL: http://en.wikipedia.org/wiki/Ward%27s_method (accessed 31 October 2012)

100. Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования // Военный Университет Ссвязи - СПб, 1999. - 199 c.

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

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

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

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

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

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

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

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

107. Батура Т.В., Копылова Н.С., Мурзин Ф.А., Проскуряков А.В.

Методы анализа данных из социальных сетей // Вестник НГУ. Серия: Информационные технологии. - Новосибисрк, 2013. - Том 11, Вып. 3. - С. 5-21.

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

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

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

111. 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-й работы)

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

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

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

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

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

117. 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)

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

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

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

121. 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)

Прочие публикации

122. Ганжа В.Г., Мурзин Ф.А., Шапеев В.П. Два алгоритма вычисления в символьном виде определителей разреженных матриц и их реализация на ЭВМ // Препринт ИТПМ СО АН № 24, 1980. - 14 с.

123. Дуванов А.А., Мурзин Ф.А., Шапеев В.П. Аналитическое диф ференцирование функций на ЭВМ // Препринт ИТПМ СО АН № 4, 1981. - 10 с.

124. Валиуллин А.Н., Ганжа В.Г., Мурзин Ф.А., Шапеев В.П. Применение символьных преобразований на ЭВМ // Препринт ИТПМ СО АН № 7, 1981. - 10 с.

125. Ганжа В.Г., Мурзин Ф.А., Шапеев В.П. Реализация алгоритма скобок Пуассона на ЭВМ // ЧМСС, т. 12, 4, 1981. - С. 48-52.

126. Валиуллин А.Н., Ганжа В.Г., Мазурик С.И., Мурзин Ф.А., Шапеев В.П., Яненко Н.Н. Применение ЭВМ для исследования и построения разностных схем // Тр. совещания по системам аналит. вычислений на ЭВМ. - Дубна, 1982. - 12 с.

127. Ганжа В.Г., Мелешко С.В., Мурзин Ф.А., Шапеев В.П., Яненко Н.Н. Об использовании ЭВМ для анализа на совместность систем дифф. уравнений // Тр. совещания по системам аналит. вычислений на ЭВМ. -Дубна, 1982. - 7 с.

128. Valiullin A.N., Ganzha V.G., Meleshko S.V., Murzin F.A., Shapeev V.P., Yanenko N.N. Symbolic manipulations in the methods of

mathematical physics // Les Mathematiques de l' Informatique Mathematics for computer science: Proceedings of Symposium (Paris, March 16-18, 1982). - Paris, 1982. - P.431-438. - P. 437-438.

129. Ганжа В.Г., Мелешко С.В., Мурзин Ф.А., Шапеев В.П., Яненко Н.Н. Анализ на совместность систем дифф. уравнений на ЭВМ // Препринт ИТПМ СО АН № 20, 1982. - 28 с.

130. Валиуллин А.Н., Ганжа В.Г., Мелешко С.В., Мурзин Ф.А., Шапеев

B.П. Символьные преобразо вания в методах решения задач мат. физики // Комплексы программ мат. физик, 1982. - С. 128-129.

131. Мазурик С.И., Мурзин Ф.А., Мурзина Т.С. Разработка математической теории и программного обеспечения светосильных растровых структур с автокорреляционными функциями без побочных максимумов // Технические материалы, ИТПМ СО АН, НИС НГУ, Новосибирск - 1983, 100 с.

132. Мазурик С.И., Мурзин Ф.А., Шапеев В.П. Комплекс программных модулей, реализующих в символьном виде спектральный метод Фурье исследования устойчивости разност ных схем // Комплексы программ мат. физик, 1984. - С. 24-32.

133. Мурзин Ф.А., Мурзина Т.С., Чайка Н.Ф., Шлишевский В.Б. Светосильная растровая спектроскопия на основе матриц Адамара // Препринт №17 - 84 , ИТПМ СО АН, НИИГАиК, Зап.Сиб.РНИИ, Новосибирск, 51 с.

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

C. 313-316.

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

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

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

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

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

140. 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.

141. 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.

142. Крючков В.Н., Мурзин Ф. А., Нартов Б.К. Исследование связей в коллективах и сетях ЭВМ на основе анализа предпочтений // Проблемы конструирования эффективных и надежных программ. - Новосибирск, 1995. - C. 136-141.

143. Ларин М.И., Мурзин Ф. А. Концепция языкового обеспечения спецпроцессора информационного поиска // Проблемы конструирования эффективных и надежных программ. - Новосибирск, 1995. - C. 153-162.

144. 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.

145. Воеводин А.Ф., Мурзин Ф.А., Пономарев М.Ю. Параллельный алгоритм расчета гидравлических систем с эластичными трубами // Междунар. симп. "Математические модели и численные методы механики сплошной среды". - Новосибирск, 1996. - С.188-189.

146. Мурзин Ф. А., Мурзина Т.С. О распараллеливании алгоритма WZ-разложений // Оптимизирующая трансляция и конструирование программ. - Новосибирск, 1997. - C. 113-122.

147. Воеводин А.Ф., Мурзин Ф. А.,Пономарев М.Ю. Параллельный алгоритм расчета гидравлических систем с эластичными трубами // Оптимизирующая трансляция и конструирование программ. -Новосибирск, 1997. - C. 123-132.

148. 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.

149. Лобив И.В., Мурзин Ф.А. О распараллеливании метода частиц в ячейках и метода дискретных вихрей // Материалы междунар. конф. Distributed Data Processing. - Новосибирск, 1998, - С. 43-44.

150. Лобив И.В., Мурзин Ф. А. О распараллеливании метода дискретных вихрей // Тр. XVI Междунар. школы - семинара по численным методам механики вязкой жидкости. - Новосибирск, 1998. - С. 37-38.

151. Вшивков В.А., Лобив И.В., Мурзин Ф. А. Параллельный алгоритм на основе PIC-метода для расчета задач о взаимодействии потоков плазмы // Тр. XVI Междунар. школы - семинара по численным методам механики вязкой жидкости. - Новосибирск, 1998. - С. 38-39.

152. Лобив И.В., Мурзин Ф.А. Исследование вопросов, связанных с распараллеливанием PIC-метода // Тр. XVI Междунар. школы -семинара по численным методам механики вязкой жидкости. -Новосибирск, 1998. - С. 44-46.

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

154. Корабельщиков Д.Г., Мурзин Ф.А., Мурзина Т.С., Шлишевский В.Б. Разработка алгоритмов и программ поиска оптимальных растровых структур ИНПРИМ-2000, Часть IV, Новосибирск, 2000, 1с.

155. Мурзин Ф.А., Мурзина Т.С., Шлишевский В.Б. Новая методика построения растров больших размерностей ИНПРИМ-2000, Часть IV, Новосибирск, 2000, 1с.

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

157. Бурдонов И.В., Мурзин Ф.А. О распараллеливании метода МЕДУЗА // Поддержка супервычислений и Интернет-ориентированные технологии, ИСИ СО РАН, 2001, - С. 82-107.

158. Мурзин Ф.А., Семич Д.Ф. Программные средства для тестирования алгоритмов по обработке изображений // Поддержка супервычислений и Интернет-ориентированные технологии, ИСИ СО РАН, 2001, - С. 108-113.

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

160. Винокуров А.А., Ильин И.В., Лобив И.В., Мурзин Ф.А., Половинко О.Н., Семич Д.Ф. Программное обеспечение для поддержки процесса

ядерного каротажа нефтяных скважин // Пятая междунар. конф. памяти акад. А.П. Ершова, "Перспективы систем информатики", Рабочий семинар "Наукоемкое программное обеспечение", Новосибирск 2003, -

C. 40-42.

161. 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.

162. Murzin F.A., Murzina T.S., Shlishevsky V.B. High luminosity raster spectrometers // Пятая междунар. конф. памяти акад. А.П. Ершова, "Перспективы систем информатики", Рабочий семинар "Наукоемкое программное обеспечение", Новосибирск 2003, -С. 53-54.

163. Батура Т.В., Еркаева О.Н., Мурзин Ф.А. К вопросу об анализе текстов на естественном языке // "Новые информационные технологии в науке и образовании", ИСИ СО РАН, Новосибирск 2003, -С. 7-58.

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

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

166. Мехонцев Д.Ю., Лобив И.В., Мурзин Ф.А. Решение задачи нахождения оптимального положения тела в пространстве по данным, поступающим с одномерных камер, для 3D оптической системы анализа движения объектов // "Новые информационные технологии в науке и образовании", ИСИ СО РАН, Новосибирск 2003, -С. 246-253.

167. Мурзин Ф.А., Мурзина Т.С., Хаяров Е.М., Шлишевский В.Б. Светосильные растровые структуры для режима автоколлимации // "Новые информационные технологии в науке и образовании", ИСИ СО РАН, Новосибирск 2003, -С. 254-255.

168. Мурзин Ф.А., Половинко О.Н., Лобив И.В. Распознавание текстур по пространственным закономерностям // "Новые информационные технологии в науке и образовании", ИСИ СО РАН, Новосибирск 2003, -С. 256-268.

169. Винокуров А.А., Ильин И.В., Лобив И.В., Мурзин Ф.А., Половинко

О.Н., Семич Д.Ф. Программный комплекс предназначенный для обработки результатов, полученных методом ядерного каротажа нефтянных скважин // Конф. аспирантов и молодых ученых ИСИ СО РАН "Новые подходы и решения" Новосибирск 2003, -С. 23-31.

170. Лобив И.В., Мехонцев Д.Ю., Мурзин Ф.А. Восстановление положения тела в пространстве по данным, поступающим с одномерных камер для системы реального времени анализа движения объектов // Конф. аспирантов и молодых ученых ИСИ СО РАН "Новые подходы и решения" Новосибирск 2003, -С. 44-52.

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

172. Valeev T., Murzin F. Some algorithms of videosequences compression and their investigation // Proceedings of the 15th International Conference on Computer Graphics and Applications (GraphiCon'05), Jun 20-24, 2005; pp 326-328.

173. Васильева М.Б., Лобив И.В., Мурзин Ф.А. Автоматизация процесса морфометрии гистологического материала // Proceedings of the 15th International Conference on Computer Graphics and Applications (GraphiCon'05), Jun 20-24, 2005; pp 326-328.

174. Т.В. Батура, О.В. Корда, Ф.А. Мурзин, А.А. Позименко Исследовательская система для анализа текстов на естественном языке // Методы и инструменты конструирования и оптимизации программ, Новосибирск, ИСИ СО РАН, С. 7 - 20.

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

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

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

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

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

180. Батура Т.В., Мурзин Ф.А. О логических методах анализа текста на естественном языке // Междунар. научно-практическая конф. "Казахстанское общество: приоритеты и ключевые факторы конкурентоспособности", том 1, г. Тараз, Унивеситет "Аулие-Ата", Респ. Казахстан, 2007. - С. 240-245.

181. Винокуров А.А., Ильин И.В., Мурзин Ф.А., Семич Д.Ф. Алгоритмы и программный комплекс для интерпретации данных радиоактивного каротажа нефтяных скважин // Междунар. научно-практическая конф. "Казахстанское общество: приоритеты и ключевые факторы конкурентоспособности", том 1, г. Тараз, Унивеситет "Аулие-Ата", Респ. Казахстан, 2007. - С. 245-249.

182. 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. - Р. 141 - 158.

183. Ануреев И.С., Бодин Е.В., Городняя Л.В., Марчук А.Г., Мурзин Ф.А., Шилов Н.В. Проблема классификации компьютерных языков // Материалы 11 национальной конференции по искусственному интеллекту с международным участием (КИИ-08), Дубна, 2008. — Том 3. — С. 199-207.

184. Копылова Н.С., Мурзин Ф.А. Моделирование механизмов социального влияния на основе мультиагентного подхода // Труды 11 -ой национальной конференции по искусственному интеллекту с международным участием КИИ-2008 (г.Дубна, Россия). -М.: ЛЕНАНД, 2008. -Т.3. -С.226-234.

185. Батура Т.В., Мурзин Ф.А. О формировании речи человека и и анализе текстов на естественном языке// Междунар. научно-практическая конф. "Казахстан на этапе социально-политического и экономического развития в условиях глобализации", том 1, г. Тараз,

Унивеситет "Аулие-Ата", Респ. Казахстан, 2008. - С. 271-273.

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

187. Городняя Л.В., Марчук А.Г., Мурзин Ф.А., Шилов Н.В. Классификация компьютерных языков: состояние, проблемы, перспективы. // Труды международной конференции "Космос, астрономия и программирование" (Лавровские чтения). — Санкт-Петербургский государственный университет, Санкт-Петербург, 2008. — С. 15-22.

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

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

190. Anureev I.S., Bodin I.V., Gorodnyaya L.V., Marchuk A.G., Murzin F.A., Shilov N.V. On the problem of computer language classification // Bull. of NCC. Ser.: Comput. Sci. — 2008. — Iss. 28. — P. 31-42.

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

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

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

4, 2011, - С. 91-103.

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

195. Т.А.Андреева, И.С. Ануреев, Е.В. Бодин, Л.В. Городняя, А.Г. Марчук, Ф.А. Мурзин, Н.В. Шилов ОБРАЗОВАТЕЛЬНОЕ ЗНАЧЕНИЕ КЛАССИФИКАЦИИ КОМПЬЮТЕРНЫХ ЯЗЫКОВ. Международная конференция памяти академика А.П. Ершова «Перспективы систем информатики» (15-19 июня 2009, Новосибирск). «Информатика образования». С.19-26.

196. 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.

197. Guzhavina I.V., Denisyuk V.S., Murzin F.A., Palyanov A.Yu., Trelevich J. On the recognition of texts of very bad quality. // Bull. of NCC. Ser.: Comput. Sci. — 2009. — Iss. 29. — P. 49—61.

198. Копылова Н. С., Мурзин Ф. А. Моделирование механизмов социального влияния на основе мультиагентного подхода // Вопросы искусственного интеллекта (Вестник НСМИИ РАН), — 2009. — С. 173— 183.

199. 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—43.

200. Perfiliev 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. 91—109.

201. 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.

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

203. Кальменов Т.Ш., Мурзин Ф.А., Поплевина Н.В. Анализ данных

радиоактивного каротажа на основе метода И.Б. Мучника. Доклады НАН РК, №6, 2011. - С. 17-23.

204. Batura Tatiana, Murzin Feodor, Proskuryakov Alexey, Trelevich Jennifer Some Approaches to Detection of Spam and Senders of Spam // Восьмая междунар. конф. памяти акад. А.П. Ершова, "Перспективы систем информатики", Рабочий семинар "Наукоемкое программное обеспечение", Новосибирск 2011. - С. 1-6.

205. Мурзин Ф.А., Поплевина Н.В., Семич Д.Ф. Алгоритмы определения нефтенасыщенных пластов на основе данных радиоактивного каротажа // Восьмая междунар. конф. памяти акад. А.П. Ершова, "Перспективы систем информатики", Рабочий семинар "Наукоемкое программное обеспечение", Новосибирск 2011. - С. 169-175.

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

207. Копылова Н.С., Мурзин Ф.А., Курков И.А. Моделирование социальных процессов на основе мультиагентного подхода // Труды третьего семинара Знания и Онтологии *ELSEWHERE* 2011 Ершовской конфернеции по информатике 2011, Новосибирск 2011 - С. 58-70.

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

209. Городняя Л.В., Марчук А.Г., Мурзин Ф.А. О магистерской программе «Математика информационных систем» и специализации по системному программированию // Междунар. суперкомпьютерная конф. «Научный сервис в сети Интернет: поиск новых решений». Организаторы: РАН и Суперкомпьютерный Консорциум Университетов России, 18-21 сентября 2012, Абрау Дюрсо, - С. 249252. Также размещено по адресу: http: //agora. guru.ru/abrau2012/pdf/249.pdf

210. Городняя Л.В., Марчук А.Г., Мурзин Ф.А. О математике информационных систем и системном программировании // Региональная научно-практическая конференция с международным участием «Информатика и информационные технологии в

образовании: теория, приложения, дидактика», 10с.

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

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

213. Батура Т.В., Мурзин Ф.А., Проскуряков А.В., Сперанский Д.О. Методы анализа и обработки данных из социальных сетей // Проблемы информатики. — 2014. — № 2 (23). — С. 39—53.

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

215. Batura T.V., Kopylova N.S., Murzin F.A., Proskurykov A.V. Computer social networks and their analysis // International conference "Advanced Mathematics, Computations and Applications — 2014" (AMCA 2014). Abstracts. Novosibirsk, June 8—11, 2014. Novosibirsk: Academizdat, 2014. — P. 65.

216. 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.

217. Marchuk A., Murzin F., Bulyonkova A., Krayneva I. 25 Yeas of A.P. Ershov Institute of Informatics Systems: a History Overview. // Bull. of NCC. Ser.: Comput. Sci. 2014. Vol. 35. (in appear).

218. Батура Т.В., Мурзин Ф.А., Проскуряков А.В., Байжанов Б.С., Немченко М.В. О методах анализа компьютерных социальных сетей // Доклады Национальной академии наук Республики Казахстан. — Алматы, 2014. — №. 5. — С. 11—20.

219. Батура Т.В., Мурзин Ф.А., Сперанский Д.О., Байжанов Б.С., Немченко М.В. Модели определения релевантности текста заданной теме, графы ассоциированные с текстами и задача реферирования // Известия Национальной академии наук Республики Казахстан. — Алматы, 2014. — №. 5 (297). — С. 25—32.

220. Батура Т.В., Мурзин Ф.А., Перфильев А.А., Байжанов Б.С., Немченко М.В. Машинно-ориентированные методы определения степени близости предложений на естественном языке // Вестник

Национальной академии наук Республики Казахстан. - Алматы, 2014. -№. 5. - С. 3-12.

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

ПРИЛОЖЕНИЕ

ЗАО

НОКБГП

РОССИЙСКАЯ ФЕДЕРАЦИЯ г. Новосибирск

ЗАО «НОВОСИБИРСКОЕ ОПЫТНО-КОНСТРУКТОРСКОЕ БЮРО ГЕОФИЗИЧЕСКОЕО ПРИБОРОСТРОЕНИЯ»

630117, г. Новосибирск, ул. Арбузова 1/1. тел [phone], ИНН 5408186061 БИК 045004762 тел. [phone], Р/сч 40702810400430003313 Факс [phone] К/сч 30101810900000000762 тТофтеда^дпаКсот в Новосибирском филиале БАНКА МОСКВЫ, г. Новосибирск._http://www meqasignal.com/

АКТ

о внедрении программного комплекса "Анализатор спектров"

Программный комплекс "Анализатор спектров" был задуман как часть программного обеспечения для прибора радиоактивного каротажа ИНГК-С-95. созданного в ЗАО "НОВОСИБИРСКОЕ ОПЫТНО -КОНСТРУКТОРСКОЕ БЮРО ГЕОФИЗИЧЕСКОГО ПРИБОРОСТОРОЕНИЯ" в 2004 году.

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

Наибольший вклад в усовершенствование математических алгоритмов для программного комплекса внесен Ф.А. Мурзиным.

За время эксплуатации, прибор ИНГК-С-95 и программное обеспечение "Анализатор спектров" показал отличные результаты на промыслах Западной Сибири и других регионов России.

Основные результаты внедрения программного обеспечения "Анализатор спектров":

1. Исключен человеческий фактор в задачах расчета сложных геофизических параметров.

2. В среднем в 4 раза уменьшилось время расчета и выдачи результатов заказчику.

3. Точность расчета некоторых параметров выросла более чем на 20 %.

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

Генеральный директор ЗАО «Новосибирское ОКБ ГП

с

Хегай А.П.

т

РОССИЙСКАЯ ФЕДЕРАЦИЯ ХАНТЫ-МАНСИЙСКИЙ АВТОНОМНЫЙ ОКРУГ

ОТКРЫТОЕ АКЦИОНЕРНОЕ ОБЩЕСТВО ЗАПАДНО-СИБИРСКАЯ КОРПОРАЦИЯ

ТЮМЕНЬПРОМГЕОФИЗИКА

Тел. [phone] Факс [phone] E-mail imegion'ntpg.ru www.tpg.ru

628681,отделение связи №1,, а и 34, г.Мегион. ХМАО

Р. с 40702810500010000443 в АКБ "K)i ра" г.Мегион, ИНН 8605013881. ВПК 047171779 К/с ЗОЮ 1810500000000779

АКТ

о внедрении программного комплекса "Анализатор спектров"

Программный комплекс "Анализатор спектров" был разработан и внедрён в марте 2004 года Западно-Сибирской Корпорацией "ТЮМЕНЬПРОМГЕОФИЗИКА" совместное сотрудниками Института систем информатики имени А.П. Ершова СО РАИ.

Наибольший вклад в усовершенствование математических алгоритмов для программного комплекса внесен Ф.А. Мурзиным.

С момента внедрения и по сегодняшний день "Анализатор спектров" приносит большую пользу интерпретационным службам ЗСК "ТЮМЕНЬПРОМГЕОФИЗИКА" и позволяет успешно решать задачи обработки данных, получаемых методом радиоактивного каротажа на промыслах Западной Сибири и дру гих регионов России.

Основные результаты внедрения программного обеспечения "Анализатор спектров":

1. Исключен человеческий фактор в задачах расчета сложных геофизических параметров.

2. В среднем в 4 раза уменьшилось время расчета и выдачи результатов заказчику.

3. Точность расчета некоторых параметров выросла более чем на 20 %.

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

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

За время эксплуатации "Анализатор Спектров" зарекомендовал себя как надежная система, резу льтатам работы которой доверяют ведущие специалисты ЗСК "ТЮМЕНЬПРОМГЕОФИЗИКА".

Генеральный директор

ОАО ЗСК «Тюменьпромгеофизика»

Т.Г. Малания

КАЗАКСТАН РЕСПУБЛИКАСЫ Б1Л1М ЖЭНЕ ГЫЛЫМ МИНИСТРЛ1Г1 ГЫЛЫМ КОМИТЕТ1Н1Н «МАТЕМАТИКА ЖЭНЕ МАТЕМАТИКАЛЫК МОДЕЛДЕУ ИНСТИТУТЫ» ШАРУАШЫЛЫК ЖУРГВУ КУКЫГЫНДАГЫ РЕСПУБЛИКАЛЫК МЕМЛЕКЕТТ1К КЭС1ПОРЫНЫ

050010, Алматы каласы, Пушкин кешеЫ,125 Тел./факс: [phone] e-mail: rgpimimtft mail.ru

РЕСПУБЛИКАНСКОЕ ГОСУДАРСТВЕННОЕ ПРЕДПРИЯТИЕ НА ПРАВЕ ХОЗЯЙСТВЕННОГО ВЕДЕНИЯ «ИНСТИТУТ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ» КОМИТЕТА НАУКИ МИНИСТЕРСТВА ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН

050010, город Алматы. улица Пушкина 125, Тел./факс: [phone] e-mail: repimimffl mail.ru

АКТ

о внедрении программного комплекса "ОПТетрег"

Программный комплекс "ОПТетрег" был разработан в течение 2009 года в Институте систем информатики им. А.П. Ершова СО РАН по заказу Института математики, информатики и механики Комитета науки Министерства образования и науки Республики Казахстан (Договор № 20 от 1 октября 2009 г.).

Наибольший вклад в разработку алгоритмов для программного комплекса внесен сотрудником ИСИ СО РАН Ф.А. Мурзиным.

С момента внедрения и по сегодняшний день программный комплекс "ОПТетрег" находится в опытной эксплуатации в Институте математики и математического моделирования КН МОН РК и приносит большую пользу для исследования данных, получаемых методом радиоактивного каротажа.

Основные результаты внедрения программного обеспечения " ОПТетрег ":

1. Предложены и испытаны 4 метода расчета коэффициента нефтенасыщенности: по спектру ГИРЗ с помощью метода "Кросс-плот"; по спектру ГИНР с помощью метода "Кросс-плот"; методом "Дельта С/О" по спектру ГИРЗ; методом "Дельта С/О" по спектру ГИНР. Апробация на физических моделях пластов из метрологического центра прошла успешно - расчетные коэффициенты нефтенасыщенности по этим методам согласуются с истинным значением в пределах погрешности измерений.

2. Проверка методов расчета на ряде скважин дает основания предположить, что метод "Кросс-плот" с использованием аналитических параметров по спектру ГИРЗ дает результаты наиболее близкие к реальным. Заслуживает также внимания расчеты методом "Дельта С/О", по спектру ГИНР.

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

Зам директора —

Чл.- корр. НАН РК (О П Б.С. Байжанов

"СУЛЕИ МЛ Н ДЕ МИР ЕЛ Ь AI ММДЛГЫ УНИВЕРСИТЕ MEKEMECI

SULEYMAN DKMIREL UNIVERSITY

040900, Ка ики an Респуиликасы. Каске icu каласы. Лбылай хам кошео. 1/1 Tea '7727 307 95 60 Фаю: • 7 727 307 95 58

п

1/1. Abylaykhan sir . 040900 Kaskclcn. Republic of Kazakhstan

Tel.: [phone] Fan: • 7 727 307 95 58

(J N IV В К в IT Y

w w » . s d u с d u k r

fJ°Q50b- -ЮШ ^.06. ¿0-16

о внедрении результатов докторской диссертационной работы Мурзина Федора Александровича

АКТ

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

Бюджетная программа: 055 «Научная ннли научно-техническая деятельность».

Подпрограмма 101 «Грантовое финансирование научных исследований».

Специфика: 156 «Оплата консалтинговых услуг и исследований».

По приоритету: «Информационные и телекоммуникационные технологии».

По подприоритету: Интеллектуальные системы и технологии».

Тема: «Исследования по математической лингвистике и анализ социальных сетей»

Результаты внедрены в Учреждении «Университет имени Сулеймана Демиреля» в научных исследованиях и в учебном процессе.

Основные результаты

1. Проведены исследования и критический анализ публикаций, посвященных современным алгоритмам и их программным реализациям для анализа текстов на естественном языке и анализа социальных сетей. Осуществлен логический анализ связей (коннекторов), предоставляемых синтаксическим анализатором Link Grammar Parser. Уточненены возможности использования нечеткой логики Заде.

2. В исследованиях и разработках принимают участие ученики Ф.А. Мурзина: сотрудники, аспиранты н студенты На основе проведенных исследований под его руководством полностью реализована и отлажена рабочая версия программы для извлечения и анализа информации из социальных сетей Twitter и Вконтакте. Были проведены эксперименты с некоторыми активными блогерами, живущими в Казахстане, число подписчиков у которых исчисляется десятками тысяч.

Директор института Дискретной математики и математической логики СДУ д.ф.-м.н.