авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 2 | 3 ||

«Министерство образования и науки Российской федерации САНКТ–ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ И.В.Штурц ОСНОВЫ ...»

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

Метафора – троп, основанный на подобии, признак которого характеризует предмет мысли: «меню» на экране компьютера как «ресторанное меню», употребленное в переносном значении.

Монолог – форма речи, развернутое высказывание одного лица.

Омонимы – (от греч. homos «одинаковый» + onyma «имя») – слова, которые пишутся одинаково, но имеют разные, никак не связанные значения.

Паронимы (от греч. para «возле» + onyma «имя») – однокоренные слова, сходные по звучанию, но разные по значению, как «существо» и «сущность».

Плеоназм (от греч. pleonasmos «излишество») – многословие;

выражение, содержащее синонимичные и поэтому излишние слова.

Полисемия (от лат. poly «много» + sema «знак») – наличие у языковой единицы более одного значения при условии семантической связи между ними.

Понятие – идея, представление о предмете в нашем сознании.

Правильность речи – соответствие общеобязательным нормам современного литературного языка.

Реферат – 1. Обзор литературы на некоторую тему;

2. То же, что аннотация.

Речь – 1. Проявление и функционирование языка, процесс общения;

2. Текст на языке.

Риторический вопрос – утвердительное высказывание в виде вопроса, который не предполагает ответа.

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

Синонимы (от греч. synonymos «одноименный») – слова и устойчивые словосочетания, которые имеют очень близкие или тождественные значения.

Синтаксис – (от греч. syntaxis «построение, порядок») – 1.

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

2. Соответствующий раздел грамматики.

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

Структура – (от лат. structure – строение, расположение, порядок) – совокупность внутренних связей, строение, внутреннее устройство объекта.

Структуризация информации – членение информации на части с указанием отношений между частями.

Тавтология (от греч. tauto «то же самое» + logos «слово») – повторение одного и того же другими словами, не добавляющее смысла.

Термин – имя понятия некоторой области знаний.

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

Транскрипция – запись звучания слова на одном языке буквами алфавита другого языка. Не путать с транслитерацией.

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

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

Точность речи – свойство речи точно выражать то, что хочет сказать автор.

Целостность текста – глобальная связь компонентов текста на содержательном уровне.

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

Фраза (от греч. phrasis «выражение, оборот речи») – отрезок речи, относительно самомтоятельный в смысловом и интонационном отношении.

Этимология (от греч. etymon «истина, основное значение слова + logos «учение») – 1. Раздел языкознания, исследующий происхождение слов;

2. Происхождение слова или выражения.

Язык – система знаков, выражающих понятия.

Ясность речи – свойство речи быть понятной адресату правильно без излишних усилий с его стороны.

Приложение ОТВЕТЫ НА УПРАЖНЕНИЯ РАЗДЕЛА 2.4.5.

1) Сделать предложения более ясными.

а) Диспетчер процессов переводит задачу в ждущее состояние, когда она запрашивает операцию ввода-вывода.

б) Процессор обрабатывает входные пакеты данных в порядке их появления.

в) Мы обработали результаты эксперимента по методике руководителя лаборатории А.Петровой, — методике, появившейся на свет в 2005 г.

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

2) Исправьте предложения так, чтобы логическое ударение падало на наиболее важное слово или словочочтание предложения.

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

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

в) Программное обеспечение — вот что вносит наибольший вклад в ненадежность современных вычислительных систем.

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

3) Улучшить стиль текстовых фрагментов.

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

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

в) Данный метод реализует оригинальный подход к преодолению трудностей языковых преобразований;

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

Приложение ПРИМЕР НАУЧНОЙ СТАТЬИ И ЕЕ ПЕРЕВОД НА АНГЛИЙСКИЙ ЯЗЫК Поисковая отбраковка химических подструктур с помощью поисковых образов, созданных перебором подграфов Дмитрий Павлов, Игорь Штурц Кафедра «Прикладная математика»

С.-Петербургского государственного Политехнического университета Политехническая 29, 195251, С.-Петербургског E-mail: dmitry.pavlov@gmail.com, ishturts@gmail.com АННОТАЦИЯ Статья посвящена оптимизации обработки массовых запросов поиска подструктур в большой базе данных органической химии.

Метод оптимизации основан на так называемых поисковых образах — компактных битовых массивах, которые представляют струкуру графа в упакованной форме. Поисковые образы позволяют делать дешевую (но не полную) отбраковку ошибочных случаев, делая ненужным применение алгоритма поиска изоморфизма подграфов большую часть времени. Поисковые образы, впервые предложенные фирмой Daylight, встроены в три независимых фазы: определение характерных образов графа, хеширование этих образов и упаковка хеш-кодов в битовый массив. Наш подход имеет новизну на первой фазе, где мы используем подсчет реберных подграфов и во второй, где мы применяем новый алгоритм хеширования графа.

Ключевые слова: поисковые образы, сопоставление подграфов, поиск подструктур.

ПОСТАНОВКА ЗАДАЧИ Химическая структура органического соединения традиционно представляется помеченным графом, в котором вершины — это атомы, а ребра — связи между атомами (см. рис. 1).

Рис. 1. Структура парацетомола содержит основные органические элементы (C, N, O, H, и т. д.) с одинарными и двойными связями.

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

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

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

Формальная постановка задачи — следующая. Обозначим G — множество всех графов с помеченными вершинами и ребрами:

G = (V, E,, ) E [V ]2 : V V : E E {a, b} E a b V E V E В нашей прикладной области V содержит пометки химических элементов (C, N, H, O, S, Cl, Br, etc.) и E содержит 4 типа химических связей (одиночная, двойная, тройная и ароматическая).

Будем говорить, что граф P = (V, E,, ) cодержит граф Q = (V, E,, ) и писать Q P, если Q изоморфен некоторому подграфу P:

: V V, : E E v1, v2 V v1 v2 (v1 ) (v2 ) e1, e2 V e1 e2 (e1 ) (e2 ) e {a, b} E (e) { (a), (b)} E v V (v) ( (v)) e E (v) ( (e)) Для данного поискового запроса QG и базы данных P G,мы должны найти соответствия Pq = {P P: QP} для каждого Q Q.

Рис. 2. Примеры соответствия подграфов ПРЕДЫДУЩИЕ РАБОТЫ Поскольку проблема изоморфизма подграфов — NP-полная и множество результатов поиска подструктур часто мала по сравнению с множеством соединений в базе данных, очень важно отфильтровать возможно большее число соединений базы данных до выполнения сопоставления графов атом-за-атомом. Первая работа, посвященная отбраковки при поиске подструктур, была опубликована в 1970 г.1. С тех пор типичный размер базы данных химических соединений вырос до миллионов, и много исследований было нацелено на эффективные алгоритмы отбраковки.

В 1979 г. фирма MDL реализовала способ отбраковки для своей системы MACCS. Этот алгоритм был опубликован только в 2002 г.2.

На препроцессорной стадии для каждого соединения вычисляется битовый вектор фиксированной длины и сохраняется в базе данных.

Анализируется предопределенный набор дескрипторов, общий для всех структур;

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

