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

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

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


Pages:   || 2 | 3 | 4 |
-- [ Страница 1 ] --

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

Сборник трудов

молодых ученых и сотрудников

кафедры ВТ

Выпуск 1

Санкт-Петербург

2010

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ Сборник трудов молодых ученых и сотрудников кафедры ВТ Санкт-Петербург 2010 Сборник трудов молодых ученых и сотрудников кафедры ВТ / Под ред. д.т.н., проф. Т.И. Алиева – СПб: СПбГУ ИТМО, 2010. – 90 с.

Сборник содержит избранные труды студентов, аспирантов и сотрудников кафедры ВТ, отобранные по результатам докладов, представленных на XXXVIII научной и учебно-методической конференции СПбГУ ИТМО и на научно практической конференции молодых ученых «Вычислительные системы и сети (Майоровские чтения)», состоявшихся в 2009 году. Конференции направлены на ознакомление научной общественности с результатами научных исследований, выполненных студентами, аспирантами и сотрудниками кафедры ВТ в рамках научного направления «Организация вычислительных систем и сетей», программы развития Национального исследовательского университета, аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы (2006–2010 г.)», Федеральной целевой программы «Научные и научно педагогические кадры инновационной России на 2009-2013 годы», а также в ходе выполнения научно-исследовательских и опытно-конструкторских работ, проводимых, в том числе, по заказу предприятий и организаций Санкт-Петербурга.

ISBN 978-5-7577-0360- В 2009 году Университет стал победителем многоэтапного конкурса, в результате которого определены 12 ведущих университетов России, которым присвоена категория «Национальный исследовательский университет». Министерством образования и науки Российской Федерации была утверждена Программа развития государственного образовательного учреждения высшего профессионального образования «Санкт-Петербургский государственный университет информационных технологий, механики и оптики» на 2009–2018 годы.

© Санкт-Петербургский государственный университет информационных технологий, механики и оптики, «САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ»

Сборник трудов молодых ученых и сотрудников кафедры ВТ СОДЕРЖАНИЕ ПРЕДИСЛОВИЕ.................................................................................................................................... ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ Беликов П.А., Кириллов В.В., Громов Г.Ю. Классификация неструктурированных данных в контексте управления жизненным циклом информации.

......................... Зараковский А.В., Насонова Н.В., Фдорова М.В. Анализ функциональных возможностей rdf-хранилищ......................................................................................... Громов Г.Ю., Громова И.В., Беликов П.А. Информационные технологии в управлении дистанционным обучением...................................................................... Бессмертный И.А., Шеховцов М.М. Индексация фактов для ускорения логического вывода в базах знаний.................................................................................................... Колюшин С.А., Ожиганов А.А. Принципы построения сайтов с использованием системы управления контентом.................................................................................... Кириллов В.В., Лаптева А.А. Использование Oracle APEX для создания корпоративных интернет-приложений........................................................................ КОМПЬЮТЕРНЫЕ СИСТЕМЫ Герасимов А.А., Кустарев П.В. Способы формального описания асинхронных схем.................................................................................................................................. Муравьева-Витковская Л.А., Сафин Д.О. Подход к созданию моделей коммута торов компьютерных сетей........................................................................................... Басов М.А. Методы повышения производительности RISC-процессоров..................... Касаткин Н.В., Сергеев А.О. Клонирование компьютеров в локальной сети с использованием свободного программного обеспечения.......................................... Асафьев Г.К. Современные системы имитационного моделирования............................ Румянцев А.С. Отказоустойчивый алгоритм маршрутизации для сетей на кристалле. СЖАТИЕ И ОБРАБОТКА МУЛЬТИМЕДИЙНЫХ ДАННЫХ Артюхин А.Ю., Тропченко А.А. Современные форматы аудиофайлов......................... Балакшин П.В., Тропченко А.Ю. Развитие и применение алгоритмов распознавания речи для скрытых марковских моделей....................................................................... Пиуновский Е.В. Построение биортогональных вейвлетов с помощью лифтинговой схемы для решения задач сжатия аудиосигналов....................................................... Сборник трудов молодых ученых и сотрудников кафедры ВТ СОДЕРЖАНИЕ МЕТОДЫ И СИСТЕМЫ ЗАЩИТЫ ИНФОРМАЦИИ Дроздов В.Ю., Ожиганов А.А. Сравнение гибридной и асимметричной крипто систем............................................................................................................................... Тропченко А.Ю., Ван Цзянь Методы маркирования цифровых изображений в коэффициентах дискретно-косинусного преобразования.......................................... Шибаева Т.А. Метод защиты программного обеспечения от вредоносных программ................................................................................................................ Тропченко А.Ю., Ван Цзянь Анализ методов маркирования цифровых изображений в пространственной области.......................................................................................... Сборник трудов молодых ученых и сотрудников кафедры ВТ ПРЕДИСЛОВИЕ Кафедра вычислительной техники (ВТ) Санкт-Петербургского государственного уни верситета информационных технологий, механики и оптики — одна из старейших, она более 70 лет ведет подготовку высококвалифицированных специалистов в области вычислительной техники. С первых лет существования в далеком 1939 г. на кафедре начали выполняться ра боты по исследованию механических и электромеханических счетно-решающих устройств, а уже в 1956 г. кафедра приступила к проектированию первой в институте электронной вычис лительной машины для оптических расчетов «ЛИТМО-1».

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

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

В настоящий сборник включены научные статьи студентов и аспирантов кафедры ВТ, отобранные по результатам докладов, представленных на XXXVIII научной и учебно методической конференции СПбГУ ИТМО и на научно-практической конференции молодых ученых «Вычислительные системы и сети (Майоровские чтения)», состоявшихся в 2009 г.

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

Широкий диапазон научных исследований, выполняющихся на кафедре ВТ, обусловил разнообразие тематики представленных статей, которые помещены в 4 раздела: «Информа ционные технологии», «Компьютерные системы», «Сжатие и обработка мультимедийных данных», «Методы и системы защиты информации».

Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ УДК 004.633. КЛАССИФИКАЦИЯ НЕСТРУКТУРИРОВАННЫХ ДАННЫХ В КОНТЕКСТЕ УПРАВЛЕНИЯ ЖИЗНЕННЫМ ЦИКЛОМ ИНФОРМАЦИИ П. А. Беликов, В. В. Кириллов, Г. Ю. Громов При внедрении в информационные системы стратегий управления жиз ненным циклом информации и данных одной из основных проблем яв ляется трудоемкость процесса классификации информации для установ ления формальных критериев ее соответствия уровням хранения. Пред лагается алгоритм классификации неструктурированных данных на ос нове вычисления потенциалов отдельных элементов.

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

