🗊Презентация Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №1Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №2Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №3Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №4Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №5Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №6Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №7Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №8Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №9Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №10Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №11Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №12Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №13Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №14Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №15Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №16Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №17Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №18Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №19Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №20Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №21Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №22Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №23Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №24Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №25Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №26Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №27Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №28Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №29Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №30Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №31Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №32Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №33Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №34Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №35Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №36Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №37Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №38Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №39Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №40Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №41Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №42
Скачать

Содержание ▲

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

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

Слайд 1


Linked lists Односвязный список
Описание слайда:
Linked lists Односвязный список

Слайд 2


Операции над списками
Описание слайда:
Операции над списками

Слайд 3


Random Access Memory У каждой ячейки свой адрес Быстрый доступ к ячейке по адресу Поддержка адресной арифметики
Описание слайда:
Random Access Memory У каждой ячейки свой адрес Быстрый доступ к ячейке по адресу Поддержка адресной арифметики

Слайд 4


Array Сплошной массив элементов в памяти Задан адрес начального элемента Быстрое вычисление адреса элемента по индексу Невозможность расширения Сложность операций:
Описание слайда:
Array Сплошной массив элементов в памяти Задан адрес начального элемента Быстрое вычисление адреса элемента по индексу Невозможность расширения Сложность операций:

Слайд 5


Linked lists once again…. Произвольное расположение элементов Возможность расширения Медленный доступ по индексу:
Описание слайда:
Linked lists once again…. Произвольное расположение элементов Возможность расширения Медленный доступ по индексу:

Слайд 6


Формулировка проблемы Необходимость быстрого поиска данных в огромных массивах Где применить: Справочники Базы данных пользователей Реализация множеств Ассоциативные массивы Желаемая сложность выполнения операций:
Описание слайда:
Формулировка проблемы Необходимость быстрого поиска данных в огромных массивах Где применить: Справочники Базы данных пользователей Реализация множеств Ассоциативные массивы Желаемая сложность выполнения операций:

Слайд 7


Создание баз данных логинов-паролей Огромное количество пользователей системы Время доступа – критический параметр Огромное количество возможных комбинаций Доступ по индексу не требуется Безопасность хранения данных
Описание слайда:
Создание баз данных логинов-паролей Огромное количество пользователей системы Время доступа – критический параметр Огромное количество возможных комбинаций Доступ по индексу не требуется Безопасность хранения данных

Слайд 8


База данных телефонных номеров Ограниченное количество всевозможных номеров Ключевой параметр – скорость поиска Каждый номер уникален Относительно небольшое количество номеров реально задействовано База данных постоянно пополняется
Описание слайда:
База данных телефонных номеров Ограниченное количество всевозможных номеров Ключевой параметр – скорость поиска Каждый номер уникален Относительно небольшое количество номеров реально задействовано База данных постоянно пополняется

Слайд 9


База данных телефонных номеров Решение – список Проблемы: Очень долгий поиск Решение – огромный массив
Описание слайда:
База данных телефонных номеров Решение – список Проблемы: Очень долгий поиск Решение – огромный массив

Слайд 10


Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №10
Описание слайда:

Слайд 11


База данных телефонных номеров Решение – список Проблемы: Очень долгий поиск Решение – огромный массив Проблемы: Массив занимает очень много места Большое количество полей массива не заполнено
Описание слайда:
База данных телефонных номеров Решение – список Проблемы: Очень долгий поиск Решение – огромный массив Проблемы: Массив занимает очень много места Большое количество полей массива не заполнено

Слайд 12


Концепция Хеш-таблицы Массив фиксированной длинны Положение элемента определяется хеш-функцией Отображение элементов на множество индексов не взаимно-однозначное Достоинства: Занимает относительно мало места Быстрый поиск элемента Недостатки: Не сохраняется порядок Не эффективны при малом количестве элементов В одну ячейку могут попасть много элементов
Описание слайда:
Концепция Хеш-таблицы Массив фиксированной длинны Положение элемента определяется хеш-функцией Отображение элементов на множество индексов не взаимно-однозначное Достоинства: Занимает относительно мало места Быстрый поиск элемента Недостатки: Не сохраняется порядок Не эффективны при малом количестве элементов В одну ячейку могут попасть много элементов

Слайд 13


Организация хеш-таблицы и проблема коллизий
Описание слайда:
Организация хеш-таблицы и проблема коллизий

Слайд 14


Решение проблемы коллизий Метод цепочек (закрытая адресация)
Описание слайда:
Решение проблемы коллизий Метод цепочек (закрытая адресация)

Слайд 15


Закрытая адресация В каждой ячейке хранится список значений При добавлении элемент с заданным хешом добавляется в конец списка Простое удаление элемента из списка При хорошей хеш-функции сложность поиска , где – коэффициент заполненности При большом коэффициенте заполненности необходима перестройка таблицы Тратится место на хранение ссылок в списках
Описание слайда:
Закрытая адресация В каждой ячейке хранится список значений При добавлении элемент с заданным хешом добавляется в конец списка Простое удаление элемента из списка При хорошей хеш-функции сложность поиска , где – коэффициент заполненности При большом коэффициенте заполненности необходима перестройка таблицы Тратится место на хранение ссылок в списках

Слайд 16


Закрытая адресация
Описание слайда:
Закрытая адресация

Слайд 17


Открытая адресация Порядок вставки определяется последовательностью проб Последовательность проб должна содержать каждую ячейку таблицы не более одного раза При коэффициенте заполненности, близком к 1 поиск занимает , где N – размер таблицы Сложная операция удаления
Описание слайда:
Открытая адресация Порядок вставки определяется последовательностью проб Последовательность проб должна содержать каждую ячейку таблицы не более одного раза При коэффициенте заполненности, близком к 1 поиск занимает , где N – размер таблицы Сложная операция удаления

