Алгоритмы поиска и сортировки данных

Одной из основных задач информатики как науки является накопление информации. С момента создания первых ЭВМ они использовались как хранилища информации. На магнитных лентах, а позднее на барабанах и дисках создавались библиотеки взаимосвязанных данных (базы данных) как локального, так и глобального доступа. Возможность получения данных из этих библиотек и послужила одним из важнейших стимулов создания глобальных сетей типа Internet. В настоящее время объем накопленных баз данных приближается к сотням и тысячам терабайт.

---

Если хотите узнать, сколько стоит сделать курсовую работу , сервис Work5 подскажет.

---

. Очевидно, что для быстрого поиска необходимой информации на информационных серверах глобальных сетей необходимо специальное программно-алгоритмическое обеспечение, входящее в состав так называемых информационно-поисковых систем. Наиболее известными из таких систем в сети Internet являются AltaVista, Yahoo, Rambler, Ау, Апорт и т.д. Основой таких систем являются 2 программы: программа сортировки непрерывно поступающей на сайты (узлы, серверы) Internet’а информации по какому-либо признаку (по ключевым словам, по авторам, по времени создания, по странам и компаниям-разработчикам и т.д.) и программа поиска информации по вышеприведенным признакам. От эффективности и скорости работы этих программ в конечном итоге зависит время получения необходимой информации, как через глобальные сети, так и из локальных баз данных на конкретном компьютере. Алгоритмы и программы сортировки и поиска информации непрерывно совершенствуются, что вызвано необходимостью создания более быстродействующих информационно-поисковых систем, способных справиться с непрерывно нарастающим объемом информации, т.к. при современном уровне телекоммуникаций именно эти программы являются наиболее медленным звеном. Проблемам сортировок Дональд Кнут посвятил целый том своего «Искусства программирования». На данный момент существует множество алгоритмов сортировки данных. Зачастую выбор алгоритма решения задачи зависит от структуры сортируемых данных. В случае сортировки эта зависимость имеет большое значение, и методы сортировки обычно разделяют на две категории: Сортировка массивов (внутренняя сортировка) Сортировка последовательных файлов (внешняя сортировка) При внутренней сортировке массивы располагаются в оперативной памяти ЭВМ, что обеспечивает быстрый произвольный доступ к данным. При внешней сортировке файлы хранятся в более "медленной", но более вместительной внешней памяти, т.е. на запоминающих устройствах с механическим передвижением (магнитных дисках и других носителях). Критериями оценки методов сортировки являются: количество операций сравнения пар ключей число перестановок элементов экономное использование памяти. Одним из видов алгоритма поиска является двоичный поиск, основан на инварианте цикла. Инвариант цикла – это соотношение, которое истинно перед циклом, истинно в процессе выполнения цикла и истинно при выходе из цикла. Все это описано у Дейкстры в книге «Дисциплина программирования», и детально разжевано у Гриса в книге «Наука программирования». Целью данной курсовой работы является рассмотрение алгоритмов сортировки и поиска. Задачи курсовой работы: - рассмотреть алгоритмы сортировки; - рассмотреть алгоритмы поиска; - привести примеры решения задач с помощью алгоритмов сортировки и поиска.

Алгоритм – это точно определенная (однозначная) последовательность простых (элементарных) действий, обеспечивающих решение любой задачи из некоторого класса, т.е. такой набор инструкций, который можно реализовать чисто механически, вне зависимости от умственных способностей и возможностей исполнителя. Как заметил Кнут: «Алгоритм должен быть определен настолько четко, чтобы его указаниям мог следовать даже компьютер». Теория алгоритмов и практика их построения и анализа является концептуальной основой разнообразных процессов обработки информации. В настоящее время теория алгоритмов образует теоретический фундамент вычислительных наук. Применение теории алгоритмов осуществляется как в использовании самих результатов (особенно это касается использования разработанных алгоритмов), так и в обнаружении новых понятий и уточнении старых. С ее помощью проясняются такие понятия как доказуемость, эффективность, разрешимость, перечислимость и другие. Эффективность алгоритма определяется анализом, который должен дать четкое представление, во-первых, о емкостной и, во-вторых, о временной сложности процесса. Речь идет о размерах памяти, в которой предстоит размещать все данные, участвующие в вычислительном процессе (естественно, к ним относятся входные наборы, промежуточная и выходная информация), а также физических ресурсах, затраченных исполнителем. В курсовой работе представлены различные подходы и методы использования алгоритмов, приведены оценки сложностей алгоритмов, реализации математических задач с помощью алгоритмов. Проведена краткая характеристика используемых структур данных, эффективность их применения в данной задаче. Рассмотрены алгоритмы поиска: Алгоритм поиска A* — особый случай поиска по первому наилучшему совпадению; используется эвристика, увеличивающая скорость работы алгоритма Алгоритм выбора (англ.) — модификация алгоритма линейного поиска; находит k-тый по величине элемент в списке; Двоичное дерево поиска — использует бинарное дерево для хранения элементов; Двоичный поиск — находит элемент в отсортированном списке Интерполирующий поиск (Предсказывающий поиск, Поиск по словарю) Линейный поиск — находит элемент в неотсортированном списке Локальный поиск (оптимизация) Поиск в глубину — проходит граф ветка за веткой Поиск в ширину — проходит граф уровень за уровнем Поиск по первому наилучшему совпадению (англ. Best-first search) — проходит граф в порядке важности, используя очередь приоритетов Троичный поиск — находит максимум или минимум функции Поиск в хеш-таблице Алгоритм Ли (волновой алгоритм) — поиск пути на карте. А также алгоритмы сортировки: Bogosort Stooge sort Наивная сортировка — генерация всех n! возможных перестановок и проверка на отсортированность Блинная сортировка Блочная сортировка (также известен как корзинная сортировка), ср. с поразрядной Быстрая сортировка — с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине Глупая сортировка Гномья сортировка — имеет общее с сортировкой пузырьком и сортировкой вставками. Сложность алгоритма — O(n2). Пирамидальная сортировка (Сортировка кучей) — превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка Плавная сортировка (англ.) Поразрядная сортировка — сортирует строки буква за буквой. Сортировка Бентли — Седжвика (англ. BeSe sort) — модификация быстрой сортировки для составных ключей, заключающаяся в делении не пополам, а на три части — в третью попадают одинаковые (по текущему символу) ключи Сортировка с помощью двоичного дерева (англ. Tree sort) Сортировка методом вставок — определяем, где текущий элемент должен находиться в отсортированном списке, и вставляем его туда Сортировка методом выбора — наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка Сортировка перемешиванием (Сортировка коктейлем) Сортировка подсчётом — используется диапазон входных данных, подсчитывается число одинаковых элементов (3 варианта) Сортировка пузырьком Сортировка расчёской Сортировка слиянием — сортируем первую и вторую половину списка отдельно, а затем — сливаем отсортированные списки Сортировка Шелла — попытка улучшить сортировку вставками Топологическая сортировка Хитрая сортировка — извлекает из исходной последовательности отсортированные подпоследовательности, производя их слияние с уже извлечёнными данными. Цифровая сортировка — то же, что и Поразрядная сортировка. ?

Ананий В. Левитин Глава 4. Метод декомпозиции: Бинарный поиск // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 180-183. 2. Амосов А.А., Дубинский Ю. А., Копченова Н.П. Вычислительные методы для инженеров. — М.: Мир, 1998. 3. Бахвалов Н.С., Жидков Н.П., Кобельков Г.Г. Численные методы. — 8-е изд.. — М.: Лаборатория Базовых Знаний, 2000. 4. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989. 5. Волков Е.А. Численные методы. — М.: Физматлит, 2003. 6. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985. 7. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576. 8. Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд. Глава 7. Быстрая сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-e издание. — М.: «Вильямс», 2005. 9. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. 10. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — Энергоатомиздат, 1972. 11. Кнут Д. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. - М. Мир, 1978. 12. Лэнгсам Й., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ. - М.: Мир, 1989. 13. Лорьер Ж.-Л. Системы искусственного интеллекта / Пер. с фр. и ред. В. Л. Стефанюка. — М.: Мир, 1991. — С. 238—244. — 20 000 экз. 14. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982. 15. Нильсон Н. Искусственный интеллект: методы поиска решений = Problem-solving Methods in Artificial Intelligence / Пер. с англ. В. Л. Стефанюка; под ред. С. В. Фомина. — М.: Мир, 1973. — С. 70 — 80. 16. Рассел С. Дж., Норвиг, П. Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach / Пер. с англ. и ред. К. А. Птицына. — 2-е изд.. — М.: Вильямс, 2006. — С. 157—162. — 3000 экз. 17. Сибуя М., Ямамото Т. Алгоритмы обработки данных. - М.: Мир, 1986. 18. Dechter, R., Pearl, J. Generalized best-first search strategies and the optimality of A* // Journal of the ACM. — 1985. — Т. 32. — № 3. — С. 505 — 536. 19. Hart P. E., Nilsson, N. J., Raphael, B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths // IEEE Transactions on Systems Science and Cybernetics SSC4. — 1968. — № 2. — С. 100 — 107. 20. Hart P. E., Nilsson, N. J., Raphael, B. Correction to «A Formal Basis for the Heuristic Determination of Minimum Cost Paths» // SIGART Newsletter. — 1972. — Т. 37. — С. 28 — 29. 21. Pearl J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. — Addison-Wesley, 1984.