Лабораторная: Брутфорс vs DP для задачи 'калькулятор'
Лабораторная работа: Оценка эффективности алгоритмов: брутфорс и динамическое программирование
Новинка
Описание
Задача 1: Калькулятор
Условие:Дана последовательность из n натуральных чисел. Необходимо разместить между этими числами знаки арифметических операций «+» и «-» таким образом, чтобы в результате вычисления выражения получилось число, максимально близкое к нулю.
Задания:
- Разработать алгоритм поиска решения «в лоб» (полный перебор всех комбинаций знаков).
- Описать шаги алгоритма и оценить его асимптотическую сложность.
- Реализовать алгоритм на языке Python.
- Провести эксперимент: измерить время выполнения для различных значений n и построить график зависимости времени выполнения от размера входных данных.
Задача 2: Рейтинг
Условие:Имеется n университетов. В каждом университете — 100 студенческих групп. В каждой группе — 30 студентов. У каждого студента есть оценки по 20 дисциплинам. Необходимо отсортировать студентов в пределах групп по убыванию среднего балла.
Задания:
- Разработать алгоритм поиска решения «в лоб» для сортировки студентов.
- Описать шаги алгоритма и оценить его асимптотическую сложность.
- Реализовать алгоритм на языке Python.
- Провести эксперимент: измерить время выполнения для различных значений n и построить график зависимости времени выполнения от количества университетов.
Дополнительное задание (повышенная сложность)
Задание:Для задачи «Калькулятор» предложить и реализовать более эффективный алгоритм (например, на основе динамического программирования), обосновать его преимущества, оценить асимптотическую сложность и сравнить время выполнения с алгоритмом полного перебора на одном графике.Показать/скрыть дополнительное описание
Лабораторная работа по оценке эффективности алгоритмов: реализованы брутфорс и динамическое программирование для задачи типа 'калькулятор', а также сортировка студентов внутри групп. Включены Python-коды, измерения времени и графики — удобно для студентов и преподавателей..
Характеристики лабораторной работы
Предмет
Учебное заведение
Семестр
Просмотров
1
Размер
11,05 Mb
Список файлов
Лабораторная.docx
🎓 Никольский - Помощь студентам 📚 Любые виды работ: тесты, сессии под ключ, практики, курсовые и дипломные с гарантией результата ✅ Все услуги под ключ ✅ Знаем все тонкости именно вашего ВУЗа ✅ Сдадим или вернем деньги
Комментарии
Нет комментариев
Стань первым, кто что-нибудь напишет!
МТИ
nikolskypomosh











