Домашнее задание № 2

ОЦЕНКА ЭФФЕКТИВНОСТИ АЛГОРИТМОВ

Цель работы – познакомиться с различными алгоритмами сортировки и поиска, оценить их эффективность по памяти и количеству операций.

Контрольные вопросы

1. Что такое сортировка?

2. Какие виды сортировки Вы знаете?

3. Какие методы сортировки называются устойчивыми?

4. Какое среднее количество сравнений требуется для прямых и быстрых методов сортировки?

5. На какие категории можно разбить прямые методы сортировки?

6. Опишите алгоритм сортировки методом пузырька

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

8. Опишите алгоритм сортировки методом вставки

9. Опишите алгоритм сортировки методом прямого выбора

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

11. Опишите алгоритм шейкерная сортировки

12. Опишите алгоритм сортировки методом Шелла

13. Опишите алгоритм сортировки с помощью пирамиды

14. Опишите алгоритм сортировки Хоара

15. Опишите алгоритм поразрядной сортировки

16. Какие методы сортировки файлов Вы знаете?

17. Какие особенности требуется учитывать при сортировке файлов?

18. Опишите алгоритм сортировки методом прямого слияния

19. Опишите алгоритм сортировки методом естественного слияния

20. Опишите алгоритм сортировки методом многопутевого слияния

21. Опишите алгоритм многофазной сортировки

22. Какой метод сортировки обычно используется для подготовки серий перед сортировкой файлов и почему выбран именно он?

23. Что такое поиск? Какие виды поиска Вы знаете

24. Что такое ключ поиска? Какие бывают ключи поиска?

25. Методы поиска в неупорядоченной таблице

26. Методы поиска в упорядоченной последовательности

27. Что такое поисковый индекс?

28. Что такое индекс в индексно-последовательном поиске?

29. Что такое дерево бинарного поиска?

30. Как добавить элемент в дерево бинарного поиска?

31. Как удалить элемент из дерева бинарного поиска?

32. Какие виды сбалансированных деревьев бинарного поиска Вы знаете?

33. Методы балансировки бинарного дерева.

34. Как добавить элемент в красно-черное дерево?

35. Как удалить элемент из красно-черного дерева?

36. Как добавить элемент в декартово дерево?

37. Как удалить элемент из декартова дерева?

38. Что такое «метод ножниц и клея»? Для каких деревьев он применяется?

39. Деревья цифрового поиска. Бор

40. Как добавить элемент в бор?

41. Как удалить элемент из бора?

42. Б-деревья

43. Поиск с использованием хеш-таблиц.

44. Разрешение коллизий при хешировании методом открытой адресации

45. Разрешение коллизий при хешировании методом цепочек

Постановка задачи

Написать две программы согласно номеру индивидуального варианта (номер варианта определяется по последней цифре номера зачетной книжки).

Перед написанием программ создать файл, содержащий N4 неупорядоченных целых чисел (значение N4 указано в вариативной части в первом задании).

---

В первой программе провести сравнение указанных алгоритмов сортировки массивов, содержащих N1, N2, N3 и N4 элементов. Каждую функцию сортировки вызывать трижды: для сортировки упорядоченного массива, массива, упорядоченного в обратном порядке и неупорядоченного массива. Сортируемая последовательность для всех методов должна быть одинаковой (считывать необходимое количество элементов из созданного файла). Оценить эффективность алгоритмов сортировки по заданному критерию и объему требуемой дополнительно памяти.

Во второй программе реализовать две указанные структуры данных, заполнив их значениями из созданного файла, выполнить поиск вводимых с клавиатуры 10 ключей в указанных структурах данных. Оценить количество требуемой памяти для реализации каждой структуры и количество сравнений при поиске.

При оформлении отчета перед каждой программой привести теоретические расчеты трудоемкости в нотации О. После результатов работы программ сделать выводы о правильности выполненных расчетов и выбрать из анализируемых наиболее эффективный алгоритм. После первой программы, помимо этого, вычислить количество используемой каждым алгоритмом дополнительной памяти, а после второй – количество используемой каждой реализованной структурой данных памяти. По результатам проведенных вычислений сделать выводы по соотношению трудоемкость/объем_памяти для анализируемых алгоритмов.

Вариант № 7

1. Порядок: по возрастанию элементов. Методы: пузырька, Шелла (шаг сортировки h_k-1=3h_k+1, h_t=1, t=log₃n-1 и h_k-1=2h_k+1, h_t=1, t=log₂n-1), многопутевого слияния. N1=1000, N2=3000, N3=7000, N4=10000. Критерий – количество присваиваний.

Упорядоченный список, хеш-таблица с разрешением коллизий методом открытой адресации.

---

Смотрите также файлы

• Домашнее задание 1.docx

• 2. Лекции Паскаль (Часть 2).doc

• 1. Лекции Паскаль (Часть 1).doc

• Информатика КР2.pdf

• проектирование информационных систем радчук.docx