Без темы
<<  Реализация предпрофессиональных программ в МБОУ ДОД «ДЮСШ №1» Ребячья Республика  >>
Реализация рекурсивных запросов в динамической ассоциативной ресурсной
Реализация рекурсивных запросов в динамической ассоциативной ресурсной
Ассоциативная ресурсная сеть
Ассоциативная ресурсная сеть
Обеспечение быстрого доступа к часто используемым данным реализуется
Обеспечение быстрого доступа к часто используемым данным реализуется
I. Яркость
I. Яркость
Ii
Ii
Ресурсная сеть
Ресурсная сеть
Ассоциативная ресурсная сеть
Ассоциативная ресурсная сеть
Распространение яркости
Распространение яркости
Правила распространения яркости (правило 1)
Правила распространения яркости (правило 1)
Правила распространения яркости (правило 2)
Правила распространения яркости (правило 2)
Распространение яркости
Распространение яркости
Изменение топологии сети
Изменение топологии сети
Медленное и быстрое время
Медленное и быстрое время
Алгоритм построения сети
Алгоритм построения сети
Изменение проводимостей
Изменение проводимостей
Пример построения сети
Пример построения сети
Пример построения сети
Пример построения сети
Пример построения сети
Пример построения сети
Пример построения сети
Пример построения сети
Готовый фрагмент сети
Готовый фрагмент сети
Восстановление образа по его части
Восстановление образа по его части
Управление движением яркости
Управление движением яркости
Реализация рекурсивных запросов
Реализация рекурсивных запросов
Виды запросов
Виды запросов
2. Удаление одной или нескольких вершин из входного множества
2. Удаление одной или нескольких вершин из входного множества
2. Удаление одной или нескольких вершин из входного множества
2. Удаление одной или нескольких вершин из входного множества
Комбинируя все возможные сочетания добавления и удаления вершин,
Комбинируя все возможные сочетания добавления и удаления вершин,
Операции над графами
Операции над графами
Операции над графами
Операции над графами
Операции над графами
Операции над графами
Заключение
Заключение
Спасибо за внимание
Спасибо за внимание

Презентация: «Реализация рекурсивных запросов в динамической ассоциативной ресурсной сети». Автор: Ludmila Yu. Zhilyakova. Файл: «Реализация рекурсивных запросов в динамической ассоциативной ресурсной сети.ppt». Размер zip-архива: 2332 КБ.

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

содержание презентации «Реализация рекурсивных запросов в динамической ассоциативной ресурсной сети.ppt»
СлайдТекст
1 Реализация рекурсивных запросов в динамической ассоциативной ресурсной

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

сети

Л.Ю. Жилякова ПИ ЮФУ, г. Ростов-на-Дону zhilyakov@aaanet.ru

Тверь, КИИ-2010

2 Ассоциативная ресурсная сеть

Ассоциативная ресурсная сеть

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

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

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

Вершины сети соответствуют сущностям предметной области, ребра — ассоциативным связям между ними.

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

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

благодаря двум свойствам сети.

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

E

А

В

С

D

F

G

H

I

J

4 I. Яркость

I. Яркость

Каждая вершина обладает яркостью: доступность вершины тем выше, чем больше ее яркость, – тем эта вершина «виднее» при поиске.

Свойства сети

5 Ii

Ii

Пропускная способность (проводимость)

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

11

6 Ресурсная сеть

Ресурсная сеть

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

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

7 Ассоциативная ресурсная сеть

Ассоциативная ресурсная сеть

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

8 Распространение яркости

Распространение яркости

Ресурс вершины отвечает за яркость соответствующего ей понятия. Чем он больше, тем понятие ярче, тем оно доступнее в памяти. Яркость попадает в вершины, участвующие в запросе, и передается по рёбрам от вершины к вершине. При перетекании яркости высвечиваются вершины, ассоциированные с данными.

9 Правила распространения яркости (правило 1)

Правила распространения яркости (правило 1)

Ресурс вершины qi

i

10 Правила распространения яркости (правило 2)

Правила распространения яркости (правило 2)

Ресурс вершины qi

11 Распространение яркости

Распространение яркости

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

12 Изменение топологии сети

Изменение топологии сети

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

13 Медленное и быстрое время

Медленное и быстрое время

Пока в сеть не поступает запросов, она находится в неактивном состоянии. В сети вводится время двух типов: 1) медленное время ? ; 2) быстрое время t. Один такт медленного времени соответствует выполнению одного запроса. Медленное время отвечает за изменение проводимостей ребер и создание новых ребер. За один такт ? у каждого ребра происходит не более одного изменения проводимости. Быстрое время включается во время исполнения запроса. Оно отвечает за распределение ресурса по вершинам.

14 Алгоритм построения сети

Алгоритм построения сети

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

Двусторонняя пара, связывающая две вершины;

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

15 Изменение проводимостей

Изменение проводимостей

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

rii = rii +?0

rjj = rjj +?0

rij = rij +?0

rji = rji +?0

Сеть обязательно заполняется с самого начала. На нулевом шаге она пуста.

16 Пример построения сети

Пример построения сети

Дом, который построил Джек

Вот дом, Который построил Джек.

Джек

Дом

17 Пример построения сети

Пример построения сети

Дом, который построил Джек

А это пшеница, Которая в темном чулане хранится В доме, Который построил Джек.

Чулан

Пшеница

Джек

Дом

18 Пример построения сети

Пример построения сети

Дом, который построил Джек

А это веселая птица-синица, Которая часто ворует пшеницу, Которая в темном чулане хранится В доме, Который построил Джек.

Синица

Чулан

Пшеница

Джек

Дом

19 Пример построения сети

Пример построения сети

Дом, который построил Джек

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

Кот

Синица

Чулан

Пшеница

Джек

Дом

20 Готовый фрагмент сети

Готовый фрагмент сети

Дом, который построил Джек

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

21 Восстановление образа по его части

Восстановление образа по его части

22 Управление движением яркости

Управление движением яркости

Запрос к ассоциативной сети — входное множество вершин и количество яркости, которое им приписывается.

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

23 Реализация рекурсивных запросов

Реализация рекурсивных запросов

Под рекурсивным запросом будем понимать многократный запрос, входное множество вершин которого изменяется в зависимости от выходного множества на предыдущем шаге по одному из наперед заданных правил. Алгоритм выполнения одного шага рекурсии 1. В начальное множество вершин поступает яркость; 2. Яркость начинает распространяться в соответствии с правилами 1-2 ресурсной сети tR тактов быстрого времени t. (Величина tR задана заранее.); 3. По окончании распределения из вершин, имеющих яркость, выбирается новое начальное множество. И процесс повторяется.

24 Виды запросов

Виды запросов

1. Добавление к входному множеству одной или нескольких вершин из выходного множества предыдущего шага рекурсии

Этот тип изменений соответствует ситуации, когда самый ожидаемый (вероятный) ответ на поставленный запрос является удовлетворительным, но его нужно расширить и/или уточнить.

L – мощность выходного множества, l* – мощность пересечения входного и выходного множества.

25 2. Удаление одной или нескольких вершин из входного множества

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

предыдущего запроса

2. a) Удаляются вершины из пересечения множеств вопрос-ответ, т.е. входного и выходного множеств предыдущего запроса.

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

.

26 2. Удаление одной или нескольких вершин из входного множества

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

предыдущего запроса

2. b) Удаляются вершины из предыдущего входного множества, которых не оказалось в множестве выходном.

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

M – мощность входного множества.

.

27 Комбинируя все возможные сочетания добавления и удаления вершин,

Комбинируя все возможные сочетания добавления и удаления вершин,

получим

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

.

28 Операции над графами

Операции над графами

1. Оператор T(G) – транзитивное замыкание графа G. Действует он следующим образом: для любого графа G T(G) – такой граф, что для любых двух вершин верно: если есть путь любой длины из вершины vi в вершину vj, то есть и двусторонняя пара <(vi, vj),(vj, vi)>, связывающая эти вершины. GInOut(i) = T(GIn(i) ? GOut(i)). Множество его вершин – это по-прежнему вершины графа GIn(i) ? GOut(i). Проводимость каждого вновь созданного ребра рассчитывается как среднее геометрическое проводимостей ребер, составляющих цепочку. 2. Оператор А – добавление вершин. Запись: (G1, G2) означает, что из графа G2 в граф G1 будет добавлено k вершин с номерами j1, …, jk вместе со всеми ребрами, соединяющими эти вершины с вершинами G1.

.

29 Операции над графами

Операции над графами

3. Оператор Е (удаление вершин) применяется к одному графу. Запись: (G) означает, что из графа G будет удалено h вершин с номерами j1', …, jh' вместе с их инцидентными ребрами. Тогда на шаге i + 1 удаление из графа GIn(i) вершин с номерами j1', …, jh', где h ? m (m – мощность множества вершин GIn(i)), запишется в следующем виде:

GIn (i +1) = (GIn(i)).

.

30 Операции над графами

Операции над графами

Будем считать, что сначала к графу GIn(i) применяется оператор Е, а затем к результату – оператор А. Операторы не коммутируют, порядок их применения важен. Таким образом, на шаге i + 1 входной граф запроса находится по следующей рекуррентной формуле: GIn(i +1) = ( (GIn(i))).

Непосредственно из этой формулы вытекает, что каждый новый входной подграф однозначно определяется входным и выходным подграфами на предыдущем шаге и парой последовательностей натуральных чисел переменной длины: ({j1', …, jh'}; { j1, …, jk}).

.

31 Заключение

Заключение

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

32 Спасибо за внимание

Спасибо за внимание

«Реализация рекурсивных запросов в динамической ассоциативной ресурсной сети»
http://900igr.net/prezentacija/pedagogika/realizatsija-rekursivnykh-zaprosov-v-dinamicheskoj-assotsiativnoj-resursnoj-seti-157341.html
cсылка на страницу

Без темы

2329 презентаций
Урок

Педагогика

135 тем
Слайды
900igr.net > Презентации по педагогике > Без темы > Реализация рекурсивных запросов в динамической ассоциативной ресурсной сети