Структуры и алгоритмы обработки данных

8. САМОСТОЯТЕЛЬНАЯ РАБОТА СТУДЕНТОВ 
Для более детального изучения дисциплины в рамках самостоятельной
работы студент должен готовиться к выполнению и защите лабораторных 
работ. Расчётные задания и курсовой проект выполняется студентом 
самостоятельно по индивидуальному заданию.
 

---

17 
8.1 
 Структура и объём самостоятельной работы 
Вид самостоятельной работы 
Объём в часах 
3-й семестр 4-й семестр 
Всего 
Подготовка к лабораторным работам 
36 
38 
74 
Выполнение расчетных заданий 
30 
- 
30 
Самостоятельное изучение отдельных 
тем (реферат)
- 
Выполнение курсового проекта 

52 
52 
Подготовка к зачёту 
14 

14 
Подготовка к экзамену 
35 
35 
И т о г о
80 
125 
205 
8.2 
Расчетные задания 
Расчетные задания (РГР) выполняются в 3-ем семестре и предназначены 
для развития у студентов творческого подхода при решении различных задач. 
Как правило, решения этих задач нет в учебниках. 
Тематика первого расчетного задания определяется преподавателем 
индивидуально и посвящена разработке алгоритма и программы формирования 
и редактирования оригинальной структуры данных. Например: 
1. Разработать алгоритм и написать программу построения 2-3 дерева и 
процедуру вставки ключа в это дерево. 
2. Разработать алгоритм и написать программу построения 2-3 дерева и 
процедуру удаления ключа из этого дерева. 
3. Разработать алгоритм и написать программу построения АВЛ-дерева и 
процедуру вставки ключа в это дерево и его балансировки в случае 
необходимости. 
4. Разработать алгоритм и написать программу построения АВЛ дерева и 
процедуру удаления ключа из этого дерева и его балансировки в случае 
необходимости. 
5. Разработать алгоритм и написать программу прошивания дерева при 
симметричном порядке обхода его. 

---

18 
6. Разработать алгоритм и написать программу вставки узла в прошитое и 
обычное деревья и оценить эффективность 
7. Разработать алгоритм и написать программу прошивания дерева при 
прямом порядке обхода его. 
8. Разработать алгоритм и написать программу прошивания дерева при 
обратном порядке обхода его. 
9. Разработать алгоритм и написать программу построения случайного 
дерева, поиск в дереве.
10. Разработать алгоритм и написать программу построения 
сбалансированного дерева, поиск в дереве.
11. Разработать алгоритм и написать программу построения АВЛ-дерева, 
поиск минимального и максимального элемента.
12. Разработать алгоритм и написать программу построения прошитого 
АВЛ-дерева, поиск соседнего элемента.
13. Разработать алгоритм и написать программу построения 2-3-дерева, 
поиск минимального и максимального элемента.
14. Разработать алгоритм и написать программу построения прошитого 2-
3-дерева, поиск соседнего элемента.
15. Разработать алгоритм и написать программу построения trie-дерева, 
добавление вершин.
16. Разработать алгоритм и написать программу построения trie-дерева, 
удаление вершин.
17. Разработать алгоритм и написать программу построения trie-дерева, 
поиск минимального и максимального элемента.
18. Разработать алгоритм и написать программу построения прошитого 
trie-дерева, поиск соседнего элемента.
19. Разработать алгоритм и написать программу построения B-дерева, 
добавление вершин.
20. Разработать алгоритм и написать программу построения B-дерева, 
удаление вершин.

---

