Процессы управления и устойчивость

смежны, B и C смежны. В результате раскраски графа G и при-

ведения ее к минимальной получаем для случая, когда необходима

2НФ, две таблицы R

1

= {Z

1

, T

1

} и R

2

= {Z

2

, T

2

}, где Z

1

= {A, D, E},

Z

2

= {A, B, C}, для случая, когда необходима 3НФ, три таблицы

R

1

= {Z

1

, T

1

}, R

2

= {Z

2

, T

2

}, R

3

= {Z

3

, T

3

}, где Z

1

= {A, D, E},

Z

2

= {A, B}, Z

3

= {B, C}.

5. Заключение. Построена модель разбиения реляционной таб-

лицы на минимальное количество более простых таблиц по сравне-

нию с исходной. В модели учтены все аспекты данных, рассматри-

ваемые в реляционных таблицах: структура, целостность, обработка

данных. Модель позволяет построить отношения, нормализованные

до любой небходимой степени. Причем условие нормализованности

таблицы может отличаться от классических и быть дополненным

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

не одно, а все возможные решения для заданных условий разбиения,

причем количество таблиц в каждом разбиении будет минималь-

ным. Неоднозначность минимального разбиения позволяет выбрать

из множества таких разбиений те, которые будут удовлетворять до-

полнительным условиям.

Литература

1. Горьковой В.Ф. Экстремальные задачи на графах. СПб.: Изд-во

СПбГУ, 2004. 178 с.

2. Дейт К.Дж. Введение в системы баз данных, 7-е издание. М.: Из-

дательский дом ”Вильямс”, 2001. 1072 c.

329

Евчиц В.В.

Санкт-Петербургский государственный университет

Разработка средств автоматизации решений

задач транспортной логистики

Рекомендовано к публикации доцентом Гришкиным В.М.

1. Постановка задачи. В рыночных условиях важным тре-

бованием потребителя транспортных услуг является своевременная

и качественная доставка груза [1–4]. Выполнить заданные условия

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

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

математических методов позволяет оптимизировать работу отдель-

ных элементов транспортного процесса и объединить эти элементы

в единую систему.

Для каждой предстоящей грузоперевозки перед мультимодаль-

ной транспортной компанией возникает комплекс важных задач, ос-

новными из которых являются:

• скоординировать работу отделов и сотрудников, выполняющих

различные функции;

• учесть опыт предыдущих перевозок;

• выбрать

наиболее

удачную

комплектацию

перевозимого

груза;

• выбрать наиболее подходящий маршрут.

Наилучшее решение этих задач в комплексе не только помогает

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

критериев быстрота-качество-стоимость, но и напрямую является за-

логом успешного развития транспортного предприятия.

В данной работе рассматривается концепция построения специ-

ального программного продукта, предоставляющего возможность

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

бора оптимальной совокупности таких решений.

2. Логика работы. Разрабатываемое программное средство

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

нирования возможных транспортных маршрутов и товарных пото-

ков предстоящих грузоперевозок для мультимодальной транспорт-

330

ной компании. С точки зрения структурирования используемой ин-

формации будет уместно в дальнейшем именовать описываемое сред-

ство как "Реестр запросов" (РЗ). Каждый запрос в отдельности

представляет собой исчерпывающую информацию по интересующей

перевозке. В частности, это информация о заказчике товара, о по-

ставщике, о перевозчике, о самом товаре, об особенностях маршрута,

о стоимости производимых в маршруте операции и т.д. РЗ – средство

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

Пользовательский интерфейс программы сделан таким образом,

что создание нового запроса происходит последовательно, т.е. каж-

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

годаря такой организации механика создания запроса становится

прозрачной даже для пользователя, не обладающего специальны-

ми познаниями, а также значительно повышается простота освоения

программы, что является огромным плюсом.

Ниже по шагам с целью описания логики работы программы опи-

сывается последовательность создания запроса.

1. Первоначально пользователю предлагается ввести информа-

цию, которая носит исключительно справочный характер и не

играет особой роли в дальнейших этапах планирования. Здесь

указывается вся необходимая информация о перевозимом гру-

зе, заказчике, сотрудниках, выставляется категория сложности

перевозки.

2. На следующем этапе пользователем задаются начальные и ко-

нечные пункты перевозки. Суммарное количество пунктов от-

правления и приема груза не ограничивается двумя, благодаря

чему можно создавать достаточно сложные маршрутные схе-

мы.

3. На третьем этапе вводятся элементы спецификации – груз, под-

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

в спецификацию можно включить как груз "целиком", напри-

мер, грузовой кран, так и груз "по деталям", например, башня

крана, гусеничная основа, кабина и т.д. Каждая из таких вари-

аций создается в рамках новой спецификации в этом запросе.

Это сделано для того, чтобы составить несколько комплекта-

ций одного и того же товара и в дальнейшем после построения

возможных маршрутов для каждой из них выбрать наиболее

331

подходящую с точки зрения различных критериев: минималь-

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

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

зические параметры детали: длина, ширина, высота, вес, пло-

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

и конечный пункт прибытия груза.

4. РЗ позволяет создавать в рамках одного запроса для каждой

спецификации неограниченное количество различных модифи-

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

наиболее оптимальную для данной ситуации и данных требо-

ваний.

На данном этапе происходит построение возможного маршру-

та. С технологической точки зрения маршрут строится в два

этапа: построение географического маршрутного пути ("марш-

рутная карта") и указание причинно-следственных связей и

временных рамок ("диаграмма Гантта"). Такая организация

позволяет координировать многие аспекты, помогающие при-

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

• "Маршрутная карта" (рис. 1).

Структурно она состоит из набора "узлов", "маршрутов"

и "операций":

(a) "узлы". Начальные и конечные узлы заданы изна-

чально – те пункты погрузки и выгрузки груза, кото-

рые задаются пользователем на втором этапе. Поль-

зователь может лишь ввести и расположить промежу-

точные узлы, суммарное количество которых не огра-

ничено.

(b) "маршруты". Пользователь может организовать пере-

возку груза из одного узла в другой определенным

видом транспорта. Для этого ему достаточно просто

соединить эти узлы линией необходимого типа. При

этом все грузы, которые были в первом узле, автома-

тически переместятся во второй.

(c) "операции". Это действия, которые происходят с гру-

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

узел и каждый маршрут может содержать неогра-

ниченное количество операций. Для добавления но-

вой операции служит специальная кнопка, которая

332

есть на каждом узле и на каждом маршруте. При

добавлении появляется окно со списком возможных

для данной сущности операций. Также присутствует

возможность указать операцию, предшествующую до-

бавляемой. Это необходимо для того, чтобы програм-

ма помогла пользователю сформировать для данного

маршрутного пути временную и причинно-следствен-

ную диаграмму – диаграмму Гантта.

Рис. 1. Маршрутная карта

Существует возможность посмотреть, какие части груза

содержатся в том или ином узле, из какого пункта они

пришли и если были перевезены, то куда. Также, выбрав

какую-нибудь операцию, можно указать, какие части гру-

за участвуют в ней.

• "Диаграмма Гантта" (рис. 2).

Визуально, делится на две части. В левом окне представ-

лен список всех операций, их длительность. Можно до-

бавлять новые столбцы для ввода различной информа-

ции. В правом окне формируется временная и причинно-

следственная схема прокладываемого маршрута. Блоками

представлены операции, причем каждому блоку соответ-

ствует операция слева, находящаяся с ним на одной го-

ризонтали. Стрелки символизируют зависимости между

операциями.

5. Если на предыдущем этапе основной целью действий пользова-

теля было планирование возможного маршрута, то на данном

этапе производится его стоимостная оценка. Выводятся все опе-

рации по данному маршруту с дополнительной информацией,

333

Рис. 2. Диаграмма Гантта

существует возможность задать для каждой них персональную

формулу для расчета себестоимости, а также ввести дополни-

тельные столбцы, необходимые для этого расчета. В итоге под-

бивается общая себестоимость перевозки. Таким образом, по-

строив различные варианты возможных решений задачи пере-

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

из них, пользователь может выбрать наиболее подходящий.

3. Архитектура построения системы (рис. 3). Система ба-

зируется на двухуровневой клиент-серверной архитектуре на базе

Microsoft SQL Server. Сервер БД отвечает за хранение, управление и

целостность данных, а также обеспечивает возможность одновремен-

ного доступа нескольких пользователей. Помимо всего этого часть

бизнес-логики – основных правил работы системы – содержится на

сервере в виде хранимых процедур и пользовательских функций.

Клиентская часть представлена приложением, на котором сконцен-

трированы механизмы доступа к БД, часть логики работы системы,

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

ющие его модули.

Первоначально происходит загрузка объектов доступа к БД.

Выполняется авторизация пользователя. Если авторизация прошла

успешно, то инициализируются объекты для работы с БД. Они из-

влекают из БД необходимую информацию. Все объекты, осуществ-

ляющие соединение и обмен информацией с БД, на рисунке помече-

ны как "DB A".

Далее извлеченная информация передается в специальные гра-

фические модули ("IC"), которые структурно представляют собой

334

Рис. 3. Архитектура построения системы

совокупность как простых графических объектов – кнопок, тексто-

вых полей, окон для ввода текста, так и сложных ("EC") – специ-

альных таблиц с особой логикой поведения, выпадающих списков,

в которых информация представляется в виде дерева и т.д. Так как

зачастую такие сложные графические объекты пишутся сторонними

программистами и их вручную нужно подключать к разрабатывае-

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

обособить, что и показано на рисунке. С технологической же точки

зрения графические модули – инструменты, специально разработан-

ные для выполнения какой-либо комплексной задачи в рамках раз-

рабатываемого проекта: расчета себестоимости операций, создания

маршрутной карты и т.д. Эти модули располагаются на формах и

представляют пользовательский интерфейс ("UF"), именно их ви-

дит и с ними работает пользователь. При разработке и в процессе

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

хранится в особых классах ("LM").

Всю извлекаемую информацию можно логически поделить на две

категории: информация, представляемая только определенным гра-

фическим модулем, и информация, используемая сразу несколькими

графическими модулями. Было решено хранить общую информацию

335

в формате XML, как наиболее гибком и удобном способе представле-

ния данных. Специальный класс ("XML CC") выполняет все основ-

ные, связанные с обработкой общей информации функции: добавле-

ние, удаление, частичное удаление, выборка определенных данных и

т.д. Также он отвечает за синхронизацию использующих общую ин-

формацию элементов – передает изменения, сделанные в одном мо-

дуле, другим элементам, которые отражают их пользователю долж-

ным образом. Синхронизация графических модулей реализована с

помощью механизма событий.

При добавлении или изменении пользователем какой-либо ин-

формации соответствующие изменения отражаются и в объектах,

осуществляющих обмен информацией с БД, но в саму БД пока не

вносятся. И только лишь когда пользователь дает команду "Сохра-

нить", вся информация, которая на данный момент хранится в объ-

ектах, подается на вход в хранимые процедуры, которые записывают

эти данные в соответствующие таблицы.

4. Заключение. В настоящее время программный продукт нахо-

дится на стадии опытного тестирования. Если он зарекомендует себя

в практическом использовании, то работа над проектом будет про-

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

и контроля за протекающими в настоящий момент грузоперевозка-

ми.

Литература

1. Горелов П.П. Транспортные свойства и характеристики грузов:

Справочник. СПб.: ЗАО "ЦНИИМФ", 1999.

2. Карбанович И.И. Международные автомобильные перевозки.

Мн.: Юнипак, 2002.

3. Саркисов СВ. Управление логистикой. М.: Бизнес-школа, 2001.

4. http://www.logistics.ru, http://www.interlogistics.com

336

Завьялов Д.С.

Санкт-Петербургский государственный университет

Морфологический анализ естественного языка

Рекомендовано к публикации доцентом Кривцовым А.Н.

Аннотация. Разработана библиотека для морфологического ана-

лиза русского языка. Словарь, используемый при анализе, базиру-

ется на грамматическом словаре А.А. Зализняка [1]. В качестве ре-

ализуемого алгоритма используется алгоритм В.А. Тузова [2, 3].

Введение. Основное назначение морфологического анализа тек-

стов заключается в определении морфологических признаков слов

текста и в определении канонических (начальных, нормализован-

ных) форм слов. Задача является актуальной для любых ком-

пьютерных систем, обрабатывающих тексты на естественном языке

(информационно-поисковые системы, электронные библиотеки, ав-

томатические текстовые классификаторы, фильтры и др.).

Метод морфологического анализа. Построение морфологи-

ческого анализатора не требует решения каких-либо принципиально

теоретических проблем. Однако сложность чисто технической реа-

лизации для получения достоверных и значимых сведений ставит

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

сведения делает необходимым условием формализации языка.

При строго математическом подходе любая задача распадается

на две подзадачи – прямую и обратную. В случае морфологическо-

го анализа прямой задачей является генерация по основной форме

слова (единственное число, именительный падеж – для склоняемых

частей речи, инфинитив – для глаголов) всей парадигмы этого сло-

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

его основную форму, получив морфологический описатель этой про-

извольной формы.

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

русского языка позволяет прямую задачу – построение полной па-

радигмы основной формы слова – решить достаточно просто с точ-

ки зрения теории. Однако практически потребовалась длительная

и кропотливая рутинная работа по переложению этого процесса на

вычислительные возможности компьютера.

337

Как уже отмечалось, в качестве исходного словаря был выбран

словарь А.А. Зализняка. Но в прямом виде словарная статья, за-

несенная в компьютер, не имеет никакой практической значимости

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

сти на машинный язык весь механизм генерации, описанный в этом

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

рого состоят из слова, морфологического описателя и адреса набора

окончаний в словаре окончаний и выглядят так:

1. АНАЛИЗ м1 12

2. СУМАСБРОД м1о 12

3. ТЕМНЕТЬ г1нН 1552

Но этого недостаточно для решения прямой задачи. Дело в том,

что слово в предложении может сильно отличаться от своей исходной

формы. И дело здесь не только в окончании слов, а в изменении ос-

новы слова. Существует несколько тысяч слов с сильно изменяемой

основой (изменения могут наблюдаться уже во второй или третьей

букве). Например, СОН, СПАТЬ, СНОВИДЕНИЕ, БЕСПРОСЫП-

НЫЙ. Эти изменения зависят от морфологических и семантических

свойств слова. Следовательно, при генерации словоформ необходимо

отслеживать такие изменяемые слова. С этой целью были построе-

ны два рабочих словаря. В первом находятся все слова, парадигма

которых содержит формы, отличающиеся двумя первыми символа-

ми (с учетом перекодировки) от основной формы; во втором – тремя

символами. Фрагмент первого словаря (osn1):

1. БОЕ БОЙ м6о 238

2. ПАШ ПАХАТЬ г6н 36759

3. ПН ПЕНЬ м2 2769

Фрагмент второго словаря (osn2):

1. ЛАЙКА ж3 891

2. ТАЯТЬ г6нН 5614

3. ЧАСТЫЙ п1@ 23008

Наличие только этих рабочих словарей уже достаточно для то-

го, чтобы построить парадигмы всех слов, входящих в основной сло-

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

парадигмы по произвольно задаваемому слову. Чтобы решить эту

338

подзадачу, были созданы рабочие словари информационных окон-

чаний. В этих словарях сгруппированы сведения о последних слогах

слов основного словаря по количеству входящих в них букв. Макси-

мальная длина таких окончаний может содержать до восьми симво-

лов, поэтому и словарей окончаний также восемь (tail1 – tail8).

После этого стало возможным по произвольной форме слова по-

строить его полную парадигму и, тем самым, прямая задача была

решена.

Механизм генерации словоформ. Вначале (первый этап) по-

иск парадигмы заданного слова осуществляется по первым его бук-

вам в словарях основ. Сначала в словаре тех слов, парадигма ко-

торых содержит формы, отличающиеся от основной формы двумя

первыми символами (osn1). Если там такого слова нет, то поиск про-

исходит в аналогичном словаре, но уже по первым трем символам

(osn2). Если и там слово не найдено, то делается вывод о том, что ис-

ходное слово не относится к словам с сильно изменяющейся основой

и алгоритм поиска переходит к следующему этапу. Но и нахождение

прообраза этого слова в любом из словарей не гарантирует, что его

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

же по написанию слово может нести различные смысловые значения,

например, ПЕЧЬ – имя существительное и ПЕЧЬ – глагол. Поэтому

генератор предусматривает проверку наличия парадигмы последо-

вательно на всех этапах генерации, отсечение полностью совпавших,

если таковые будут, и сохранение оставшихся после последнего эта-

па.

На втором этапе поиска происходит обращение к словарям окон-

чаний. Здесь анализируются последние (от восьми до одного) сим-

волы слова и, в случае нахождения таковых, они автоматически от-

брасываются и с оставшейся частью генератор переходит к поиску

его словоформ в словаре основ. В случае отсутствия окончаний слово

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

по словарным статьям основного словаря.

На третьем этапе строится полная парадигма слова путем при-

соединения окончаний из словаря окончаний и проверки на допу-

стимость. Данная проверка необходима для того, чтобы отбросить

"лишние" основные формы. Например, слово "стола". При анализе

данного слова анализатор, при проходе по словарю, также выберет

слово "столб". Но после присоединения окончаний из словаря окон-

339

чаний нельзя получить словоформу "стола", какое бы окончание не

присоединяли к "столб". Тем самым данный подход позволяет полу-

чить все словоформы, исключая "лишние".

Обратная задача. В результате реализации прямой задачи

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

слова. Первый из них – основной морфологический описатель слова-

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

слова – его окончание.

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

речи разбить определенным образом на соответствующие классы,

характеризующие то или иное морфологическое свойство данного

класса. По существу, это законы образования словоформ. И если об-

ратиться к такой таблице и в ее структуре найти поле (столбец),

описывающее основную форму, то по уникальному и единственному

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

является морфологическим описателем данного слова. Таким обра-

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

жүктеу/скачать 30,48 Mb.

Достарыңызбен бөлісу: