Презентация АиФП 4. Пространственно-временной компромисс при разработке алгоритмов онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему АиФП 4. Пространственно-временной компромисс при разработке алгоритмов абсолютно бесплатно. Урок-презентация на эту тему содержит всего 17 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:17 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:131.00 kB
- Просмотров:68
- Скачиваний:1
- Автор:неизвестен
Слайды и текст к этой презентации:
№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 in-1 do
k←0
while km-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
Скачать все slide презентации АиФП 4. Пространственно-временной компромисс при разработке алгоритмов одним архивом:
