📘 О чем эта работа
Отчет посвящен оценке эффективности алгоритмов на двух практических задачах: 1) «Калькулятор» — размещение знаков '+' и '-' между n натуральными числами так, чтобы результат был максимально близок к нулю; 2) «Рейтинг» — сортировка студентов внутри групп по убыванию среднего балла при входных параметрах: n университетов, 100 групп в каждом, 30 студентов в группе, по 20 дисциплин у студента.
📚 Что внутри
Работа содержит конкретные реализации и измерения производительности на Python:
- Исходный код брутфорс-решения для задачи «Калькулятор» с перебором 2^(n-1) комбинаций и демонстрацией роста времени при ns = range(10, 20, 2); приведены результаты для n = 20 и n = 24 (Рис.1, Рис.2).
- Реализация алгоритма сортировки внутри групп: генерация n университетов, по 100 групп и по 30 студентов с оценками по 20 дисциплинам; вычисление среднего и сортировка по убыванию; измерения времени при n от 1 до 10 (Рис.3, Рис.4).
- Улучшенный подход для «Калькулятора»: редукция задачи к задаче разбиения множества и реализация динамического программирования (DP) с целевой суммой total//2, время O(n * S); сравнение времен брутфорса и DP (Рис.6, Рис.7), объединённый график для обеих задач (Рис.5).
- Блок-схемы алгоритмов: традиционный брутфорс и улучшенный DP для калькулятора (Рис.8) и диаграмма алгоритма вычисления рейтинга (Рис.9).
📊 Для кого подходит
Полезно студентам и преподавателям курсов по программированию и алгоритмам, направлениям «Информационные технологии» и «Прикладная информатика». Материал подходит для лабораторных, демонстраций сравнений по времени выполнения и подготовки теоретических выводов о сложности.
✨ Особенности
Конкретные преимущества этой работы: готовые Python-скрипты для генерации входных данных и замеров времени, ясное сравнение экспоненциального брутфорса и полиномиального DP, численные эксперименты (диапазоны n указаны в коде), формулы асимптотик (O(2^n) для перебора и O(n*S) для DP) и графики, позволяющие визуально оценить пределы применимости каждого метода.
❓ Частые вопросы
Подойдет ли для моего ВУЗа?
Структура отчёта соответствует требованиям лабораторных работ: постановка задачи, описание алгоритмов, листинги реализации, таблицы/графики и выводы.
Можно адаптировать?
Да. Код генерации входных данных легко настраивается: изменить диапазоны ns, число групп, число студентов и количество дисциплин для повторных экспериментов.
Что можно извлечь из графиков?
Графики показывают, что при n≈14 брутфорс для «Калькулятора» начинает работать медленнее, чем задача ранжирования студентов при данных константах; DP резко снижает время при большем суммарном диапазоне значений.
Примечание: в тексте приведены конкретные листинги функций find_closest_to_zero_brute, find_closest_to_zero_dp и sort_students_brute, а также используемые диапазоны ns и параметры генерации случайных оценок (random.randint(1,100) и random.randint(50,100) для оценок студентов).
