Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 74

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

Вып. 41. — С. 81—85. 8. Терзиян, В.Я. Формализация процесса устранения многозначности синтаксического разбора естественоязыкового высказывания. Сообщение 1 и 2 [Текст] / В.Я. Терзиян, И.И. Попков // Проблемы бионики. — 1991. — Вып.47. С. 23-36. 9. Осыка, А.Ф. О формализации семантики словосочетания с инструмен­тальным значением [Текст] / А.Ф. Осыка, О.А. Кравец //Проблемы бионики. — 1990. — Вып.45(90). — Харьков: Основа. С. 3 — 10. 10. Кольцов, В.П. О содержательной интерпретации алгебры идей [Текст] / В.П. Кольцов, Ю.П. Шабанов-Кушнаренко // Проблемы бионики.

— 1990. — Вып.45(90). Харьков: Основа. С. 10—17. 11. Бондаренко, М.Ф. О математическом моделировании семантики производных с модификационными значе­ниями [Текст] / М.Ф. Бондаренко, А. С. Левицкий // Проблемы бионики. — 1990. — Вып.45(90). — Харьков: Основа. С. 17—22. 12. Шабанов-Кушнаренко, Ю. П. Математические модели межморфемных связей на мно­жестве полисемантических производящих основ и словоо­бразовательных суффиксов [Текст] / В.И. Булкин, Д.И. Ситников, Ю. П. Шабанов-Кушнаренко // Проблемы бионики. — 1991. — Вып. 47. — Харьков: Основа. С. 3—22. 13. Осыка, А.Ф. К вопросу о формировании семантических признаков слов. [Текст] / А.Ф. Осыка, О.А. Кравец // Проблемы бионики. — 1991. — Вып. 47. — Харьков: Осно­ва. С. 8—16. 14. Рябова, Н.В. Моделирование семантики производных слов русского языка. [Текст] / Н.В. Рябова // Проблемы бионики. — 1990. Вып.45(90). Харьков: Осно­ва. С. 17—23. 15. Четвериков, Г.Г. Структура элементов компьютерной лингвистики и пути ее моделирования [Текст] / Г.Г. Четвериков, Т.Н. Федорова, И.Д. Вечирская // Прикладная лингвистика и лингвистические технологи: сборник научных трудов.К.: Довіра, 2010. — С. 206—214. 16. Широков, В.А. Очерк основных принципов квантовой лингвистики [Текст] / В.А. Широков // Бионика интел­лекта. — 2007. — №1(66). — С. 25—32. 17. Бондаренко, М.Ф. Теория интеллекта [Текст]: учеб. / М.Ф. Бондаренко Ю.П. Шабанов-Кушнаренко Харьков: Изд-во СМИТ, 2006. — 571 с. 18. Васильєв, Н.Р. Математическая модель псев­доорганизма (КАУС) — путь к созданию искусственного интеллекта [Электронный ресурс] / Н.Р. Васильєв, Е.В. Задорин — 2008. — Режим доступа: http://arupa-manas. narod.ru/BASE/nauka/index.html

Надійшла до редколегії 12.09.2011

УДК 519.71

Концепция унификации информационно-интеллекту­альных технологий в языковых системах / М.Ф. Бонда­ренко, З.Д. Коноплянко, Г.Г. Четвериков // Бионика интеллекта: научн.-техн. журнал. — 2011. — № 3 (77). —

С. 150-156.

Проведен обзор состояния проблемы моделирования функций интеллекта человека на уровне его языкового поведения; дан сравнительный синтаксический и семан­тический анализ морфологии словоформ. Предложен аппаратный способ реализации моделей естественного языка в виде k-значных структур (АКП-структур). Из­ложена суть концепции в области дальнейшего развития систем искусственного интеллекта.

Ил. 1. Библиогр.: 18 назв.

Concept of unification information intellectual technologies in language systems / M.F. Bondarenko, Z.D. Konoplyanko, G.G. Chetverikov // Bionics of Intelligense: Sci. Mag. — 2011. — № 3 (77). —P. 150-156.

The review condition of modelling functions intelligence person problem at level of its language behaviour is spent. The comparative syntactic and semantic analysis of morphol­ogy word forms is given. The hardware way realization natu­ral language models in the form of k-unit structures (AKP-STRUCTURES) is offered. The concept matter in the field of the further development artificial intelligence systems is stated.

Fig. 1. Ref.: 18 items.

УДК 004.652: 519.765:519.767:004.93

т ____

Б.М. Павлишенко

Львівський національний університет імені Івана Франка, Україна, pavlsh@yahoo.com

КВАНТОВИЙ АЛГОРИТМ ПОШУКУ КЛЮЧОВИХ СЛІВ У МАСИВАХ ТЕКСТОВИХ ДАНИХ

Запропонована модель квантового запису масиву текстових даних. Проаналізовано пошук ключових слів у квантовій базі даних текстових масивів, використовуючи елементи алгоритму Гровера. Показана ефективність квантового алгоритму у випадку великих розмірів текстових масивів, які суттєво переви­щують розмір словника, та у випадку багатократної появи ключових слів в аналізованому текстовому масиві.

КВАНТОВІ ОБЧИСЛЕННЯ, АНАЛІЗ ТЕКСТІВ, КВАНТОВИЙ АЛГОРИТМ ГРОВЕРА

Вступ

Квантові комп'ютери та алгоритми є новим перспективним напрямком сучасних інформацій­них технологій. Вони дають можливість суттєво пришвидшити розв'язок деяких класів задач вна­слідок реалізації квантового паралелізму та заплу­таності квантових станів. Одним із відомих кван­тових алгоритмів є алгоритм Гровера для пошуку даних у неструктурованій базі даних [1,2,3]. Цей алгоритм дає можливість знайти дані, які відпові­дають певним критеріям за час , викорис­товуючи кількість елементів пам'яті, пропорційну O(log N), де N — кількість елементів бази даних. В порівнянні із класичним алгоритмом, в якому пошук здійснюється за час O(N), алгоритм Гро­вера дає квадратичне прискорення розв язку, що є актуальним при великих значеннях N. Особли­вістю квантового алгоритму Гровера є те, що він є імовірнісним алгоритмом, тобто дає правильний розв'язок із заданою ймовірністю, яка може бути збільшена шляхом повторного використання ал­горитму. Алгоритм Гровера може бути складовою частиною інших квантових алгоритмів, зокрема, в роботі [4] він використовується для еволюційного аналізу кліткових автоматів. Інтелектуальний ана­ліз даних, зокрема, текстового типу є також одним із поширених напрямків інформаційних техноло­гій. Зростаючий об'єм інформації зумовлює пошук нових комплексних рішень для інтелектуального аналізу даних. З цих позицій є перспективним роз­гляд можливих квантових алгоритмів аналізу слабо структурованих даних, таких як текстові масиви.

На даний час розвитку квантових комп'ютерів розроблені лише елементарні базові елементи та пристрої з квантовим регістром, який містить де­кілька кубітів. Тому паралельно із розвитком еле­ментної бази є необхідність розробки систем чи­сельного моделювання квантових алгоритмів на класичних комп'ютерах. В даній роботі розглянемо чисельне моделювання алгоритму Гровера для ре­алізації квантового пошуку ключових слів у масиві текстів.

1. Постановка задачі

Розглянемо базові елементи квантових обчис­лень, які можуть бути використані в алгоритмах аналізу текстів. Створимо модель квантового запи­су масиву текстових даних. Розглянемо пошук за­даних ключових слів у квантовій базі даних тексто­вих масивів, використовуючи елементи алгоритму Гровера. Проаналізуємо ефективність квантового пошуку ключових слів у порівнянні із класичними алгоритмами.

2. Базові елементи квантових обчислень

Розглянемо базові квантові принципи реалізації квантових алгоритмів [5,6]. Основною відмінністю квантового біта - кубіта від класичного біта є те, що кубіт крім станів 10) і 11) може також знаходитись в суперпозиції цих станів

|i|/) = a\0) + Ь\ 1).

Стани 10) і 11) є базисними векторами, які мож­на представити у матричному вигляді

г0) і»=f°1

|0> =

Регістр із nкубітів \x1,x2,...xn) утворює суперпо­зицію із N = 2n станів, яку можна записати так:

N-1

k)=X ai\{).

i=0

2n

на-

Ортонормований базис { |0),|1),.. зивають обчислювальним базисом.

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

I

Операцію заперечення використовують для ре­алізації інверсії значень кубітів і визначають так:

x = | 0><1|+

У спінорному зображенні оператор заперечення має вигляд матриці

x

Одним із важливих елементів є «контрольоване НЕ», яке здійснюється над двома кубітами і змінює значення другого кубіта на протилежне, якщо зна­чення першого кубіта рівне 1. Цей логічний еле­мент може бути визначений як

Ucnot = |0)<0|® I + Ю(1 ® X ,

а матриця оператора унітарного перетворення «кон­трольоване НЕ» має вигляд

UCNOT

Дію вентиля «контрольоване НЕ» можна зобра­зити так:

UCNOT : |а,Ь) \a,a© Ь),

де © означає сумування за модулем 2. Ще одним важливим логічним елементом є вентиль Тоффолі, який діє на три кубіти і змінює значення третього кубіта на протилежне, якщо значення першого та другого кубітів рівне 1. Від логічного елемента «контрольоване НЕ» вентиль Тоффолі відрізняється наявністю ще одного додаткового керуючого кубіта. Цей вентиль можна визначити так:

T = |0)(0|®I®I + Ю(1 ®uCNOT.

Перетворення Тоффолі можна зообразити в та­кому вигляді:

T: |a,b,c) |a,b,c © .

Вентиль Тоффолі є універсальним квантовим логічним елементом на основі якого можна побуду­вати оборотну квантову машину Тюрінга. В подаль­ших дослідженнях будемо використовувати вентиль Тоффолі із n керуючими кубітами. В такому вентилі відбувається інверсія керованого кубіта при умові, що n керуючих кубітів мають значення 11).

3. Представлення текстових масивів у квантовій пам'яті

Нехай існує деякий текстовий масив, який мож­на представити у вигляді впорядкованої множини

T = {ti\i = U...N,} ,

де Nt — кількість слів у текстовому масиві. Індекс кожного елемента цієї множини відповідає його по -

ложенню в текстовому масиві. Словник слів цього масиву розглянемо у вигляді такої впорядкованої множини:

W = {wi\i = 1,2,...NW} ,

де Nw — кількість слів у словнику. Кожне слово wi цього словника можна закодувати його номером i за допомогою відображення

Wi i .

Для простоти розгляду будемо вважати, що роз­мір множини текстового масиву рівний Nt = 2(nt), а розмір словника рівний Nw = 2(nw). Тоді для ко­дування положення слова в масиві потрібно nt двійкових елементів, а для кодування положення номера слова у словнику потрібно nW двійкових елементів. Нехай квантовий регістр складається із двох частин \qt) і \qw):

\qt) ®\qw),

|qt)=|q! ,q1 ,...,qn^,

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа