Ассоциативная память. Адресная, ассоциативная и стековая организации памяти. Отрывок, характеризующий Ассоциативная память

Ассоциативная память

Ассоциативная память (АП) или Ассоциативное запоминающее устройство (АЗУ) является особым видом машинной памяти, используемой в приложениях очень быстрого поиска. Известна также как память, адресуемая по содержимому , ассоциативное запоминающее устройство , контентно-адресуемая память или ассоциативный массив , хотя последний термин чаще используется в программировании для обозначения структуры данных. (Hannum и др., 2004)

Аппаратный ассоциативный массив

В отличие от обычной машинной памяти (памяти произвольного доступа, или RAM), в которой пользователь задает адрес памяти и ОЗУ возвращает слово данных, хранящееся по этому адресу, АП разработана таким образом, чтобы пользователь задавал слово данных, и АП ищет его во всей памяти, чтобы выяснить, хранится ли оно где-нибудь в нем. Если слово данных найдено, АП возвращает список одного или более адресов хранения, где слово было найдено (и в некоторых архитектурах, также возвращает само слово данных, или другие связанные части данных). Таким образом, АП - аппаратная реализация того, что в терминах программирования назвали бы ассоциативным массивом.

Промышленные стандарты адресуемой содержанием памяти

Определение основного интерфейса для АП и других Сетевых Элементов Поиска (Network Search Elements, NSE) было специфицировано в Соглашении о возможности взаимодействий (Interoperability Agreement), названном Интерфейс предысторий(Look-Aside Interface) (LA-1 и LA-1B ) который был разработан Форумом Сетевой Обработки, который позже был объединен с Оптическим Межсетевым Форумом (Optical Internetworking Forum, OIF). Многочисленные устройства были произведены компаниями Integrated Device Technology, Cypress Semiconductor, IBM, Netlogic Micro Systems и другими по этим соглашениям LA. 11 декабря 2007, OIF издал соглашение об интерфейсе последовательной предыстории (Serial Lookaside, SLA ).

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

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

Альтернативные реализации

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

Троичная Ассоциативная память

Двоичная АП - простейший тип ассоциативной памяти, который использует слова поиска данных, состоявшие полностью из единиц и нулей. В троичной АП добавляется третье значение для сравнения «X» или «не важно», для одного или более битов в сохраненном слове данных, добавляя таким образом большей гибкости поиску. Например, в троичной АП могло бы быть сохранено слово «10XX0», которое выдаст совдпадение на любое из четырех слов поиска «10000», «10010», «10100», или «10110». Добавление гибкости к поиску приходит за счет увеличения цены двоичной АП, поскольку внутренняя ячейка памяти должна теперь закодировать три возможных состояния вместо двух. Это дополнительное состояние обычно осуществляется добавлением бита маски «важности»(«важно»/«не важно») к каждой ячейке памяти.

Голографическая ассоциативная память обеспечивает математическую модель для интегрированного ассоциативного воспоминания бита «не важно», используя комплекснозначное представление.

Примеры приложений

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

Троичные АП часто используются в тех сетевых маршрутизаторах, в которых у каждого адреса есть две части: (1) адрес сети, который может измениться в размере в зависимости от конфигурации подсети, и (2) адрес хоста, который занимает оставшиеся биты. У каждой подсети есть маска сети, которая определяет, какие биты - адрес сети и какие биты - адрес хоста. Маршрутизация делается путем сверки с таблицей маршрутизации, которую поддерживает маршрутизатор (router). В ней содержатся все известные адреса сети назначения, связанная с ними маска сети и информация, необходимая пакетам, маршрутизируемым по этому назначению. Маршрутизатор, реализованный без АП, сравнивает адрес назначения пакета, который будет разбит, с каждым входом в таблице маршрутизации, выполняя при этом логическое И с маской сети и сравнивая результаты с адресом сети. Если они равны, соответствующая информация направления используется, чтобы отправить пакет. Использование троичной АП для таблицы маршрутизации делает процесс поиска очень эффективным. Адреса хранятся с использованием бита «не важно» в части адреса хоста, таким образом поиск адреса назначения в АП немедленно извлекает правильный вход в таблице маршрутизации; обе операции - применения маски и сравнения - выполняются аппаратно средствами АП.

Другие приложения АП включают

• Диспетчеры кэша центрального процессора и ассоциативные буфера трансляции (TLB)

Библиография

• Кохонен Т. Ассоциативные запоминающие устройства. М.: Мир, 1982. - 384 с.

На английском языке

• Anargyros Krikelis, Charles C. Weems (editors) (1997) Associative Processing and Processors , IEEE Computer Science Press. ISBN 0-8186-7661-2

• Hannum et al. (2004) System and method for resetting and initializing a fully associative array to a known state at power on or through machine specific state . U.S. Patent 6,823,434.

Ссылки

Wikimedia Foundation . 2010 .

Смотреть что такое "Ассоциативная память" в других словарях:

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

ассоциативная память - Память, в которой адресация определяется не местом расположения объекта, а его содержанием. Для нахождения адреса проводится анализ объекта и совпадение его названия (по определенным словам) с другими адресами. Использование ассоциативной памяти… … Справочник технического переводчика

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

ассоциативная память - asociatyvioji atmintis statusas T sritis automatika atitikmenys: angl. associative memory vok. assoziativer Speicher, m; Durchsuchspeicher, m rus. ассоциативная память, f pranc. mémoire associative, f … Automatikos terminų žodynas

АССОЦИАТИВНАЯ ПАМЯТЬ - См. память, ассоциативная … Толковый словарь по психологии

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Человеческая память ассоциативна, то есть некоторое воспоминание может порождать большую связанную с ним область. Один предмет напоминает нам … Википедия

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

Что такое ассоциации?

Ассоциация - это связь между отдельными фактами, событиями, предметами или явлениями, отражёнными в сознании человека и закреплёнными в его памяти. Ассоциативное восприятие и мышление человека приводят к тому, что появление одного элемента в определенных условиях вызывает образ другого, связанного с ним.

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

Упражнения

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

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

Упражнение 4. Подходящие ассоциации. Выберите два слова, и постарайтесь назвать ассоциации, подходящие одновременно для каждого из этих слов. Например, для слов «белый» и «легкий» можно назвать такие ассоциации: снег, пух, перо и т.д. Для усложнения упражнения можете выбрать не два, а три или даже больше слов.

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

• Русский поэт - Пушкин
• Домашняя птица - курица
• Фрукт - яблоко
• Часть лица - нос

Постарайтесь с этими же словами придумать другие, менее популярные ассоциации.

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

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

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

1. вызывать у вас подлинный интерес (как этого добиться, было написано в предыдущем уроке);
2. затрагивать различные органы чувств;
3. быть необычной, но осмысленной вами;
4. содержать максимально детализированную картинку (размер, цвет и т.п.).

А главное - чтобы ассоциация была яркой и легко запоминающейся.

Итак, второе правило запоминания:

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

Проверьте свои знания

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

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

В попытках как-то объяснить этот обескураживающий феномен нейробиологи из Института биологических исследований Солка (Salk Institute for Biological Studies) в пригороде Сан-Диего (США, штат Калифорния) провели серию интересных экспериментов. Институт Солка - это независимая некоммерческая организация, занимающаяся фундаментальными исследованиями, лечением людей и обучением будущих специалистов, а назван этот институт по имени его основателя (1965) - иммунолога Джонаса Эдвардса Солка (Jonas Edward Salk (1914-1995), в свое время одержавшего победу над полиомиелитом). О полученных результатах сообщается в выпуске журнала Neuron ("Нейрон") от 20 октября. Грубо говоря, удалось впервые показать, что мозг помнит про грозовую угрозу, даже если мы ее игнорируем и оставляем зонтик дома.

"Впервые при взгляде на мозговую активность обезьяны резус мы научились отгадывать, что в действительности знает животное", - говорит Томас Д. Олбрайт (Thomas D. Albright), что руководит Vision Center Laboratory. А основной автор исследования, Адам Мессинджер (Adam Messinger), бывший аспирант Олбрайта, который ныне трудится в американском Национальном институте психического здоровья (National Institute of Mental Health - NIMH), сравнивает предмет своего изучения с подсознательным знанием. Это знание остается у нас даже в том случае, если оно недоступно непосредственно сознанию. Он приводит такой пример: "Вы знаете, что встретили жену вашего коллеги по работе, хотя и не способны вспомнить ее лицо".

Человеческая память полагается главным образом на ассоциации ; когда мы пытаемся восстановить какую-либо информацию, один предмет напоминает нам о каком-то другом, который в свою очередь напоминает нам о третьем, и так далее... Как раз на учете этого обстоятельства и основаны, например, феноменальные успехи рекордсменов по запоминанию цифровых рядов, увязывающих с каждой цифрой какие-то более привычные предметы из окружающего мира - это так называемые мнемонические приемы. Разумеется, нейробиологи уже давно и весьма активно пытаются разобрать устройство всей этой ассоциативной памяти "по винтикам". Некоторые специалисты вообще утверждают, что внутри нас запрятано по меньшей мере два типа памяти (а кто-то насчитывает их до десяти разновидностей, но это уже скорее из области курьезов). Первая - основная память - функционально связана с работой фронтальной коры головного мозга, а вторая, гораздо более емкая, - ютится в специфической области мозга, получившей название нижней височной коры (inferior temporal cortex - ITC). Именно там хранится информация едва ли не обо всех событиях нашей жизни. Правда, памятные следы в височной коре окружены неработающими участками мозга, они как бы замурованы. И активизировать, пробудить эту память можно, например, в состоянии гипнотического транса с помощью особых наводящих вопросов.

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

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

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

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

Ассоциативная память

Таблица страниц

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

Итак, виртуальный адрес состоит из виртуального номера страницы (high-order bits) и смещения (low-order bits). Номер виртуальной страницы используется как индекс в таблице страниц для нахождения записи (entry) о виртуальной странице. Из этой записи в таблице страниц находится номер кадра (page frame number), затем прибавляется смещение и формируется физический адрес. Помимо этого запись в таблице страниц содержит информацию об атрибутах страницы, в частности биты защиты.

Основную проблему для эффективной реализации таблицы страниц создают большие размеры виртуальных адресных пространств современных компьютеров, которые обычно определяются разрядностью архитектуры процессора. Самыми распространенными на сегодняшний день являются 32-разрядные процессоры, позволяющие создавать виртуальные адресные пространства такого размером 4 Гб (для 64-разрядных компьютеров эта величина равна 2**64б).

Подсчитаем примерный размер таблицы страниц. В 32-битном адресном пространстве при размере страницы 4К (Intel) получаем 1М страниц, а в 64-битном и того более. Т.о. таблица должна иметь 1М строк (entry), причем запись в строке состоит из нескольких байт. Заметим, что каждый процесс, нуждается в своей таблице страниц (а в случае сегментно-страничной схемы по одной на каждый сегмент). Итак, в данном случае таблица страниц должна быть чересчур большой.

Вместе с тем, отображение должно быть быстрым. Отображение должно быть быстрым, так как оно делается при каждом обращении к памяти, ĸᴏᴛᴏᴩᴏᴇ происходит практически в каждой машинной инструкции. Эта проблема решается главным образом за счёт реализации ассоциативной памяти.

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

Рассмотрим модельный пример (рис.10.4). Предположим, что 32-разрядный адрес делится на 10-разрядное поле Рtr1, 10-разрядное поле Рtr2 и 12-разрядное смещение Offset. 12 разрядов смещения позволяют локализовать байт внутри страницы размером 4К (2**12), а всœего имеем 2**20 страниц. Как видно из рис. 9.4 1024 строки в таблице верхнего уровня при помощи поля Ptr1 ссылаются на 1024 таблицы второго уровня, каждая из которых содержит также 1024 строки. При помощи поля Ptr2 каждая строка таблицы второго уровня указывает на конкретную страницу. Смысл такой организации в том, чтобы избежать поддержки всœех таблиц второго уровня (а их 1024) в памяти постоянно. Рассмотрим пример с круглыми цифрами. Допустим, что процессу нужны 12М памяти: 4М в нижней части памяти для кода, 4М в нижней части для данных и 4М в верхней части памяти для стека. Между дном стека и верхом данных гигантское пространство размером 4Gb-12Mb, ĸᴏᴛᴏᴩᴏᴇ не используется. Для этого случая необходимы лишь 1 таблица верхнего уровня и 3 таблицы второго уровня. Такой подход естественным образом обобщается на три и более уровней таблицы.

Рассмотрим одну из записей таблицы страниц. Ее размер колеблется от системы к системе, но 32 бита - наиболее общий случай. Самое важное поле - номер кадра. Цель страничного отображения - локализовать эту величину. Далее бит присутствия, биты защиты (к примеру, 0 - read/write, 1 - read only ...), биты модификации (если на нее писали) и биты ссылки, которые помогают выделить мало используемые страницы, биты разрешающие кэширование. Заметим, что адреса страниц на диске не являются частью таблицы страниц.

Рисунок 10.4 - Пример двухуровневой таблицы страниц.

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

Количество уровней в таблице страниц зависит от конкретных особенностей архитектуры. Можно привести примеры реализации одноуровневого (DEC PDP-11), двухуровневого (Intel, DEC VAX), трехуровневого (Sun SPARC, DEC Alpha) paging"а, а также paging"а с задаваемым количеством уровней (Motorola). Функционирование RISC процессора MIPS R2000 осуществляется вообще без таблицы страниц. Здесь поиск нужной страницы, в случае если эта страница отсутствует в ассоциативной памяти, должна взять на себя ОС (так называемый zero level paging).

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

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

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

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

Отображение виртуальных страниц, хранимых в ассоциативной памяти, осуществляется быстро, однако кэш память является дорогостоящей и имеет ограниченный размер.
Размещено на реф.рф
Число записей в TLB от 8 до 2048

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

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

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

Процент раз, когда номер страницы находится в ассоциативной памяти, принято называть hit (совпадение) ratio (пропорция, отношение). Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, hit ratio - часть ссылок, которая должна быть сделана с использованием ассоциативной памяти. Обращение к одним и тем же страницам повышает hit ratio.

К примеру, предположим, что для доступа к таблице страниц крайне важно 100 нс, а для доступа к ассоциативной памяти 20 нс. С 90% hit ratio среднее время доступа - 0.9*20+0.1*100 = 28 нс.

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

Необходимо обратить внимание на следующий факт. При переключении процессов нужно добиться того, чтобы новый процесс не видел в ассоциативной памяти информацию, относящуюся к предыдущему процессу, к примеру, очищать ее. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, использование ассоциативной памяти увеличивает время переключения контекстов.

Ассоциативная память - понятие и виды. Классификация и особенности категории "Ассоциативная память" 2017, 2018.

В отличие от обычной машинной памяти, в которой пользователь задает адрес памяти и ОЗУ возвращает слово данных, хранящееся по этому адресу, АП разработана таким образом, чтобы пользователь задавал слово данных, и АП ищет его во всей памяти, чтобы выяснить, хранится ли оно где-нибудь в нем. Если слово данных найдено, АП возвращает список одного или более адресов хранения, где слово было найдено (и в некоторых архитектурах, также возвращает само слово данных, или другие связанные части данных). Таким образом, АП - аппаратная реализация того, что в терминах программирования назвали бы ассоциативным массивом.

1. 
   Автоассоциативная память

1. 
   Гетероассоциативная память

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

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

1. 
   Приведите определение процесса распознавания образов

1. 
   Охарактеризуйте два типа машин распознавания образов.

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

2ой тип машины.

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

1. 
   Опишите способ решения задачи идентификации систем.

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

1. 
   Опишите способ построения инверсной системы

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

1. 
   Приведите блок-схему системы управления с обратной связью

В этой системе используется единственная обратная связь, охватывающая весь объект управления. Таким образом, выход объекта управления вычитается из эталонного сигнала (), принимаемого из внешнего источника. Полученный таким образом сигнал ошибки (e) подаётся на нейроконтроллер для настройки свободных параметров. Основной задачей контроллера является поддержание такого входного вектора объекта, для которого выходной сигнал (у) соответствовал бы эталонному значению (d). Другими словами, в задачу контроллера входит инвертирование отображения вход-выход объекта управления.

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

Операция логической суммы:

Пусть
- наименьшее нечёткое подмножество, которое включает как так и с функцией принадлежности:

Операция логического произведения над нечёткими множествами:

Пусть
- наибольшее нечёткое подмножество, которое содержится одновременно в и в , тогда функция принадлежности имеет вид:

1. 
   Опишите операции отрицания множества и нормализации множества для нечётких множеств

Пусть - всё то множество, что не , тогда элемент, принадлежащий множеству , определяется согласно функции:

Нормализация нечётких множеств:

СУПРЕМУМ: Sup - точная верхняя грань (максимальное значение принадлежности, присутствующее в множестве).

НОРМАЛИЗАЦИЯ: нечеткое множество нормально если супремум множества равен единице. Для нормализации перечитывают принадлежности элементов:

M"a(x) = Ma(x)/(Sup Ma(x))

1. 
   Опишите операцию концентрации и растяжения для нечётких множеств

Операция размывания:

1. 
   Дайте определение лингвистической переменной

Математическое определение лингвистической переменной:
, где -имя переменной;
-множество имён лингвистических значений переменной , каждое из которых является нечёткой переменой на множестве
; - синтаксическое правило для образования имён значений ;
семантическое правило для ассоциирования каждой величины значения с её понятием.

1. 
   Опишите операцию алгебраического произведения для нечётких множеств

1. 
   Опишите меру Егера, характеризующую степень нечёткости множеств

,

количество элементов в ,
расстояние между множествами и в метрике (которое равно 1 или 2). Метрике Хэмминга соответствует значение

1. 
   Опишите метрику Евклида, характеризующую меру нечёткости множества

1. 
   Опишите энтропийную меру нечёткости множества Коско

1. 
   Опишите систему нечёткого вывода Мамдани-Заде

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

Для обеспечения взаимодействия этих двух видов вводится нечеткая система с так называемым фазификатором (преобразователем множеств входных данных в нечеткое множество) на входе и дефазификатором (преобразователем нечетких множеств в конкретное значение выходной переменной) на выходе.

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

В модели вывода Мамдани-Заде присутствуют следующие операторы:

Рис 1. Пример системы вывода Мамдани-Заде

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

1. 
   Охарактеризуйте фаззификатор

1. 
   Охарактеризуйте понятие функции принадлежности

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

Действительное число, принимающее значение в диапазоне (0,1), при этом 1 означает 100%-ю (безусловную) принадлежность a к множеству , а 0 - безусловное отсутствие в . Значения между 0 и 1 характеризуют нечётко включенные элементы.

Отображение множества элементов во множество значений образует функцию принадлежности .

Функция может быть определена явно в виде, например, алгебраического выражения или таблично (дискретно) в виде массива пар

1. 
   Опишите обобщённую гауссовскую функцию принадлежности

Также существует обобщённая гауссова функция:
параметр формы.

Рис 3. График обобщённой функции Гаусса для с=1,

Обобщённая функция Гаусса также может быть и в рациональной форме:
.

1. 
   Опишите понятие дефаззификации нечёткого множества

1. 
   Опишите дефаззификацию относительно среднего центра

1. 
   Опишите дефаззификацию относительно центра области

1. 
   Приведите блок-схему работы генетического алгоритма.

1. 
   Охарактеризуйте понятия целочисленного и вещественного кодирования.

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

Целочисленное кодирование.

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

Вещественное кодирование.

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

1. 
   Опишите способы селекции.

Рулеточная селекция. В данном варианте селекции вероятность i-й особи принять участие в скрещивании pi пропорциональна значению ее приспособленности fi и равна .

Процесс отбора особей для скрещивания напоминает игру в «рулетку».

Рулеточный круг делится на сектора, причем площадь i-го сектора пропорциональна значению pi. После этого n раз «вращается» рулетка, где n – размер популяции, и по сектору, на котором останавливается рулетка, определяется особь, выбранная для скрещивания.

Селекция усечением. При отборе усечением после вычисления значений приспособленности для скрещивания выбираются Ln лучших особей, где L – «порог отсечения», 0
Как правило, выбирают L в интервале от 0,3 до 0,7.

Турнирный отбор. В случае использования турнирного отбора для скрещивания, как и при рулеточной селекции, отбираются n особей.

Для этого из популяции случайно выбираются t особей, и самая приспособленная из них допускается к скрещиванию. Говорят, что формируется турнир из t особей, t – размер турнира. Эта операция повторяется n раз.

Чем больше значение t, тем больше давление селекции. Вариант турнирного отбора, когда t = 2, называют бинарным турниром. Типичные значения размера турнира t = 2, 3, 4, 5.
28. Охарактеризуйте принцип работы одноточечного, двухточечного и однородного операторов кроссовера для целочисленного кодирования.

Для целочисленного кодирования часто используются 1-точечный, 2-точечный и однородный операторы кроссинговера.

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

Для оператора 2-точечного кроссинговера выбираются 2 случайные точки разрыва, после чего для создания потомков родительские хромосомы обмениваются участками, лежащими между точками разрыва. Отметим, что для 2-точечного оператора кроссинговера, начало и конец хромосомы считаются «склеенными» в результате чего одна из точек разрыва может попасть в начало/конец хромосом и в таком случае результат работы 2-точечного кроссинговера будет совпадать с результатом работы 1-точечного кроссинговера.

При использовании однородного оператора кроссинговера разряды родительских хромосом наследуются независимо друг от друга. Для этого определяют вероятность p0, что i-й разряд хромосомы 1-го родителя попадет к первому потомку, а 2-го родителя – ко второму потомку. Вероятность противоположного события равна (1 – p0). Каждый разряд родительских хромосом «разыгрывается» в соответствии со значением p0 между хромосомами потомков. В большинстве случаев вероятность обоих событий одинакова, т.е. p0 = 0,5.
29. Опишите принцип работы двухточечного кроссовера для вещественного кодирования.

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

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

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

Другими словами, способность целочисленного кроссинговера к разрушению зависит от того, насколько сильно он «перемешивает» (рекомбинирует) содержимое родительских хромосом. Так, 1-точечный кроссинговер считается слаборазрушающим, а однородный кроссинговер в большинстве случаев является сильно разрушающим оператором. Соответственно, 2-точечный кроссинговер по разрушающей способности занимает промежуточную позицию по отношению к 1-точечному и однородному операторам кроссинговера.

В случае кроссинговера для вещественного кодирования способность к разрушению определяется тем, насколько велико расстояние в пространстве поиска между точками, соответствующими хромосомам родителей и потомков. Таким образом, разрушающий эффект 2 точечного кроссинговера зависит от содержимого родительских хромосом. Разрушающая способность арифметического кроссинговера зависит от значения параметра l, например, при l >> 1 и l >> 0, способность к разрушению будет низкой. Для BLX-a кроссинговера разрушающая способность зависит как от значения a, так и от разности значений соответствующих генов родительских особей.

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

Канонический генетический алгоритм разработан Джоном Холландом и описан в его книге «Адаптация в естественных и искусственных системах», 1975 г. . Представляет одну из базовых моделей эволюционного поиска, подробно исследованную в 70-80-х годах 20 века.

Канонический ГА имеет следующие характеристики:

Целочисленное кодирование;

Все хромосомы в популяции имеют одинаковую длину;

Постоянный размер популяции;

Рулеточная селекция;

Одноточечный оператор кроссинговера;

Битовая мутация;

Новое поколение формируется только из особей-потомков (разрыв поколений Т = 1).
32. Какие вы знаете модели представления знаний?

Наиболее распространенными моделями представления знаний в экспертных системах являются:

• 
  модель представления знаний средствами логики предикатов первого порядка;

• 
  продукционная модель;

• 
  фреймовая модель;

• 
  модель представления знаний в виде семантической сети;

• 
  модель представления знаний в виде доски объявлений;

• 
  модель представления знаний в виде сценария;

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

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

Логическая модель представления знаний основана на логике предикатов. Предикатом, или логической функцией, называется функция от любого числа аргументов, принимающей истинное или ложное значение. Аргументы функции – значения из произвольного, конечного или бесконечного множества
, называемого предметной областью. Предикат от -аргументов называют -местным предикатом. Для модели представления знаний используется логика предикатов первого порядка, на которой основан Пролог.
34. Из чего состоит продукционная система?

Продукционная система – система обработки знаний, использующая представления знаний продукционными правилами. Продукционные правила – это выражения типа «Если (условие) то (действие)». “Условие” – предложение образец, по которому осуществляется поиск в базе знаний; “действие” – действие, выполняемое при успешном исходе поиска. Вывод на такой базе знаний может быть прямым (от данных к поиску цели) и обратным (от цели для её подтверждения – к данным). Данные – исходные факты, хранящиеся в базе фактов, на основании которых запускается машина вывода или интерпретатор правил, перебирающий правила из продукционной базы знаний.

В состав продукционной системы входят база правил, база данных и интерпретатор правил. База правил – это область памяти, которая содержит базу знаний – совокупность знаний, представленных в форме правил вида ЕСЛИ … ТО; база данных – это область памяти, содержащая фактические данные (факты). Интерпретатор – механизм вывода, это тот компонент системы, который формирует заключение, используя базу правил и базу данных.
35. Охарактеризуйте модель представления знаний в виде фреймов

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

36. Каким образом осуществляется представление знаний в семантической сети?

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

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

Информация, содержащаяся в базе знаний, обрабатывается с помощью машины вывода, которая использует эмпирические ассоциации или правила «ЕСЛИ … ТО» для формирования и проверки возможных решений. Интерфейс пользователя в доступной форме передает полученные результаты оператору.

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

38. Опишите функции машины (механизма) вывода

Главным в ЭС является механизм, осуществляющий поиск в БЗ по правилам рациональной логики, для получения решений. Этот механизм, называемый машиной вывода, приводится в действие при получении запроса пользователя и выполняет следующие задачи:

• 
  сравнивает информацию, содержащуюся в запросе пользователя, с информацией базы знаний;

• 
  ищет определенные цели или причинные связи;

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

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

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

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

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

На этапе выполнения осуществляется наполнение БЗ системы. На этапе тестирования эксперт (и инженер по знаниям) в интерактивном режиме, используя диалоговые и объяснительные средства, проверяет компетентность ЭС. Процесс тестирования продолжается до тех пор, пока эксперт не решит, что система достигла требуемого уровня компетентности.

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

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