В 1997 г. Фирма Daylight опубликовала обобщение структурных ключей MDL, названное fingerprints3 (буквально — «отпечатки пальцев»;

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

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

Поисковые образы — более гибкие, чем структурные ключи MDL, так как они работают для всех баз данных и всех нетривиальных запросов, безотносительно точного химического соединения. Идея индексации цепочек (или путей) в графе используется и в других алгоритмах поиска подграфов, например APEX4 и GraphGrep5. В дополнеиие к алгоритмам отбраковки, основанным на предварительном вычислении некоторого компактного битового массива для каждого соединения в базе данных, существует другая группа алгоритмов, которх стоит упомянуть. Их общая идея — построение древовидного индекса базы данных (в противоположность линейной индексации структурными ключами или поисковыми образами). Первая работа, предлагающая древовидный индекс, была опубликована в 1997 г.6 В последние годы многие статьи были посвящены поиска частых подграфов и построению древовидных индексов из них 7-9.

Индексация путей теряет стркутурную информацию о циклах.

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

АЛГОРИТМ Алгоритм построения поисковых образов состоит из трех шагов:

(i) определение поисковых образов графа, (ii) хеширование этих образов, и (iii) упаковка хеш-кодов в компактную структуру данных.

Главный недостаток поисковых образов Daylight в том, что на шаге (i) теряется много структурной информации. Например, не сохраняется информация о циклических цепочках сязей. Рис. 3 показыват, что информация теряется даже для очень маленьких и общих химисских структур. Мы предлагаем следующее улучшение: использовать связные подграфы как характерные образы на шаге (i) генерации поисковых образов. С этим подходом свзяны две трудности. Первая — подсчет соединенных подграфов, что не так просто, как подсчет цепочек. Вторая — двоичное кодирование подграфа. Мы используем исходную идею Daylight о псевдослучайных битах, но построение строки для начального числа определяется графами, а не цепочками.

Наш алгоритм основан на обратном поиске и связанном с этим алгоритмом подсчета порожденных подграфов, предложенном Avis и Fukuda в 1992 г.10. Порожденный подграф G G — это подграф, заданный (порожденный) подмножеством вершин графа G: V V (G).

Все ребра графа G, имеющие оба конца в V ', присутствуют в G.

Очевидно, что произвольный связный подграф графа G порожден подмножеством ребер графа G, которые можно рассматривать как вершины линейного графа L(G) графа G. На рис. 3 показан пример связного подграфа и соответствующий порожденный подграф линейного графа.

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

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

1. У изоморфных графов должны быть одинаковые коды.

2. У не изоморфных графов желательны разные коды.

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

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

Основной алгоритм Он вычисляет поисковый образ графа G, получая три числовых параметра: K — размер поискового образа, L — предельный размер подграфа, и p — число бит для каждого подграфа. K = 6 делает различимым шестиугольные кольца, показанные на рис.1.

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

Но они существенны для эффективности отбраковки и размера базы данных. Для наилучшей производительности эти параметры нужно настраивать для каждой базы данных. При испытаниях, описанных в следующем разделе, мы выбрали p = 2 и L = 2560.

ПРАКТИЧЕСКИЕ РЕЗУЛЬТАТЫ Предложенный алгоритм был реализован в картридже Oracle, созданном для выполнения различных видов поиска в базах данных химических соединений, особенно для поиска поструктур.

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

Использовалась база данных MDL ACD2D, содержащая ~ описаний химических соединений. Набор запросов содержал структур, более или менее часто используемых специалистами. Мы сравинвали эффективность отбраковки двумя алгоритмами — измеряли отношение числа положительных сопоставлений к числу структур, прошедших фазу отбраковки. Наилучшая величина этого показателя — это 1, и она была достигнута для нескольких запросов.

Результаты сранения показаны на графике рис. 4;

точки графиков упорядочены по эффективности отбраковки нашим алгоритмом.

Существенное преимущество нашего алгоритма очевидно.

Наш алгоритм Daylight Рис. 4. Сравнение эффективности отбраковки ЗАКЛЮЧЕНИЕ Предложено существенное улучшение хорошо известного спосба отбраковки Daylight. Мы показали на практике, что структурная информация, теряемая в поисковых образах, основанных на путях в графе, очень важна для эффективности отбраковки в химических базах данных. В аальнейших исследованиях можно изучать применение идеи поисковых образов переменной длины3 для улучшения алгоритма построения поискового образа.

ЛИТЕРАТУРА 1. Crowe, J. E.;

Lynch, M. F.;

Town, W. G. Analysis of Structural Characteristics of Chemical Compounds in a Large Computer-Based File.

Part I. Non-Cyclic Fragments. J. Chem. Soc. 1970, pp. 990-996.

2. Durant, J.;

Leland, B.;

Henry, D.;

Nourse, G. Reoptimization of MDL Keys for Use in Drug Discovery. J. Chem. Inf. Comput. Sci. 2002, 42, pp.1273-1280.

3. James, C. A.;

Weininger, D.;

Delaney, J. Fingerprints – Screening and Similarity. Daylight Theory Manual;

Daylight Chemical Information Systems Inc.: 1997;

http://daylight.com/dayhtml/doc/theory/theory.finger.html 4. Chung, C.-W.;

Min, J.-K;

Shim, K. APEX: An adaptive path index for XML data. ACM SIGMOD International Conference on Management of Data. 2002, pp.121-132.

5. Giugno, R.;

Shasha, D. GraphGrep: A Fast and Universal Method for Querying Graphs. International Conference on Pattern Recognition (ICPR). 2002.

6. Ozawa, K.;

Yasuda, T.;

Fujita, S. Substructure search with tree structured data. J. Chem. Inf. Comput. Sci. 1997, 37 (4), pp. 688-695.

7. Yan, X.;

Han, J. Span: Graph-based substructure pattern mining.

International Conference on Data Mining (ICDM). 2002, pp. 721-724.

8. Yan, X.;

Yu, P. S.;

Han, J. Graph Indexing: A Frequent Structure based Approach. ACM SIGMOD International Conference on Management of Data. 2004.

9. He, H.;

Singh, A. K. Closure-Tree: An Index Structure for Graph Queries. 22nd International Conference on Data Engineering. 2006.

10. Avis, D.;

Fukuda, K. Reverse search for enumeration. Discrete Applied Math. 1996, 6, pp. 21-46.

Chemical substructure search screening with fingerprints built with subgraph enumeration Dmitry Pavlov, Igor Shturts Applied Mathematics Department, St. Petersburg State Polytechnical University Polytekhnicheskaya 29, 195251, St. Petersburg, Russia E-mail: dmitry.pavlov@gmail.com, igor@d-inter.ru ABSTRACT The paper is aimed at efficient mass query optimization of substructure search on a large organic chemical database. Optimization method is based on so called fingerprints — compact bit arrays that represent graph structure in a packed form. Fingerprints allow cheap (but not complete) screening of fault cases, avoiding the subgraph isomorphism algorithm most of the time. Fingerprints, originally proposed by Daylight, are built in three independent sequential phases: determining the characteristic features of a graph, hashing these features, and packing the hashes into the bit array. Our approach is novel in the first phase, in which we are using the edge subgraph enumeration, and in the second, in which we use the new graph hashing algorithm.

Keywords: fingerprints, subgraph matching, substructure search.

PROBLEM DEFINITION Chemical structure of organic compounds is traditionally represented by a labeled graph, in which nodes are atoms, and edges are bonds between atoms.

Figure 1. Paracetamol structure contains the basic organic elements (C, N, O, H, etc.) and has single and double bonds.

Compound descriptions are stored in a relational database which can be considered as a simple array of molecules. Relational databases do not have any built-in functionality for chemistry or general graph-based data processing, so all the algorithms related to subgraph matching must be implemented in third-side software products called cartridges. Well-known ones are MDL Direct and Daylight cartridges.

The substructure search problem is to find all the molecules in the database, which contain the given query molecule as a substructure. The most effective approach for mass query optimization is called screening and is quite simple: the most of false hits are screened before checking the exact subgraph match. Screening technique must be simple (otherwise, there is no point to do it instead of subgraph matching), and efficient (the more false hits are cheaply detected, the better).

The formal problem definition is the following. We denote by G the set of all graphs having labeled vertices and edges. Here is the definition of the labeled graph that we use:

G = (V, E,, ) E [V ]2 : V V : E E {a, b} E a b V E V E In our application area, V contains the element labels (C, N, H, O, S, Cl, Br, etc.), and E contains 4 chemical bond types (single, double, triple and aromatic). We say that the graph P = (V, E,, ) contains graph Q = (V, E,, ) and write Q P, if Q is isomorphic to some subgraph of P, i.e.:

: V V, : E E v1, v2 V v1 v2 (v1 ) (v2 ) e1, e2 V e1 e2 (e1 ) (e2 ) e {a, b} E (e) { (a), (b)} E v V (v) ( (v)) e E (v) ( (e)) Given a query set Q G and the database P G,we have to find matches Pq = {P P: QP} of each Q Q.

Figure 2. Examples of subgraph matching PREVIOUS WORKS Since the subgraph isomorphism problem is NP-complete, and the substructure search result set is often small in comparison to the database compound set, it is very important to screen as many as possible database compounds out before conducting the atom-by-atom subgraph matching.

The first paper considering screening in substructure search was published in 19701. Since then, the typical size of chemical compound database grew up to millions, and a lot of research has been focused on the efficient screening algorithms.

In 1979 MDL implemented the screening technique for their MACCS system. The algorithm was published in 20022. On the preprocessing stage the fixed-length bit vectors are calculated and saved for each compound in the database. Using the predefined set of descriptors that is common for all structures, the presence of each descriptor maps to one or more bits in the resulting bit vector. If the descriptor is absent, the corresponding bit(s) remain zero. Various structural keys may have some common bits to reduce the vector size. Screening is performed trivially by using bitwise AND operation on the structural key vectors of the query compound and the database compound.

In 1997, Daylight published the generalization of MDL structural keys, called fingerprints3. The main difference from the structural keys is that no predefined data is required for building fingerprints. Each bond chain in the graph of the chemical compound is considered as a descriptor.

The bits that correspond to the descriptor are obtained with a pseudo random number generator. The initial seed for this generator is calculated from the numerical hash of the string representation of the chain.

Fingerprints are more flexible than MDL structural keys, as they work equally well for all databases and all non-trivial queries, regardless of the exact chemical composition. The idea of the chain-based (or path-based) indexing is used in other subgraph searching algorithms, for example, APEX4 and GraphGrep5. In addition to the screening algorithms based on precalculating some compact bit array for each compound in the database, there is another group of algorithms that are also worth mentioning. The general idea is building a tree-structured database index (in oppose to linear indexing by structural keys or fingerprints).The first paper proposing the tree-structured index was published in 19976. In the recent years, numerous papers have been devoted to the frequent subgraphs mining and to building the tree-structured indices from them7-9.

The path-based indexing loses the structural information about cycles.

The tree-based frequent structure indices do not lose structural information, but take much more resources to calculate, store, and manage large chemical databases. In the following section, we will propose the improvement for the Daylight technique which operates on subgraphs of limited size instead of chains of limited length.

THE ALGORITHM The fingerprints building algorithm consists of three steps: (i) determining the characteristic features of graph, (ii) hashing these features, and (iii) packing the hashes into the compact data structure. The main drawback of Daylight fingerprints is that they lose a lot of structural information on stage (i). For example, the chains contained in a structure do not represent its rings. Figure 3 shows that the information loss can occur even on very small and common chemical structures. The improvement that we are proposing is to use the connected subgraphs as characteristic features at stage (i) of fingerprint generation. This approach bears two algorithmic challenges. The first is the enumeration of the connected subgraphs, which is not as trivial as the chain enumeration. The second is the bit encoding of the subgraph. We will use the original Daylight’s idea of the pseudo-random bits, but the construction of the string for the initial seed should operate on graphs rather than on chains.

Our algorithm is based on the reverse search and related induced subgraphs enumeration algorithm proposed by Avis and Fukuda in 1992 10.

The induced subgraph G G is the subgraph defined (induced) with the subset of G’s vertices V V (G) All the edges of G having both ends in V ' are present inG. It is evident that an arbitrary connected subgraph of graph G is induced by the subset of G’s edges, which can be considered as vertices of line graph L(G) of G. Fig. 3 shows an example of the connected subgraph and the corresponding induced subgraph of the line graph.

Figure 3. Graph G (left) and its line graph L(G) (right) Hence, the connected G’s subgraph enumeration procedure can be written similar to the induced subgraph enumeration, operating on L(G).

Like the original reverse search algorithm, our modified version handles each subgraph once.

Encoding of the subgraphs Each of the extracted subgraphs should be coded to a bit string. The numerical hash of this stiring should be then given as a seed to the pseudo random number generator. There are two obvious requirements for the encoding scheme, first of which is obligatory, and the second one is desirable:

1. Isomorphic graphs must have identical codes.

2. Non-isomorphic graphs are desired to have different codes.

In terms of screening, the first requirement does not allow screening off true positive matches, and the second requirement educes the number of false positives, yet it is theoretically impossible to eliminate them all. The encoding that meets both requirements is called the canonical one. The encoding that we propose is not canonical, i.e. it can give equal codes for some non-isomorphic graphs. Nonetheless, its discriminative ability is sufficient for chemical compound screening. It is also faster compared to the canonical encoding as it does not perform backtracking (practically unavoidable for canonical code computation).

The main algorithm It calculates the fingerprint of a graph G, taking three numerical parameters: K – the size of the fingerprint, L – the subgraph size limit, and p – the number of bits being set for each subgraph. K = 6 makes hexagonal rings like one on Figure 1 discriminative. Hexagonal and pentagonal rings are the most common kinds of rings in the chemical compounds, so setting K higher than 6 is inappropriate as seriously increases the amount of subgraphs and therefore slows down the fingerprints calculation. The L and p parameters do not affect the fingerprint calculaion performance, but they are essential for screening efficiency and database storage size. For best performance these parameters should be tuned for each database. For testing described in the next section, we chose p = 2 and L = 2560.

PRACTICAL RESULTS The proposed algorithm was implemented within the Oracle cartridge designed for performing various types of search on stored chemical compounds, especially substructure search. Original Daylight fingerprints were also implemented as an option for performance comparison. (Note that our implementation of Daylight fingerprints cannot be compared directly with performance of the Daylight cartridge.) The target set was the MDL ACD2D database, containing ~ chemical compounds. The query set contained 95 structures used more-or less frequently in the user retrieval. We compare two algorithms by screening efficiency — the quotient of hits number and the number of structures that passed the screening phase. The best possible screening efficiency ratio is 1, and it is achieved on some queries.


The comparison results are shown on Fig. 4;

the plot points are sorted by screening efficiency of our algorithm. It is evident a solid advantage of our algorithm.

CONCLUSION We have presented the solid improvement of the well-known Daylight screening technique. We have shown on practice that the structural information being lost by path-based fingerprints is dramatically important for the screening efficiency on the chemical databases. The further research may involve applying variable-sized fingerprints idea3 to the improved fingerprint building algorithm.

Figure 4. Screening efficiency comparison REFERENCES 1. Crowe, J. E.;

Lynch, M. F.;

Town, W. G. Analysis of Structural Characteristics of Chemical Compounds in a Large Computer-Based File.

Part I. Non-Cyclic Fragments. J. Chem. Soc. 1970, pp. 990-996.

(And so on) Приложение ПРИМЕР РЕФЕРАТА И РАЗДЕЛА «СОДЕРЖАНИЕ»

МАГИСТЕРСКОЙ ДИССЕРТАЦИИ А.В. Налеушкина. Диссертация на соискание ученой степени магистра Тема: "Сравнение методов генерации процедурных текстур на примере природных объектов с нечеткими границами" Направление: 510200 — прикладная математика Магистерская программа: 510209 — математическое и программное обеспечение вычислительных машин РЕФЕРАТ стр. 75, илл. 15, табл. Магистерская диссертация посвящена алгоритмам генерации процедурных текстур, их оценкам и сравнению. Из множества объектов, для которых могут быть применены процедурные текстуры, наибольший интерес представляют объекты с нечеткими границами.

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

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

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

ABSTRACT This thesis is devoted to procedural textures generation algorithms, their estimation and comparison. Among wide variety of objects that can be produced with procedural textures, the most interesting are amorphous or gaseous phenomena. They simulate natural objects such as smoke, clouds or dust and must be compared with them in similarity. As a comparison criterion, visual realism of the image was selected. For quantitative estimation of realism level, an autocorrelation function, entropy and image power spectrum were chosen. These metrics were compared with the experts’ poll results to find their correlation. The best result shows image power spectrum metric which is applied to the comparison of a few procedural textures generation algorithms.

KEYWORDS Computer graphics, texturing techniques, procedural textures, image power spectrum.

СОДЕРЖАНИЕ Введение 1. Mетоды генерации процедурных текстур 1.1. Виды процедурных текстур 1.2. Шумовые функции 1.2.1. Числовой шум 1.2.2. Градиентный шум 1.3. Спектральный анализ 1.3.1. Ряды Фурье и преобразование Фурье 1.3.2. Использование рядов Фурье в спектральном синтезе шума 1.4. Характеристические функции для модификации функции плотности 1.5. Применение процедурных текстур к эффекту облаков 1.5.1. Кучевые облака 1.5.2. Перистые и слоистые облака 2. Подходы к оценке качества изображений 2.1. Оценка качества 2.2. Обзор литературы 2.3. Статистические оценки 2.3.1. Автокорреляционная функция 2.3.2. Энтропия 2.3.3. Метод оценки естественных изображений с помощью спектра энергии 2.4. Применение метода анализа спектра энергии к синтезированным изображениям 3. Реализация алгоритмов генерации процедурных текстур для нечетких объектов 3.1. Программное окружение 3.2. Структуры данных 3.3. Программный интерфейс 4. Вычисление метрик и анализ результатов 4.1. Расчет метрик 4.2. Выбор окна 4.3. Применение метрик к выбору параметров алгоритмов 4.4. Верификация метрики, основанной на спектре энергии 4.5. Экспертный опрос 4.6. Сравнение модификаций методов генерации процедурных текстур 5. Вопросы охраны труда и эргономики 5.1. Микроклимат 5.2.Эргономика рабочих мест 5.3. Уровень шума 5.4. Освещение 5.5. Электробезопасность 5.6. Мероприятия по созданию благоприятных условий труда Заключение Список использованных источников Приложения Приложение 1. Пример описания процедурной текстуры облака Приложение 2. Исходный код модуля расчета спектра энергии Приложение РЕКОМЕНДАЦИИ ПО ПОДГОТОВКЕ И ПРЕДСТАВЛЕНИИЮ ТЕХНИЧЕСКИХ ПРЕЗЕНТАЦИЙ Richard Gaughon. Technical Presentations. OE Reports, 1996.

(Cited from the book: Alexander Melker. Noophysics (science and scientists). — SPb.: Nestor, 2006. — 151 pp.) At some point in our career we're all required to give presentations. If you're like most people, this prospect bothers, irritates, even frightens you more than nearly anything else. Surveys consistently show we are more frightened of public speaking than we are of doing. Well, why not be frightened? After aft, your reputation, your self-image, even your career may be on the line every time you get up to speak. But if you face this challenge like you face every other challenge in your career, you'll see it for the opportunity I t is.

How do you face technical challenges? You understand the physics, you plan experiments, and you prepare to make your measurements. For the technical presentation you need to follow those same steps: understand, plan, prepare.


Rule one: the audience wants you to succeed If "stage flight" Is a problem for you, it's probably because you view the audience as a pack of wolves, circling, reedy to leap at the first sign of weakness. But out there in the audience are people just like you! Even if your business competitors are speaking you don't want them to screw up, because you want to know what they're up to, and you won’t learn if they can't tell you. You want the speaker to communicate well. To speak well yourself you must this statement:

the audience wants me to succeed, Rule two: know what your message is Your audience is only going to remember about 10 percent of your speech. That may be sad (especially when your work is so important), but it is truer It's up to you to ensure they remember the right ten percent, II you spend the first ninety percent of your talk describing the laser sources you used in your laboratory you how have only a few minutes to describe your new material and its fascinating properties. The audience has now filled their minds with details of your lab set up and your important information Is just crammed in with the trivial details.

You have something to say? Say it. Right up front. If they're in your breakthrough they'll sit up and pay real attention / If they're not better they learn at the beginning than wade through the detailed description of your experimental effort and find the payoff at the far shore was not worth the effort. If "stage fright" Is a problem for you, It's probably.

Professional speakers all follow some form of this rule:

1. Tell them what you're going to tell them 2. Tell them 3. Then tell them what you told them.

Remember 10 percent retention rule;

you as a speaker, must give the audience enough clues to help them realize what's important about your presentation. This does not mean you save the best for your very last sentence. It means you let them know up front what you've got.

Message and purpose Say you are requesting additional funding far your research.

Your purpose is to get money. You might think your message is "look, how well this material can withstand high energy densities." It is not.

Your message is "give us $3 million in additional finding and well give you an optical coating that can withstand anything you can throw at it." And then you support that message with a report of what you've done already.

Entertain and impress Webster's Unabridged defines "entertain" as "to cause the time to pass pleasantly for someone," The same source defines "impress" as to "amuse the strong interest or admiration of another". You must both entertain and impress. It does not mean that you polish your comedy routine or buy those impressive $300 Italian leather shoes. A presenter who entertains and impresses stimulates curiosity in such a way that the members of the audience enjoy themselves. Conversely, the presenter who ignores those two key verbs bores the audience and ensures an unpleasant experience.

You say you just want to inform? You can’t inform if your audience isn't attentive. The members of the audience are about to give you one of their most valuable possessions: their time, Even before you speak they're wondering if it's worth It. If you stroll up there looking as if you're going to read last month's newspaper, and you'd rather be doing it alone, why should they listen? If you aren't interested in your material, why should they be?' You have to begin to show enthusiasm and interest the moment you're introduced, because — gosh dam, it — you're excited, about what you've got to say! This doesn't mean you've got to froth and bubble like a bottle of champagne. Just let your interest in your subject show through. The world may indeed be amazed by your new technique, but if you don't communicate effectively they'll never realize what you have. You need to be sure they're giving you their full attention. The attention of your audience is divided: they're wondering what session to attend next, where to attend lunch and with whom, and who's going to win the basketball game. Your ideas have to fight for a piece among all these other concerns. The more of their attention you engage, the more their minds are working with you, and the easier it is for them to hear and remember your presentation.

Tools of entertainment OK, so I admit I want my audience to enjoy my presentation and be interested In my ideas, but I don't know about this entertainment stuff. What am I supposed to do? You can use some specific presentation techniques to make your material come alive. For example, tie your ideas into concrete images, if you say: The experiments were done tn a vacuum of 10-12 mm Hg" you have given your audience the facts. But if you say: The experiments were done in a vacuum of 10-12 mm Hg that is close to the conditions when a spacecraft is high enough". Now you have given your audience an image — an image that will help them recall your message. The imagery entertains, and the image impresses itself on their memory.

Some other presentation hints that will keep your audience attentive: vary your voice tone, volume, and rate. Use gestures to illustrate your points. Focus your attention on your audience — look at them, not at the view-foil, the walls, or your feel. A lot to remember?

No, because you did all those things already. Remember when you told your colleagues how you had finally managed to co-align your beams to half a microradlan ? Your face and voice were animated, your hands created pictures of what you have done, your eyes focused on her face as you watched her reaction. Did you practice these techniques? No, you just let your enthusiasm show through. What excites you about your project? Why? What do you find most interesting, and why? Your audience will probably be excited and interested in the same things you are, but you have to communicate, not just the facts and ideas, but the excitement and interest also.

What visual aids should do Visual aids provide a framework for your ideas, making It easier for your audience to follow and remember your presentation.

Say you've spent the last three months refining a complex image processing algorithm that significantly enhances pattern recognition.

To prove this, you would have to fill several slides with equations. To illustrate what you have done, you could simply list your algorithm's major steps in enough detail to show you know what you're doing.

"But why should they believe me," you say, "when I haven't proven anything? Perhaps you haven't, but most people would have to take pencil to paper and convince themselves you're right anyway.

Your presentation should demonstrate the soundness of your ideas so effectively that you audience wants to work it out for themselves.

Getting in their heads Where psychologists used to discuss the "short-term store" to describe the first stage of our memory, they now use the term "working memory" because it reflects the fact that the brain is actively considering only about seven items at any one time.

Implication 1: Don't push it! Put no more than five or six items on a slide.

Implication 2: Don't put long, involved descriptions in your visuals. Your audience will occupy themselves trying to figure out what you have written rather than to pay attention to you. Don't waste some of their seven items on distractions.

Implication 3: Make your organization evident so your audience doesn't have to think about how to organize the information in their own brains. They can use the structure you provide.

The "easy rule" You must give the audience the benefit of your hard-earned expertise in only a few short moments. Your message may be of great technical complexity, but your visual aids are there to make it easy on your audience: easy on the eyes, easy to understand, and easy to remember. If you follow easy rule, the audience will have no trouble seeing your point.

Your appearance It’s likely that your parents told you that first impressions make the difference. When you stand up to speak, you make that first impression before you open your mouth. Professional speakers say they present themselves first, then their malarial. Luckily, our audience is technical and they are more likely to evaluate your presentation based on content, regardless of the appropriateness of your dress. The real-world key? Dress so you'll feel comfortable in front of the audience — just realize that they will evaluate you in terms of your appearance.

Your nerves There are a couple of techniques you can use in the real world to calm your nerves. First, identify what you do when you're nervous, and the opposite. If you pace and wring your hand, force yourself to stand still and relax your hands. You want be acting like you're nervous;

so you can fool yourself into thinking you aren't nervous. It may sound silly, but it works. Second, and more powerful, concentrate on the benefit to your audience. You are speaking to do something for your audience. If you focus on how to help your audience to learn about your technique, you won't concentrate on you - your tie, your heart rate, and your sweaty palms. Then your ideas will dominate your presentation. Instead of your presentation skills (or lack thereof) dominating уour ideas.

Your time Everybody in the audience knows you're not a full-time presenter. They know the time you spend preparing your presentation is time taken from technical investigations that may eventually make the world a better place. But they are taking their time to listen to you!

If you make it worth their while, they will be very appreciative. What does that mean?

• Don't just present lists of data! Organize and prioritize your material. Limit your material based on that priority. Develop an opening and closing that establish and reiterate the importance of your work. Give the audience the benefit of your experience, not just the facts.

• Prepare clear visual aids. Visual aids are nearly a necessity for technical presentations, complex concepts, descriptions, and conclusions are difficult to convey without the benefit of visuals. They don't have to be "Monets," but they must be clear!

Convey your emotions Djn’t assume that because it's a technical talk you can't show you're excited about your material. Show and explain your interest and enthusiasm, and the audience can feel it, too. Everybody in the audience.

• Practice. The most difficult item to fit in to our busy schedules.

Sure, you're intimately familiar with your presentation — you wrote it! That doesn't mean you know where it's smooth, where the leaps of logic are, or where it may drag. Practice until you're very comfortable with the way you present the material, and include at least one "dress rehearsal duplicating as many of the real conditions as you can. Your presentation will be smooth, and you'll...

• Keep to your allotted time! Yes, yes, your material is important, but so is the rest of the world. Your audience has given you the privilege of addressing them — don't abuse it.

Штурц Игорь Викторович ОСНОВЫ СЛОВЕСНОЙ КОММУНИКАЦИИ В СФЕРЕ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ Лицензия ЛР № 020593 от 07.08. Налоговая льгота – Общероссийский классификатор продукции ОК 005-93, т. 2;

95 3005 – учебная литература Подписано в печать 2010. Формат 6084/16. Печать цифровая Усл. печ. л. _. Уч.-изд. л. _. Тираж. Заказ Отпечатано с готового оригинал-макета, предоставленного авторами в цифровом типографском центре Издательства Политехнического университета:

195251, Санкт-Петербург, Политехническая ул., 29.

Тел. (812) 540-40- Тел./факс: (812) 927-57-

Pages:     | 1 |   ...   | 2 | 3 ||
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

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