Информатика Курсовая работа МИЭМ, 25.12.2009 Изучить алгоритм быстрого поиска Бойера-Мура (БМ) и реализовать его с визуализацией. Выполнил: Матвеев А.В.

Презентация:



Advertisements
Похожие презентации
Алгоритм Бойера - Мура Применяется для поиска подстроки в строке.
Advertisements

Определения Пусть задана строка, состоящая из некоторого количества символов. Проверим, входит ли заданная подстрока в данную строку. Если входит, то.
CAOD, dep.OSU1 Задачи поиска в структурах данных Поиск - нахождение какой-либо конкретной информации в большом объеме ранее собранных данных.
Лекция 5 Поиск. Задача поиска Объекты в общем случае будем рассматривать как записи произвольной природы, однако имеющие в своей структуре один и тот.
Алгоритмы поиска подстроки в строке 1. «Наивный» алгоритм оба обобрали обои бобра обои Число сравнений символов: = 24 public static.
Массивы данных Подготовила: Камышная И.Н.. Массивы данных Массив – это упорядоченная по возрастанию индексов (номеров) совокупность данных одного типа,
АЛГОРИТМЫ Умение составлять алгоритмы просто необходимо, если человек хочет поручить обработку информации машине Алгоритм - определенная последовательность.
АЛГОРИТМИЗАЦИЯ. Алгоритм Алгоритм – описание конечной последовательности действий, приводящей от исходных данных к нужному результату. Где встречаются.
Презентация к курсовой работе По дисциплине: «Объектно-ориентированное программирование» На тему: «Поиск информации с использованием алгоритмов хеширования»
JavaScript Регулярные выражения Введение Создание регулярных выражений Флаги (способы поиска по шаблону) Метасимволы Специальные символы Квантификаторы.
Контрольные измерительные материалы для апробации экзамена по информатике и ИКТ в компьютерной форме Крылов Сергей Сергеевич, декан факультета прикладной.
Этапы моделирования. Постановка задачи: Описание задачи; Цель моделирования; Анализ объекта Разработка информационной модели Разработка компьютерной модели.
Моделирование – исследование объектов путем построения и изучения их моделей. Моделирование – творческий процесс, и поэтому заключить его в формальные.
Основные этапы моделирования. Моделирование – исследование объектов путем построения и изучения их моделей. Моделирование – творческий процесс, и поэтому.
Логическое программировыание Презентация 5 Списки в Прологе.
ПРАКТИКУМ по предмету: Информатика Алгоритмический язык Турбо-Паскаль.
Презентацию создавали учащиеся СОШ 269 г. Снежногорска (учитель Татаришвили Л.И.) УМНЫЙ МЯЧИК.
НАЗВАНИЕ Работу выполнил: ст. 4 курса ФИО Научный руководитель: Должность, ФИО Г. Пермь, 2009 ГОУ ВПО Пермский государственный университет Физический факультет.
Строковый тип данных. Для обработки строковой информации в Турбо Паскаль введен строковый тип данных. Строка - последовательность из определенного количества.
Транксрипт:

Информатика Курсовая работа МИЭМ, Изучить алгоритм быстрого поиска Бойера-Мура (БМ) и реализовать его с визуализацией. Выполнил: Матвеев А.В.

Задачи: МИЭМ, Описание алгоритма Реализация Варианты

3 Описание алгоритма Алгоритм Бойера Мура поиска строки считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером (англ. Robert S. Boyer) и Джеем Муром (англ. J Strother Moore) в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск) шаблон сравнивается с исходным текстом не во всех позициях часть проверок пропускаются как заведомо не дающие результата.

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

5 Реализация упрощенного алгоритма Для шаблона строится таблица совпадений первого символа abeccaebabcaabcd abcd -строка -шаблон Накладываем образец на строку abeccaebabcaabcd abcd

6 Реализация упрощенного алгоритма abeccaebabcaabcd abcd abeccaebabcaabcd abcd abeccaebabcaabcd abcd abeccaebabcaabcd abcd

7 Варианты Название Предварительная обработка Сложность Сред.Макс. Алгоритм Бойера-Мура- Хорспула O(n+σ)