Введение Ввиду того что с каждым годом объем хранимых данных и информации возрастает на 50—100 % [1], внедрение концепций и технологий, которые позволят повысить эффектив ность систем хранения, становится все более актуальной задачей. Одной из них является кон цепция управления жизненным циклом информации. Согласно данной концепции, различные классы информации размещаются на различных уровнях хранения и соответственно на раз личных физических носителях. Целью данной работы является создание алгоритма класси фикации, требующего минимальных трудозатрат пользователей, как на этапе внедрения, так и на этапе эксплуатации системы хранения данных (СХД).

Жизненный цикл информации Выделяют следующие основные этапы жизненного цикла информации [2].

1. Создание информации (данных).

2. Активные данные (информация), или данные (информация), только что поступившие в СХД.

3. «Менее активные» данные (информация), используемые и обновляемые время от времени.

4. Архивные данные (информация), данные (информация), используемые время от вре мени и при этом не подвергающиеся изменению.

5. Сжатые (архивные) данные, данные (информация), необходимость хранения которых регламентируется соответствующими законодательными актами [3] или же внутренними ин струкциями организации.

6. Удаление информации.

При этом каждый из этапов 2—5 ассоциирован со своим уровнем хранения (см. рис. 1).

Основной задачей является классификация информации для дальнейшего установления формальных критериев миграции информации и данных между различными этапами жиз ненного цикла и/или физическими носителями. Применительно к данной задаче важным яв ляется очевидное выделение различных видов информации и данных:

— структурированные данные, хранимые в различных СУБД и в плоских файлах;

— частично-структурированные данные, хранимые в XML-файлах;

Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ — неструктурированные данные, мультимедиа, HTML-страницы, файлы текстовых процессоров.

Рис. 1. Этапы жизненного цикла информации и соответствующие им элементы СХД Анализ первых двух видов информации, очевидно, не представляет какой-либо трудно сти. Работа с третьим видом является более сложной задачей. На данный момент задача ана лиза и классификации неструктурированных данных реализуется в рамках концепции управ ления жизненным циклом данных (Data Lifecycle Management - DLM). При этом используют ся такие атрибуты, как тип файла, его размер и возраст. Содержимое учитывается только на основе заданных пользователем метаданных [4], что ведет за собой неминуемое снижение производительности труда (рост трудозатрат) пользователя. Предлагаемый алгоритм (метод) классификации данных позволит значительно снизить трудозатраты за счет отсутствия необ ходимости составления дополнительного описания к различным данным.

Потенциальный метод классификации неструктурированных данных Предлагаемый метод классификации на основе вычисления потенциалов классифицируе мых данных по отношению к существующим в СХД классам данных и информации (рис. 2).

При создании данного метода исследовались методы распознавания образов [5] и, в частно сти, гипотеза компактности [6].

К?

К1 К P P P P1 P3 P К Рис. 2. Классификация данных на основе вычисления потенциалов Потенциал в данном случае представляет собой числовой критерий посимвольного со ответствия классифицируемой информации известным эталонам. Он может быть гарантиро ванно применен для любых текстовых данных. Потенциал для отдельной лексемы вычисля ется следующим образом: начиная с первого символа лексемы каждый следующий символ, соответствующий эталону добавляет единицу к потенциалу лексемы, добавление производит ся до тех пор, пока не встретится символ, отсутствующий в эталоне. Суммарный потенциал файла (набора лексем) вычисляется как сумма потенциалов каждой лексемы.

Алгоритм состоит из 2 этапов.

1. Выделение значащих лексем.

Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ 2. Сравнение значащих лексем с соответствующими порядковыми номерами в класси фицируемых данных и лексем в данных — эталонах классов и вычисление потенциалов.

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

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

1. Приведение данных в шестнадцатеричное представление (рис. 3).

2. Выделение значащих лексем, разделенных шестнадцатеричными байтами «00100000»

в случае данных, созданных при помощи текстового процессора Microsoft Word 2003 или другими разделителями.

3. Порядковая нумерация значащих лексем для дальнейшего анализа.

Рис. 3. Шестнадцатеричное представление тестового файла test.doc, содержащего лексему «test»

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

1. Для каждой лексемы вычисляется потенциал (рис. 4).

2. Потенциалы каждой лексемы суммируются для вычисления полного потенциала данных.

Эталон: 74 65 73 74 = Hex(test) P= Классифицируемая лексема: test 74 65 73 64 = Hex (tesd) 1 1 1 Рис. 4. Вычисление потенциала для лексемы «tesd»

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

Заключение На современном этапе внедрение стратегии управления жизненным циклом включает в себя 3 этапа.

1. Анализ данных.

2. Определение класса данных.

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

Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ Предлагаемый алгоритм позволяет автоматизировать первый и второй этап и за счет этого увеличить производительность труда пользователей. Предложенный в данной работе алгоритм может быть в дальнейшем модернизирован с использованием технологий нейрон ных сетей и алгоритмов искусственного интеллекта и, как следствие, использован для анали за и классификации мультимедийных данных.

ЛИТЕРАТУРА 1. Petrochelli Т. Data Protection and Information Lifecycle Management. Prentice Hall, 2005. 288 p.

2. Волков Д. Два взгляда на ILM [Электронный ресурс]: http://www.oracle.com/global/ru/ oramag/august2004/general_ilm.html.

3. Федеральный закон «Об архивном деле в Российской Федерации» от 22.10.2004 № 125-ФЗ.

4. Gauri S. ACE: Classification for Information Lifecycle Management [Electronic resource]:

http://www.cs.yale.edu/homes/shah/pubs/IBM-RJ10372.pdf.

5. Поветкин А. Распознавание образов методом потенциальных функций [Электронный ресурс]: http://www.citforum.ru/programming/delphi/recognition_2/.

6. Классификация. Гипотеза компактности [Электронный ресурс]: http://www.aiportal.ru/ articles/autoclassification/classification.html.

УДК 004. АНАЛИЗ ФУНКЦИОНАЛЬНЫХ ВОЗМОЖНОСТЕЙ RDF-ХРАНИЛИЩ А. В. Зараковский, Н. В. Насонова, М. В. Фдорова Проведен сравнительный анализ характеристик распространенных от крытых реализаций RDF-хранилищ. Подробно проанализированы (в том числе и посредством бенчмарков) основные параметры RDF-хранилищ Jena, Sesame и Virtuoso. На основании результатов тестирования сдела ны выводы о применимости этих хранилищ в САПР и экспертных си стемах, использующих семантический анализ текстовой информации.

Ключевые слова: RDF-хранилище, RDF, SPARQL, Jena, Sesame, Virtuoso, семантический анализ, те стирование, бенчмарки.

Введение RDF-хранилище (RDF store) — аналог базы данных для хранения RDF-триплетов и за просов к ним. В дополнение к обычным функциям баз данных RDF-хранилище имеет воз можность объединять данные из разных источников, используя URI для идентификации оди наковых объектов.

Фундаментальное отличие RDF-хранилища от реляционной базы данных заключается в возможности автоматически сопоставлять две различные записи из разных источников, ес ли они относятся к одному объекту. Благодаря гибкости модели данных RDF эта процедура четко определена: любые два ресурса с одним URI будут считаться эквивалентными в итого вом наборе данных [1, 2].

Целью данной работы является выбор RDF-хранилища, которое будет использоваться в качестве основы нашего проекта — экспертной системы, использующей семантический Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ анализ текстовой информации. Это хранилище должно максимально полно удовлетворять нашим требованиям функциональности и по возможности наиболее эффективно использо вать ресурсы машин, на которых оно будет работать.

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

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

— федеративность;

— поддержка именованных графов;

— хранение истории изменений;

— репликация (RDF-данные с сервера могут частично кэшироваться на машине клиента, оставаясь доступными даже при отсутствии связи с сервером);

— безопасность (безопасность именованных графов обеспечивает ролевая система контроля доступа);

— уведомления (клиент получает через JMS уведомления об изменениях триплетов и именованных графов);

— масштабируемость;

— совместимость со стандартами RDFS, OWL, SPARQL, Prolog;

— поддержка типов данных;

— кроссплатформенность.

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

— открытость;

— хорошая документированность;

— возможность загрузки данных в хранилище в формате RDF/XML;

— поддержка языка запросов SPARQL;

— наличие собственного API, либо совместимость с Jena API.

Описание RDF-хранилищ На сегодняшний день существует множество RDF-хранилищ, как от коммерческих компаний, так и от независимых разработчиков: Boca, D2RQ и D2R Server, Franz Inc’s AllegroGraph, Intellidimension’s RDF Gateway, Jena’s Joseki, Mulgara, OpenLink Virtuoso, Oracle Spatial 10g, OWLIM, Sesame, Tucana Suite, YARS, 3Store и другие. Рассмотрим несколько наиболее распространенных решений [3].

Jena — это популярный Java-фреймворк. Позволяет хранить данные как в реляционной базе данных (поддерживаются MySQL и PostgreSQL), так и в собственном формате. В данной статье рассмотрен вариант использования Jena с MySQL.

Aduna Sesame — это достаточно популярный открытый фреймворк для хранения данных и выполнения запросов к ним. Важным преимуществом этого фреймворка является его очень хорошая документированность.

OpenLink Virtuoso — универсальный сервер, обеспечивающий управление SQL-, XML и RDF-данными. Распространяется как под открытой, так и под коммерческой лицензиями.

Сравнение RDF-хранилищ Открытость. У всех рассматриваемых хранилищ имеется открытая версия.

Язык запросов. Все перечисленные RDF-хранилища поддерживают язык запросов SPARQL, рекомендованный консорциумом W3C и ставший в последнее время довольно по Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ пулярным. Фреймворк Jena требует отдельной установки SPARQL-сервера, но это не вызы вает особых затруднений.

Добавление данных в хранилище. Добавить RDF-данные в хранилище Sesame можно через web-интерфейс, а также программно в форматах RDF/XML, TriG, TriX, N-Triples, N3,Turtle. Virtuoso понимает форматы RDF/XML, Turtle, N3 / N-Triples, однако не предостав ляет удобного интерфейса для их добавления.

API. Sesame и Jena имеют собственные API;

Virtuoso обеспечивает совместимость по API и с Jena, и с Sesame.

Документация и информация по продукту Наиболее подробно документирован фреймворк Sesame — на сайте проекта доступна доку ментация по всем актуальным версиям продукта. По Jena также имеется достаточно документа ции, в том числе и подробная информация по всем способам хранения RDF-триплетов. RDF хранилище компании OpenLink является частью универсального сервера Virtuoso, и документа ция существует как часть общего руководства по этому программному продукту.

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

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

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

Бенчмарки Ниже представлены несколько бенчмарков для RDF-хранилищ [4]:

1. Lehigh University Benchmark (LUBM).

2. Ontology Benchmark (UOBM) — дополняет LUBM возможностями тестирования умозаключений и масштабируемости.

3. A Benchmark for Spatial Semantic Web Systems — расширяет LUBM пространствен ными данными.

Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ 4. Berlin SPARQL Benchmark (BSBM) — позволяет сравнивать производительность хранилищ RDF и именованных графов, а также систем, поддерживающих SPARQL.

5. The SP2Bench SPARQL Performance Benchmark — обеспечивает масштабируемый генератор RDF-данных и ряд стандартных запросов для них.

6. The ISLab Instance Matching Benchmark.

7. THALIA Testbed — позволяет тестировать выразительность языков, выполняющих разметку реляционных данных на RDF.

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

— время загрузки RDF-данных;

— размер хранилища;

— время ответа на запрос.

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

Результаты тестирования [5] рассмотренных выше хранилищ по этому набору критериев приведены в таблице (tз — время загрузки триплетов в хранилище;

tо — время ответа на за прос всей информации об определенном субъекте) Критерий Jena Sesame Virtuoso tз, с (15 млн триплетов) 70 22 tз, с(450 тыс триплетов) 6,3 2,3 1, tз, с(200 тыс триплетов) 5,2 2,4 1, tо, мс 560 400 300— tо, с (на запрос 2) 53 70—80 tо, с (на запрос 3) 14 260 Заключение Проанализировав существующие RDF-хранилища, авторы пришли к выводу, что по функциональности поддерживаемые разработчиками и постоянно обновляемые хранилища различаются слабо. Более значимым показателем для их сравнения является эффективность реализации данной функциональности, т.е. насколько хорошо они справляются с задачей обеспечения быстрой и удобной работы с хранящимися в них данными. Как видно из полу ченных количественных показателей, лучшим хранилищем по этим параметрам является Virtuoso. Однако Sesame по большинству параметров также показывает неплохие результаты, положительно выделяясь среди остальных решений наличием отличной документации (что очень важно при реализации первого проекта) и большим сообществом пользователей, осу ществляющих его поддержку и дальнейшее развитие.

ЛИТЕРАТУРА 1. Manola F., Miller E., McBride B. RDF Primer [Electronic resource]: http://www.w3.org/ TR/rdf-primer/.

2. Allemang D., Hendler J. Semantic Web for the working ontologist [Electronic resource]:

http://ais-portal.ru/2009/05/semantic-web-for-the-working-ontologist-dean-allemang-jim hendler-часть-1/http://ais-portal.ru/2009/07/semantic-web-for-the-working-ontologist-dean allemang-jim-hendler-Часть-2-Архитектура-semantic-web-пр/.

3. Навернюк М. Список инструментов Semantic Web [Electronic resource]:

http://www.semantictools.ru/tools/5-tools/12-toolslist.html.

Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ 4. Bizer Ch. RDF Store Benchmarking [Electronic resource]: http://esw.w3.org/topic/ RdfStoreBenchmarking.

5. Becker Ch. RDF Store Benchmarks with DBpedia [Electronic resource]: http://www4.wiwiss.

fu-berlin.de/benchmarks-200801/.

УДК 004. ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ В УПРАВЛЕНИИ ДИСТАНЦИОННЫМ ОБУЧЕНИЕМ Г. Ю. Громов, И. В. Громова, П. А. Беликов Рассмотрены возможные решения наиболее важных проблем современ ного дистанционного образования, оказывающих существенное влияние на развитие технологий и методов управления в этой сфере образова тельной деятельности вузов России, использован опыт ведущих евро пейских высших образовательных учреждений.

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

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

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

Стремление объединить наработки системы образования с новейшими информацион ными технологиями вызвано желанием сформировать в России открытое образовательное пространство, доступное для самых широких слоев населения. По этой же причине многие государственные и негосударственные учебные заведения разрабатывают и внедряют в прак тику технологии дистанционного, или открытого, обучения. Управление этими системами основано на использовании информационных технологий [1—7].

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

Управление ролями пользователей Управление ролями пользователей подразумевает обеспечение степени доступа к элек тронным учебно-методическим комплексам (УМК), размещенным в системе, и результатам учебного процесса. Степень доступа определяется не только группой безопасности пользова теля, но и рядом дополнительных факторов, к которым относятся: назначение тьютором (преподавателем) на дисциплину, назначение куратором на учебный план, права владения Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ подразделением, отношение подразделения к учебному плану или его элементам, права вла дения схемой, где размещены элементы УМК, права автора УМК или его элементов.

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

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

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

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

Мониторинг и управление качеством образования Электронный журнал дает пользователям возможность просмотра результатов успевае мости студентов по различным видам контроля знаний. Это приложение доступно всем поль зователям системы ДО, однако объем отображаемой информации зависит от роли конкретно го пользователя. Система содержит результаты запроса из базы данных различного рода ин формации (результаты обучения, мониторинг, статистика), представленные в удобном виде, имеется возможность продления сроков сессии с целью ликвидации студентами академиче ских задолженностей.

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

Анализ использования информационных технологий европейских вузов Анализ использования информационных технологий европейских вузов основан на опыте университетов Испании: Национального университета дистанционного образования в Мадриде UNED (Universidad Nacional de Educacion a Distancia) и Открытого университета Ка талонии в Барселоне UOC (Universitat Oberta de Catalunya).

Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ В целом технологии дистанционного образования этих университетах не отличаются от практики дистанционного обучения, используемой в лучших вузах России. Отличительными особенностями этих технологий является масштабность (филиалы действуют во всем мире) и массовость (более 200 тысяч студентов в 2008/2009 учебном году) [1]. Главной особенностью дистанционного обучения в высшем образовании Европы является наличие нормативно правовой базы. В Европе форма дистанционного обучения признана государством как само стоятельная форма обучения наряду с очной, очно-заочной и заочной. По результатам ди станционного обучения выдаются дипломы государственного образца, тогда как в России ди станционное обучение является лишь одной из технологий, обеспечивающих повышение эф фективности и качества образования.

Национальный университет дистанционного образования в Мадриде был создан для обеспечения равных возможностей доступа к высшему образованию для тех, кто по таким-то причинам (удаленное место жительства, полная трудовая занятость и т.п.) не может посещать занятия по программам, предлагаемым традиционными университетами. Особое место в об разовательной деятельности UNED в последние годы занимает решение таких важнейших социальных проблем общества, как доступ к высшему и дополнительному профессионально му образованию для инвалидов и людей, отбывающих временное наказание в местах заклю чения (тюрьмах). Для организации и управления учебным процессом ДО этот университет разрабатывает и постоянно совершенствует свою платформу для создания виртуальных кам пусов [1]. В 2008/2009 учебном году использовалась программная платформа WebCT, а в 2009/2010 учебном году будет осуществлен переход на платформу alf. Ее отличительной осо бенностью является расширение функций для поддержки ДО студентов, обучаемых в ассоци ированных центрах университета, а также для мониторинга и оценки качества образования. В частности, в этом году появится новая возможность, позволяющая осуществлять удаленный мониторинг активности работы студентов и тьюторов (преподавателей) в центрах. С этой це лью все процедуры выдачи, приемки и оценивания практических заданий, а также проведе ния дистанционных консультаций по ходу выполнения этих заданий фиксируются в среде виртуального кампуса. Кроме того, на платформе alf разработана новая технология для орга низации и проведения дистанционных защит проектных работ. Руководитель проекта в ре жиме многоточечной Интернет-конференции проводит прием выпускных работ студентов, находящихся в своих центрах, при этом каждый участник конференции может видеть и слы шать речь защищающегося, вопросы руководителя и ответы на них. Руководитель выступает в роли модератора конференции, передавая (по запросам студентов) право выступить в дис куссии при обсуждении результатов того или иного проекта.

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

— Социальные инструменты, обеспечивающие совместную работу (блоги, вики и т.д.);

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

— Современные средства синхронной и асинхронной коммуникации, которые обеспе чивают адаптацию студента в любой ситуации (видеоконференции, системы коллективного интеллекта в форумах и т.д.).

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

— Доступ к обучению с помощью мобильных устройств.

Новая платформа программы Campus 5.0, которая будет введена в действие в 2009/ учебном году, отличается гибкостью и адаптивностью по отношению ко всем участникам ди станционного учебного процесса [1]. Концепция новой платформы «Мой университет» ори ентирована на формирование индивидуальной информационно-образовательной среды сту Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ дента с возможностью включения/ выключения удаленных служб и ресурсов, трансформации систем меню и навигации, а также подключения извне новых приложений и ресурсов.

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

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

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

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

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

— При разработке информационно-образовательных сред и методов управления ди станционным обучением студентов в них следует ориентироваться на комплексное решение проблем образования в контексте требований федеральных ГОС третьего поколения и ре форм Болонского процесса.

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

ЛИТЕРАТУРА 1. Информационные технологии в университетском управлении: Сборник аналитических материалов по проекту ICT4UM. М.—Тверь: Твер. гос. ун-т, 2009. 308 с.

2. Васильев В.Н., Лямин А.В., Чежин М.С. Система дистанционного обучения второго поколения // Науч.-технич. вестн. СПбГУ ИТМО. 2007. Вып. 45. С. 148—157.

3. Васильев В.Н., Павлова А.А., Чежин М.С. Жизненный цикл электронного учебно методического комплекса в системе дистанционного обучения университета // Там же.

2009. Вып. 61. С. 94— 4. Лисицына Л.С. Теория и практика компетентностного обучения и аттестаций на основе сетевых информационных систем. СПб.: СПбГУ ИТМО, 2006. 147 с.

5. Лисицына Л.С. Средства и технологии для управления самостоятельной работой студентов. Методическое пособие. СПб: СПбГУ ИТМО, 2008. 53 с.

Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ 6. Лямин А.В., Плешкова М.В. Программирование структуры электронного курса // Тр. XIV Всеросс. науч.-метод конф. «Телематика'2007». СПб, 2007. Т. 1. - С. 211—212.

7. Лямин А.В., Чежин М.С. Модульное построение электронных учебно-методических комплексов для системы дистанционного обучения // Тр. XII Всеросс. науч.-метод. конф.

«Телематика'2005». СПб, 2005.

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

Ключевые слова: искусственный интеллект, индексация фактов, логический вывод.

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

Пусть база знаний содержит n атомов (элементарных фактов) вида f = (s,p,o), а также множество правил R = {r}, где s — субъект, p — предикат, o — объект. Каждое правило r со стоит результирующей части (консеквента) и тела (антецедента или условий правила). Для простоты будем считать, что консеквент содержит один атом, а тело — множество условий С = {c}. Пусть среднее число условий в одном правиле равно k, а мощность множества пра вил равна m. Каждое условие также состоит из атомов, причем субъекты и объекты как в кон секвенте, так и в антецеденте могут быть представлены константами либо переменными.

Запуск процедуры применения всех правил к множеству фактов вызывает последова тельный перебор всех фактов для каждого из условий правил. Общее число вершин A дерева решений равно A = mnk.

Фактическое число развертываемых вершин на дереве поиска зависит от метода поиска и от того, требуется ли найти первое подходящее решение или надо искать все решения. Дан ная формула показывает линейный рост сложности поиска от числа правил, степенную зави симость от числа фактов и показательную — от среднего числа условий в правиле. Таким об разом, комбинаторная сложность задачи даже для небольших баз знаний не позволяет решать ее путем «буквального» или «наивного» логического вывода. Заметим, что из этой формулы Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ следует, что декомпозиция правил способствует сокращению сложности задачи поиска.

Самым известным методом ускорения логического вывода является алгоритм Rete [2], используемый в экспертных системах CLIPS, Jess, Soar и др. В алгоритме предусматривается построение для каждого правила префиксного дерева, узлами которого являются условия правил. В каждом узле префиксного дерева создается список фактов из базы знаний, которые удовлетворяют условиям правила. Фактически это означает, что правило заранее применяется к имеющемуся множеству фактов, но вместо консеквентов запоминаются множества фактов для каждого из условий правил.

«Узким» местом алгоритма Rete является необходимость обновления префиксного дере ва при изменении фактов базы знаний. Большинство модификаций алгоритма Rete, например Modify-in-place, Scaffolding, Decision Tree [3], «нацелены» именно на ускорение изменения префиксного дерева. Между тем модификация множества фактов происходит в системах ис кусственного интеллекта постоянно, поскольку каждое правило дает в качестве результата но вые факты, которые должны сразу же использоваться в ходе резолюции. Указанные недостат ки привели к тому, что алгоритм Rete не получил широкого распространения.

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

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

fn = (i,s,p,o).

Для множества термов T = {t}, встречающегося в фактах в качестве субъекта, объекта или предиката, построим индекс в виде X {x} {(t, w,{itw })}, (1) где w — место данного терма в атоме (в качестве субъекта, предиката или объекта), {itw} — множество номеров фактов, имеющих терм t в роли w, w=(‘s’;

’p’;

’o’). Резолюция правила за ключается в установлении истинности условий и присвоении значений переменным.

