Матричный алгоритм сравнения строк Выполнила: студентка группы ИМ-11 Чаркова Виктория Научный руководитель: канд. физ.-мат. наук Бобылева О. В.

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

Задачи исследования: 1. Разработать теоретические основы матричного алгоритма нечеткого поиска; 2. Доказать справедливость выполнения алгоритма на конкретных примерах; 3. Проанализировать преимущества и ограничения матричного алгоритма. Объект исследования: алгоритмы нечеткого поиска. Предмет исследования: матричные алгоритмы нечеткого поиска. 3

Теоретические основы алгоритма (1) 4

Теоретические основы алгоритма 5

12345 ЧИЖОВ 1Ч1 2И 1 3Ж 1 4О 1 5В 1 6

АБДУЛОВ 1А10 2Б 10 3У 01 4Л 01 5О 01 6В 01 7

ЧЕРЕПАНОВ 1Ч100 2Е 101 3Р 100 4П 010 5Н 001 6О 001 7В 001 8

9

Теорема. След диапазона точного смещения есть разность между длиной наибольшей строки и количеством допущенных ошибок. Теоретические основы алгоритма 10

Матричный алгоритм сравнения строк 11

Реализация алгоритма сравнения строк 12

БАРЖЕНАКОВ 1Б10 2А 10 3Ж 01 4И 00 5Н 01 6А 01 7К 01 8О 01 9В 01 Реализация алгоритма сравнения строк 2) 13

Реализация алгоритма сравнения строк 14

Выводы 1. Сформулированы и доказаны теоретические основы матричного алгоритма нечеткого поиска; 2. Разработанный алгоритм устанавливает точность совпадения двух строк с точностью до двух несовпадений; 3. Алгоритм прост в реализации; 4. Результаты могут быть использованы для нечеткого поиска в базах данных. 15

СПАСИБО ЗА ВНИМАНИЕ!!!