Слайд 18


Открытая адресация
Описание слайда:
Открытая адресация

Слайд 19


Последовательность проб: пробивание Линейное пробирование
Описание слайда:
Последовательность проб: пробивание Линейное пробирование

Слайд 20


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

Слайд 21


Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №21
Описание слайда:

Слайд 22


Хеширование Хеширование (англ. hashing) — преобразование массива входных данных произвольной длины в битовую строку фиксированной длины, выполняемое определённым алгоритмом. Хеш-функция – функция, реализующая алгоритм хеширования Хеш (хеш-сумма, хеш-код) – результат выполнения хеширования
Описание слайда:
Хеширование Хеширование (англ. hashing) — преобразование массива входных данных произвольной длины в битовую строку фиксированной длины, выполняемое определённым алгоритмом. Хеш-функция – функция, реализующая алгоритм хеширования Хеш (хеш-сумма, хеш-код) – результат выполнения хеширования

Слайд 23


Хеш-функции
Описание слайда:
Хеш-функции

Слайд 24


Хеш-функции Результат применения хеш-функции имеет фиксированную длину При небольшом изменении входных данных существенно меняется результат Нет взаимно-однозначного соответствия между входными данными и ответом Ключевые свойства хеш-функций: Вычислительная сложность Разрядность Криптостойкость
Описание слайда:
Хеш-функции Результат применения хеш-функции имеет фиксированную длину При небольшом изменении входных данных существенно меняется результат Нет взаимно-однозначного соответствия между входными данными и ответом Ключевые свойства хеш-функций: Вычислительная сложность Разрядность Криптостойкость

Слайд 25


Хорошие хеш-функции Свойства «хорошоих» хеш-функций: Минимальное количество коллизий Равномерное распределение ответов Быстрое вычисление Идеальная хеш-функция – хеш-функция которая отображает каждый ключ из набора S во множество целых чисел без коллизий
Описание слайда:
Хорошие хеш-функции Свойства «хорошоих» хеш-функций: Минимальное количество коллизий Равномерное распределение ответов Быстрое вычисление Идеальная хеш-функция – хеш-функция которая отображает каждый ключ из набора S во множество целых чисел без коллизий

Слайд 26


Применение хеш-функций Хранение и поиск данных Компьютерная графика Контрольные суммы Информационная безопасность
Описание слайда:
Применение хеш-функций Хранение и поиск данных Компьютерная графика Контрольные суммы Информационная безопасность

Слайд 27


Примеры хеш-функций Остаток от деления Не криптостойкий Отсутствует лавинный эффект При некоторых N возникает много коллизий
Описание слайда:
Примеры хеш-функций Остаток от деления Не криптостойкий Отсутствует лавинный эффект При некоторых N возникает много коллизий

Слайд 28


Примеры хеш-функций Полиномиальный хеш Не криптостойкий При некоторых N возникает много коллизий
Описание слайда:
Примеры хеш-функций Полиномиальный хеш Не криптостойкий При некоторых N возникает много коллизий

Слайд 29


Примеры хеш-функций XOR – хеширование Не криптостойкий Отсутствует лавинный эффект
Описание слайда:
Примеры хеш-функций XOR – хеширование Не криптостойкий Отсутствует лавинный эффект

Слайд 30


Примеры хеш-функций Cyclic redundancy check (CRC) Не криптостойкий
Описание слайда:
Примеры хеш-функций Cyclic redundancy check (CRC) Не криптостойкий

Слайд 31


Примеры хеш-функций Семейство MD (Message Digest) MD4 (взломан) MD5 (взломан) MD6 Семейство SHA (Secure Hash Algorithm) SHA-1 (взломан) SHA-2 (взломан) SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/256, SHA-512/224 SHA-3 (Keccak)
Описание слайда:
Примеры хеш-функций Семейство MD (Message Digest) MD4 (взломан) MD5 (взломан) MD6 Семейство SHA (Secure Hash Algorithm) SHA-1 (взломан) SHA-2 (взломан) SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/256, SHA-512/224 SHA-3 (Keccak)

Слайд 32


Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №32
Описание слайда:

Слайд 33


Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №33
Описание слайда:

Слайд 34


Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №34
Описание слайда:

Слайд 35


Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №35
Описание слайда:

Слайд 36


Сравнение производительности Добавление 10000 элементов
Описание слайда:
Сравнение производительности Добавление 10000 элементов

Слайд 37


Сравнение производительности Поиск несуществующего элемента
Описание слайда:
Сравнение производительности Поиск несуществующего элемента

Слайд 38


Сравнение производительности Поиск 1000 случайных элементов
Описание слайда:
Сравнение производительности Поиск 1000 случайных элементов

Слайд 39


Сравнение производительности Поиск 1000 существующих элементов
Описание слайда:
Сравнение производительности Поиск 1000 существующих элементов

Слайд 40


Linked lists. Односвязный и двусвязный списки. Концепция хеш-таблицы, слайд №40
Описание слайда:

Слайд 41


Встроенные хеш-таблицы в Python Словари (dict) Ассоциативный массив Хранит пары ключ-значение Быстрый поиск по ключам Множества (set) Операции над множествами Быстрый поиск элемента
Описание слайда:
Встроенные хеш-таблицы в Python Словари (dict) Ассоциативный массив Хранит пары ключ-значение Быстрый поиск по ключам Множества (set) Операции над множествами Быстрый поиск элемента

Слайд 42


Слайд №42
Описание слайда:
Слайд №42

Скачать

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