Репетиторам – НЕТ !

  • Предметы

  • Управление

    • Курс лекций (8)

    2.6 Применение методов хеширования для поиска по соответствию

    Напомним, что основная цель введения адресации по содержанию состояла в выделении всех элементов, определенные фрагменты которых в точности совпадали бы с заданным аргументом поиска. Очевидно, что работа биологической ассоциативной памяти построена несколько на иных принципах. Например, человек способен воспроизводить события, часто руководствуясь весьма неопределенной ключевой информацией. Однако важнейшая особенность памяти человека, отличающая ее от АЗУ ЭВМ, состоит в том, что она не производит перебора всей информации, отвечающей в какой-то мере ключевой, а концентрируется обычно на одном воспоминании, степень совпадения для которого оказывается максимальной. Вероятно, процесс выборки данных из биологической памяти более близок к работе устройств, предназначенных для распознавания образов.

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

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

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

    (Дискриминант – на языке Ада -  отличительный компонент объекта, или значение именуемого типа).

    (далее…)

    27.02.09 , , , , , , , , , , Ассоциативная память и ассоциативные процессоры в интеллектуальных компьютерах

    Курс лекций (5)

    2.3 Обработка коллизий

    2.3.1 Основные концепции

    Все существующие методы обработки коллизий можно разделить на две основные категории:

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

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

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

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

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

    (далее…)

    27.02.09 , , , , , Ассоциативная память и ассоциативные процессоры в интеллектуальных компьютерах