ПЗ (х4) Алгоритмы и структуры данных
Контрольная работа по дисциплине «Алгоритмы и структуры данных» представляет собой комплект из четырёх практических заданий, выполняемых на языке C++. В представленных материалах раскрыты задания №2–№4. Практическое задание №2 посвящено теме «Хеширование»: рассматриваются основные методы вычисления хеш-функций (деление, умножение, динамическое и расширяемое хеширование) и разрешение коллизий. Требуется разработать программу, генерирующую 400 случайных идентификаторов и сохраняющую их в файл, выбрать и реализовать две хеш-функции с диапазоном значений от 1 до 1000, выполнить чтение идентификаторов, вычисление хешей и организацию таблицы идентификаторов. Практическое задание №3 относится к теме «Алгоритмы сортировки. Анализ алгоритмов» и включает изучение и реализацию сортировок включением, выбором, обменом, Шелла, Хоара и пирамидальной, а также алгоритмов поиска в неупорядоченном (линейный, быстрый линейный) и упорядоченном (быстрый, бинарный, блочный) массивах. Предусмотрен сравнительный анализ времени работы методов и анализ числа итераций до нахождения искомого элемента. Практическое задание №4 охватывает тему «Основные алгоритмы на графах»: обход графа поиском в глубину и в ширину, определение вершин на фиксированном расстоянии от заданной, алгоритмы Дейкстры и Флойда, пост
