АиФП 4. Пространственно-временной компромисс при разработке алгоритмов

Нажмите для полного просмотра!

АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №2

АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №3

АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №4

АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №5

АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №6

АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №7

АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №8

АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №9

АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №10

АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №11

АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №12

АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №13

АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №14

АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №15

АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №16

АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №17

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему АиФП 4. Пространственно-временной компромисс при разработке алгоритмов. Доклад-сообщение содержит 17 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

4. Пространственно-временной компромисс при разработке алгоритмов « Значащее много никогда не должно находиться во власти значащего мало» - Иоганн Вольфганг фон Гете.

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

Основные подходы к решению задачи пространственно-временного компромисса Улучшение входных данных (- метод сортировки подсчетом, - алгоритм Хорспула для поиска подстрок); Предварительная структуризация (- хеширование, - индексирование при помощи В-деревьев); 3. Динамическое программирование.

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

Пример работы алгоритма сортировки подсчетом сравнений Массив A[0..5] | 62 | 31 | 84 | 96 | 19 | 47 | Изначально Count | 0 | 0 | 0 | 0 | 0 | 0 | После прохода i=0 Count | 3 | 0 | 1 | 1 | 0 | 0 | i=1 Count | | 1 | 2 | 2 | 0 | 1 | i=2 Count | | | 4 | 3 | 0 | 1 | i=3 Count | | | | 5 | 0 | 1 | i=4 Count | | | | | 0 | 2 | Конечный результат Count | 3 | 1 | 4 | 5 | 0 | 2 | Массив S[0..5] | 19 | 31 | 47 | 62 | 84 | 96 |

Слайд 6

Описание слайда:

4.2. Улучшение входных данных в поиске подстрок Задача поиска подстрок состоит в поиске данной подстроки из m символов, именуемой шаблон или образец, в более длинной строке из n символов, называемой текст. Общее количество сравнений в наихудшем случае C(n)=m*(n-m+1) Производительность алгоритма на основе «грубой силы» равна O(n*m). Для случайного естественного текста эффективность в среднем O(n).

Слайд 7

Описание слайда:

Алгоритм Хорспула Пример. Поиск подстроки BARBER в некотором тексте: S0 …. …. c ……Sn-1 BARBER Алгоритм Хорспула определяет величину сдвига, рассматривая символ с текста, который при выравнивании находится напротив последнего символа образца.

Слайд 8

Описание слайда:

Случай 1. Если символа с в образце нет, то можно сдвинуть образец на всю его длину. S0 …. …. S …… Sn-1  B A R B E R B A R B E R

Слайд 9

Описание слайда:

Случай 2. Если символ с в образце есть, но он не последний. S0 …. …. B ……Sn-1  B A R B E R B A R B E R Сдвиг должен выровнять образец так, чтобы напротив с в тексте было первое справа вхождение символа в образец.

Слайд 10

Описание слайда:

Случай 3. Если символ с последний символ образца и среди остальных (m-1) символов образца такого символа нет, то сдвиг должен быть подобен сдвигу в случае 1, т.е. на величину m. S0 …. …. M E R ……Sn-1  = = L E A D E R LEADER

Слайд 11

Описание слайда:

Случай 4. Если символ с последний символ образца и среди остальных (m-1) символов образца имеются вхождения этого символа, то сдвиг должен быть подобен сдвигу в случае 2. S0 …. …. O R ……Sn-1  = R E O R D E R R E O R D E R

Слайд 12

Описание слайда:

Величины сдвигов для символа с : Величины сдвигов для символа с : Длина образца m, если с нет среди первых m-1 символов образца. t(c)= Расстояние от крайнего справа символа с среди первых (m-1) символов образца до его последнего символа Для образца B A R B E R все элементы таблицы равны 6 , а для символов : E 1, B  2, R  3, A  4.

Слайд 13

Описание слайда:

Алгоритм ShiftTable (P[0..m-1]) Алгоритм ShiftTable (P[0..m-1]) // Заполнение таблицы сдвигов // Вх. данные: Образец P[0..m-1] и алфавит возможных символов // Вых. данные: таблица Table [0..size-1] Инициализация всех элементов Table значениями m for j←0 to m-2 do Table[P[j]] ←m-1-j return Table

Слайд 14

Описание слайда:

Алгоритм Хорспула Шаг 1. Для данного образца длиной m и алфавита, используемого в тексте и образце, строится таблица сдвигов. Шаг 2. Выравнивается начало образца с началом текста. Шаг 3. До тех пор, пока не будет найдена искомая подстрока или пока образец не достигнет последнего символа текста, повторять следующие действия.

Слайд 15

Описание слайда:

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

Слайд 16

Описание слайда:

Алгоритм Horspool (P [0..m-1], T [0..m-1]) Алгоритм Horspool (P [0..m-1], T [0..m-1]) // Вх. данные: Образец P [0..m-1], и текст T [0..m-1] // Вых. данные: Индекс левого конца первой найденной подстроки или -1, если подстроки в тексте нет. ShiftTable (P[0..m-1]) i←m-1 while in-1 do k←0 while km-1 and P[m-1-k]=T[i-k] do k←k+1 if k=m return i-m+1 else i←i+ Table[T[i]] return -1

Слайд 17

Описание слайда:

Пример поиска подстроки BARBER в тексте из латинских букв и пробелов ( _ ) Таблица сдвигов J I M _ S A W _ M E _ I N _ A _ B A R B E R S H O P BAR B E R BAR B E R B A R B E R B A R B E R B A R B E R B A R B E R