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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
АиФП 4. Пространственно-временной компромисс при разработке алгоритмов, слайд №1АиФП 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. Пространственно-временной компромисс при разработке алгоритмов « Значащее много никогда не должно находиться во власти значащего мало» - Иоганн Вольфганг фон Гете.
Описание слайда:
4. Пространственно-временной компромисс при разработке алгоритмов « Значащее много никогда не должно находиться во власти значащего мало» - Иоганн Вольфганг фон Гете.

Слайд 2


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

Слайд 3


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

Слайд 4


4.1. Сортировка подсчетом Основная идея: подсчитать для каждого элемента сортируемого списка общее количество элементов, меньших данного, и занести полученный результат в таблицу. Полученные числа указывают позиции элементов в отсортированном списке.
Описание слайда:
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 |
Описание слайда:
Пример работы алгоритма сортировки подсчетом сравнений Массив 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).
Описание слайда:
4.2. Улучшение входных данных в поиске подстрок Задача поиска подстрок состоит в поиске данной подстроки из m символов, именуемой шаблон или образец, в более длинной строке из n символов, называемой текст. Общее количество сравнений в наихудшем случае C(n)=m*(n-m+1) Производительность алгоритма на основе «грубой силы» равна O(n*m). Для случайного естественного текста эффективность в среднем O(n).

Слайд 7


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

Слайд 8


Случай 1. Если символа с в образце нет, то можно сдвинуть образец на всю его длину. S0 …. …. S …… Sn-1  B A R B E R B A R B E R
Описание слайда:
Случай 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 Сдвиг должен выровнять образец так, чтобы напротив с в тексте было первое справа вхождение символа в образец.
Описание слайда:
Случай 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
Описание слайда:
Случай 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
Описание слайда:
Случай 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.
Описание слайда:
Величины сдвигов для символа с : Величины сдвигов для символа с : Длина образца 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
Описание слайда:
Алгоритм 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. До тех пор, пока не будет найдена искомая подстрока или пока образец не достигнет последнего символа текста, повторять следующие действия.
Описание слайда:
Алгоритм Хорспула Шаг 1. Для данного образца длиной m и алфавита, используемого в тексте и образце, строится таблица сдвигов. Шаг 2. Выравнивается начало образца с началом текста. Шаг 3. До тех пор, пока не будет найдена искомая подстрока или пока образец не достигнет последнего символа текста, повторять следующие действия.

Слайд 15


1. Начиная с последнего символа образца, сравниваем соответствующие символы в шаблоне и в тексте, пока не будет обнаружена пара разных символов. 1. Начиная с последнего символа образца, сравниваем соответствующие символы в шаблоне и в тексте, пока не будет обнаружена пара разных символов. 2. Находим элемент t(c) из таблицы символов, где c  символ текста, находящийся напротив последнего символа образца , и сдвигаем образец вдоль текста на t(c) символов вправо.
Описание слайда:
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
Описание слайда:
Алгоритм 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
Описание слайда:
Пример поиска подстроки 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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию