Главная > Документ


В результате вычислительных исследований на компьютере с процессором Intel Core 2 Duo, 3,16 ГГц (ОЗУ 2 Гб) установлено, что продолжительность синтеза полной совокупности эффективных оценок и соответствующих им оптимально-компромиссных стратегий обслуживания не превышает 68 с, объем требуемой оперативной памяти не превышает 1,5 Гб, что позволяет рекомендовать разработанный алгоритм для включения в автоматизированные системы диспетчеризации процессов рассмотренного типа.

Список литературы: 1Коган Д.И. Задача диспетчеризации: анализ вычислительной сложности и полиномиально разрешимые подклассы / Д.И. Коган, Ю.С. Федосенко / Дискретная математика. – 1996. – Т. 8. – Вып. 3. – С. 135-147. 2Коган Д.И. Проблема синтеза оптимального расписания обслуживания бинарного потока объектов mobile-процессором / Д.И. Коган, Ю.С. Федосенко, А.В. Шеянов / Труды III Международной конференции ";Дискретные модели в теории управляющих систем";, Москва, 1998. – М.: Изд-во МГУ им. М.В. Ломоносова. 1998. – С. 43-46. 3Подиновский В.В. Парето-оптимальные решения многокритериальных задач / В.ВПодиновский, В.ДНогин. – М.: Физматлит, 2007. – 256 с. 4Лотов В.А. Многокритериальные задачи принятия решений / В.А. Лотов, И.И. Поспелова. – М: МАКС Пресс, 2008. – 197 с. 5Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982. – 416 c. 6Беллман Р. Прикладные задачи динамического программирования / Р. Беллман, С. Дрейфус. – М.: Наука, 1965. – 457 с. 7Коган Д.И. Динамическое программирование и дискретная многокритериальная оптимизация / Д.И. Коган. – Н. Новгород: Изд-во ННГУ, 2005. – 260 с. 8Кормен Т. Алгоритмы: построение и анализ / ТКормен, ЧЛейзерсон, РРивест, КШтайн. – М.: Вильямс, 2007. – 1296 с.

УДК 681.31+519.8

Синтез обмежених за структурою оптимально-компромісних стратегій обслуговування потоку об'єктів / Федосенко Ю.С., Куiмова А.С. // Вісник НТУ ";ХПІ";. Тематичний випуск: Інформатика і моделювання. – Харків: НТУ ";ХПІ";. – 2011. – № 17. – С. 70 – 75.

Вводиться модель однофазного обслуговування детермінованого потоку об'єктів. Формулюється бікрітеріальная завдання синтезу стратегій обслуговування. Показано, що врахування обмежень на структуру стратегій обслуговування виводить завдання з класу NP-важких та дозволяє побудувати поліноміальний алгоритм синтезу стратегій обслуговування, оптимальних за Парето. Наводиться приклад. Бібліогр.: 8 назв.

Ключові слова: стратегії обслуговування, NP-важкий, оптимальність за Парето.

UDC 681.31+519.8

The synthesis of structure-bounded optimal compromise service policies of object flow / Fedosenko Yu.S., Kuimova A.S. // Herald of the National Technical University ";KhPI";. Subject issue: Information Science and Modelling. – Kharkov: NTU ";KhPI";. – 2011. – №. 17. – P. 70 – 75.

In this paper a model of single-phase service of deterministic objects flow is discussed. A bicriteria problem of service policies synthesis is formulated. It is shown that if restrictions on service policies structure are imposed the problem will become non NP-hard and it will be possible to design a polynomial algorithm for Pareto-optimal service policies synthesis. Example is introduced. Refs.: 8 titles.

Key words: service policies, NP-hardness, Pareto optimality.

Поступила в редакцию 15.02.2011

УДК 81.322.3:81.366

А.І. КУРСІН, зав. лаб. НТУ ";ХПІ";, Харків

МЕТОД НОРМАЛІЗАЦІЇ СЛОВОФОРМ ЗІ СЛОВНИКОМ ПОЧАТКОВИХ ФОРМ СЛІВ БЕЗ ГРАМАТИЧНОЇ ІНФОРМАЦІЇ

Запропоновано оригінальний метод нормалізації словоформ флективних мов з використанням словника початкових форм слів, в якому слова не мають кодів типу словозміни. Такий алгоритм хоча і використовує словник, але не потребує граматичного кодування слів у ньому, хоча і вираховує можливі початкові форми за таблицею псевдо-закінчень, але досягає більшої точності, перевіряючи результати за словником. Табл.: 2. Бібліогр.: 8 назв.

Ключові слова: нормалізація словоформ, словник початкових форм.

Постановка проблеми і аналіз літератури. Неодмінною складовою більшості систем автоматичної обробки природномовної текстової інформації є етап морфологічного аналізу словоформ. На цьому етапі встановлюється початкова форма слова, його граматичний клас та граматична інформація щодо форми слова. Для великого класу задач, наприклад, інформаційного пошуку, буває достатньо лише встановлення початкової форми слова (ця операція ще називається нормалізацією словоформ або лемматизацією).

Традиційно алгоритми морфологічного аналізу розділяються на словникові і безсловникові. Словниковий алгоритм [1 – 3] оперує словником слів або основ з приписаною їм інформацією щодо граматичних категорій слова та типу словозміни [4]. Одним з суттєвих недоліків такого підходу є великі трудозатрати на створення такого словника, бо граматичне кодування слів попри всі спроби автоматизації виконується в значній мірі вручну. Безсловниковий алгоритм [5, 6] замість словника використовує списки флексій, квазі-флексій, квазі-суфіксів, притаманних словам даної мови, і робить аналіз, перевіряючи кінець словоформи за цими списками. Безумовною перевагою таких алгоритмів є те, що множина слів, які можуть бути ними оброблені, не обмежується рамками словників, що використовуються. Але безсловникові алгоритми зазвичай відрізняє менша точність аналізу, більша кількість хибних варіантів, хоча й дещо більша швидкість роботи.

Мета статті – описати оригінальний алгоритм нормалізації словоформ, який поєднує властивості обох типів алгоритмів морфологічного аналізу та частково позбавлений недоліків їх обох. Такий алгоритм хоча і використовує словник, але не потребує граматичного кодування слів у ньому, хоча і вираховує можливі початкові форми за таблицею псевдо-закінчень, але досягає більшої точності, перевіряючи результати за словником.

Опис задачі. Скажемо декілька слів про задачу, яка дала поштовх до розробки алгоритму. Створювалася програма підтримки електронних словників з функцією пошуку в них довільних форм слів. Виявилося, що словники, якими мала бути наповнена система, містять багато слів відсутніх у словникові наявної процедури морфологічного аналізу, а введення їх до цього словника разом з граматичним кодуванням було неприйнятним через стислі строки відведені для виконання робіт. Тоді з’явилася ідея, використовуючи морфологічні таблиці словникового алгоритму, генерувати всі можливі початкові форми для даної довільної форми слова, а потім ";просіювати"; їх по списку початкових форм слів словника.

Опис алгоритму. Класичний словниковий алгоритм морфологічного аналізу [1, 2] разом зі словником використовує морфологічні таблиці, зокрема таблицю парадигм. Кожний з рядків цієї таблиці відповідає певній парадигмі або типу словозміни, а кожна позиція в рядку – певній формі слова і містить відповідну флексію. На базі цієї таблиці ми створили власну, кожний рядок якої містить одну з флексій непрямих форм слів та всі флексії початкових форм, що зустрічаються спільно з нею в парадигмах. Фрагмент такої таблиці показаний в табл. 1.

Таблиця 1. Флексії непрямої форми та початкових форм

Флексія непрямої форми

Флексії початкових форм

-ет

-ть, -ять, -ти, -уть, -вать, -ать, -ить, -оть, -ь

-ете

-ть, -ять, -ти, -уть, -вать, -ать, -ить, -оть, -ь

-етесь

-ться, -яться, -уться, -аться, -оться, -тись, -ваться, -иться, -ься

-ется

-ться, -яться, -уться, -аться, -оться, -тись, -ваться, -иться, -ься

-ех

-ехсот

-иста

-ехстах

-иста

-ец

-цы, -ьца, -ца, -ьцо

-ешь

-ть, -ять, -ти, -уть, -вать, -ать, -ить, -оть, -ь

-ешься

-ться, -яться, -уться, -аться, -оться, -тись, -ваться, -иться, -ься

Для певної словоформи алгоритм знаходить в таблиці всі можливі для неї флексії непрямих форм. Та будує потенційні варіанти початкових форм слова, використовуючи флексії з відповідних рядків таблиці. Приклад такого списку для російської словоформи ";девочкой"; наведений в табл. 2.

Таблиця 2. Список для словоформи ";девочкой";

девочкый

девочкоить

девочкойя

девочкий

девочкыть

девочка

девочкая

девочкеть

девочко

девочкое

девочкоять

Потім проводиться пошук початкових форм зі списку в індексі початкових форм слів словника. Звісно, згенерований список початкових форм містить багато хибних варіантів. Але зазвичай лише один з них збігається з якою-небудь початковою формою зі словника. Ми були самі здивовані результатами попередніх тестів, які показали, що алгоритм ";не сходиться";, тобто дає більше одного можливого результату, або не дає жодного збігу, лише для 6% російських словоформ і 4% українських. До цих відсотків входили також і дійсні омоформи, тобто такі випадки, де і людина не може зробити однозначну нормалізацію, не вдаючись до контексту.

Згодом морфологічна таблиця даного алгоритму була вдосконалена за матеріалами граматичного словника Залізняка [4]. Всі непрямі закінчення довжини менш ніж 4 були розширенні до цієї довжини додаванням останніх літер основ, з якими вони вживаються. Таке ж розширення було проведене і з деякими окремими закінченнями, які давали суттєву кількість хибних результатів. Короткі слова (переважно службові слова, займенники, тощо) були винесені в окремий список стоп-слів (300 – 400 одиниць). Також, зважаючи на задачу, в якій застосовувався даний алгоритм, виявилося доцільним ввести певний пріоритет закінчень у таблиці. Наприклад, непрямі форми дієприкметників (напр., ";пораненими";) спершу приводяться до чоловічого роду однини (";поранений";), і лише за відсутності такої форми в словнику, проводиться пошук неозначеної форми дієслова (";поранити";).

В результаті зазначених вдосконалень кількість випадків ";несходимості"; алгоритму зменшилася для російської мови – до 3,3%, з яких 2,7% складають дійсні омоформи.

Зауваження щодо реалізації. Будь-якийалгоритм, що стосується пошуку інформації у словнику і претендує на практичну реалізацію, мусить мати достатньо швидку пошукову частину. В нашому випадку кількість пошукових операцій у словнику зростає завдяки великій кількості хибних початкових форм, які приймають участь у пошуку (в середньому в 15,1 рази для російської мови). Тому треба було вжити заходи для забезпечення достатньої швидкості пошуку. Ми використовували індексацію слів словника за допомогою В дерева [7] з ключами мінливої довжини зі стисненням методом Купера [8]. Така структура поєднує можливість швидкого пошуку строкових ключів з компактним об’ємом індексу. Збільшення кількості пошукових ключів для однієї словоформи нівелюється пакетним пошуком в індексі відразу всього списку початкових форм. Швидкість нормалізації в тестах складала приблизно 25 мс на тисячу словоформ (AMD Athlon 2.2 ГГц).

На базі описаного алгоритму ми розробили процедури нормалізації для російської та української мов, а також для англійської мови. В останньому випадку замість використання таблиць флексій працює підпрограма, яка генерує можливі початкові форми слів за правилами англійської мови. Ці процедури нормалізації використовуються в ряді інформаційно-пошукових та лінгвістичних систем, як в своєму первинному варіанті – для пошуку довільної форми слова у списку початкових форм слів, так і у вигляді окремого модуля нормалізації, який комплектується достатньо великим словником слів відповідної мови. Перевага практичного використання даного алгоритму в тому, що укладачі словника позбавляються кодування ключових слів щодо типу їх словозміни. Проблему обробки незнайомих слів ми не вирішуємо кардинально, але процедура поповнення словника новими словами також значно спрощується. Завдяки використанню достатньо швидкого пошукового індексу, наша процедура нормалізації може замінити собою пошук ключових слів в індексі інформаційно-пошукової системи.

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

Список літератури: 1.Белоногов Г.Г. Алгоритм морфологического анализа русских слов / Г.Г. Белоногов, Ю.Г. Зеленков // Вопр. инф. теории и практики. – М.: 1985. – № 53. – С. 62–93. 2. Антошкина Ж.Г. Морфологический процессор русского языка / Ж.Г. Антошкина // Бюллетень машинного фонда русского языка. – М.: 1996. – Вып. 3. – С. 53–57. 3. Сегалович И. Русский морфологический анализ и синтез с генерацией моделей словоизменения для не описанных в словаре слов / И. Сегалович, М. Маслов // Труды международного семинара Диалог'98 по компьютерной лингвистике и её приложениям. – Том 2. – 1998. – С. 547–552. 4. Зализняк А.А. Грамматический словарь русского языка / А.А. Зализняк. – М.: Русские словари, 2003. – 795 с. 5. Sheremetyeva S.Rapid Deployment Morphology / S. Sheremetyeva, W. Jin,S. Nirenburg// Machine Translation. – 1998. – Vol. 13. – № 4. – С. 239–268. 6.Ножов И.М. Прикладной морфологический анализ без словаря / И.М. Ножов // КИИ-2000. Труды конференции. – М.: 2000. – Т.1. – С. 424–429. 7Bayer R. Organization and Maintenance of Large Ordered Indexes / R. Bayer, E. McCreight // Acta Informatica. – 1972. – № 1 (3). – P. 173–189. 8. Cooper W.S. The storage problem / W.S. Cooper  // Mechanical Translation. – 1958. – Vol. 5. – № 2. – P. 74–83.

Стаття представлена д.т.н., проф. НТУ ";ХПІ"; Серковим О.А.

УДК 81.322.3:81.366

Метод нормализации словоформ со словарём начальных форм слов без грамматической информации / Курсин А.И. // Вестник НТУ ";ХПИ";. Тематический выпуск: Информатика и моделирование. — Харьков: НТУ ";ХПИ";. – 2011. – № 17. – С. 76 – 80.

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

Ключевые слова: нормализация словоформ, словарь начальных форм.

UDC 81.322.3:81.366

Word form normalization method using a dictionary of citation word forms without grammatical codes / Kursin A.I. // Herald of the National Technical University ";KhPI";. Subject issue: Information Science and Modelling. – Kharkov: NTU ";KhPI";. – 2011. – №. 17. – P. 76 – 80.

An original method of word form normalization if proposed for inflectional languages. The method eliminates the necessity of inflection type codes for words in a dictionary used for normalization. Such algorithm uses a dictionary though, but does not need grammatical code of words in him, though calculates possible initial forms after the table of psevdo-end, but arrives at greater exactness, checking up results after a dictionary. Tabl.: 2. Refs.: 8 titles

Keywords: word form normalization, dictionary of initial forms.

Надійшла до редакції 22.04.2010

УДК 004.02

В.В. ЛЮБЧЕНКО, к.т.н., доц. ОНПУ, Одеса,

О.С. ШИНКАРЮК, бакалавр ОНПУ, Одеса

МЕТОД БУДУВАННЯ НАВЧАЛЬНОЇ ТРАЄКТОРІЇ В УМОВАХ МОБІЛЬНОГО НАВЧАННЯ

Розглянуто вплив на вимоги до навчального матеріалу обмеженості у часі сеансів навчання в умовах мобільного навчання. Модифіковано алгоритм визначення компонент сильної зв’язності для застосування його до змішаних графів з метою отримання декомпозиції навчального курсу. Запропоновано метод будування навчальної траєкторії на основі множин пов’язаних навчальних концептів. Бібліогр.: 8 назв.

Ключові слова: мобільне навчання, компоненти сильної зв’язності, декомпозиція навчального курсу, навчальна траєкторія.

Постановка проблеми. Стрімкий розвиток та популяризація мобільних пристроїв, таких як смартфони, нетбуки, планшетні комп'ютери, карманні персональні комп‘ютери (КПК) і мобільні телефони, призвів до виникнення ідеї про їх використання в процесі навчання для створення освітнього середовища. Мобільне навчання (m learning) – це форма навчання, яка комбінує можливості мобільних обчислювальних пристроїв з можливостями електронного навчання [1].

Мобільне навчання повинно давати можливість об’єктам навчання отримувати необхідну інформацію, що стосується навчального курсу, в будь-який час та з будь-якого місця. Цією інформацією можуть бути адаптовані навчальні матеріали, приклади практичного застосування теоретичного матеріалу, посилання на додаткові ресурси тощо. Процес навчання здійснюється відповідно до навчальної траєкторії – логічної послідовності вивчення навчального курсу, яка дозволяє досягти всі навчальні цілі цього курсу. Але при будуванні навчальної траєкторії слід враховувати особливість мобільного навчання – обмеження у часі сеансів навчання, які пов’язані з його технічними (наприклад, обмеження заряду джерела енергії мобільного пристрою) та організаційними (наприклад, мобільність об’єкта навчання) умовами.

Аналіз літератури. Будування навчальної траєкторії є дослідженим питанням в галузі електронного навчання. Знання об’єкта навчання в будь-якій області найчастіше представляються оверлейною моделлю, яка заснована на структурній моделі предметної області [2, 3] представленій як мережа концептів. Концепти пов'язані один з одним, утворюючи в такий спосіб семантичну мережу, яка відбиває структуру предметної області навчального курсу. Ідея оверлейної моделі полягає в тому, щоб представити знання об’єкту навчання з певної теми як перекриття або накладення на модель предметної області. Для кожного концепту моделі предметної області, індивідуальна оверлейна модель зберігає визначене значення, яке є оцінкою рівня знань об’єкту навчання щодо цього концепту.

Слід зазначити, що всі роботи з цієї тематики як одиниці, на яких виконується будування навчальної траєкторії, розглядають окремі концепти навчального курсу або окремі об’єкти навчального матеріалу [4]. Такий підхід є цілком виправданим в умовах, коли об’єкт навчання має постійний доступ до навчального ресурсу. Але в умовах мобільного навчання він призводить до певних утруднень. Для ефективного використання мобільних ресурсів об’єкт навчання має завантажувати на свій пристрій матеріали, які пов’язані з певною множиною навчальних концептів. Проте існуючи методи будування навчальної траєкторії не надають рекомендацій щодо формування подібних множин. Отже об’єкт навчання може спотворити заплановану в навчальному курсі послідовність вивчення концептів, чим погіршить власне розуміння навчального матеріалу.

Мета роботи – розробка методу будування навчальної траєкторії для використання в умовах мобільного навчання, який забезпечує поліпшення розуміння навчального матеріалу в умовах обмежених у часі сеансів навчання.

