Лабораторная: Брутфорс vs DP для задачи 'калькулятор'

Задача 1: Калькулятор

Условие:
Дана последовательность из n натуральных чисел. Необходимо разместить между этими числами знаки арифметических операций «+» и «-» таким образом, чтобы в результате вычисления выражения получилось число, максимально близкое к нулю.

Задания:

1. Разработать алгоритм поиска решения «в лоб» (полный перебор всех комбинаций знаков).
2. Описать шаги алгоритма и оценить его асимптотическую сложность.
3. Реализовать алгоритм на языке Python.
4. Провести эксперимент: измерить время выполнения для различных значений n и построить график зависимости времени выполнения от размера входных данных.

---

Задача 2: Рейтинг

Условие:
Имеется n университетов. В каждом университете — 100 студенческих групп. В каждой группе — 30 студентов. У каждого студента есть оценки по 20 дисциплинам. Необходимо отсортировать студентов в пределах групп по убыванию среднего балла.

Задания:

1. Разработать алгоритм поиска решения «в лоб» для сортировки студентов.
2. Описать шаги алгоритма и оценить его асимптотическую сложность.
3. Реализовать алгоритм на языке Python.
4. Провести эксперимент: измерить время выполнения для различных значений n и построить график зависимости времени выполнения от количества университетов.

---

Дополнительное задание (повышенная сложность)

Задание:
Для задачи «Калькулятор» предложить и реализовать более эффективный алгоритм (например, на основе динамического программирования), обосновать его преимущества, оценить асимптотическую сложность и сравнить время выполнения с алгоритмом полного перебора на одном графике.Показать/скрыть дополнительное описание