Тип публикации: препринт
Год издания: 2006
Аннотация: Задача сортировки привлекала большое внимание ученых (программистов) еще на заре компьютерной эры. С 50-х годов началось решение проблемы поиска элементов, обладающих определенным свойством в заданном множестве. В данной работе рассматриваются алгоритмы поиска посредством хеширования (открытого и закрытого, способ разрешения коллизПоказать полностьюий, реструктуризация хеш-таблиц), дается их анализ, оценивается эффективность и время выполнения. Приведены практические занятия и лабораторная работа по теме «Хеширование», образцы выполнения заданий, демонстрационное приложение и список литературы. Основной частью данного раздела является ознакомление студентов с двумя различными формами хеширования (хеширование способ организации структуры данных, при котором сложность поиска в среднем составляет O(const)): - открытым, или внешним, хешированием, позволяющим хранить множества в потенциально бесконечном пространстве; - закрытым, или внутренним, хешированием, использующим ограниченное пространство дял хранения данных. На практических занятиях отрабатываются навыки добавления элементов в хеш-таблицу, закрепляются теоретические знания в области анализа времени выполнения операторов вставки, удаления и поиска и методов их программирования. На лабораторных занятиях студентам предлагается разработать и реализовать модуль работы с хеш-таблицей, включающий возможность добавления новых данных в хеш-таблицу и поиск необходимой информации. Наглядный процесс хеширования представлен в приложении в виде картинок. Работа предназначена для студентов вузов, изучающих информатику в качестве профильной дисциплины
Место издания: ВИНИТИ РАН