Теперь при обращении к правилу, тело которого состоит из множества условий {c1,c2,…, ck}, где cj = (sj,pj,oj), sj — субъект, pj — предикат, oj — объект, (s;

o) = (t;

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

Для каждого из cj условий правила извлечение релевантных фактов для перечисленных сочетаний термов заключается в нахождении пересечений множеств индексов:

I j {its } {itp } {ito }, s j const,p j const, o j const;

I j {itp } {ito }, p j const, o j const;

I j {its } {itp }, s j const, p j const;

I j {itp }, p j const Каждой переменной v, используемой в j-м условии, из списков Ij можно поставить в со ответствие множество кортежей {i,ui}, где i — номер факта, i I j, ui — значение переменной v, извлекаемое из i-го факта. Если переменная v используется более чем в одном условии пра вила, пересечение U v {uv } {u} j jC Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ множеств значений переменной во всех cj условиях правила, в которых эта переменная ис пользуется, позволит сократить число фактов, требуемых для унификации этих условий. Для получения списка фактов Ivj, содержащих переменную v для j-го условия правила, где эта пе ременная встречается, достаточно выполнить операцию реляционного деления Ivj i, uiuv.

Наконец, если в условии правила cj участвуют более одной переменной, то пересечение списков Ij I vj vc j для каждой из двух переменных даст окончательный список фактов, которые отвечают j-му условию правила.

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

fn(1, ivan, has_a, computer). fn(7, ivan, parent, vasily).

fn(2, vasily, has_a, computer). fn(8, ivan, parent, andrey).

fn(3, ivan, is_a, person). fn(9, natalia, parent, vasily).

fn(4, natalia, is_a, person). fn(10, natalia, parent, andrey).

fn(5, vasily, is_a, person). fn(11, vasily, parent, stepan).

fn(6, natalia, has_a, byke). fn(12, andrey, parent, egor).

Построим для этих фактов индекс, как показано в формуле (1).

x(ivan, s, [1,3,7,8]). x(computer, o, [1,2]).

x(vasily, s, [2,5,11]). x(person, o, [3,4,5]).

x(natalia, s, [4,7,9,10]). x(byke, o, [6]).

x(andrey, s, [12]). x(vasily, o, [7,9]).

x(has_a, p, [1,2,6]). x(andrey, o, [8,10]).

x(is_a, p, [3,4,5]). x(stepan, o, [11]).

x(parent, p, [7,8,9,10,11,12]). x(egor, o, [12]).

Создадим правила в виде r(conditionList, resultingList) с использованием переменных, начинающихся с вопросительного знака, где conditionList — список условий, resultingList — список триплетов результата. Первое правило устанавливает, что субъект является грамотным, если он является человеком и имеет компьютер r([c(“?x”, is_a, person), c(“?x”, has_a, computer)], [f(“?x”, is_a, literal)].


Таблица 1.

Предварительный отбор фактов для правила ?x is_a literal Факт 1-е условие правила 2-е условие правила Исходное условие ?x, is_a, person ?x, has_a, computer Индекс для используемых термов x(is_a, p, [3,4,5]). x(has_a, p, [1,2,6]).

x(person, o, [3,4,5]). x(computer, o, [1,2]).

Пересечение по номерам ?x, s, [3,4,5] ?x, s, [1,2] Значения переменной ?x = [ivan, natalia, vasily] ?x = [ivan, vasily] Пересечение по значениям [ivan, vasily] Отфильтрованный индекс ?x, s, [3, 5] ?x, s, [1,2] Используем индекс для отбора фактов и находим пересечение значений переменной ?x, используемых во всех условиях.

[ivan, natalia, vasily] [ivan, vasily] = [ivan, vasily].

Фильтруем списки фактов, требуемых для резолюции каждого условия правила, вклю чая в них только значения термов, попавшие в пересечение. Для первого условия это факты Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ [3,5], а для второго — [1,2]. Таким образом, для резолюции правила требуется унифицировать условия правила с пятью фактами. Если не использовать индекс, то каждое условие правила нужно сопоставлять со всеми 12 фактами, всего 24 факта.

Создадим более сложное правило, определяющее отношение «прародитель» (grandparent):

r([c(“?x”, parent, “?y”), c(“?y”, parent, “?z”)], [f(“?x”, grandparent, “?z”)].

Таблица 2.

Предварительный отбор фактов для правила ?x grandparent ?z Факт 1-е условие правила 2-е условие правила Исходное условие “?x”, parent, “?y” “?y”, parent, “?z” Индекс для используемых термов x(parent, p, [7,8,9,10,11,12]). x(parent, p, [7,8,9,10,11,12]).

Пересечение по номерам ?x, s, [7,8,9,10,11,12]). ?y, s, [7,8,9,10,11,12]).

?y, o, [7,8,9,10,11,12]). ?z, o, [7,8,9,10,11,12]).

Значения переменной [vasily, andrey, vasily, andrey, [ivan, ivan, natalia, natalia, vasily, stepan, egor] andrey] Пересечение по значениям [vasily, andrey].

Отфильтрованный индекс [7,8,9,10] [11,12] Более одного раза в правиле встречается только переменная ?y;

пересечение ее допусти мых значений в первом и втором условиях равно [ vasily, andrey, vasily, andrey, stepan, egor] [ivan, ivan, natalia, natalia, vasily, andrey] = = [vasily, andrey].

В качестве допустимых значений переменной ?y получен список объектов, которые яв ляются одновременно родителями и детьми. Прореживаем список фактов для первого усло вия [7,8,9,10,11,12], оставляя в нем только факты, имеющие термы [vasily, andrey] в качества объекта. Получаем список [7,8,9,10]. Аналогично получаем список фактов [11,12] для второго условия. Находим пересечение номеров фактов, соответствующих каждой из переменных, в каждом из условий. Для первого условия [7,8,9,10,11,12] [7,8,9,10] = [7,8,9,10], для второго — [11,12] [7,8,9,10,11,12] = [11,12]. Таким образом, каждому из условий правила в процессе унификации будут предъявляться только факты, гарантированно порождающие результаты.

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

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

c(age, greater, 18), предварительному отбору подлежат все факты, имеющие в качестве субъекта age.

Оценка быстродействия алгоритма Предлагаемый здесь метод реализован в программе Semantic, разработанной специально для изучения принципов построения систем искусственного интеллекта, визуализации знаний, а также для исследований способов построения интеллектуальных агентов. Поскольку прямой логический вывод предполагает независимую обработку каждого правила, длительность вывода имеет линейную зависимость от числа правил. Следовательно, оценку быстродействия можно оценивать на одном правиле. Тестирование данного метода проводилось на базе знаний, описы вающей родственные отношения. Факты вида субъект-is_parent-объект создавались с помо щью генератора случайных чисел. Правило, которое использовалось для измерения времени вывода, описывает отношение типа «прапрародитель» и имеет три условия:

Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ r([с("?x1","is_parent","?x2"), с("?x2","is_parent","?x3"), с("?x3","is_parent","?x4")], [f("?x1","is_grandgrandparent","?x4")]).

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

Так, если в каждом правиле должны использоваться 10% фактов, то индексация и предвари тельный отбор фактов дают увеличение скорости на порядок. Если каждая комбинация ис ходных фактов приводит к успешной резолюции (ситуация, на практике маловероятная), то использование индексов только увеличивает время за счет издержек на индексацию.

Заключение Предлагаемый метод существенно отличается от алгоритма Rete. Главное отличие за ключается в том, только индексация фактов выполняется заблаговременно, а операция пред варительного отбора фактов выполняется непосредственно перед резолюцией. Это означает, что факты и правила могут существовать отдельно, в том числе на разных сетевых ресурсах, что соответствует концепции Глобальной Семантической Сети [4]. В ходе предварительного отбора фактов для каждого условия правила создаются множества кортежей значений пере менных, используя которые, можно в отдельных случаях отказаться от резолюции правил, а используя операции реляционной алгебры над кортежами, сразу получить множество реше ний правила. Тестирование метода индексации фактов показало его работоспособность и ускорение приблизительно на порядок по сравнению с «наивным» логическим выводом.

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

ЛИТЕРАТУРА 1. Рассел С., Норвиг П. Искусственный интеллект: Современный подход. М.: Изд. дом «Вильямс», 2006.

2. Forgy C. L. RETE: A fast algorithm for the many pattern / many object pattern match problem // Artificial Intelligence, 1982. Vol. 19. P. 17—37.

3. Doorenbos R. B. Production Matching for Large Learning Systems. PhD Theses. University of South California, 1995. 208 p.

4. Berners-Lee T., Hendler J., Lassila O. The Semantic Web // Scientific American Magazine.

2001. May.

Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ УДК 004.738. ПРИНЦИПЫ ПОСТРОЕНИЯ САЙТОВ С ИСПОЛЬЗОВАНИЕМ СИСТЕМЫ УПРАВЛЕНИЯ КОНТЕНТОМ С. А. Колюшин, А. А. Ожиганов Системы управления контентом (Content Management Systems — CMS) позволяют создавать сайты без навыков программирования, упрощают администрирование и обновление контента информационных ресурсов.

Приведена классификация CMS, описаны функции и проблемы подоб ных систем, представлены принципы построения web-сайтов с исполь зованием CMS.

Ключевые слова: система управления контентом, web-сайт.

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

Второй: воспользоваться помощью сторонних разработчиков, для создания сайт «под ключ».

И, наконец, — воспользоваться готовым решением.

В данный момент в интернете появились системы управления содержимым сайта (Con tent Management System — CMS), позволяющие реализовывать компромиссное решение меж ду низкой стоимостью статических сайтов и высокой гибкостью динамических [1]. Благодаря подобным системам резко повысилась управляемость сайтом и значительно снизились расхо ды на его администрирование.

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

Помимо модульной структуры построения сайтов идеализированные системы управле ния контентом обладают рядом отличительных качеств[2]:

— Малое время оборота страниц и их обновления.

— Качественная систематизация.

— Улучшенная навигация по сайту.

— Повышенная гибкость сайта.

— Поддержка децентрализованной разработки.

— Повышенная безопасность.

— Высокая маштабируемость.

— Небольшие затраты на обслуживание сайта.

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

Применительно к организациям, оперирующим огромным количеством информации, уместно говорить уже о системах управления информационными ресурсами предприятия (Enterprise Content Management — ECM) [3]. В результате термин «content management» рас Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ширился: им стали обозначать управление не только информацией на сайте, но и всеми раз розненными и разнообразными фрагментами корпоративной информации.


Поставщики автоматизированных систем и решений быстро оценили тенденции в обла сти Интернет-бизнеса. В 2001 г. Microsoft выпустил Content Management Server 2001. по ито гам 2003 г. корпорация IBM занимала 20 % всего рынка [1].

Классификация CMS — По функциональной и внутренней организации [2] (рис. 1).

Однопользовательские системы предназначены для создания одного сайта, т.е. факти чески CMS является самим сайтом. Пользователю предоставляется возможность настроить оформление сайта. Подобные системы бывают как бесплатными, так и коммерческими. Яр кие примеры: runCMS, PHPNuke.

Многопользовательские системы позволяют создавать некоторое множество сайтов:

разнообразных блоков значительно больше, чем однопользовательских систем. Есть возмож ность создания новых блоков, которые сохраняются в базе данных системы. Однако самосто ятельно, без CMS, сайт не будет работать, т.к. его выполнение обеспечивается за счет ядра системы. Как правило, подобные системы коммерческие, но есть и исключения: narod.ru.

Для решения конкретного типа задач строятся специализированные системы.

— По способу сборки страниц [1].

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

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

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

— По подходам к разработке [1].

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

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

CMS Функциональная и внутрен- Способ сборки стра- Подход к разработке няя организация ниц однопользовательские динамические универсализированные многопользовательские с динамической универсальные сборкой специализированные со статической сборкой Рис. 1. Классификация CMS Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ Функции CMS-систем Функциональные возможности систем управления контентом могут быть разделены на несколько основных категорий [2] (Рис. 2):

— Создание контента.

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

CMS также позволяет управлять структурой сайта. Многие из таких систем предлагают возможности по реструктурированию сайта без потерь внутренних связей. Кроме того во многих системах организована возможность администрирования сайта удаленно от среды разработки. Именно эта особенность — ключ к успеху CMS. Администрирование сайта мо жет быть передано непосредственно его владельцу.

— Управление контентом.

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

Использование подобной базы данных позволяет CMS обеспечивать ряд полезных осо бенностей.

— Существует возможность хранения всех версий страниц, а также журнала их изменений.

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

— Интеграция c существующими информационными источниками и системами IT.

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

— Публикация.

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

Вполне естественно, что каждый сайт должен отличаться внешне. Системы позволяют дизайнерам и web-разработчикам выбирать предложенные варианты оформления.

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

— Представление.

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

Рис. 2. Анатомия CMS Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ Недостатки CMS-систем В качестве основных недостатков CMS-систем можно выделить следующие.

— Шаблонный дизайн и расположение элементов сайта. Большинство популярных CMS-систем не позволяют создавать сайты с индивидуальным дизайном.

— Невозможность добавления собственных динамических блоков. Эта черта присуща многопользовательским CMS-системам, добавлять динамические блоки в которые может только администрация сайта. В однопользовательские же системы можно добавлять динами ческие блоки самостоятельно, однако нет инструментария для их создания. Кроме того, в од нопользовательских системах нет глобального хранилища блоков, в котором хранились бы все блоки, написанные для данной CMS-системы.

— Из-за ограниченного набора числа динамических блоков и невозможности простого создания собственных динамических блоков CMS-системы не способны создавать сайты лю бой сложности.

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

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

Этапы создания сайта с помощью CMS и их проблемы 1. Проектирование прототипа сайта. Определяется, какая информация и в какой форме будет представлена на сайте. Создается проект дизайна сайта. Этот процесс делится на сле дующие этапы.

— Формирование технического задания.

— Определение структуры меню и разделов сайта.

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

— Формирование списка шаблонов страниц с указанием динамических блоков, распо ложенных на них.

К сожалению, CMS-системы не предоставляют автоматизированных средств, для про ектирования макета сайта.

2. Установка и настройка необходимых динамических блоков.

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

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

— Отсутствие глобального хранилища блоков. Однопользовательские CMS-системы имеют ограниченное количество типовых блоков. Большинство из них имеет возможность присоединять новые блоки, а также создавать свои собственные. Однако CMS-системы не предоставляют возможности публиковать свои блоки в глобальных хранилищах блоков и при необходимости загружать блоки из глобального хранилища. Это существенно снижает функ циональность CMS-систем.

— Неотделимость созданного сайта от CMS-системы. Вариантом решения этой пробле мы является создание системы конструирования сайтов, которая позволит созданному сайту Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ работать отдельно от CMS. Такая система фактически будет генерировать код динамического сайта.

3. Задание параметров сайта (логотип, название, электронный адрес администратора и т.д.).

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

Явным недостатком CMS-систем является конечное, заданное разработчиками CMS, число параметров сайта. Разработчик сайта не может создавать свои собственные параметры и в дальнейшем с ними работать.

4. Наполнение сайта информацией и последующая его отладка.

Основной проблемой этапа наполнения информацией и обновления сайта является про блема неотделимости интерфейса администрирования от интерфейса создания сайта.

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

ЛИТЕРАТУРА 1. Базаров Р. Содержательная часть // CIO. 2004. № 10.

2. Robertson J. So,what is a content management system // KMC. 2003. june.

3. Макаров C. Что такое ECM // CIO. 2003. № 4.

Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ УДК 681.3. ИСПОЛЬЗОВАНИЕ ORACLE APEX ДЛЯ СОЗДАНИЯ КОРПОРАТИВНЫХ ИНТЕРНЕТ-ПРИЛОЖЕНИЙ В. В. Кириллов, А. А. Лаптева Обоснован выбор Oracle APEX как средства разработки и инфраструк туры для создания и выполнения web-приложений, основанных на базе данных Oracle. Разработано демонстрационное приложение, которое используется как пример в создаваемом учебном пособии по работе с Application Express. Рассматривается возможность организации практи ческого курса по изучению среды студентами. По результатам исследо ваний удалось сделать вывод, что данный продукт представляет собой одновременно полномасштабную среду разработки, внедрения и адми нистрирования приложений и рабочих пространств.

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

APEX представляет собой декларативное средство разработки и инфраструктуру для со здания и выполнения web-приложений, основанных на базе данных Oracle. APEX позволяет создавать порталы, как корпоративные, так и информационные, решающие следующие зада чи.

— объединение всей существующей корпоративной информации в единой системе web доступа;

— предоставление актуальной информации в режиме реального времени;

— генерация отчетности в табличной и графической форме;

— импорт—экспорт данных в форматах PDF и CSV;

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

— обеспечение механизма единой авторизации пользователей портала;

— предоставление и разграничение доступа сотрудников к необходимой им информации.

Oracle Application Express состоит из репозитория метаданных, где хранятся определе ния приложений, и механизм отображения и обработки страниц [1]. К нему обращаются че рез Web-браузер посредством встроенного в СУБД Oracle Web-сервера Embedded PL/SQL Gateway. Application Express полностью содержится в базе данных и представляет собой ядро Application Express и хранилище метаданных. Принцип работы Oracle Application Express.

— Данные о приложении (метаданные) хранятся в базе данных в виде таблиц, — Ядро Application Express преобразует метаданные и в режиме реального времени формирует визуальное представление (интерфейс, изображение) приложения.

Уникальный метод управления состоянием сеансов сводит к минимуму потребление ре сурсов процессора. Состоянием сеанса управляет база данных. Каждый просмотр страницы приводит к созданию нового сеанса базы данных, поэтому когда механизм Oracle Application Express не обрабатывает и не отображает страницу, ресурсы обработки базы данных не ис пользуются [2].

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

Сборник трудов молодых ученых и сотрудников кафедры ВТ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ни разработчику, ни конечному пользователю не требуется устанавливать на настольном компьютере программное обеспечение.

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

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

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

— Developers (разработчики) — это пользователи, которые создают и изменяют прило жения.

— End users (конечные пользователи) — это пользователи, которые имеют доступ к приложениям без использования внешних идентификационных схем.

Application Express содержит три главных средства разработки.

— Application Builder — создание динамических веб-приложений на основе баз данных.

— SQL Workshop — просмотр объектов баз данных, выполнение нерегламентирован ных запросов SQL, а также графический конструктор запросов.

— Utilities — загрузка и выгрузка данных для плоских файлов и электронных таблиц.

В процессе исследования продукта разработано приложение на основе базы данных ПАНСИОНАТ, в котором реализовано большинство стандартных функций [3, 4]. Сейчас в приложение добавляются дополнительные возможности продукта, такие как генерация диа грамм, возможности полноценного расширения с помощью PL/SQL, Javascript, печать PDF и др. Рассматривается возможность организации практического курса по изучению данной среды разработки студентами. Приложение используется как пример в создаваемом учебном пособие по работе с Application Express. Выбор базы обусловливается тем, что при изучении студентами СПбГУ ИТМО курса «Проектирование приложений к базам данных» пособие по созданию приложений спомощью Oracle Forms основывалось именно на базе ПАНСИОНАТ и она знакома студентам.

Заключение Oracle Application Express свободная среда разработки программного обеспечения на основе СУБД Oracle. Позволяет очень быстро проходить весь процесс разработки веб приложения. С помощью APEX можно разрабатывать как небольшие приложения с дюжиной пользователей, так и масштабные приложения корпоративного уровня с тысячами пользова телей. Предполагается использовать эту среду для расширения лекционного курса и лабора торного практикума по изучению студентами методов создания приложений к базам данных, а также для построения новой версии корпоративного портала СПбГУ ИТМО.

ЛИТЕРАТУРА 1. [Электронный ресурс]: http://www.apex-dev.blogspot.com/2007/05/1.html.

2. [Электронный ресурс]: http://www.ratprog.msevm.com/docum/oracle/apexint.htm.

3. Кириллов В.В. Основы проектирования реляционных баз данных. СПб: ИТМО, 1994. 88 с.

4. Кириллов В.В., Громов Г.Ю. Введение в реляционные базы данных. СПб: BHV-Петербург, 2009. 464 с.

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ УДК 004. СПОСОБЫ ФОРМАЛЬНОГО ОПИСАНИЯ АСИНХРОННЫХ СХЕМ А. А. Герасимов, П. В. Кустарев Рассмотрена проблема разработки асинхронных схем. Дан обзор суще ствующих методов описания асинхронных схем, используемых при их создании, автоматическом синтезе и анализе. Рассматриваются модели вычислений, применяемые при проектировании как на высоких уровнях абстракции (взаимодействующие процессы, взаимодействующие моду ли), так и на уровне вентильной реализации (конечные автоматы, графы изменений сигналов), а также средства временного анализа (графы зави симостей).

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

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

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

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



Pages:   || 2 | 3 | 4 |
 





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

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