Математична модель структури навчального матеріалу. Як показано в [5], для аналізу структурованості і логічної зв’язності навчального матеріалу – головних факторів, що визначають його якість – доречно використовувати апарат асоціативних зв’язків і побудовану на їх основі асоціативну карту навчального курсу. Асоціативна карта – це змішаний граф, вершинам якого відповідають концепти навчального матеріалу, а ребрам/дугам – визначені на цих концептах асоціативні зв'язки. Цей граф є зваженим, вагові коефіцієнти ребер/дуг визначаються мірою асоціативного зв’язку , який моделюється відповідними ребрами/дугами. Очевидно, що множинам пов’язаних концептів навчального курсу відповідають підграфи асоціативної карти.

Ключовою властивістю шуканих множин пов’язаних концептів – навчальних модулів – є їх незалежність. Для того, щоб отримати незалежний навчальний модуль слід дотримуватися принципів зв’язності і зчеплення [6]. Принцип зв’язності полягає в тому, що кожен навчальний модуль має бути сконцентрований на одній і тільки на одній цілі. Відбір і організація контенту і діяльностей для навчального модуля зосереджена на його цілі. Принцип зчеплення стверджує, що навчальний модуль має бути як найменше прив'язаний до інших модулів. Тобто зміст навчального модуля не повинен посилатися та використовувати матеріал іншого навчального модуля таким чином, щоб створювати необхідні залежності, оскільки потім цей модуль не може бути використаний незалежно від інших.

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

Алгоритм будування декомпозиції. В умовах обмеження у часі сеансів навчання виникає потреба представляти навчальний матеріал компактними порціями, які з одного боку будуть достатньо цілісними, а з іншого – досить самостійними. Для виконання такої декомпозиції навчального матеріалу пропонується розкласти асоціативну карту на компоненти сильної зв’язності. Компонента сильної зв’язності орієнтованого графа є максимальною множиною вершин , такою що пари вершин u та v з T досяжні одна з одної. Для ефективного пошуку компонент сильної зв’язності звичайно використовують алгоритм Косарайю, який дозволяє виконати пошук таких компонент за лінійний час та пам'ять [7].

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

1. Початкове перетворення змішаного графу.

a. Кожне ребро змішаного графу замінити на дві протилежно спрямовані дуги.

b. Якщо в графі між парою вершин v та u існує три дуги, дві з яких спрямовані в одному напрямку і одна в протилежному, замінити їх всі дугою в напрямку двох односпрямованих дуг.

Як результат отримуємо орієнтований граф.

2. Інвертування ребер орієнтованого графа. Як результат отримуємо звернений граф.

3. Виконання пошуку в глибину на зверненому графі. Як результат отримуємо вектор обходу вершин зверненого графу.



Скачать документ

Похожие документы:

  1. Государственное бюджетное города москвы «центральная универсальная

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

    Документ
    ... деятельности ЗабКИПКРО………………………………………………………… 17 V. Периодические издания:…………………………………………… Научно-методический журнал «Педагогическое ... и методическим работникам.  Статистика результатов государственной (итоговой) аттестации выпускников (9-х классов в ...
  3. Государственное и муниципальное управление (3)

    Ученые записки
    ... государственных экономических, социальных, и других программ, издание и продвижение нормативно-правовых актов, реклама государственных учреждений и государственных ... ра­бот свидетельствует 5-е издание учебного пособия «Государственная и муниципаль­ная ...
  4. Государственная центральная ХАНТЫ-МАНСИЙСК

    Библиографический указатель
    ... с 1941 г. - «Ханты-Мансийск». Справочный аппарат издания включает «Указатель предприятий, учреждений и организаций ... Институт природопользования Севера (Филиал Тюменской Государственной сельскохозяйственной академии) Факультет экономики и ...
  5. Государственная центральная ХАНТЫ-МАНСИЙСК

    Библиографический указатель
    ... с 1941 г. - «Ханты-Мансийск». Справочный аппарат издания включает «Указатель предприятий, учреждений и организаций ... Институт природопользования Севера (Филиал Тюменской Государственной сельскохозяйственной академии) Факультет экономики и ...

Другие похожие документы..