19 
21. Разработать алгоритм и написать программу построения B-дерева, 
поиск минимального и максимального элемента.
22. Разработать алгоритм и написать программу построения прошитого 
B-дерева, поиск соседнего элемента.
23. Разработать алгоритм и написать программу преобразования 
заданного упорядоченного дерева в бинарное. 
24. Разработать алгоритм и написать программу прошивания бинарного 
дерева. 
25. Разработать алгоритм и написать программу балансировки бинарного 
дерева. 
26. Разработать алгоритм и написать программу реализации алгоритма 
Хаффмена. 
27. Разработать алгоритм и написать программу формирования таблиц 
символов с помощью бинарных деревьев. 
28. Разработать алгоритм и написать программу использования 
синтаксических деревьев для синтаксического анализа.
29. Разработать алгоритм и написать программу сортировки Шелла.
30. Разработать алгоритм и написать программу быстрой сортировка 
Хоара. Рекурсивный вариант.
31. Разработать алгоритм и написать программу быстрой сортировка 
Хоара. Улучшенный вариант с одним рекурсивным вызовом.
32. Разработать алгоритм и написать программу пирамидальной 
сортировки. Рекурсивный вариант.
33. Разработать алгоритм и написать программу пирамидальной 
сортировки. Нерекурсивный вариант.
34. Разработать алгоритм и написать программу цифровой сортировки 
однобайтовых чисел.
35. Разработать алгоритм и написать программу цифровой сортировки 
строк одинаковой длины.
36. Разработать алгоритм и написать программу Цифровая сортировка 
строк различной длины.

---

20 
37. Разработать алгоритм и написать программу Сортировка слиянием. 
Рекурсивный вариант.
38. Разработать алгоритм и написать программу Сортировка слиянием. 
Нерекурсивный вариант.
39. Разработать алгоритм и написать программу Вычисление k-го 
элемента методом Хоара.
40. Разработать алгоритм и написать программу Внешняя сортировка 
сбалансированным двухпутевым слиянием.
41. Разработать алгоритм и написать программу Внешняя многофазная 
сортировка двухпутевым слиянием.
42. Разработать алгоритм и написать программу Дихотомический поиск 
одного элемента массива.
43. Разработать алгоритм и написать программу Дихотомический поиск 
всех одинаковых элементов.
44. Разработать алгоритм и написать программу Хеширование с открытой 
адресацией. Вставка, поиск элементов.
45. Разработать алгоритм и написать программу Хеширование, метод 
цепочек. Вставка, поиск элементов.
46. Разработать алгоритм и написать программу Хеширование, метод 
цепочек. Вставка, поиск, удаление элементов.
47. Разработать алгоритм и написать программу Построение случайного 
дерева, поиск в дереве.
48. Разработать алгоритм и написать программу Построение случайного 
дерева, поиск, удаление вершин в дереве.
49. Разработать алгоритм и написать программу Построение 
выровненного дерева, поиск в дереве.
50. Разработать алгоритм и написать программу Построение 
выровненного дерева, поиск, удаление вершин в дереве.
51. Разработать алгоритм и написать программу Построение прошитого 
АВЛ-дерева, поиск соседнего элемента.

---

21 
52. Разработать алгоритм и написать программу Иерархическая 
сортировка таблицы.
53. Разработать алгоритм и написать программу Независимая сортировка 
ссылками таблицы по двум ключам.
54. Разработать алгоритм и написать программу Хеширование для 
независимого поиска в таблице по двум ключам. Добавление, поиск и удаление.
55. Разработать алгоритм и написать программу Вычисление проекции 
таблицы с помощью иерархической сортировки.
56. Разработать алгоритм и написать программу Вычисление проекции 
таблицы с помощью предварительной, независимой сортировки по двум 
ключам.
57. Разработать алгоритм и написать программу Вычисление проекции 
таблицы с помощью хеширования.
58. Разработать алгоритм и написать программу Вычисление соединения 
двух таблиц по одному ключу. Таблицы отсортированы по этому ключу.
59. Разработать алгоритм и написать программу Вычисление соединения 
двух таблиц по одному ключу. Имеется сортировка ссылками таблиц по этому 
ключу.
60. Разработать алгоритм и написать программу Вычисление соединения 
двух таблиц по одному ключу. Имеются хеш-таблицы со ссылками по этому 
ключу.
61. Разработать алгоритм и написать программу Простейший алгоритм 
распознавания подцепочки.
62. Разработать алгоритм и написать программу Алгоритм распознавания 
подцепочки, вычисляющий функцию отказов.
63. Разработать алгоритм и написать программу Алгоритм Бауэра-Мура 
распознавания подцепочки.
64. Разработать алгоритм и написать программу Поиск в лабиринте. 
Рекурсивный вариант.
65. Разработать алгоритм и написать программу Поиск в лабиринте. 
Нерекурсивный вариант.

---

22 
66. Разработать алгоритм и написать программу Бэктрекинг для какой-
либо головоломки. Рекурсивный вариант.
67. Разработать алгоритм и написать программу Задача коммивояжера. 
Полный перебор, рекурсивный вариант.
68. Разработать алгоритм и написать программу Задача коммивояжера. 
Алгоритм ближайшего соседа.
69. Разработать алгоритм и написать программу Задача коммивояжера. 
Алгоритм ближайшего города.
70. Разработать алгоритм и написать программу Задача коммивояжера. 
Алгоритм, основанный на построении остовного дерева наименьшей 
стоимости.
71. Разработать алгоритм и написать программу Поиск гамильтонового 
цикла переборным алгоритмом.
72. Разработать алгоритм и написать программу Нахождение наибольшей 
максимальной клики переборным алгоритмом с отсечениями.
73. Разработать алгоритм и написать программу Вычисление эйлерова 
цикла в графе.
74. Разработать алгоритм и написать программу Остовное дерево 
наименьшей стоимости, алгоритм Прима.
75. Разработать алгоритм и написать программу Остовное дерево 
наименьшей стоимости, алгоритм Крускала.
76. Разработать алгоритм и написать программу Остовное дерево 
наименьшей стоимости, алгоритм Крускала с алгоритмом быстрого 
объединения множеств (сжатие путей).
77. Разработать алгоритм и написать программу Остовное дерево 
наименьшей стоимости c предварительным построением пирамиды для весов 
ребер.
78. Разработать алгоритм и написать программу Поиск в глубину, 
выделение компонент связности графа. Рекурсивный вариант.
79. Разработать алгоритм и написать программу Поиск в глубину, 
выделение компонент связности графа. Нерекурсивный вариант.

---

23 
80. Разработать алгоритм и написать программу Разработать алгоритм и 
написать программу Поиск в ширину, выделение компонент сильной связности 
графа. Рекурсивный вариант.
81. Разработать алгоритм и написать программу Поиск в ширину, 
выделение компонент сильной связности графа. Нерекурсивный вариант.
82. Разработать алгоритм и написать программу Нахождение всех 
кратчайших путей в графе.
83. Разработать алгоритм и написать программу Нахождение 
кратчайшего пути из одной вершины в графе. Алгоритм Дейкстры.
84. Разработать алгоритм и написать программу Транзитивное замыкание, 
алгоритм Уоршалла.
85. Разработать алгоритм и написать программу Транзитивное замыкание, 
алгоритм Уоршалла с использованием битовых операций.
86. Разработать алгоритм и написать программу Построение кода 
Хаффмана для символов конкретного текста.
87. Разработать алгоритм и написать программу Кодирование и 
декодирование текста заданным неравномерным кодом.
88. Разработать алгоритм и написать программу построения кода со 
сжатием повторяющихся символов. Кодирование и декодирование для этого 
кода.
Тематика второго расчетного задания определяется преподавателем 
индивидуально и посвящена исследованию новейших структур данных, о 
которых имеется информация в разрозненных изданиях. При этом от студента 
требуется найти материалы по этой структуре, разобраться с ней и оценить ее 
эффективность. Например: 
1. Префиксные деревья 
2. Trie- хеширование 
3. Деревья решений 
4. Полиномиальное хеширование 
5. Интерполяционный поиск 
6. Упорядоченное хеширование 

---

24 
7. АВЛ – деревья 
8. Спиральное хеширование 
9. Описание алгоритма и программы реализации деревьев типа tv-trees 
10. Деревья И/ИЛИ 
11. Квантильное хеширование
12. Нагруженные деревья 
13. Поиск строк в реальном времени 
14. RB-деревья 
15. Строки и эволюционные деревья 
16. Многомерные деревья 
17. Квадродерево и октодеревья 
18. Вероятностные деревьея, алгоритмов их построения
19. Алгоритмы сжатия графических данных 
20. R-деревья 
21. Деревья промежутков 
22. Неравенство Крафта, энтропия, кодирование 
23. Оптимальные бинарные деревья поиска 
24. Транспортная задача 
25. Суффиксные деревья 
26. Дерево классификаций 
27. Расширяющиеся деревья
28. Кодовые деревья, оптимальные префиксные коды 
29. Виртуальное хеширование
30. SR – деревья 
31. Хеширование с использованием деревьев 
32. Генетические алгоритмы 
33. Совершенное хеширование