Домашнее задание № 4

Для выполнения задания найди ссылку-приглашение в онлайн чате, получи доступ к репозиторию с файлом-заготовкой и заполни пропуски в нём. Фиксируй изменения (делай коммиты) после решения каждой задачи. Оставь название файла неизменным, иначе робот-проверятель не найдёт твои ответы. Отправить решения на GitHub нужно до истечения установленного срока.

Вступление

Алиса П. Хакер проектирует систему, призванную помочь людям решать инженерные задачи. Помимо прочего она хочет реализовать возможность производить вычисления с неточными величинами (например, измеренные физические величины), обладающими известной погрешностью, так что когда с такими неточными величинами производятся вычисления, результаты также представляют собой числа с известной погрешностью.

Идея Алисы состоит в том, чтобы реализовать интервальную арифметику как набор арифметических операций над «интервалами» (объектами, которые представляют диапазоны возможных значений неточной величины). Результатом сложения, вычитания, умножения или деления двух интервалов также будет интервал, который представляет диапазон возможных значений результата.

Алиса вводит абстрактный объект «интервал», обладающий двумя границами: верхней и нижней. Она также предполагает, что для построения интервала (с помощью конструктора) достаточно иметь значения верхней и нижней границ. Используя конструктор и селекторы, она определяет следующие операции:

def str_interval(x):
    """Возвращает строковое представление интервала x.

    >>> str_interval(interval(-1, 2))
    'от -1 до 2'
    """
    return 'от {0} до {1}'.format(lower_bound(x), upper_bound(x))

def add_interval(x, y):
    """Возвращает интервал всевозможных сумм значений из x и y.

    >>> str_interval(add_interval(interval(-1, 2), interval(4, 8)))
    'от 3 до 10'
    """
    lower = lower_bound(x) + lower_bound(y)
    upper = upper_bound(x) + upper_bound(y)
    return interval(lower, upper)

def mul_interval(x, y):
    """Возвращает интервал всевозможных произведений значений из x и y.

    >>> str_interval(mul_interval(interval(-1, 2), interval(4, 8)))
    'от -8 до 16'
    """
    p1 = lower_bound(x) * lower_bound(y)
    p2 = lower_bound(x) * upper_bound(y)
    p3 = upper_bound(x) * lower_bound(y)
    p4 = upper_bound(x) * upper_bound(y)
    return interval(min(p1, p2, p3, p4), max(p1, p2, p3, p4))

После завершения работы над каждым вопросом требуется фиксировать изменения (делать коммит), сопровождая его вменяемым описанием сделанного, например:

$ git add .
$ git commit -m "Решение вопроса X"

Так же не возбраняется в любое время проталкивать изменения на GitHub:

$ git push

Вопрос 1

Программа Алисы не завершена, поскольку не содержит реализации абстракции «интервал». Определи конструктор и селекторы в терминах двухэлементных списков.

def interval(a, b):
    """Создает интервал от a до b."""
    "*** ТВОЙ КОД ЗДЕСЬ ***"

def lower_bound(x):
    """Возвращает нижнюю границу интервала x."""
    "*** ТВОЙ КОД ЗДЕСЬ ***"

def upper_bound(x):
    """Возвращает верхнюю границу интервала x."""
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 2

Алиса реализовала деление через умножение на величину, обратную к y. Иван Машкодов, системный программист-эксперт, подсмотрев через плечо Алисы, заметил: «Неясно, что должно означать деление на интервал, пересекающий ноль». Добавь проверку assert в код Алисы, чтобы удостовериться, что пересекающий ноль интервал не используется в качестве делителя.

def div_interval(x, y):
    """Возвращает интервал, содержащий частные любых значений из x на
    любые значения из y.

    Деление реализовано как умножение x на величину, обратную к y.

    >>> str_interval(div_interval(interval(-1, 2), interval(4, 8)))
    'от -0.25 до 0.5'
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"
    reciprocal_y = interval(1/upper_bound(y), 1/lower_bound(y))
    return mul_interval(x, reciprocal_y)

Вопрос 3

Рассуждая в духе Алисы, реализуй функцию вычитания интервалов:

def sub_interval(x, y):
    """Возвращает интервал, содержащий разности любых значений из x с
    любыми значениями из y.

    >>> str_interval(sub_interval(interval(-1, 2), interval(4, 8)))
    'от -9 до -2'
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 4

После продолжительной работы Алиса П. Хакер закончила и сдала систему. Несколько лет спустя, после того, как она совсем забыла про интервальную арифметику, с ней связался Прэд эл Неточнес — разгневанный пользователь системы, который, похоже, пытался сообщить, что формулу для параллельных резисторов можно математически записать двумя разными, но эквивалентными способами:

\[par1(r_1, r_2) = \frac{r_1\cdot r_2}{r_1 + r_2}\]

или

\[par2(r_1, r_2) = \frac{1}{ \frac{1}{r_1} + \frac{1}{r_2}}\]

Прэд написал две следующие функции для вычисления сопротивления двух параллельных резисторов в соответствии с формулами:

def par1(r1, r2):
    return div_interval(mul_interval(r1, r2), add_interval(r1, r2))

def par2(r1, r2):
    one = interval(1, 1)
    rep_r1 = div_interval(one, r1)
    rep_r2 = div_interval(one, r2)
    return div_interval(one, add_interval(rep_r1, rep_r2))

Прэд выразил недовольство, что система Алисы выдает разные результаты для двух эквивалентных способов вычисления. Это серьёзная заявка!

Покажи, что Прэд прав. Изучи поведение системы на разных арифметических выражениях. Задай интервалы a и b и покажи, что par1 и par2 могут выдавать разные результаты. Наилучшего понимания ты достигнешь, если будешь рассматривать интервалы, размах которых будет задаваться как доля от среднего значения.

# Вот эти два интервала дают разные результаты при вычислении сопротивления параллельных резисторов:
"*** ТВОЙ КОД ЗДЕСЬ ***"
Это задание проверяться не будет.

Вопрос 5

Госпожа Вычос Ли Телль, ещё один пользователь системы, также заметила, что алгебраически эквивалентные, но различные выражения могут давать разные результаты. Госпожа Ли утверждает, что проблема во множественных использованиях одного и того же интервала в формуле.

Проблема множественных ссылок: формула для работы с интервалами будет давать более жёсткие границы, если её можно записать в такой форме, что ни одна интервальная величина в формуле не будет повторяться.

Таким образом, госпожа Ли утверждает, что par2 «лучше», чем par1. Права ли она? Почему?

Напиши функцию, которая возвращает строку с развернутым описанием твоего понимания этой непростой ситуации.

На ответ, быть может, посмотрит человек.
def multiple_references_explanation():
    return """Проблема множественных ссылок..."""

Вопрос 6

Напиши функцию quadratic, которая возвращает интервал, описывающий область значения \(f(t)\), при условии, что \(f\) — квадратичная функция, определяемая константами \(a\), \(b\), \(c\), а x — интервал описывающий возможные значения аргумента.

\[f(t) = a\cdot t^2 + b\cdot t + c\]

Удостоверься, что твоя реализация возвращает наименьший возможный интервал и не подвержена проблеме множественных ссылок.

Поскольку \(f'(t) = 2at + b\) , то экстремум квадратичной функции находится в \(-\frac{b}{2a}\).
def quadratic(x, a, b, c):
    """Возвращает интервал, описывающий область значения квадратичной функции с
    коэффициентами a, b и c для интервала области определения x.

    >>> str_interval(quadratic(interval(0, 2), -2, 3, -1))
    'от -3 до 0.125'
    >>> str_interval(quadratic(interval(1, 3), 2, -3, 1))
    'от 0 до 10'
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 7* (cложная задачка)

Напиши полиномиальную функцию, которая принимает интервал x, список коэффициентов c и возвращает интервал, содержащий все значения \(f(t)\) для \(t\) в интервале x, где:

\[f(t) = c_{k-1}\cdot t^{k-1} + c_{k-2}\cdot t^{k-2} + ... + c_0\cdot 1\]

Как и в случае с квадратичной функцией, нужно отыскать наименьший возможный интервал, который не подвержен проблеме множественных ссылок.

Можешь аппроксимировать результат с помощью метода Ньютона.
def polynomial(x, c):
    """Возвращает интервал, описывающий область значения полиномиальной функции с
    коэффициентами c для интервала области определения x.

    >>> str_interval(polynomial(interval(0, 2), [-1, 3, -2]))
    'от -3 до 0.125'
    >>> str_interval(polynomial(interval(1, 3), [1, -3, 2]))
    'от 0 до 10'
    >>> str_interval(polynomial(interval(0.5, 2.25), [10, 24, -6, -8, 3]))
    'от 18.0 до 23.0'
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"