Код | 509486 |
Дата создания | 2022 |
Мы сможем обработать ваш заказ (!) 23 декабря в 16:00 [мск]
Файлы будут доступны для скачивания только после обработки заказа.
|
Тольяттинский государственный университет (Росдистант). Алгоритмы и структуры данных. Практические задания 1-4. Решение.
Для Росдистант имеются и другие готовые работы. Пишем уникальные работы под заказ. Помогаем с прохождением онлайн-тестов. Пишите, пожалуйста, в личку (Евгений).
Практическое задание 1
Тема 2.2. Решение задач на использование рекурсивных алгоритмов
Цель работы: изучить основные понятия, связанные с рекурсией и рекурсивными алгоритмами, научиться применять рекурсивные алгоритмы при решении задач.
Формулировка задания 1
Выполните следующие задачи с использованием рекурсивных функций.
1. Дано натуральное число n. Выведите все его цифры.
2. Дано натуральное число n. Найти сумму цифр данного числа.
3. Дано натуральное число n. Запишите его в обратном порядке.
4. Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Выведите все нечетные числа из этой последовательности, сохраняя их порядок.
Практическое задание 2
Тема 4.1. Хеширование. Основные методы вычисления хеш-функций: метод деления, метод умножения, динамическое хеширование, расширяемое хеширование. Разрешение коллизий
Цель работы: изучить построение функции хеширования и алгоритмов хеширования данных и научиться разрабатывать алгоритмы открытого и закрытого хеширования при решении задач на языке C++ .
Формулировка задания 2
1. Разработка алгоритма хеш-функции для реализации таблиц идентификаторов:
a. Разработайте программу на выбранном языке программирования, генерирующую 400 случайных идентификаторов (начинаются с символа латиницы и имеют случайную длину), и сохраните их в файл ID.txt.
b. Выберите две любые хеш-функции на основе открытых источников или предложенной для практики литературы. Диапазон значений хеш-функций должен лежать в пределах от 1 до 1000.
c. Реализуйте вычисление хеш-функций на выбранном языке программирования.
d. Реализуйте чтение идентификаторов с файла ID.txt, вычисление для них хеш-функции и сохранение в массив M_ID в ячейку с номером полученного хеш-значения идентификатора (для которого вычислялась хеш-функция).
e. Если в данном элементе массива уже есть идентификатор (коллизия), то добавьте новый идентификатор через разделитель к имеющемуся в элементе массива. Одновременно занесите оба идентификатора в отдельный массив M_Col в порядке их обнаружения.
f. По окончании чтения всего списка входных идентификаторов выведите массивы M_Col и M_ID в отдельные файлы с расширением txt.
• Файл M_ID должен иметь запись всех ячеек массива в порядке возрастания с указанием в первом столбце номера элемента массива. Пустые элементы также подлежат выводу в файл.
• Файл M_Col должен содержать номер элемента массива, хеш-значение и список идентификаторов.
• В конце файла должно быть вычислено отношение количества коллизий к количеству идентификаторов в %.
• Расчет хеш-значений должен быть выполнен для двух хеш-функций.
g. Проведите сравнение полученных результатов на эффективность хеш-функций с точки зрения возникновения коллизий.
2. Разработка и реализация модуля по созданию таблицы идентификаторов:
a. Разработайте программу, реализующую создание таблицы идентификаторов по заданным алгоритмам (один из них на основе хеш-функции, взятой из предыдущей работы). В качестве реализации возьмите за основу автоматное программирование.
b. Добавьте в программу глобальный счетчик для подсчета затраченных элементарных тактов процессора с целью исследования эффективности разработанной программы.
c. Выполните исследование эффективности работы разработанной программы с помощью подсчета затраченных элементарных операций при заполнении таблицы идентификаторов на 25, 50, 75 и 100 %.
d. Представьте сравнительный анализ эффективности работы разработанной программы в виде электронной таблицы с получением выводов по данным алгоритмам реализации.
Практическое задание 3
Тема 5.1. Алгоритмы сортировки. Анализ алгоритмов
Цель работы: изучить основные алгоритмы поиска и сортировки; провести сравнительный анализ различных алгоритмов поиска и сортировки.
Формулировка задания 3
1. Изучите методы сортировки:
– включением;
– выбором;
– обменом;
– Шелла;
– Хоара;
– пирамидальную.
2. Реализуйте методы сортировки. Проанализируйте время, затрачиваемое на каждый метод сортировки при одинаковом количестве измерений (количестве элементов в массиве).
3. Изучите алгоритмы поиска:
• в неупорядоченном массиве:
– линейный;
– быстрый линейный;
• в упорядоченном массиве:
– быстрый;
– бинарный;
– блочный;
4. Реализуйте алгоритмы поиска в одном файле в виде отдельных подпрограмм (функций).
5. Проанализируйте, на какой итерации при разных алгоритмах поиска было найдено искомое число.
Практическое задание 4
Тема 6.2. Основные алгоритмы на графах: выделение компонент сильной связности в ориентированном графе; кратчайшие пути, остовные деревья
Формулировка задания 4
1. Реализуйте программу, в которой выполняется алгоритм обхода графа на основе поиска в глубину.
2. Реализуйте программу, в которой выполняется алгоритм обхода графа на основе поиска в ширину.
3. Используйте обход графа в ширину для определения всех вершин графа, находящихся на фиксированном расстоянии d от данной вершины.
4. Реализуйте программы, в которых выполняются алгоритм Дейкстры и алгоритм Флойда.
5. Реализуйте программу, в которой определяется минимальное остовное дерево графа.